Efficient index for low latency search of large graphs
US10102268B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Dec 27, 2016 |
| Grant date | Oct 16, 2018 |
| Priority date | — |
| Expiry date | Dec 27, 2036 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/29
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.