Landmark indexing for evaluation of label-constrained reachability queries

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

13 Citaten (Scopus)

Samenvatting

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.
Originele taal-2Engels
TitelProceedings of the 2017 ACM SIGMOD International Conference on Management of Data (SIGMOD 2017)
UitgeverijAssociation for Computing Machinery, Inc
Pagina's345-358
Aantal pagina's14
ISBN van elektronische versie9781450341974
DOI's
StatusGepubliceerd - 9 mei 2017
Evenement2017 ACM SIGMOD International Conference on Management of Data (SIGMOD 2017) - Chicago, Verenigde Staten van Amerika
Duur: 14 mei 201719 mei 2017
http://sigmod2017.org/ (SIGMOD/PODS 2017)

Congres

Congres2017 ACM SIGMOD International Conference on Management of Data (SIGMOD 2017)
Verkorte titelSIGMOD 2017
LandVerenigde Staten van Amerika
StadChicago
Periode14/05/1719/05/17
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'Landmark indexing for evaluation of label-constrained reachability queries'. Samen vormen ze een unieke vingerafdruk.

Citeer dit