Landmark indexing for evaluation of label-constrained reachability queries

L.D.J. Valstar, G.H.L. Fletcher, Y. Yoshida

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

27 Citations (Scopus)


Consider a directed edge-labeled graph, such as a social network or a citation network. A fundamental query on such data is to determine if there is a path in the graph from a given source vertex to a given target vertex, using only edges with labels in a restricted subset of the edge labels in the graph. Such label-constrained reachability (LCR) queries play an important role in graph analytics, for example, as a core fragment of the so-called regular path queries which are supported in practical graph query languages such as the W3C's SPARQL 1.1, Neo4j's Cypher, and Oracle's PGQL. Current solutions for LCR evaluation, however, do not scale to large graphs which are increasingly common in a broad range of application domains. In this paper we present the first practical solution for efficient LCR evaluation, leveraging landmark-based indexes for large graphs. We show through extensive experiments that our indexes are significantly smaller than state-of-the-art LCR indexing techniques, while supporting up to orders of magnitude faster query evaluation times. Our complete C++ codebase is available as open source for further research.
Original languageEnglish
Title of host publicationProceedings of the 2017 ACM SIGMOD International Conference on Management of Data (SIGMOD 2017)
PublisherAssociation for Computing Machinery, Inc
Number of pages14
ISBN (Electronic)9781450341974
Publication statusPublished - 9 May 2017
Event2017 ACM SIGMOD International Conference on Management of Data (SIGMOD 2017) - Chicago, United States
Duration: 14 May 201719 May 2017 (SIGMOD/PODS 2017)


Conference2017 ACM SIGMOD International Conference on Management of Data (SIGMOD 2017)
Abbreviated titleSIGMOD 2017
Country/TerritoryUnited States
OtherThe conference: The annual ACM SIGMOD/PODS conference is a leading international forum for database researchers, practitioners, developers, and users to explore cutting-edge ideas and results, and to exchange techniques, tools, and experiences. The conference includes a fascinating technical program with research and industrial talks, tutorials, demos, and focused workshops. It also hosts a poster session to learn about innovative technology, an industrial exhibition to meet companies and publishers, and a careers-in-industry panel with representatives from leading companies.
Internet address


  • Label-constrained reachability
  • Labeled graph
  • Path queries


Dive into the research topics of 'Landmark indexing for evaluation of label-constrained reachability queries'. Together they form a unique fingerprint.

Cite this