Answering billion-scale label-constrained reachability queries within microsecond

Peng, Y; Zhang, Y; Lin, X; Qin, L; Zhang, W

Answering billion-scale label-constrained reachability queries within microsecond

Peng, Y Zhang, Y

Lin, X Qin, L Zhang, W

Permalink

Publisher:: VLDB Endowment
Publication Type:: Journal Article
Citation:: Proceedings of the VLDB Endowment, 2020, 13, (6), pp. 812-825
Issue Date:: 2020-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Published VersionAdobe PDF (303.05 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Peng, Y
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Lin, X
dc.contributor.author	Qin, L
dc.contributor.author	Zhang, W
dc.date.accessioned	2020-11-03T01:31:14Z
dc.date.available	2020-11-03T01:31:14Z
dc.date.issued	2020-01-01
dc.identifier.citation	Proceedings of the VLDB Endowment, 2020, 13, (6), pp. 812-825
dc.identifier.issn	2150-8097
dc.identifier.issn	2150-8097
dc.identifier.uri	http://hdl.handle.net/10453/143715
dc.description.abstract	In this paper, we study the problem of label-constrained reachability (LCR) query which is fundamental in many applications with directed edge-label graphs. Although the classical reachability query (i.e., reachability query without label constraint) has been extensively studied, LCR query is much more challenging because the number of possible label constraint set is exponential to the size of the labels. We observe that the existing techniques for LCR queries only construct partial index for better scalability, and their worst query time is not guaranteed and could be the same as an online breadth-first search (BFS). In this paper, we propose novel label-constrained 2-hop indexing techniques with novel pruning rules and order strategies. It is shown that our worst query time could be bounded by the in-out index entry size. With all these techniques, comprehensive experiments show that our proposed methods significantly outperform the state-of-the-art technique in terms of query response time (up to 5 orders of magnitude speedup), index size and index construction time. In particular, our proposed method can answer LCR queries within microsecond over billion-scale graphs in a single machine.
dc.language	en
dc.publisher	VLDB Endowment
dc.relation	http://purl.org/au-research/grants/arc/FT170100128
dc.relation	http://purl.org/au-research/grants/arc/DP180103096
dc.relation.ispartof	Proceedings of the VLDB Endowment
dc.relation.isbasedon	10.14778/3380750.3380753
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	0802 Computation Theory and Mathematics, 0806 Information Systems, 0807 Library and Information Studies
dc.title	Answering billion-scale label-constrained reachability queries within microsecond
dc.type	Journal Article
utslib.citation.volume	13
utslib.for	0802 Computation Theory and Mathematics
utslib.for	0806 Information Systems
utslib.for	0807 Library and Information Studies
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - AAII - Australian Artificial Intelligence Institute
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney
utslib.copyright.status	open_access	*
dc.date.updated	2020-11-03T01:31:04Z
pubs.issue	6
pubs.publication-status	Published
pubs.volume	13
utslib.citation.issue	6

Abstract:

In this paper, we study the problem of label-constrained reachability (LCR) query which is fundamental in many applications with directed edge-label graphs. Although the classical reachability query (i.e., reachability query without label constraint) has been extensively studied, LCR query is much more challenging because the number of possible label constraint set is exponential to the size of the labels. We observe that the existing techniques for LCR queries only construct partial index for better scalability, and their worst query time is not guaranteed and could be the same as an online breadth-first search (BFS). In this paper, we propose novel label-constrained 2-hop indexing techniques with novel pruning rules and order strategies. It is shown that our worst query time could be bounded by the in-out index entry size. With all these techniques, comprehensive experiments show that our proposed methods significantly outperform the state-of-the-art technique in terms of query response time (up to 5 orders of magnitude speedup), index size and index construction time. In particular, our proposed method can answer LCR queries within microsecond over billion-scale graphs in a single machine.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/143715