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

US10235474B2 · kind B2 · utility

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 27, 2017
• Grant date: Mar 19, 2019
• Expiry date: Sep 4, 2037

Classification

• Technology area (CPC G): Physics
• CPC primary: G06F16/28
• WIPO field: Computer technology
• WIPO sector: Electrical 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.