Scaling Up Distance Labeling on Graphs with Core-Periphery Properties

Li, W; Qiao, M; Qin, L; Zhang, Y; Chang, L; Lin, X

Scaling Up Distance Labeling on Graphs with Core-Periphery Properties

Li, W Qiao, M Qin, L Zhang, Y

Chang, L Lin, X

Permalink

Publisher:: ACM
Publication Type:: Conference Proceeding
Citation:: Proceedings of the ACM SIGMOD International Conference on Management of Data, 2020, pp. 1367-1381
Issue Date:: 2020-06-14

Closed Access

	Filename	Description	Size
	SIGMOD_scale.pdf	Accepted version	1.31 MB	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	Li, W
dc.contributor.author	Qiao, M
dc.contributor.author	Qin, L
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Chang, L
dc.contributor.author	Lin, X
dc.contributor.editor	Maier, D
dc.contributor.editor	Pottinger, R
dc.contributor.editor	Doan, A
dc.contributor.editor	Tan, W-C
dc.contributor.editor	Alawini, A
dc.contributor.editor	Ngo, HQ
dc.date.accessioned	2020-11-03T01:19:51Z
dc.date.available	2020-11-03T01:19:51Z
dc.date.issued	2020-06-14
dc.identifier.citation	Proceedings of the ACM SIGMOD International Conference on Management of Data, 2020, pp. 1367-1381
dc.identifier.isbn	9781450367356
dc.identifier.issn	0730-8078
dc.identifier.uri	http://hdl.handle.net/10453/143710
dc.description.abstract	© 2020 Association for Computing Machinery. In indexing a graph for distance queries, distance labeling is a common practice; in particular, 2-hop labeling which guarantees the exactness of the query results is widely adopted. When it comes to a massive real graph with a relatively large treewidth such as social networks and web graphs, however, 2-hop labeling can hardly be constructed due to the oversized index. This paper discloses the theoretical relationships between the graph treewidth and 2-hop labeling's index size and query time. To scale up distance labeling, this paper proposes Core-Tree (CT) Index to facilitate a critical and effective trade-off between the index size and query time. The reduced index size enables CT-Index to handle massive graphs that no existing approaches can process while the cost in the query time is negligible: the query time is below 0.4 milliseconds on all tested graphs including one graph with 5.5 billion edges.
dc.language	en
dc.publisher	ACM
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/DP160101513
dc.relation.ispartof	Proceedings of the ACM SIGMOD International Conference on Management of Data
dc.relation.ispartof	SIGMOD/PODS '20: International Conference on Management of Data
dc.relation.isbasedon	10.1145/3318464.3389748
dc.rights	info:eu-repo/semantics/closedAccess
dc.title	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties
dc.type	Conference Proceeding
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	closed_access	*
dc.date.updated	2020-11-03T01:19:43Z
pubs.publication-status	Published

Abstract:

© 2020 Association for Computing Machinery. In indexing a graph for distance queries, distance labeling is a common practice; in particular, 2-hop labeling which guarantees the exactness of the query results is widely adopted. When it comes to a massive real graph with a relatively large treewidth such as social networks and web graphs, however, 2-hop labeling can hardly be constructed due to the oversized index. This paper discloses the theoretical relationships between the graph treewidth and 2-hop labeling's index size and query time. To scale up distance labeling, this paper proposes Core-Tree (CT) Index to facilitate a critical and effective trade-off between the index size and query time. The reduced index size enables CT-Index to handle massive graphs that no existing approaches can process while the cost in the query time is negligible: the query time is below 0.4 milliseconds on all tested graphs including one graph with 5.5 billion edges.

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

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