Index and query serving for low latency search of large graphs

• US 9,576,007 B1
• Filed: 12/10/2013
• Issued: 02/21/2017
• Est. Priority Date: 12/21/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Sivathanu, Muthian, Garg, Puneet, S R, Rajesh
• Primary Examiner(s): Kuddus, Daniel
• Application Number:
  US14/101,878
• Time in Patent Office: 1,169 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

A search index for searching a graph-based data store can include triple entries, each triple entry having a posting list value, at least one intersection identifier associated with the posting list value, and at least one result identifier associated with the intersection identifier. The index may also include search entries having a posting list value that corresponds to a text search aid. The search index may also include pre-computed path entries, such as chain path entries and converge path entries. The index may also include bucket posting lists representing ranges of object values for a particular predicate and proximity posting lists that include one or more entities and the areas of a location hierarchy with locations within the proximity of the entity. Queries for the data graph may have at least two stages, each stage being associated with a posting list from a graph index.

Claims

1. A system comprising:

a graph-based datastore representing entities connected by predicates; and

a query serving system including;

at least one processor, and

memory storing;

an index of the graph-based datastore, the index including predicate posting lists, each predicate posting list having a plurality of intersection identifiers and, for each intersection identifier, at least one result identifier, the at least one result identifier identifying an entity connected by the predicate to an entity identified by the respective intersection identifier; and

instructions that, when executed by the at least one processor cause the query serving system to;

receive a query that executes in at least two stages, each stage associated with a different predicate posting list from the index,

execute a forward query path on the stages to generate first query results, wherein executing the forward query path includes;

 

applying an expand operator on a predicate posting list for a first stage to generate intersection identifier-result identifier pairs,

 

generating a list of result identifiers as first stage query results, and

 

providing the first stage query results to a downstream stage as incident identifiers, and

execute a reverse query path on the stages to generate second query results, where the first query results include different entities than the second query results.

2. The system of claim 1, wherein executing the forward query path also includes generating an entity map from the intersection identifier-result identifier pairs, the entity map being indexed by result identifier.

3. The system of claim 2, wherein executing the forward query path includes:

intersecting the incident identifiers with intersection identifiers from a predicate posting list for the downstream stage to generate the first query results.

4. The system of claim 3, wherein executing the reverse query path includes:

providing the first query results to the first stage; and

using the entity map and the first query results to generate the second query results.

5. The system of claim 4, wherein using the entity map includes:

intersecting the first query results with the result identifiers of the entity map to find matching result identifiers; and

selecting the intersection identifiers associated with matching result identifiers as the second query results.

6. The system of claim 1, wherein executing the reverse query path includes further processing of the first query results to generate the second query results.

7. The system of claim 1, wherein entities of the first query results differ in type from the entities of the second query results.

8. The system of claim 7, wherein executing the reverse query path translates the entities of the first query results into the entities of the second query results.

9. A system comprising:

a graph-based datastore; and

an indexing system including;

at least one processor,

a memory storing an index for searching the graph-based datastore, the index including;

posting lists for one or more proximity ranges compatible with a space, a posting list including;

one or more entities of a type compatible with the space, each entity having a location within the space, the location being a basic unit in a location hierarchy for the space, and

for each entity, at least one node in the location hierarchy that falls within the proximity range of the posting list with reference to the location of the entity,

at least one distance-predicate posting list that includes nodes in the location hierarchy and, for each node, one or more entities of a type compatible with the space and located within an area represented by the node, and

a memory storing instructions that, when executed by the at least one processor cause the indexing system to use the index to respond to a query that includes a query proximity range for the space.

10. The system of claim 9, wherein the at least one node has a respective associated context that represents the location for the entity.

11. The system of claim 9, wherein responding to the query includes:

identifying at least one base entity associated with entity parameters from the query;

selecting a posting list with a proximity range larger than the query proximity range;

using the selected posting list to locate the one or more nodes for the at least one base entity;

using the distance-predicate posting list to locate one or more target entities for the at least one base entity; and

generating a query result that includes information for the at least one base entity and the one or more target entities.

12. The system of claim 11, wherein the one or more entities of the distance-predicate posting list has an associated context that represents the location for the associated entity in base units.

13. The system of claim 12, wherein locating the one or more target entities includes:

calculating a distance between the base entity and the target entity using the context of the target entity; and

including the target entity in the query result when the distance is within the proximity range for the query.

14. The system of claim 11, wherein the distance-predicate posting list includes forward distance-predicate entries that include:

a plurality of entities of a type compatible with the space; and

for each entity, the nodes in the location hierarchy that represent an area encompassing the location of the entity.

15. The system of claim 14, wherein responding to the query includes:

determining that a posting list with a proximity range larger than the query proximity range does not exist; and

using the forward distance-predicate entries to locate the one or more nodes for the at least one base entity.

16. The system of claim 9, wherein responding to the query includes:

calculating a location that corresponds to a basic unit of the hierarchy from a value specified in the query;

determining the nodes in the hierarchy with an area covering the query proximity range;

using the distance-predicate posting list to locate one or more target entities for the location; and

generating a query result that includes information for the one or more target entities.

17. A search index for performing low-latency searches of a data graph, the data graph having entities linked by predicates, the search index comprising:

predicate posting lists, wherein a predicate posting list for a particular predicate includes subject entities and one or more object entities related to respective subject entities by the particular predicate;

bucket posting lists that represent ranges of object values for a predicate, a bucket posting list for the particular predicate includes at least one subject entity related by the particular predicate to at least one object entity having an object value that falls within a start value and an end value for the bucket posting list; and

object-rank posting lists, wherein an object-rank posting list for the particular predicate includes subject entities and one or more object entities related to respective subject entities by the particular predicate, wherein each object entity is associated with a rank; and

wherein the start value and the end value for the bucket posting lists are associated with respective ranks,

wherein the search index is stored a non-transitory computer-readable medium on one or more computing systems in communication with an indexing server and a query server and is used to generate search results in response to queries.

18. The search index of claim 17, wherein the query server comprises:

at least one processor; and

a memory storing instructions that, when executed by the at least one processor, cause the query server to;

receive a query that includes a range for the particular predicate;

convert the range to a query start rank and a query end rank;

determine, using the at least one processor, at least one bucket posting list for the particular predicate from the search index that has a start value less than the query end rank and an end value greater than the query start rank, the at least one bucket posting list having at least a first subject entity;

determine first object entities related to the first subject entity using the object-rank posting list and the bucket posting list for the particular predicate;

determine whether the first object entities have an associated rank within the query start rank and query end rank; and

generate a query result that includes information from the first subject entity and the first object entities that have an associated rank within the query start rank and the query end rank.

19. The search index of claim 17, wherein the query server comprises:

at least one processor; and

a memory storing instructions that, when executed by the at least one processor, cause the query server to;

receive a query that includes a request to sort the search results by object entity for the particular predicate;

determine, using the at least one processor, query results, the query results including first subject entities;

order the query results based on the ranks of the object entities in a bucket posting list for the particular predicate; and

provide information from the ordered query results as the search results.

20. The search index of claim 17, wherein the query server comprises:

at least one processor; and

a memory storing instructions that, when executed by the at least one processor, cause the query server to;

receive a query that includes a range for the particular predicate, the range represented by a query start value and a query end value;

determine, using the at least one processor, at least one bucket posting list for the particular predicate from the search index that has a start value less than the query end value and an end value greater than the query start value, the at least one bucket posting list having at least a first subject entity;

determine first object entities related to the first subject entity using the predicate posting list and the bucket posting list for the particular predicate;

determine whether the first object entities have an object value within the query start value and query end value; and

generate a query result that includes information from the first subject entity and the first object entities that have an object value within the query start value and the query end value.

21. A system comprising:

a graph-structured knowledge base that supplies triples for indexing, where a triple represents a subject linked with an object by at least one relationship; and

an indexing system including;

at least one processor, and

memory storing;

an index for searching the graph-structured knowledge base, each entry of at least some entries in the index having;

a posting list value,

a plurality of intersection identifiers associated with the posting list value, and

for each of the intersection identifiers, one or more result identifiers, and

instructions that, when executed by the at least one processor cause the indexing system to;

generate and store, for at least one of the triples from the knowledge base, a subject index entry where the posting list value represents a subject of the triple, an object index entry where the posting list value represents an object of the triple, and a relationship index entry where the posting list value represents a relationship linking the subject and the object of the triple,

pre-compute entries for the index representing an intersection between a first posting list value and a second posting list value, and

store the pre-computed entries in the index.

22. The system of claim 21, wherein for at least one particular triple the instructions further cause the indexing system to perform operations comprising:

generating a search triple corresponding to the particular triple, the search triple including the subject of the particular triple, a text search aid as the object of the search triple, and a special relationship that indicates the object is a search equivalent of the subject; and

generating an object index entry based on the search triple.

23. The system of claim 21, wherein at least one of the result identifiers in the index has a corresponding context value.

24. The system of claim 21, wherein pre-computing entries includes:

determining that an amount of triples represented by entries for the first posting list value and an amount of triples represented by entries for the second posting list value are large;

determining a result of an intersection between the entries of the first posting list value and the entries of the second posting list value; and

performing the pre-computing when it is determined that the result of the intersection has significantly fewer members than the amount of triples represented by the entries for the first posting list and significantly fewer members than the amount of triples represented by the entries for the second posting list value.

25. The system of claim 24, wherein pre-computing entries includes precomputing a converge path.

26. The system of claim 24, wherein pre-computing entries includes precomputing a chain path.