Distributed Asynchronous Regular Path Queries (RPQs) on Graphs

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10474284" target="_blank" >RIV/00216208:11320/23:10474284 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1145/3626562.3626833" target="_blank" >https://doi.org/10.1145/3626562.3626833</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/3626562.3626833" target="_blank" >10.1145/3626562.3626833</a>

Result language

angličtina

Original language name

Distributed Asynchronous Regular Path Queries (RPQs) on Graphs

Original language description

Graph engines play a crucial role in modern data analytics pipelines, serving as a middleware for handling complex queries across various domains, such as financial fraud detection. Graph queries enable flexible exploration and analysis, akin to SQL in relational databases. Among the most expressive and powerful constructs of graph querying are regular path queries (RPQs). RPQs enable support for variable-length path patterns based on regular expressions, such as (p1:Person)-/:Knows+/-&gt;(p2:Person) that searches for non-empty paths of any length between two persons.In this paper, we introduce a novel design for distributed RPQs that builds on top of distributed asynchronous pipelined traversals to enable (i) memory control of path explorations, with (ii) great performance and scalability. Through our evaluation, we show that with sixteen machines, it outperforms Neo4j by 91x on average and a relational implementation of the same queries in PostgreSQL by 230x, while maintaining low memory consumption.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2023

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Middleware &apos;23: Proceedings of the 24th International Middleware Conference: Industrial Track

ISBN

979-8-4007-0427-7

ISSN

—

e-ISSN

—

Number of pages

7

Pages from-to

35-41

Publisher name

Association for Computing Machinery

Place of publication

New York, United States

Event location

Bologna Italy

Event date

Dec 11, 2023

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—