Efficient index for low latency search of large graphs

• US 10,102,268 B1
• Filed: 12/27/2016
• Issued: 10/16/2018
• Est. Priority Date: 12/21/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Sivathanu, Muthian, Garg, Puneet, S R, Rajesh
• Primary Examiner(s): Kuddus, Daniel
• Application Number:
  US15/390,906
• Time in Patent Office: 658 Days
• 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 system for efficiently responding to proximity queries may include a memory storing an index for searching a graph-based data store, the index including posting lists for one or more proximity ranges compatible with a space. A posting list can include 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. The system may also include a memory storing instructions that cause the system to use the index to respond to a query that includes a query proximity range for the space. The space can be a geographic space or a time space.

Claims

1. A system comprising:

a graph-based data store; and

an indexing system including;

at least one processor,

a memory storing an index for searching the graph-based data store, 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, the at least one node being associated with a context, and

a memory storing instructions that, when executed by the at least one processor cause the indexing system to use the index and the context to respond to a query that includes a query proximity range for the space, wherein using the index and the context reduces a number of distance calculations performed on the one or more entities resulting in reduced latency in responding to the query.

2. The system of claim 1, wherein the context is stored in the index to represent the location for the entity.

3. The system of claim 1, wherein the index further includes a 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.

4. The system of claim 3, 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.

5. The system of claim 4, 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.

6. The system of claim 5, 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.

7. The system of claim 4, 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.

8. The system of claim 7, 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.

9. The system of claim 3, 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.

10. The system of claim 1, wherein the space is a geographic space.

11. The system of claim 1, wherein the space is a time space.

12. A system comprising:

a graph-based data store that includes geographic entities having an associated location in a geographic space;

a location hierarchy for the geographic space, where a root node of the hierarchy represents the geographic space, internal nodes are areas representing a portion of the geographic space, and leaf nodes are areas representing a basic unit of the geographic space, where nodes at each level of the hierarchy represent a division of the area represented by the parent node; and

an indexing system including;

at least one processor,

a memory storing an index for searching the graph-based data store, the index including posting lists for one or more proximity ranges, a posting list including;

one or more geographic entities, and

for each entity, at least one area of the geographic space that represents locations falling within the proximity range of the posting list with reference to the entity, the area being a node in the location hierarchy, the node being associated with a context, and

a memory storing instructions that, when executed by the at least one processor cause the indexing system to use the index and the context to respond to a query that includes a query proximity range for the space, wherein using the index and the context reduces a number of distance calculations performed on the one or more entities resulting in reduced latency in responding to the query.

13. The system of claim 12, wherein the index further includes a distance-predicate posting list that includes:

areas of the geographic space, each area representing one or more locations in the geographic space; and

for each area, one or more geographic entities located within the area.

14. The system of claim 13, 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 areas associated with 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, the target entities being associated with the located areas; and

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

15. The system of claim 12, wherein the proximity range of a posting list is a radius of a predetermined number of miles.

16. A method comprising:

receiving, using at least one processor, a query for a data store that stores a graph represented by entities connected by edges, at least some of the entities having a location within a space, the query including a query proximity range and entity parameters;

identifying, using the at least one processor, at least one base entity from the graph, the base entity at least partially matching the entity parameters and having a location within the space;

selecting a proximity posting list from an index for the graph associated with a predetermined proximity range larger than the query proximity range, the proximity posting list including;

an entry for the base entity, and

at least one area of the space associated with the base entity, the area representing locations in the space falling within the predetermined proximity range from the base entity, and

using the selected proximity posting list to locate the at least one area associated with the base entity;

locating one or more target entities from the graph using a distance-predicate posting list in the index that maps an area of the space to entities in the graph with locations within the area of the space, the distance-predicate posting list providing a respective context for the one or more target entities, the context being used to reduce a number of distance calculations performed to identify whether the one or more target entities are within the query proximity range; and

generating, using the at least one processor, a query result that includes information for the base entity and the one or more target entities, wherein the reduced number of distance calculations results in a reduced latency in generating the query result.

17. The method of claim 16, wherein hundreds of thousands of entities match the entity parameters and locating the target entities takes tens of milliseconds.

18. The method of claim 16, wherein the context that represents the location in base units for each respective target entity.

19. The method of claim 18, wherein locating the one or more target entities includes:

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

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

20. The method of claim 16, wherein the space is a geographic space and the predetermined proximity range is a radius of a predetermined number of miles.