Reachability Labeling for Distributed Graphs

Zhang, J; Li, W; Qin, L; Zhang, Y; Wen, D; Cui, L; Lin, X

Reachability Labeling for Distributed Graphs

Zhang, J Li, W

Qin, L

Zhang, Y

Wen, D Cui, L Lin, X

Permalink

Publisher:: IEEE
Publication Type:: Conference Proceeding
Citation:: 2022 IEEE 38th International Conference on Data Engineering (ICDE), 2022, 2022-May, pp. 686-698
Issue Date:: 2022-01-01

Closed Access

	Filename	Description	Size
	ICDE_22_Reachability Labeling for Distributed Graphs.pdf	Accepted version	340.77 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	Zhang, J
dc.contributor.author	Li, W https://orcid.org/0000-0003-4941-8814
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Wen, D
dc.contributor.author	Cui, L
dc.contributor.author	Lin, X
dc.date	2022-05-09
dc.date.accessioned	2023-01-13T04:08:07Z
dc.date.available	2023-01-13T04:08:07Z
dc.date.issued	2022-01-01
dc.identifier.citation	2022 IEEE 38th International Conference on Data Engineering (ICDE), 2022, 2022-May, pp. 686-698
dc.identifier.isbn	9781665408837
dc.identifier.issn	1084-4627
dc.identifier.uri	http://hdl.handle.net/10453/164963
dc.description.abstract	Real-world graphs are typically distributed across multiple data centers. When performing reachability queries on these distributed graphs, reachability labeling methods ensure fast query processing by using lightweight indexes. One of the best-known labeling methods is TOL; however, TOL is a serial algorithm and cannot handle distributed graphs. The main goal of this paper is to design new labeling methods that can work in parallel while producing the same index as TOL. To this end, we investigate the limitation of TOL and thus propose a filtering-and-refinement framework for index creation. This framework first obtains a super-set of each vertex's label sets and then eliminates the invalid elements. Based on this framework, we design distributed labeling algorithms and then use batch processing to improve efficiency. Experimental results on real-world graphs show that the proposed algorithms can index distributed graphs efficiently.
dc.language	en
dc.publisher	IEEE
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	2022 IEEE 38th International Conference on Data Engineering (ICDE)
dc.relation.ispartof	38th IEEE International Conference on Data Engineering (ICDE)
dc.relation.ispartofseries	IEEE International Conference on Data Engineering
dc.relation.isbasedon	10.1109/icde53745.2022.00056
dc.rights	info:eu-repo/semantics/closedAccess
dc.title	Reachability Labeling for Distributed Graphs
dc.type	Conference Proceeding
utslib.citation.volume	2022-May
utslib.location.activity	ELECTR NETWORK
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	2023-01-13T04:08:05Z
pubs.finish-date	2022-05-11
pubs.publication-status	Published
pubs.start-date	2022-05-09
pubs.volume	2022-May

Abstract:

Real-world graphs are typically distributed across multiple data centers. When performing reachability queries on these distributed graphs, reachability labeling methods ensure fast query processing by using lightweight indexes. One of the best-known labeling methods is TOL; however, TOL is a serial algorithm and cannot handle distributed graphs. The main goal of this paper is to design new labeling methods that can work in parallel while producing the same index as TOL. To this end, we investigate the limitation of TOL and thus propose a filtering-and-refinement framework for index creation. This framework first obtains a super-set of each vertex's label sets and then eliminates the invalid elements. Based on this framework, we design distributed labeling algorithms and then use batch processing to improve efficiency. Experimental results on real-world graphs show that the proposed algorithms can index distributed graphs efficiently.

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

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