公开(公告)号：US20210240456A1

公开(公告)日：2021-08-05

申请号：US16776792

申请日：2020-01-30

Applicant: Oracle International Corporation

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

IPC: G06F8/41 ,  G06F8/34 ,  G06F9/30 ,  G06F8/72 ,  G06F9/54

Abstract: Techniques are described for compiling source code to generate graph-optimized intermediate representation instructions of the source code that implement techniques for optimizing algorithms for graph analysis. A compiler, executing on a computing device, receives source code instructions for a program to be compiled. The compiler identifies a target expression, within the source code instructions, that invokes a particular method call on a particular object type. The target expression contains a target block of code to be translated into an intermediate representation using graph-optimized compilation techniques. The compiler generates a block of graph-specific intermediate representation instructions to replace the target expression. The compiler compiles the source code instructions to generate intermediate representation instructions, where the intermediate representation instructions include the block of graph-specific intermediate representation instructions in place of the target expression.

公开(公告)号：US11068538B2

公开(公告)日：2021-07-20

申请号：US16265090

申请日：2019-02-01

Applicant: Oracle International Corporation

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

IPC: G06F16/00 ,  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.

公开(公告)号：US20210182316A1

公开(公告)日：2021-06-17

申请号：US16710740

申请日：2019-12-11

Applicant: Oracle International Corporation

Inventor： Vlad Haprian ,  Laurent Daynes ,  Shasank K. Chavan ,  Jean-Pierre Lozi ,  Vasileios Trigonakis ,  Sungpack Hong ,  Marco Arnaboldi ,  Ciprian Baetu

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

Abstract: An in-memory graph query runtime is integrated inside a database management system and is capable of performing simple patter-matching queries against homogeneous graphs. The runtime efficiently combines breadth-first (BFS) and depth-first (DFS) neighbor traversal algorithms to achieve a hybrid runtime that takes the best from both sides. As a result, the hybrid runtime is able to process arbitrarily large queries with a fixed amount of memory, optimizing for memory locality.

公开(公告)号：US20210182285A1

公开(公告)日：2021-06-17

申请号：US16710715

申请日：2019-12-11

Applicant: Oracle International Corporation

Inventor： Vlad Haprian ,  Laurent Daynes ,  Shasank K. Chavan ,  Jean-Pierre Lozi ,  Vasileios Trigonakis ,  Sungpack Hong ,  Marco Arnaboldi ,  Ciprian Baetu

IPC: G06F16/2453 ,  G06F16/242 ,  G06F16/23 ,  G06F16/28

Abstract: An in-memory graph query runtime is integrated inside a database management system and is capable of performing simple patter-matching queries against homogeneous graphs. The runtime efficiently combines breadth-first (BFS) and depth-first (DFS) neighbor traversal algorithms to achieve a hybrid runtime that takes the best from both sides. As a result, the hybrid runtime is able to process arbitrarily large queries with a fixed amount of memory, optimizing for memory locality.

公开(公告)号：US20200342055A1

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

申请号：US16392386

申请日：2019-04-23

Applicant: Oracle International Corporation

Inventor： Rhicheek Patra ,  Davide Bartolini ,  Sungpack Hong ,  Hassan Chafi ,  Alberto Parravicini

IPC: G06F17/27 ,  G06N5/02

Abstract: Techniques are described herein for performing named entity disambiguation. According to an embodiment, a method includes receiving input text, extracting a first mention and a second mention from the input text, and selecting, from a knowledge graph, a plurality of first candidate vertices for the first mention and a plurality of second candidate vertices for the second mention. The present method also includes evaluating a score function that analyzes vertex embedding similarity between the plurality of first candidate vertices and the plurality of second candidate vertices. In response to evaluating and seeking to optimize the score function, the method performs selecting a first selected candidate vertex from the plurality of first candidate vertices and a second selected candidate vertex from the plurality of second candidate vertices. Further, the present method includes mapping a first entry from the knowledge graph to the first mention and mapping a second entry from the knowledge graph to the second mention. In this embodiment, the first entry corresponds to the first selected candidate vertex and the second entry corresponds to the second selected candidate.

公开(公告)号：US10809881B2

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

申请号：US15603218

申请日：2017-05-23

Applicant: Oracle International Corporation

Inventor： Julia Kindelsberger ,  Daniel Langerenken ,  Korbinian Schmid ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F3/0482 ,  G06F16/00 ,  G06F16/901 ,  G06T11/20 ,  G06F3/0484 ,  G06F3/0486

Abstract: Techniques herein visually construct and summarize property graphs. In an embodiment, a computer loads raw data tables and generates vertices and edges based on the data tables. Vertices may be disconnected or may be interconnected by edges based on foreign keys. In an embodiment, a junction vertex can be converted into a special edge that interconnects two other vertices. In an embodiment, a junction vertex can be converted into a self-directed edge that interconnects data within a single vertex. Filtration can be applied when loading raw tables and then adjusted after visual construction of vertices and edges.

公开(公告)号：US10678588B2

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

申请号：US15597460

申请日：2017-05-17

Applicant: Oracle International Corporation

Inventor： Jan van der Lugt ,  Timothy L. Harris ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F9/48

Abstract: Techniques are provided for reducing synchronization of tasks in a task scheduling system. A task queue includes multiple tasks, some of which require an I/O operation while other tasks require data stored locally in memory. A single thread is assigned to process tasks in the task queue. The thread determines if a task at the head of the task queue requires an I/O operation. If so, then the thread generates an I/O request, submits the I/O request, and may place the task at (or toward) the end of the task queue. When the task reaches the head of the task queue again, the thread determines if data requested by the I/O request is available yet. If so, then the thread processes the request. Otherwise, the thread may place the task at (or toward) the end of the task queue again.

公开(公告)号：US20200151216A1

公开(公告)日：2020-05-14

申请号：US16185236

申请日：2018-11-09

Applicant: Oracle International Corporation

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

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

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.

公开(公告)号：US10585575B2

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

申请号：US15609629

申请日：2017-05-31

Applicant: Oracle International Corporation

Inventor： Julia Kindelsberger ,  Daniel Langerenken ,  Korbinian Schmid ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F3/0484 ,  G06T11/20 ,  G06F16/904 ,  G06F16/901

Abstract: Techniques herein organize and display as branches the historical versions of filtrations of a property graph in a way that suits interactive exploration. In embodiments, a computer loads metadata that describes versions of filtration of a graph that contains vertices interconnected by edges. Based on the metadata, the computer displays, along a timeline, version indicators that each represents a respective historical version of filtration of the graph. The computer displays, responsive to receiving an interactive selection of a particular version indicator of the plurality of version indicators, a particular version of filtration of the graph that is represented by the particular version indicator. Subsequences of versions for the timeline may be organized as branches that may be interactively created and merged. Branching and merging are integrated into the general lifecycle of graph filtration. A version timeline may be presented and operated as a tool for historical navigation and speculative exploration.

公开(公告)号：US10534657B2

公开(公告)日：2020-01-14

申请号：US15607985

申请日：2017-05-30

Applicant: Oracle International Corporation

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

IPC: G06F15/16 ,  G06F11/00

Abstract: Techniques minimize communication while loading a graph. In a distributed embodiment, each computer loads some edges of the graph. Each edge connects a source vertex (SV) to a destination vertex. For each SV of the edges, the computer hashes the SV to detect a tracking computer (TrC) that tracks on which computer does the SV reside. Each computer informs the TrC that the SV originates an edge that resides on that computer. For each SV, the TrC detects that the SV originates edges that reside on multiple providing computers (PCs). The TrC selects a target computer (TaC) from the multiple PCs to host the SV. The TrC instructs each PC, excluding the TaC, to transfer the SV and related edges that are connected to the SV to the TaC. A vertex's internal identifier indicates which computer hosts the vertex. The TrC maintains a mapping between external and internal identifiers.