Bi-gram cardinality estimation in a graph database
US12032582B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jul 13, 2023 |
| Grant date | Jul 9, 2024 |
| Priority date | — |
| Expiry date | Jul 13, 2043 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/284
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method and apparatus for estimating the cardinality of graph pattern queries using graph statistics and metadata is presented. In various embodiments, node and edge labels are used to compute estimates for graph patterns (bi-grams) and the estimates for these patterns as composed to provide cardinality estimates of longer paths. The computation of bi-grams is low cost and requires only minimal changes to the existing query planner in the existing database machinery to be useful. The resulting estimates are used during query execution to minimize the amount of work needed to complete a query and return a faithful and accurate answer to the user. The apparatus includes modules containing computer-executable instructions to perform the above method.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.