公开(公告)号：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.

公开(公告)号：US10019536B2

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

申请号：US14332182

申请日：2014-07-15

Applicant: Oracle International Corporation

Inventor： Sungpack Hong ,  Zhe Wu ,  Martin Sevenich ,  Jayanta Banerjee ,  Hassan Chafi ,  Korbinian Schmid

IPC: G06F7/00 ,  G06F17/30

CPC classification number: G06F16/9024 ,  G06F16/2246 ,  G06F2201/80

Abstract: Techniques for storing and processing graph data in a database system are provided. Graph data (or a portion thereof) that is stored in persistent storage is loaded into memory to generate an instance of a particular graph. The instance is consistent as of a particular point in time. Graph analysis operations are performed on the instance. The instance may be used by multiple users to perform graph analysis operations. Subsequent changes to the graph are stored separate from the instance. Later, the changes may be applied to the instance (or a copy thereof) to refresh the instance.

公开(公告)号：US10002205B2

公开(公告)日：2018-06-19

申请号：US14947382

申请日：2015-11-20

Applicant: Oracle International Corporation

Inventor： Nicholas Roth ,  Sungpack Hong ,  Siegfried Depner ,  Thomas Manhardt ,  Hassan Chafi

IPC: G06F17/30

CPC classification number: G06F16/9024 ,  G06F16/278

Abstract: Techniques herein index data transferred during distributed graph processing. In an embodiment, a system of computers divides a directed graph into partitions. The system creates one partition per computer and distributes each partition to a computer. Each computer builds four edge lists that enumerate edges that connect the partition of the computer with a partition of a neighbor computer. Each of the four edge lists has edges of a direction, which may be inbound or outbound from the partition. Edge lists are sorted by identifier of the vertex that terminates or originates each edge. Each iteration of distributed graph analysis involves each computer processing its partition and exchanging edge data or vertex data with neighbor computers. Each computer uses an edge list to build a compactly described range of edges that connect to another partition. The computers exchange described ranges with their neighbors during each iteration.

公开(公告)号：US09971570B2

公开(公告)日：2018-05-15

申请号：US14969231

申请日：2015-12-15

Applicant: Oracle International Corporation

Inventor： Martin Sevenich ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F9/44

CPC classification number: G06F8/456

Abstract: Techniques generate memory-optimization logic for concurrent graph analysis. A computer analyzes domain-specific language logic that analyzes a graph having vertices and edges. The computer detects parallel execution regions that create thread locals. Each thread local is associated with a vertex or edge. For each parallel region, the computer calculates how much memory is needed to store one instance of each thread local. The computer generates instrumentation that determines how many threads are available and how many vertices and edges will create thread locals. The computer generates tuning logic that determines how much memory is originally needed for the parallel region based on how much memory is needed to store the one instance, how many threads are available, and graph size. The tuning logic detects a memory shortage based on the original amount of memory needed exceeding how much memory is available and accordingly adjusts the execution of the parallel region.

公开(公告)号：US09916187B2

公开(公告)日：2018-03-13

申请号：US14524838

申请日：2014-10-27

Applicant: Oracle International Corporation

Inventor： Korbinian Schmid ,  Martin Sevenich ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F17/30 ,  G06F9/50 ,  G06F9/44 ,  G06F9/45 ,  H04L29/08

CPC classification number: G06F9/5083 ,  G06F8/31 ,  G06F8/456 ,  G06F17/30321 ,  G06F17/30386 ,  G06F17/30442 ,  G06F17/30958 ,  H04L67/10

Abstract: Techniques are provided for a graph database system that accepts custom graph analytic programs that are written in a high-level graph-specific programming language and compiles the programs into executables that, when executed, directly access graph data of a graph that is stored in the graph database. In this way, a low-level data-access API is avoided. Also, a graph analytic program, which only describes an abstract description of an algorithm, does not include any details regarding data access. In one technique, a user is not required to include explicit parallelization in a graph analytic program in order for the graph analytic program to take advantage of parallelization. A compiler of the graph database system identifies portions of the graph analytic program that can benefit from parallelization and, in response, generates parallelized executable code that corresponds to those portions.

公开(公告)号：US09740536B2

公开(公告)日：2017-08-22

申请号：US14718430

申请日：2015-05-21

Applicant: Oracle International Corporation

Inventor： Jan van der Lugt ,  Merijn Verstraaten ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F9/46 ,  G06F9/50 ,  G06F17/30 ,  G06F9/44 ,  G06F9/45 ,  H04L29/08

CPC classification number: G06F9/5083 ,  G06F8/31 ,  G06F8/456 ,  G06F17/30321 ,  G06F17/30386 ,  G06F17/30442 ,  G06F17/30958 ,  H04L67/10

Abstract: Techniques are provided for efficiently distributing graph data to multiple processor threads located on a server node. The server node receives graph data to be processed by the server node of a graph processing system. The received graph data is a portion of a larger graph to be processed by the graph processing system. In response to receiving graph data the server node compiles a list of vertices and attributes of each vertex from the graph data received. The server node then creates task chunks of work based upon the compiled list of vertices and their corresponding attribute data. The server node then distributes the task chunks to a plurality of threads available on the server node.

公开(公告)号：US20170169133A1

公开(公告)日：2017-06-15

申请号：US14969789

申请日：2015-12-15

Applicant: Oracle International Corporation

Inventor： Jinha Kim ,  Oskar Van Rest ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F17/30

CPC classification number: G06F17/30958 ,  G06F17/30324

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.

公开(公告)号：US09417857B2

公开(公告)日：2016-08-16

申请号：US14594954

申请日：2015-01-12

Applicant: Oracle International Corporation

Inventor： Hassan Chafi ,  Mason Chang ,  Eric Sedlar

IPC: G06F9/45 ,  G06F9/455

CPC classification number: G06F8/4441 ,  G06F8/41 ,  G06F8/443 ,  G06F8/47 ,  G06F9/45516 ,  G06F9/45525

Abstract: Techniques are described for unifying static and dynamic compiler optimizations in source code bases. In an embodiment, a first compiler compiles source code of a target function to generate ahead-of-time (AOT) compiled machine code. A second compiler compiles the source code to generate an intermediate representation (IR) of the target function. In response to determining that the target function should be just-in-time (JIT) compiled, the AOT-compiled machine code for the target function is linked to the IR of the target function. During runtime, a physical processor executes AOT-compiled machine code of an executable program. When the target function is encountered for the first time, a JIT compiler is invoked. The JIT compiler generates JIT-compiled machine code for the target function. The physical processor executes the JIT-compiled machine code in place of the AOT-compiled machine code for the target function.