Reachability querying: an independent permutation labeling approach

Wei, H; Yu, JX; Lu, C; Jin, R

Reachability querying: an independent permutation labeling approach

Wei, H Yu, JX

Lu, C Jin, R

Permalink

Publication Type:: Journal Article
Citation:: VLDB Journal, 2018, 27 (1)
Issue Date:: 2018-02-01

Closed Access

	Filename	Description	Size
	Wei2018_Article_ReachabilityQueryingAnIndepend.pdf	Published Version	2.12 MB		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	Wei, H	en_US
dc.contributor.author	Yu, JX https://orcid.org/0000-0002-9738-827X	en_US
dc.contributor.author	Lu, C	en_US
dc.contributor.author	Jin, R	en_US
dc.date.issued	2018-02-01	en_US
dc.identifier.citation	VLDB Journal, 2018, 27 (1)	en_US
dc.identifier.issn	1066-8888	en_US
dc.identifier.uri	http://hdl.handle.net/10453/132571
dc.description.abstract	© 2017, Springer-Verlag Berlin Heidelberg. Reachability query is a fundamental graph operation which answers whether a vertex can reach another vertex over a large directed graph G with n vertices and m edges and has been extensively studied. In the literature, all the approaches compute a label for every vertex in a graph G by index construction offline. The query time for answering reachability queries online is affected by the quality of the labels computed in index construction. The three main costs are the index construction time, the index size, and the query time. Some of the up-to-date approaches can answer reachability queries efficiently, but spend nonlinear time to construct an index. Some of the up-to-date approaches construct an index in linear time and space, but may need to depth-first search G at run-time in O(n+ m). In this paper, we discuss a new randomized labeling approach, named IP label, to answer reachability queries with probability guarantee, and the randomness is by independent permutation. Two additional labels are also proposed to further enhance the query processing. In addition, to deal with dynamic graphs, we discuss the label maintenance over dynamic graphs and give efficient algorithms for the labels proposed. We conduct extensive experimental studies to compare with the up-to-date approaches using 19 large real datasets used in the existing work and synthetic datasets. We confirm the efficiency and scalability of our approach in static graphs testing, and our maintenance algorithms are about one order of magnitude faster than the existing ones in dynamic graphs testing.	en_US
dc.relation.ispartof	VLDB Journal	en_US
dc.relation.isbasedon	10.1007/s00778-017-0468-3	en_US
dc.subject.classification	Information Systems	en_US
dc.title	Reachability querying: an independent permutation labeling approach	en_US
dc.type	Journal Article
utslib.citation.volume	1	en_US
utslib.citation.volume	27	en_US
utslib.for	0804 Data Format	en_US
utslib.for	0806 Information Systems	en_US
utslib.for	0805 Distributed Computing	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	1	en_US
pubs.publication-status	Published	en_US
pubs.volume	27	en_US

Abstract:

© 2017, Springer-Verlag Berlin Heidelberg. Reachability query is a fundamental graph operation which answers whether a vertex can reach another vertex over a large directed graph G with n vertices and m edges and has been extensively studied. In the literature, all the approaches compute a label for every vertex in a graph G by index construction offline. The query time for answering reachability queries online is affected by the quality of the labels computed in index construction. The three main costs are the index construction time, the index size, and the query time. Some of the up-to-date approaches can answer reachability queries efficiently, but spend nonlinear time to construct an index. Some of the up-to-date approaches construct an index in linear time and space, but may need to depth-first search G at run-time in O(n+ m). In this paper, we discuss a new randomized labeling approach, named IP label, to answer reachability queries with probability guarantee, and the randomness is by independent permutation. Two additional labels are also proposed to further enhance the query processing. In addition, to deal with dynamic graphs, we discuss the label maintenance over dynamic graphs and give efficient algorithms for the labels proposed. We conduct extensive experimental studies to compare with the up-to-date approaches using 19 large real datasets used in the existing work and synthetic datasets. We confirm the efficiency and scalability of our approach in static graphs testing, and our maintenance algorithms are about one order of magnitude faster than the existing ones in dynamic graphs testing.

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

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