Oracle International Corporation

Hassan Chafi

Sungpack Hong

Martin Sevenich

Korbinian Schmid

Alexander Weld

Vasileios Trigonakis

Matthias Brantner

Vlad Ioan Haprian

Pit Fender

Benjamin Schlegel

Oskar Van Rest

Laurent Daynes

Thomas Manhardt

Siegfried Depner

Jean-Pierre Lozi

Jinsu Lee

Harshad Kasture

Tomas Faltin

Eric Sedlar

Andrew Witkowski

Hugo Kapp

Jinha Kim

Zhen Hua Liu

Marco Arnaboldi

Petr Koupy

Nicholas Roth

Alexander Ulrich

Arnaud Delamare

Davide Bartolini

Jan Van Der Lugt

Felix Kaser

Lei Sheng

Rhicheek Patra

Damien Hilloulin

Yahya Ez-Zainabi

Bastian Hossbach

Martijn Dwars

Alberto Parravicini

Merijn Verstraaten

Mason Chang

Sabina Petride

Zhe Wu

Jayanta Banerjee

Hesam Fathi Moghadam

Iraklis Psaroudakis

Anantha Kiran Kandukuri

Yasha Pushak

Guido Wachsmuth

Calin Iorgulescu

Michael Haubenschild

Anton Ragot

Siham Yousfi

Daniel Lehmann

Julia Kindelsberger

Daniel Langerenken

Hyungyu Shin

Raghavan Raman

Xuming Meng

Timothy Lawrence Harris

Huagang Li

Angela Amor

Christian Humer

Jonas Schweizer

Ioannis Alagiannis

Lucas Braun

Petar Tonkovic

Jinsoo Lee

Florian Gratzer

Steven Serra

Ali Seyfi

Constantin Le Clei

Valentin Venzin

Bence Czipo

Fatjon Zogaj

Irfan Bunjaku

Tomáš Faltín

Harshard Kasture

Jan Boettcher

Jürgen Christ

Juergen Christ

Manuel Then

An estimator is provided that can be used to get an estimate of final graph size and peak memory usage of the graph during loading, based on sampling of the graph data and using machine learning (ML) techniques. A data sampler samples the data from files or databases and estimates some statistics about the final graph. The sampler also samples some information about property data. Given the sampled statistics gathered and estimated by the data sampler, a graph size estimator estimates how much memory is required by the graph processing engine to load the graph. The final graph size represents how much memory will be used to keep the final graph structures in memory once loading is completed. The peak memory usage represents the memory usage upper bound that is reached by the graph processing engine during loading.

Estimating graph size and memory consumption of distributed graph for efficient resource management

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.

Method of distributed graph loading for minimal communication and good balance via lazy materialization and directory indirection using indexed tabular representation

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.

Efficient, in-memory, relational representation for heterogeneous graphs

A graph processing engine is provided for executing a graph query comprising a parent query and a subquery nested within the parent query. The subquery is an existential subquery, uses a reference to one or more correlated variables from the parent query, is inlined in the parent query pattern matching, does not have a post-processing phase, does not contain any global aggregation operations, uses a reference to at most one non-correlated variable, and does not include any filters on a non-correlated variable. Executing the graph query comprises initiating execution of the parent query, responsive to the parent query matching the one or more correlated variables in an intermediate result set, executing the subquery by applying a neighbor pattern matching operator that checks for existence of an edge, and resuming execution of the parent query based on results of the neighbor pattern matching operation.

Subqueries in distributed asynchronous graph queries

A breadth first search (BFS) algorithm is provided that uses out-of-core external storage in a memory constrained system. Memory resources are used as long as they are available and external storage is used when necessary due to memory pressure. The BFS algorithm uses a disk-spilling hash-table (DSH) as the visited set and disk-spilling queues (DSQs) as the BFS frontier queue. To get the most out of the DSH, subsequent inserts and lookups must happen in the same DSH partition. To ensure that consecutive lookups happen in the same DSH partition, the BFS frontier queue is partitioned in a manner similar to the DSH partitions.

Out-of-core BFS for shortest path graph queries

In a computer, each of multiple anomaly detectors infers an anomaly score for each of many tuples. For each tuple, a synthetic label is generated that indicates for each anomaly detector: the anomaly detector, the anomaly score inferred by the anomaly detector for the tuple and, for each of multiple contamination factors, the contamination factor and, based on the contamination factor, a binary class of the anomaly score. For each particular anomaly detector excluding a best anomaly detector, a similarity score is measured for each contamination factor. The similarity score indicates how similar, between the particular anomaly detector and the best anomaly detector, are the binary classes of labels with that contamination factor. For each contamination factor, a combined similarity score is calculated based on the similarity scores for the contamination factor. Based on a contamination factor that has the highest combined similarity score, the computer detects that an additional anomaly detector is inaccurate.

Expert-optimal correlation: contamination factor identification for unsupervised anomaly detection

A method, apparatus, and product to provide a parser for property graph queries with precise error reporting and auto-completion based on information from property graph schemas. The approach generally comprises analysis of graph queries prior to their execution to identify issues prior to execution. In some embodiments, the approach includes any of: use of a property graph schema to determine whether names in a received property graph query exist within a corresponding property graph; determining whether the property graph query includes a comparison of mismatched data types; providing an autocomplete suggestion feature for assistance in resolving errors or corresponding to a cursor position within a query string; or evaluation of a property graph query to determine whether it would return an empty result. In some embodiments, property graph query analysis is performed using a context aware approach.

Method, product, and system to provide a parser for property graph queries with precise error reporting and auto-completion based on information from property graph schemas

Techniques support graph pattern matching queries inside a relational database management system (RDBMS) that supports SQL execution. The techniques compile a graph pattern matching query that includes a bounded recursive pattern query into a SQL query that can then be executed by the relational engine. As a result, techniques enable execution of graph pattern matching queries that include bounded recursive patterns on top of the relational engine by avoiding any change in the existing SQL engine.

Efficient compilation of bounded recursive graph queries on top of SQL based relational engine

A graph processing engine is provided for executing a graph query comprising a parent query and a subquery nested within the parent query. The subquery uses a reference to one or more correlated variables from the parent query. Executing the graph query comprises initiating execution of the parent query, pausing the execution of the parent query responsive to the parent query matching the one or more correlated variables in an intermediate result set, generating a subquery identifier for each match of the one or more correlated variables, modifying the subquery to include a subquery aggregate function and a clause to group results by subquery identifier, executing the modified subquery using the intermediate result set and collecting subquery results into a subquery results table responsive to pausing execution of the parent query, and resuming execution of the parent query using the subquery results table.

Herein are graph machine learning explainability (MLX) techniques for invalid traffic detection. In an embodiment, a computer generates a graph that contains: a) domain vertices that represent network domains that received requests and b) address vertices that respectively represent network addresses from which the requests originated. Based on the graph, domain embeddings are generated that respectively encode the domain vertices. Based on the domain embeddings, multidomain embeddings are generated that respectively encode the network addresses. The multidomain embeddings are organized into multiple clusters of multidomain embeddings. A particular cluster is detected as suspicious. In an embodiment, an unsupervised trained graph model generates the multidomain embeddings. Based on the clusters of multidomain embeddings, feature importances are unsupervised trained. Based on the feature importances, an explanation is automatically generated for why an object is or is not suspicious. The explained object may be a cluster or other batch of network addresses or a single network address.

Invalid traffic detection using explainable unsupervised graph ML

A storage manager for offloading graph components to persistent storage for reducing resident memory in a distributed graph processing engine is provided. The storage manager identifies a set of graph components required to execute a graph processing operation on a graph in a graph processing engine of a database system and reserves an amount of memory needed to load the set of graph components into memory. The storage manager loads the set of graph components into memory and initiates execution of the graph processing operation using the set of graph components in memory. The storage manager evicts one or more unused graph components from memory in response to receiving a request to free a requested amount of memory from memory.

Offloading graph components to persistent storage for reducing resident memory in distributed graph processing

A graph processing system is provided for executing scouting queries for improving query planning. A query planner creates a plurality of scouting queries, each scouting query in the plurality of scouting queries corresponding to a query plan for a graph query and having an associated confidence value. A graph processing system performs limited execution of the plurality of scouting queries and determines a metric value for each scouting query in the plurality of scouting queries based on execution of the scouting query. The system determines a score for each scouting query in the plurality of scouting queries based on its metric value and the confidence value of the corresponding query plan and selects a query plan based on the scores of the plurality of scouting queries. The system executes the graph query based on the selected query plan.

Scouting queries for improving query planning in distributed asynchronous graph queries

An RDBMS specifies a graph algorithm function (GAF) that takes a graph object as input and returns a logical graph object as output. GAFs are used within graph queries to compute temporary and output properties ('GAF-computed properties'), which are live for the duration of the query cursor execution. GAF-computed output properties are accessible in the enclosing graph pattern matching query as though they were part of the input graph object of the GAF. Temporary cursor-duration tables are generated for the query cursor during compilation of a graph query that includes a GAF, and are used to store the GAF-computed properties. Each temporary table corresponds to one of the primary tables of the input graph, and includes, as a foreign key, primary key information from the corresponding primary table.

Using temporary tables to store graph algorithm results for a relational database management system

Systems and methods for improving evaluation of graph queries through depth first traversals are described herein. In an embodiment, a multi-node system evaluates against graph data a graph query that specifies a particular pattern to match by determining, at a first node of the multi-node system, in a particular instance of evaluating the graph query, that one or more first vertices on the first node match a first portion of the graph query and that a second vertex that is to be evaluated next is stored on a second node separate from the first node. In response to determining that the next vertex to be evaluated is stored on the second node separate from the first node, the first node generates a message to the second node comprising one or more results of the first portion of the graph query based on the one or more first vertices, an identifier of the next vertex, and a current stage of evaluating the graph query. In response to generating the message from the first node to the second node, the first node ceases the particular instance of evaluating the graph query.

Duplication elimination in depth based searches for distributed systems

Techniques support graph pattern matching queries inside a relational database management system (RDBMS) that supports SQL execution. The techniques compile a graph pattern matching query into a SQL query that can then be executed by the relational engine. As a result, techniques enable execution of graph pattern matching queries on top of the relational engine by avoiding any change in the existing SQL engine.

Efficient compilation of graph queries including complex expressions on top of sql based relational engine

Growing community of inventors

San Mateo, CA, United States of America

Hassan Chafi