Fast graph query engine optimized for typical real-world graph instances whose small portion of vertices have extremely large degree
US10423663B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jan 18, 2017 |
| Grant date | Sep 24, 2019 |
| Priority date | — |
| Expiry date | Aug 20, 2037 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/9024
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Techniques herein accelerate graph querying by caching neighbor vertices (NVs) of super-node vertices. In an embodiment, a computer receives a graph query (GQ) to extract result paths from a graph in a database. The GQ has a sequence of query vertices (QVs) and a sequence of query edges (QEs). The computer successively traverses each QE and QV to detect paths of the graph that match the GQ. Traversing each QE and QV entails retrieving NVs of a current graph vertex (CGV) of a current traversal path. If the CGV is a key in a cache whose keys are graph vertices having an excessive degree, then the computer retrieves NVs from the cache. Otherwise, the computer retrieves NVs from the database. If the degree is excessive, and the CGV is not a key in the cache, then the computer stores, into the cache, the CGV as a key for the NVs.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.