公开(公告)号：US20170024194A1

公开(公告)日：2017-01-26

申请号：US14805897

申请日：2015-07-22

Applicant: Oracle International Corporation

Inventor： Martin Sevenich ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F9/45

CPC classification number: G06F8/443 ,  G06F8/4443

Abstract: Techniques for optimizing program code through property merging are described. In an embodiment, a compiler identifies, from a plurality of properties of a particular data object that are referenced by the program code, one or more candidate sets of properties that are eligible for merging. For a respective candidate set of properties of the one or more candidate set of properties, the compiler determines whether to merge different properties of the particular data object that belong to the respective candidate set of properties. After determining to merge the different properties, a particular data structure is generated, within the memory of a computing device, that stores the different properties of the particular data object that belong to the respective candidate set.

Abstract translation: 描述了通过属性合并来优化程序代码的技术。 在一个实施例中，编译器从由程序代码引用的特定数据对象的多个属性中识别符合合并条件的一个或多个候选属性集合。 对于一个或多个候选属性集合的相应候选集合的属性，编译器确定是否合并属于相应候选属性集合的特定数据对象的不同属性。 在确定合并不同属性之后，在计算设备的存储器内生成存储属于相应候选集合的特定数据对象的不同属性的特定数据结构。

公开(公告)号：US20160117358A1

公开(公告)日：2016-04-28

申请号：US14524838

申请日：2014-10-27

Applicant: Oracle International Corporation

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

IPC: G06F17/30

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.

Abstract translation: 为图形数据库系统提供了技术，该数据库系统接受以高级图形编程语言编写的自定义图形分析程序，并将程序编译成可执行文件，在执行时可以直接访问图形中存储的图形数据 图形数据库。 以这种方式，避免了低级数据访问API。 此外，仅描述算法的抽象描述的图分析程序不包括关于数据访问的任何细节。 在一种技术中，用户不需要在图分析程序中包括显式并行化，以便图分析程序利用并行化。 图形数据库系统的编译器识别可以受益于并行化的图分析程序的部分，并且作为响应，生成对应于那些部分的并行可执行代码。

公开(公告)号：US20150178406A1

公开(公告)日：2015-06-25

申请号：US14139269

申请日：2013-12-23

Applicant: Oracle International Corporation

Inventor： Sungpack Hong ,  Martin Sevenich ,  Hassan Chafi

IPC: G06F17/30

CPC classification number: G06F17/30958 ,  G06F17/30312

Abstract: Techniques for identifying common neighbors of two nodes in a graph are provided. One technique involves performing a binary split search and/or a linear search. Another technique involves creating a segmenting index for a first neighbor list. A second neighbor list is scanned and, for each node indicated in the second neighbor list, the segmenting index is used to determine whether the node is also indicated in the first neighbor list. Techniques are also provided for counting the number of triangles. One technique involves pruning nodes from neighbor lists based on the node values of the nodes whose neighbor lists are being pruned. Another technique involves sorting the nodes in a node array (and, thus, their respective neighbor lists) based on the nodes' respective degrees prior to identifying common neighbors. In this way, when pruning the neighbor lists, the neighbor lists of the highly connected nodes are significantly reduced.

Abstract translation: 提供了用于识别图中两个节点的公共邻居的技术。 一种技术涉及执行二分割搜索和/或线性搜索。 另一种技术涉及为第一邻居列表创建分段索引。 扫描第二邻居列表，并且对于第二邻居列表中指示的每个节点，使用分段索引来确定节点是否也在第一邻居列表中指示。 还提供了用于计数三角形数量的技术。 一种技术是根据邻居列表被修剪的节点的节点值从邻居列表中修剪节点。 另一技术涉及在识别公共邻居之前基于节点的相应度来对节点阵列（以及因此其相应的邻居列表）中的节点进行排序。 这样，当修剪邻居列表时，高度连接的节点的邻居列表显着减少。

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

公开(公告)号：US10795672B2

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

申请号：US16176853

申请日：2018-10-31

Applicant: Oracle International Corporation

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

IPC: G06F8/75 ,  G06F8/51 ,  G06F8/41 ,  G06F8/30 ,  G06F16/901

Abstract: Techniques are described herein for automatic generation of multi-source breadth-first search (MS-BFS) from high-level graph processing language that can be executed in a distributed computing environment. In an embodiment, a method involves a computer analyzing original software instructions. The original software instructions are configured to perform multiple breadth-first searches to determine a particular result. Each breadth-first search originates at each of a subset of vertices of a graph. Each breadth-first search is encoded for independent execution. Based on the analyzing, the computer generates transformed software instructions configured to perform a MS-BFS to determine the particular result. Each of the subset of vertices is a source of the MS-BFS. In an embodiment, the second plurality of software instructions comprises a node iteration loop and a neighbor iteration loop, and the plurality of vertices of the distributed graph comprise active vertices and neighbor vertices. The node iteration loop is configured to iterate once per each active vertex of the plurality of vertices of the distributed graph, and the node iteration loop is configured to determine the particular result. The neighbor iteration loop is configured to iterate once per each active vertex of the plurality of vertices of the distributed graph, and each iteration of the neighbor iteration loop is configured to activate one or more neighbor vertices of the plurality of vertices for the following iteration of the neighbor iteration loop.

公开(公告)号：US10133827B2

公开(公告)日：2018-11-20

申请号：US14710117

申请日：2015-05-12

Applicant: Oracle International Corporation

Inventor： Manuel Then ,  Sungpack Hong ,  Martin Sevenich ,  Hassan Chafi

IPC: G06F17/30

Abstract: Techniques are described herein for automatic generation of multi-source breadth-first search (MS-BFS) from high-level graph processing language. In an embodiment, a method involves a computer analyzing original software instructions. The original software instructions are configured to perform multiple breadth-first searches to determine a particular result. Each breadth-first search originates at each of a subset of vertices of a graph. Each breadth-first search is encoded for independent execution. Based on the analyzing, the computer generates transformed software instructions configured to perform a MS-BFS to determine the particular result. Each of the subset of vertices is a source of the MS-BFS. In an embodiment, parallel execution of the MS-BFS is regulated with batches of vertices. In an embodiment, the original software instructions are expressed in Green-Marl graph analysis language. In an embodiment, the transformed software instructions are expressed in a general purpose programming language such as C, C++, Python, or Java.

公开(公告)号：US10127025B2

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

申请号：US14805897

申请日：2015-07-22

Applicant: Oracle International Corporation

Inventor： Martin Sevenich ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F8/41

Abstract: Techniques for optimizing program code through property merging are described. In an embodiment, a compiler identifies, from a plurality of properties of a particular data object that are referenced by the program code, one or more candidate sets of properties that are eligible for merging. For a respective candidate set of properties of the one or more candidate set of properties, the compiler determines whether to merge different properties of the particular data object that belong to the respective candidate set of properties. After determining to merge the different properties, a particular data structure is generated, within the memory of a computing device, that stores the different properties of the particular data object that belong to the respective candidate set.

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

公开(公告)号：US09928113B2

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

申请号：US14543058

申请日：2014-11-17

Applicant: Oracle International Corporation

Inventor： 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: An analyzer (such as a compiler) searches for a program portion that matches a pattern that may suffer from workload imbalance due to nodes with high degrees (i.e., relatively many edges). Such a pattern involves iteration over at least a subset (or all) of the nodes in a graph. If a program portion that matches the pattern is found, then the analyzer determines whether the body of the iteration contains an iteration over edges or neighbors of each node in the subset. If so, then the analyzer transforms the graph analytic program by adding code and, optionally, modifying existing code so that high-degree nodes are processed differently than low-degree nodes. High-degree nodes are processed sequentially while low-degree nodes are processed in parallel. Conversely, edges of high-degree nodes are processed in parallel while edges of low-degree nodes are processed sequentially.

公开(公告)号：US20160299991A1

公开(公告)日：2016-10-13

申请号：US14680150

申请日：2015-04-07

Applicant: Oracle International Corporation

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

IPC: G06F17/30

CPC classification number: G06F17/30958 ,  G06F17/30327 ,  G06F2201/80

Abstract: Techniques for efficiently loading graph data into memory are provided. A plurality of node ID lists are retrieved from storage. Each node ID list is ordered based on one or more order criteria, such as node ID, and is read into memory. A new list of node IDs is created in memory and is initially empty. From among the plurality of node ID lists, a particular node ID is selected based on the one or more order criteria, removed from the node ID list where the particular node ID originates, and added to the new list. This process of selecting, removing, and adding continues until no more than one node ID list exists, other than the new list. In this way, the retrieval of the plurality of node ID lists from storage may be performed in parallel while the selecting and adding are performed sequentially.

Abstract translation: 提供了有效地将图形数据加载到存储器中的技术。 从存储器检索多个节点ID列表。 每个节点ID列表根据一个或多个订单标准（如节点ID）进行排序，并被读入存储器。 节点ID的新列表在内存中创建，最初为空。 从多个节点ID列表中，基于从特定节点ID发起的节点ID列表中移除并添加到新列表的一个或多个顺序标准来选择特定节点ID。 除了新的列表之外，这个选择，删除和添加的过程将继续存在，直到不再有一个节点ID列表存在。 以这种方式，可以在顺序执行选择和添加的同时并行执行从存储器检索多个节点ID列表。