Efficient method for subgraph pattern matching
US10896223B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Dec 18, 2018 |
| Grant date | Jan 19, 2021 |
| Priority date | — |
| Expiry date | May 2, 2039 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/28
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Techniques herein optimize subgraph pattern matching. A computer receives a graph vertex array and a graph edge array. Each vertex and each edge has labels. The computer stores an array of index entries and an array of edge label sets. Each index entry corresponds to a respective vertex originating an edge and associates an offset of the edge with an offset of the respective vertex. Each edge label set contains labels of a respective edge. The computer selects a candidate subset of edges originating at a current vertex. The edge labels of each candidate edge of the candidate subset include a same particular query edge labels. The computer selects the candidate subset based on the index array and afterwards selects a result subset of vertices from among the terminating vertices of the candidate edges. The labels of each vertex of the result subset include a same particular query vertex labels.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.