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

公开(公告)号：US20190303810A1

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

申请号：US15938988

申请日：2018-03-28

Applicant: Oracle International Corporation

Inventor： Kenny C. Gross ,  Andrew I. Vakhutinsky ,  DeJun Li ,  Bradley R. Williams ,  Sungpack Hong

IPC: G06Q10/04 ,  G06Q10/00 ,  G06Q50/06

Abstract: The disclosed embodiments relate to a system that facilitates deployment of utility repair crews to nodes in a utility network. During operation, the system determines a node criticality for each node in the utility network based on a network-reliability analysis, which considers interconnections among the nodes in the utility network. The system also determines a node failure probability for each node in the utility network based on historical weather data, historical node failure data and weather forecast information for the upcoming weather event. The system uses the determined node criticalities and the determined node failure probabilities to determine a deployment plan for deploying repair crews to nodes in the utility network in preparation for the upcoming weather event. The system then presents the deployment plan to a person who uses the deployment plan to deploy repair crews to be available to service nodes in the utility network.

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

公开(公告)号：US20190102154A1

公开(公告)日：2019-04-04

申请号：US15721848

申请日：2017-09-30

Applicant: Oracle International Corporation

Inventor： Petr Koupy ,  Thomas Manhardt ,  Siegfried Depner ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F9/45 ,  G06F9/50 ,  G06F17/16 ,  G06F17/30

Abstract: Techniques herein minimally communicate between computers to repartition a graph. In embodiments, each computer receives a partition of edges and vertices of the graph. For each of its edges or vertices, each computer stores an intermediate representation into an edge table (ET) or vertex table. Different edges of a vertex may be loaded by different computers, which may cause a conflict. Each computer announces that a vertex resides on the computer to a respective tracking computer. Each tracking computer makes assignments of vertices to computers and publicizes those assignments. Each computer that loaded conflicted vertices transfers those vertices to computers of the respective assignments. Each computer stores a materialized representation of a partition based on: the ET and vertex table of the computer, and the vertices and edges that were transferred to the computer. Edges stored in the materialized representation are stored differently than edges stored in the ET.

公开(公告)号：US10228920B2

公开(公告)日：2019-03-12

申请号：US14276895

申请日：2014-05-13

Applicant: Oracle International Corporation

Inventor： Martin Sevenich ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F9/44 ,  G06F8/41

Abstract: An implementation of an abstract data type is automatically selected by a compiler of high-level language source code. The compiler chooses an implementation for each instance of an abstract data type in a program based on operations performed in the instance within the program. The compiler rewrites and compiles the high-level language source code in response to selecting the implementation.

公开(公告)号：US20180315228A1

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

申请号：US15581820

申请日：2017-04-28

Applicant: Oracle International Corporation

Inventor： Jan Boettcher ,  Alexander Weld ,  Korbinian Schmid ,  Sungpack Hong ,  Hassan Chafi

IPC: G06T11/20 ,  G06T11/60

Abstract: Techniques are provided for strategy-based graph simplification. In an embodiment, a computer provides configurable strategies that simplify edges of a graph. A client selects and configures a strategy subset of the configurable strategies to define a particular simplification scheme. The computer simplifies a graph by applying the strategy subset to the graph. In embodiments, predefined classes or other application programming interface (API) is provided to clients to obtain and customize strategy instances, such as with a factory or builder. Strategy instances may be imperative or declarative. A service implementation, such as a graph engine, may be embedded or remoted. Techniques herein provide for reuse and optimization.

公开(公告)号：US10055509B2

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

申请号：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 ,  G06F17/00

CPC classification number: G06F16/9024 ,  G06F16/2246 ,  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.

公开(公告)号：US20180203897A1

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

申请号：US15409091

申请日：2017-01-18

Applicant: ORACLE INTERNATIONAL CORPORATION

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

IPC: G06F17/30

Abstract: Techniques herein accelerate graph querying by caching neighbor vertices (NVs) of super-node vertices. In an embodiment, a computer receives a graph query (GQ) to extract result paths from a graph in a database. The GQ has a sequence of query vertices (QVs) and a sequence of query edges (QEs). The computer successively traverses each QE and QV to detect paths of the graph that match the GQ. Traversing each QE and QV entails retrieving NVs of a current graph vertex (CGV) of a current traversal path. If the CGV is a key in a cache whose keys are graph vertices having an excessive degree, then the computer retrieves NVs from the cache. Otherwise, the computer retrieves NVs from the database. If the degree is excessive, and the CGV is not a key in the cache, then the computer stores, into the cache, the CGV as a key for the NVs.

公开(公告)号：US20170249187A1

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

申请号：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.