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

9 Citations (Scopus)

Abstract

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
Pages345-358
Number of pages14
ISBN (Electronic)9781450341974
DOIs
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
http://sigmod2017.org/ (SIGMOD/PODS 2017)

Conference

Conference2017 ACM SIGMOD International Conference on Management of Data (SIGMOD 2017)
Abbreviated titleSIGMOD 2017
CountryUnited States
CityChicago
Period14/05/1719/05/17
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

Keywords

  • Label-constrained reachability
  • Labeled graph
  • Path queries

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

  • Cite this

    Valstar, L. D. J., Fletcher, G. H. L., & Yoshida, Y. (2017). Landmark indexing for evaluation of label-constrained reachability queries. In Proceedings of the 2017 ACM SIGMOD International Conference on Management of Data (SIGMOD 2017) (pp. 345-358). Association for Computing Machinery, Inc. https://doi.org/10.1145/3035918.3035955