Reachability Querying: Can It Be even Faster?

Su, J; Zhu, Q; Wei, H; Yu, JX

Reachability Querying: Can It Be even Faster?

Su, J Zhu, Q Wei, H Yu, JX

Permalink

Publication Type:: Journal Article
Citation:: IEEE Transactions on Knowledge and Data Engineering, 2017, 29 (3), pp. 683 - 697
Issue Date:: 2017-03-01

Closed Access

	Filename	Description	Size
	07750623.pdf	Published Version	962.76 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	Su, J	en_US
dc.contributor.author	Zhu, Q	en_US
dc.contributor.author	Wei, H	en_US
dc.contributor.author	Yu, JX https://orcid.org/0000-0002-9738-827X	en_US
dc.date.issued	2017-03-01	en_US
dc.identifier.citation	IEEE Transactions on Knowledge and Data Engineering, 2017, 29 (3), pp. 683 - 697	en_US
dc.identifier.issn	1041-4347	en_US
dc.identifier.uri	http://hdl.handle.net/10453/126858
dc.description.abstract	© 2016 IEEE. As an important graph operator, reachability query has been extensively studied over decades, which is to check whether a vertex can reach another vertex over a large directed graph G with n vertices and m edges. The efforts made in the reported studies have greatly improved the query time of answering reachability queries online, while reducing the offline index construction time to construct an index with a reasonable size given the approach taken, where an entry in an index for a vertex is called a label of the vertex. Among all the work, the recent development of IP (Independent Permutation) employs randomness using k-min-wise independent permutations to process reachability queries, and shows the advantages for both query time and index construction time. In this paper, we propose a new Bloom filter Labeling, denoted as BFL. We show that the probability to answer reachability queries by BFL can be bounded, and BFL has high pruning power to answer more reachability queries directly. We give algorithms and analyze the pruning power of BFL. We conduct extensive studies using 19 large datasets. We show that BFL with an interval label performs best in the index construction time for all 19 cases, and performs best in query time for 16 out of 19 cases.	en_US
dc.relation.ispartof	IEEE Transactions on Knowledge and Data Engineering	en_US
dc.relation.isbasedon	10.1109/TKDE.2016.2631160	en_US
dc.subject.classification	Information Systems	en_US
dc.title	Reachability Querying: Can It Be even Faster?	en_US
dc.type	Journal Article
utslib.citation.volume	3	en_US
utslib.citation.volume	29	en_US
utslib.for	0803 Computer Software	en_US
utslib.for	08 Information and Computing Sciences	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
utslib.copyright.status	closed_access
pubs.issue	3	en_US
pubs.publication-status	Published	en_US
pubs.volume	29	en_US

Abstract:

© 2016 IEEE. As an important graph operator, reachability query has been extensively studied over decades, which is to check whether a vertex can reach another vertex over a large directed graph G with n vertices and m edges. The efforts made in the reported studies have greatly improved the query time of answering reachability queries online, while reducing the offline index construction time to construct an index with a reasonable size given the approach taken, where an entry in an index for a vertex is called a label of the vertex. Among all the work, the recent development of IP (Independent Permutation) employs randomness using k-min-wise independent permutations to process reachability queries, and shows the advantages for both query time and index construction time. In this paper, we propose a new Bloom filter Labeling, denoted as BFL. We show that the probability to answer reachability queries by BFL can be bounded, and BFL has high pruning power to answer more reachability queries directly. We give algorithms and analyze the pruning power of BFL. We conduct extensive studies using 19 large datasets. We show that BFL with an interval label performs best in the index construction time for all 19 cases, and performs best in query time for 16 out of 19 cases.

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

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