Return to search

Graph Traversals for Regular Path Queries

Regular Path Queries (RPQs) are at the core of many recent declarative graph pattern matching languages. They leverage the compactness and expressiveness of regular expressions for matching recursive path structures. Unfortunately, most prior works on RPQs only consider breadth-first search as traversal strategy, neglecting other possible graph traversals like depth-first search or a combination of both. Within this paper, we conduct an analysis of graph traversals for RPQs by introducing a generalized graph traversal frame-work subsuming breadth-first search and depth-first search as extreme cases and thus opening up a new design space for graph traversals algorithms. We outline the underlying principles as well as provide comprehensive experimental evaluation using implementations which yield beneficial results regarding evaluation time and peak memory consumption.

Identiferoai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:86035
Date15 June 2023
CreatorsTetzel, Frank, Kasperovics, Romans, Lehner, Wolfgang
PublisherACM
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
LanguageEnglish
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/acceptedVersion, doc-type:conferenceObject, info:eu-repo/semantics/conferenceObject, doc-type:Text
Rightsinfo:eu-repo/semantics/openAccess
Relation978-1-4503-6789-9, 5, 10.1145/3327964.3328494

Page generated in 0.0017 seconds