Scaling Up Distance Labeling on Graphs with Core-Periphery Properties

Publication Type:
Conference Proceeding
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2020, pp. 1367-1381
Issue Date:
Filename Description Size
SIGMOD_scale.pdfAccepted version1.31 MB
Adobe PDF
Full metadata record
© 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: