Distributed Asynchronous Regular Path Queries (RPQs) on Graphs

Graph pattern-matching queries enable flexible graph exploration and analysis, similar to what SQL provides for relational databases. One of the most expressive and powerful constructs in graph querying is regular path queries, also called RPQs. RPQs enable support for variable-length path patterns based on regular expressions, such as (p1:person)-/:knows+/->(p2:person), which searches for non-zero 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. We evaluate our system and show that with sixteen machines, it outperforms Neo4j by 82 times on average and a relational implementation of the same queries in PostgreSQL by 71 times, while maintaining low memory consumption.