IDENTIFYING A GROUP OF RELATED INSTANCES

• US 20110106819A1
• Filed: 10/29/2009
• Published: 05/05/2011
• Est. Priority Date: 10/29/2009
• Status: Abandoned Application

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Loreto, Daniel, Komoroske, John Alexander, Brown, Randolph G., Hogue, Andrew William, Quine, Daniel N., Nevill-Manning, Craig, Coppel, Yohann R.
• Application Number:
  US12/608,395
• Publication Number:
  US 20110106819A1
• Time in Patent Office: Days
• US Class Current: 707/749
• CPC Class Codes: G06F 16/34 Browsing; Visualisation therefor
• CPC Class Codes: G06F 16/367 Ontology
• CPC Class Codes: G06F 16/9038 Presentation of query results
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for identifying a group of related instance identifiers. In one aspect, a computer storage medium is encoded with a computer program. The program comprises instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations. The operations include receiving a search query at a data processing apparatus, the search query specifying attributes shared by a group of related instances, searching an electronic document collection to identify instance identifiers that are responsive to the search query, representing features of the instance identifiers in a vertex-edge graph, and scoring relevance of the instance identifiers to the search query according to the features represented in the vertex-edge graph.

Claims

1. A method performed by one or more data processing apparatus, the method comprising:

the data processing apparatus receiving a search query at a data processing apparatus, the search query specifying attributes shared by a group of related instances;

the data processing apparatus identifying groups of instance identifiers in an unstructured collection of electronic documents with the data processing apparatus;

the data processing apparatus determining relevance of the groups of instance identifiers to the search query with the data processing apparatus;

the data processing apparatus scoring at least some of the instance identifiers in the groups of instance identifiers individually with the data processing apparatus; and

the data processing apparatus ranking the at least some instance identifiers according to the scores with the data processing apparatus.

2. The method of claim 1, wherein determining the relevance of the groups of instance identifiers to the search query comprises:

computing relevance of the groups of instance identifiers to source documents that include the groups of instance identifiers;

computing likelihoods that the identified groups of instance identifiers are indeed groups of instance identifiers; and

computing relevance of source documents which include the groups of instance identifiers to the search query.

3. The method of claim 1, wherein identifying the groups of instance identifiers comprises:

forming a first new query biased to identify groups;

forming a second new query constrained to search compendia sources; and

searching the unstructured collection of electronic documents with the received query, the first new query, and the second new query.

4. The method of claim 1, further comprising the data processing apparatus rescoring the at least some instance identifiers before ranking.

5. The method of claim 1, wherein scoring at least some of the instance identifiers in the groups of instance identifiers comprises:

representing features of the instance identifiers in a vertex-edge graph; and

scoring the instance identifiers according to the features represented in the vertex-edge graph.

6. The method of claim 5, wherein:

vertices in the vertex-edge graph represent groups of instance identifiers; and

respective edges in the vertex-edge graph are weighted according to overlap between the vertices connected by the edge.

7. The method of claim 5, wherein:

vertices in the vertex-edge graph represent individual instance identifiers; and

respective edges in the vertex-edge graph represent features shared by the instance identifiers.

8. The method of claim 6, wherein a first edge in the vertex-edge graph represents an extractor that identified a pair of vertices joined by the first edge.

9. The method of claim 6, wherein a first edge in the vertex-edge graph represents other instance identifiers in potential groups where vertices joined by the first edge are found.

10. The method of claim 6, wherein a first edge in the vertex-edge graph represents a class of the query that identified source document where vertices joined by the first edge are found.

11. The method of claim 5, wherein scoring the instance identifiers comprises identifying cliques in the vertex-edge graph.

12. The method of claim 1, wherein scoring the instances identifiers comprises scoring the instance identifiers using a predictive analytic tree-building algorithm.

13. The method of claim 1, wherein scoring the instance identifiers using the predictive analytic tree-building algorithm comprises:

training the predictive analytic tree-building algorithm using

a group of instance identifiers of confirmed accuracy that are relevant to a search query,

a set of potential groups of instance identifiers that have been identified from an unstructured collection of electronic documents, and

features of the instance identifiers in the potential groups; and

generating a classification and regression tree.

14. One or more computer storage media encoded with a computer program, the program comprising instructions that when executed by one or more data processing apparatus cause the data processing apparatus to perform operations, the operations comprising:

receiving a search query at a data processing apparatus, the search query specifying attributes shared by a group of related instances;

searching an electronic document collection to identify identifiers of instance that are responsive to the search query;

representing features of the instance identifiers in a vertex-edge graph; and

scoring relevance of the instance identifiers to the search query according to the features represented in the vertex-edge graph.

15. The computer storage medium of claim 14, wherein:

the operations further comprise;

identifying groups of instance identifiers in the electronic documents of the collection; and

determining relevance of the groups of instance identifiers to the search query; and

a first feature represented in the vertex-edge graph comprises the relevance of the groups that include respective instance identifiers to the search query.

16. The computer storage medium of claim 14, the operations further comprising:

identifying electronic documents available on the Internet that are relevant to the search query; and

extracting groups of instance identifiers from the electronic documents that are relevant to the search query.

17. The computer storage medium of claim 16, the operations further comprising:

computing relevance of the electronic documents from which the groups of instance identifiers are extracted to the search query;

computing relevance of the groups of instance identifiers to the electronic documents from which the groups of instance identifiers are extracted; and

computing likelihoods that the groups of instance identifiers are groups of instance identifiers.

18. The computer storage medium of claim 15, wherein identifying the groups of instance identifiers comprises:

forming a new query biased to identify groups; and

searching the electronic document collection with the new query.

19. The computer storage medium of claim 14, wherein a first edge in the vertex-edge graph represents a class of the query that identified a pair of vertices joined by the first edge.

20. The computer storage medium of claim 14, wherein a first edge in the vertex-edge graph represents other instance identifiers in potential groups where vertices joined by the first edge are found.

21. The computer storage medium of claim 14, wherein scoring relevance of the instance identifiers to the search query comprises identifying cliques in the vertex-edge graph.

22. A system comprising:

a client device; and

one or more computers programmed to interact with the client device and the data storage device, the computers programmed to perform operations comprising;

receiving a search query from the client device, the search query explicitly or implicitly specifying attributes of instances;

searching an electronic document collection to identify identifiers of instances that may have the attributes specified by the search query;

representing features of the search of the electronic document collection in a vertex-edge graph;

scoring the instance identifiers that may have the attributes specified by the search query according to the features represented in the vertex-edge graph; and

outputting, the client device, instructions for visually presenting at least some of the instance identifiers.

23. The system of claim 22, wherein:

outputting the instructions comprises outputting instructions for visually presenting a structured presentation at the client device; and

the client device is configured to receive the instructions and cause the structured presentation to be visually presented.

24. The system of claim 22, further comprising a data storage device storing a data describing multiple groups of instances.

25. The system of claim 22, further comprising a data storage device storing machine-readable instructions tailored to identify and extract groups of instance identifiers from electronic documents in an unstructured collection.

26. The system of claim 22, wherein:

representing features comprises representing the relevance of the groups in which the instance identifiers appear in the vertex-edge graph; and

scoring the instance identifiers comprises scoring the instance identifiers individually according to the relevance of the groups in which the instance identifiers appear to the search query.

27. The system of claim 22, wherein scoring the instance identifiers comprises identifying cliques in the vertex-edge graph.

28. The system of claim 22, wherein scoring the instance identifiers comprises scoring the instance identifiers according to an extractor represented in the vertex-edge graph.

29. The system of claim 22, wherein scoring the instance identifiers comprises scoring the instance identifiers according to a class of a query represented in the vertex-edge graph.