Patent · US Active

Hybrid in-memory BFS-DFS approach for computing graph queries involving complex path patterns including trees and cycles inside relational database systems

US11397732B2 · kind B2 · utility

0Cited by

0References

20Claims

0Family size

Assignee

Oracle International Corporation · US

Inventors

Vlad Ioan Haprian · Zürich, CH
Laurent Daynes · Le Fangeat, FR
Shasank K. Chavan · Menlo Park, US
Jean-Pierre Lozi · Zürich, CH
Vasileios Trigonakis · Zürich, CH
Sungpack Hong · Palo Alto, US
Marco Arnaboldi · Zürich, CH
Ciprian Baetu · Zürich, CH

Key dates

Filing date	Dec 11, 2019
Grant date	Jul 26, 2022
Priority date	—
Expiry date	Dec 18, 2039

Classification

Technology area (CPC G)Physics
CPC primaryG06F16/284
WIPO fieldComputer technology
WIPO sectorElectrical engineering

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.

Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.