公开(公告)号：US10831829B2

公开(公告)日：2020-11-10

申请号：US16185236

申请日：2018-11-09

Applicant: Oracle International Corporation

Inventor： Martin Sevenich ,  Sungpack Hong ,  Alexander Weld ,  Hassan Chafi

IPC: G06F16/00 ,  G06F16/901 ,  G06F16/9532 ,  G06F16/22

Abstract: Embodiments perform real-time vertex connectivity checks in graph data representations via a multi-phase search process. This process includes an efficient first search phase using landmark connectivity data that is generated during a preprocessing phase. Landmark connectivity data maps the connectivity of a set of identified landmarks in a graph to other vertices in the graph. Upon determining that the subject vertices are not closely related via landmarks, embodiments implement a second search phase that performs a brute-force search for connectivity, between the subject vertices, among the graph's non-landmark vertices. This brute-force search prevents exploration of cyclical paths by recording the vertices on a currently-explored path in a stack data structure. The second search phase is automatically aborted upon detecting that the non-landmark vertices in the graph are over a threshold density. In this case, embodiments perform a third search phase involving either a modified breadth-first search or modified bidirectional search.

公开(公告)号：US20180246986A1

公开(公告)日：2018-08-30

申请号：US15443327

申请日：2017-02-27

Applicant: Oracle International Corporation

Inventor： Michael Haubenschild ,  Sungpack Hong ,  Hassan Chafi ,  Korbinian Schmid ,  Martin Sevenich ,  Alexander Weld

IPC: G06F17/30

CPC classification number: G06F17/30958 ,  G06F17/30587

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.

公开(公告)号：US20220284056A1

公开(公告)日：2022-09-08

申请号：US17194165

申请日：2021-03-05

Applicant: Oracle International Corporation

Inventor： Damien Hilloulin ,  Vasileios Trigonakis ,  Alexander Weld ,  Valentin Venzin ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F16/901 ,  G06F16/22

Abstract: Techniques are provided for updating in-memory property graphs in a fast manner, while minimizing memory consumption. A graph is represented as delta compressed sparse rows (CSR), in which its data structure stores forward edge offsets that map reverse edges to forward edges, enabling fast traversals of graph edges in forward and reverse directions. To support fast graph updates, delta logs are used to store changes to the graph. In an embodiment, a base version of the graph data structure is initially loaded or created, and subsequent versions of the graph are created from the reference to the initial graph and a delta log data structure that records the changes compared to the base version of the graph.

公开(公告)号：US20210279282A1

公开(公告)日：2021-09-09

申请号：US17330046

申请日：2021-05-25

Applicant: Oracle International Corporation

Inventor： DAMIEN HILLOULIN ,  DAVIDE BARTOLINI ,  OSKAR VAN REST ,  Alexander Weld ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F16/901 ,  G06F16/28 ,  G06F16/22

Abstract: Techniques are provided herein for efficient representation of heterogeneous graphs in memory. In an embodiment, vertices and edges of the graph are segregated by type. Each property of a type of vertex or edge has values stored in a respective vector. Directed or undirected edges of a same type are stored in compressed sparse row (CSR) format. The CSR format is more or less repeated for edge traversal in either forward or reverse direction. An edge map translates edge offsets obtained from traversal in the reverse direction for use with data structures that expect edge offsets in the forward direction. Subsequent filtration and/or traversal by type or property of vertex or edge entails minimal data access and maximal data locality, thereby increasing efficient use of the graph.

公开(公告)号：US20190325075A1

公开(公告)日：2019-10-24

申请号：US15956115

申请日：2018-04-18

Applicant: Oracle International Corporation

Inventor： DAMIEN HILLOULIN ,  DAVIDE BARTOLINI ,  OSKAR VAN REST ,  Alexander Weld ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F17/30

Abstract: Techniques are provided herein for efficient representation of heterogeneous graphs in memory. In an embodiment, vertices and edges of the graph are segregated by type. Each property of a type of vertex or edge has values stored in a respective vector. Directed or undirected edges of a same type are stored in compressed sparse row (CSR) format. The CSR format is more or less repeated for edge traversal in either forward or reverse direction. An edge map translates edge offsets obtained from traversal in the reverse direction for use with data structures that expect edge offsets in the forward direction. Subsequent filtration and/or traversal by type or property of vertex or edge entails minimal data access and maximal data locality, thereby increasing efficient use of the graph.

公开(公告)号：US20190235913A1

公开(公告)日：2019-08-01

申请号：US15886745

申请日：2018-02-01

Applicant: Oracle International Corporation

Inventor： Alexander Weld ,  Korbinian Schmid ,  Sungpack Hong ,  Hassan Chafi ,  Vlad Ioan Haprian

IPC: G06F9/48

CPC classification number: G06F9/48

Abstract: Techniques are described herein for concurrently evaluating graph processing tasks in a fair and efficient manner. In an embodiment, a request to execute a graph processing task is received. A first mapping associates each graph processing task of a plurality of graph processing tasks to a set of workload characteristics of a plurality of sets of workload characteristics. A second mapping associates each set of workload characteristics of the plurality of sets of workload characteristics to a set of execution parameters of a plurality of sets of execution parameters. Using the first mapping, a set of workload characteristics is determined based on the graph processing task. Using the second mapping, a set of execution parameters is determined based on the determined set of workload characteristics. The graph processing task is executed based on the determined set of execution parameters.

公开(公告)号：US20180307777A1

公开(公告)日：2018-10-25

申请号：US15495193

申请日：2017-04-24

Applicant: Oracle International Corporation

Inventor： Martin Sevenich ,  Sungpack Hong ,  Alexander Weld ,  Hassan Chafi ,  Daniel Lehmann

IPC: G06F17/30

CPC classification number: G06F16/9024 ,  G06F16/23 ,  G06F16/90335

Abstract: Techniques herein minimize memory needed to store distances between vertices of a graph for use during a multi-source breadth-first search (MS-BFS). In an embodiment, during each iteration of a first sequence of iterations of a MS-BFS, a computer updates a first matrix that contains elements that use a first primitive integer type having a first width to record a distance from a source vertex of a graph to another vertex. The computer detects that a count of iterations of the first sequence of iterations exceeds a threshold. Responsively, the computer creates a second matrix that contains elements that use a second primitive integer type having a second width that is larger than the first width to record a distance from a source vertex of the graph to another vertex. During each iteration of a second sequence of iterations of the MS-BFS, the computer updates the second matrix.

公开(公告)号：US10585945B2

公开(公告)日：2020-03-10

申请号：US15666310

申请日：2017-08-01

Applicant: Oracle International Corporation

Inventor： Martin Sevenich ,  Sungpack Hong ,  Alexander Weld ,  Hassan Chafi ,  Martijn Dwars

IPC: G06F17/30 ,  G06F16/901 ,  G06F8/30 ,  G06F8/41 ,  G06F16/2453 ,  G06F8/34

Abstract: Techniques herein generate, such as during compilation, polymorphic dispatch logic (PDL) to switch between specialized implementations of a polymorphic graph algorithm. In an embodiment, a computer detects, within source logic of a graph algorithm, that the algorithm processes an instance of a generic graph type. The computer generates several alternative implementations of the algorithm. Each implementation is specialized to process the graph instance as an instance of a respective graph subtype. The computer generates PDL that performs dynamic dispatch as follows. At runtime, the PDL receives a graph instance of the generic graph type. The PDL detects which particular graph subtype is the graph instance. The PDL then invokes whichever alternative implementation that is specialized to process the graph instance as an instance of the detected particular graph subtype. In embodiments, the source logic is expressed in a domain specific language (DSL), e.g. for analysis, traversal, or querying of graphs.

公开(公告)号：US10339179B2

公开(公告)日：2019-07-02

申请号：US15096034

申请日：2016-04-11

Applicant: Oracle International Corporation

Inventor： Siham Yousfi ,  Sungpack Hong ,  Alexander Weld ,  Korbinian Schmid ,  Hassan Chafi

IPC: G06F16/90 ,  G06F16/901 ,  G06F16/25 ,  G06F16/84 ,  G06F16/903

Abstract: Techniques are provided for mapping tables and columns of a legacy relational schema into synthetic tables that are dedicated for graph analysis. In an embodiment, a computer receives a mapping of relational tables to node tables and edge tables. The node tables contain columns and rows. The edge tables contain columns and rows. The rows of the node tables and the rows of the edge tables define a graph. Based on the mapping and the relational tables, the computer calculates a value of at least one column of at least one row of the node tables. Based on an execution of a query of the graph, the computer returns the value.

公开(公告)号：US20190163704A1

公开(公告)日：2019-05-30

申请号：US16265090

申请日：2019-02-01

Applicant: Oracle International Corporation

Inventor： Michael Haubenschild ,  Sungpack Hong ,  Hassan Chafi ,  Korbinian Schmid ,  Martin Sevenich ,  Alexander Weld

IPC: G06F16/901 ,  G06F16/28

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.