Answering reachability and K-reach queries on large graphs with label constraints

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

Answering reachability and K-reach queries on large graphs with label constraints

Peng, Y Lin, X Zhang, Y

Zhang, W Qin, L

Permalink

Publisher:: SPRINGER
Publication Type:: Journal Article
Citation:: VLDB Journal, 2022, 31, (1), pp. 101-127
Issue Date:: 2022-01-01

Closed Access

	Filename	Description	Size
	Peng2022_Article_AnsweringReachabilityAndK-reac.pdf	Accepted version	987.81 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Peng, Y
dc.contributor.author	Lin, X
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Zhang, W
dc.contributor.author	Qin, L
dc.date.accessioned	2022-03-30T03:35:45Z
dc.date.available	2022-03-30T03:35:45Z
dc.date.issued	2022-01-01
dc.identifier.citation	VLDB Journal, 2022, 31, (1), pp. 101-127
dc.identifier.issn	1066-8888
dc.identifier.issn	0949-877X
dc.identifier.uri	http://hdl.handle.net/10453/155704
dc.description.abstract	The purpose of this paper is to examine the problem of label-constrained reachability (LCR) and K-reach (LCKR) queries, which are fundamental in a wide variety of applications using directed edge-labeled graphs. While reachability and K-reach queries have been extensively researched, LCR and LCKR queries are much more challenging due to the fact that the number of potential label-constraint sets is exponential to the size of the labels. We note that existing techniques for LCR queries only build a partial index and that their worse-case query time could be comparable to that of an online breadth-first search (BFS). This paper proposes a new label-constrained 2-hop indexing method with innovative pruning rules and order strategies. Our work demonstrates that the worst query time could be bounded by the number of in-out index entries. Extensive experiments demonstrate that the proposed methods substantially outperform the state-of-the-art approach in terms of the query response time (up to 5 orders of magnitude speedup), index size, and the index construction time. More precisely, the method we present can response LCR queries across billion-scale networks within microseconds on a single machine. We formally define the problem of LCKR queries and discuss critical applications for addressing it. To tackle the difficulties presented by label and hop constraints, an efficient upper and lower bound is suggested based on a search method. Using all of these techniques, extensive experiments on synthetic and real-world networks demonstrate that our algorithm outperforms the baseline by about three to four orders of magnitude while maintaining competitive indexing time and size.
dc.language	English
dc.publisher	SPRINGER
dc.relation	http://purl.org/au-research/grants/arc/FT170100128
dc.relation	http://purl.org/au-research/grants/arc/DP180103096
dc.relation	http://purl.org/au-research/grants/arc/DP210101393
dc.relation	http://purl.org/au-research/grants/arc/DP210101347
dc.relation	http://purl.org/au-research/grants/arc/FT200100787
dc.relation.ispartof	VLDB Journal
dc.relation.isbasedon	10.1007/s00778-021-00695-0
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	0804 Data Format, 0805 Distributed Computing, 0806 Information Systems
dc.subject.classification	Information Systems
dc.title	Answering reachability and K-reach queries on large graphs with label constraints
dc.type	Journal Article
utslib.citation.volume	31
utslib.for	0804 Data Format
utslib.for	0805 Distributed Computing
utslib.for	0806 Information Systems
pubs.organisational-group	/University of Technology Sydney
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
utslib.copyright.status	closed_access	*
dc.date.updated	2022-03-30T03:35:44Z
pubs.issue	1
pubs.publication-status	Published
pubs.volume	31
utslib.citation.issue	1

Abstract:

The purpose of this paper is to examine the problem of label-constrained reachability (LCR) and K-reach (LCKR) queries, which are fundamental in a wide variety of applications using directed edge-labeled graphs. While reachability and K-reach queries have been extensively researched, LCR and LCKR queries are much more challenging due to the fact that the number of potential label-constraint sets is exponential to the size of the labels. We note that existing techniques for LCR queries only build a partial index and that their worse-case query time could be comparable to that of an online breadth-first search (BFS). This paper proposes a new label-constrained 2-hop indexing method with innovative pruning rules and order strategies. Our work demonstrates that the worst query time could be bounded by the number of in-out index entries. Extensive experiments demonstrate that the proposed methods substantially outperform the state-of-the-art approach in terms of the query response time (up to 5 orders of magnitude speedup), index size, and the index construction time. More precisely, the method we present can response LCR queries across billion-scale networks within microseconds on a single machine. We formally define the problem of LCKR queries and discuss critical applications for addressing it. To tackle the difficulties presented by label and hop constraints, an efficient upper and lower bound is suggested based on a search method. Using all of these techniques, extensive experiments on synthetic and real-world networks demonstrate that our algorithm outperforms the baseline by about three to four orders of magnitude while maintaining competitive indexing time and size.

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

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