Patent · US Active

In-memory graph analytics system that allows memory and performance trade-off between graph mutation and graph traversal

US11068538B2 · kind B2 · utility

0Cited by

6References

20Claims

0Family size

Assignee

Oracle International Corporation · US

Inventors

Michael Haubenschild · Erding, DE
Sungpack Hong · Palo Alto, US
Hassan Chafi · San Mateo, US
Korbinian Schmid · Bad Abbach, DE
Martin Sevenich · Palo Alto, US
Alexander Weld · Mountain View, US

Key dates

Filing date	Feb 1, 2019
Grant date	Jul 20, 2021
Priority date	—
Expiry date	Feb 29, 2040

Classification

Technology area (CPC G)Physics
CPC primaryG06F16/28
WIPO fieldComputer technology
WIPO sectorElectrical engineering

Abstract

Techniques herein are for navigation data structures for graph traversal. In an embodiment, navigation data structures that a computer stores include: a source vertex array of vertices; a neighbor array of dense identifiers of target vertices terminating edges; a bidirectional map associating, for each vertex, a sparse identifier of the vertex with a dense identifier of the vertex; and a vertex array containing, when a dense identifier of a source vertex is used as an offset, a pair of offsets defining an offset range, for use with the neighbor array. The source vertex array, using the dense identifier of a particular vertex as an offset, contains an offset, into a neighbor array, of a target vertex terminating an edge originating at the particular vertex. The neighbor array contiguously stores dense identifiers of target vertices terminating edges originating from a same source vertex.

Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.