Distance labeling: on parallelism, compression, and ordering

Show simple item record

dc.contributor.author Li, Wentao
dc.contributor.author Qiao, Miao
dc.contributor.author Qin, Lu
dc.contributor.author Zhang, Ying
dc.contributor.author Chang, Lijun
dc.contributor.author Lin, Xuemin
dc.date.accessioned 2022-04-14T02:44:19Z
dc.date.available 2022-04-14T02:44:19Z
dc.date.issued 2021-8-31
dc.identifier.citation The VLDB Journal 31(1):129-155 31 Aug 2021
dc.identifier.issn 1066-8888
dc.identifier.uri https://hdl.handle.net/2292/58722
dc.description.abstract Distance labeling approaches are widely adopted to speed up the online performance of shortest-distance queries. The construction of the distance labeling, however, can be exhaustive, especially on big graphs. For a major category of large graphs, small-world networks, the state-of-the-art approach is pruned landmark labeling (PLL). PLL prunes distance labels based on a node order and directly constructs the pruned labels by performing breadth-first searches in the node order. The pruning technique, as well as the index construction, has a strong sequential nature which hinders PLL from being parallelized. It becomes an urgent issue on massive small-world networks whose index can hardly be constructed by a single thread within a reasonable time. This paper first scales distance labeling on small-world networks by proposing a parallel shortest-distance labeling (PSL) scheme. PSL insightfully converts the PLL’s node-order dependency to a shortest-distance dependence, which leads to a propagation-based parallel labeling in D rounds where D denotes the diameter of the graph. To further scale up PSL, it is critical to reduce the index size. This paper proposes effective index compression techniques based on graph properties as well as label properties; it also explores best practices in using betweenness-based node order to reduce the index size. The efficient betweenness estimation of the graph nodes proposed may be of independent interest to graph practitioners. Extensive experimental results verify our efficiency on billion-scale graphs, near-linear speedup in a multi-core environment, and up to 94 % reduction in the index size.
dc.language en
dc.publisher Springer Science and Business Media LLC
dc.relation.ispartofseries The VLDB Journal
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
dc.rights The version of record of this article, first published in The VLDB Journal, is available online at Publisher’s website: http://doi.org/10.1007/s00778-021-00694-1
dc.rights.uri https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
dc.rights.uri https://www.springernature.com/gp/open-research/policies/journal-policies
dc.subject Science & Technology
dc.subject Technology
dc.subject Computer Science, Hardware & Architecture
dc.subject Computer Science, Information Systems
dc.subject Computer Science
dc.subject Shortest distance
dc.subject 2-Hop labeling
dc.subject Betweenness
dc.subject Parallelism
dc.subject Compression
dc.subject Ordering
dc.subject SHORTEST-PATH
dc.subject QUERIES
dc.subject SET
dc.subject 0804 Data Format
dc.subject 0805 Distributed Computing
dc.subject 0806 Information Systems
dc.title Distance labeling: on parallelism, compression, and ordering
dc.type Journal Article
dc.identifier.doi 10.1007/s00778-021-00694-1
pubs.issue 1
pubs.begin-page 129
pubs.volume 31
dc.date.updated 2022-03-14T10:33:52Z
dc.rights.holder Copyright: The author en
pubs.author-url http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000691626000001&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=6e41486220adb198d0efde5a3b153e7d
pubs.end-page 155
pubs.publication-status Published
dc.rights.accessrights http://purl.org/eprint/accessRights/RetrictedAccess en
pubs.subtype Article
pubs.subtype Journal
pubs.elements-id 865912
dc.identifier.eissn 0949-877X
pubs.online-publication-date 2021-8-31

Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace