In-memory graph pattern matching
US9928310B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Aug 15, 2014 |
| Grant date | Mar 27, 2018 |
| Priority date | — |
| Expiry date | Dec 15, 2036 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/90335
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Techniques for identifying, in a target graph, subgraphs that match a query graph are provided. Processing a query graph comprises multiple stages, one for each query node in the query graph. In the first stage, a query node is selected, different portions of the target graph are assigned to different threads, each thread identifies nodes that match the selected query node and stores the identities of those nodes in storage that is local to the thread. The results of each thread are then stored in a “global” data structure. In the second stage, a second query node is selected and different portions of the global data structure are assigned to different threads. Each thread identifies nodes that match the second query node and that are connected to a previously-matched node. The second stage repeats until all nodes in the query graph are processed.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.