Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks**

dc.contributor.authorWang, Ye
dc.contributor.authorWang, Qing
dc.contributor.authorKoehler, Henning
dc.contributor.authorLin, Yu
dc.coverage.spatialVirtual Event China
dc.date.accessioned2024-03-05T02:42:08Z
dc.date.createdJune 20 - 25, 2021
dc.date.issued2021
dc.date.updated2022-10-16T07:26:31Z
dc.description.abstractComputing shortest paths is a fundamental operation in processing graph data. In many real-world applications, discovering shortest paths between two vertices empowers us to make full use of the underlying structure to understand how vertices are related in a graph, e.g. the strength of social ties between individuals in a social network. In this paper, we study the shortest-path-graph problem that aims to efficiently compute a shortest path graph containing exactly all shortest paths between any arbitrary pair of vertices on complex networks. Our goal is to design an exact solution that can scale to graphs with millions or billions of vertices and edges. To achieve high scalability, we propose a novel method, Query-by-Sketch (QbS), which efficiently leverages offline labelling (i.e., precomputed labels) to guide online searching through a fast sketching process that summarizes the important structural aspects of shortest paths in answering shortest-path-graph queries. We theoretically prove the correctness of this method and analyze its computational complexity. To empirically verify the efficiency of QbS, we conduct experiments on 12 real-world datasets, among which the largest dataset has 1.7 billion vertices and 7.8 billion edges. The experimental results show that QbS can answer shortest-path-graph queries in microseconds for million-scale graphs and less than half a second for billion-scale graphs.en_AU
dc.format.mimetypeapplication/pdfen_AU
dc.identifier.isbn978-1-4503-8343-1en_AU
dc.identifier.urihttp://hdl.handle.net/1885/315724
dc.language.isoen_AUen_AU
dc.publisherAssociation for Computing Machinery (ACM)en_AU
dc.relation.ispartofseriesSIGMOD/PODS '21: International Conference on Management of Dataen_AU
dc.rights© 2021 Association for Computing Machinery.en_AU
dc.sourceSIGMOD/PODS '21: Proceedings of the 2021 International Conference on Management of Dataen_AU
dc.subjectShortest pathsen_AU
dc.subjectgraphsen_AU
dc.subject2-hop coveren_AU
dc.subjectdistance labellingen_AU
dc.subjectpruned landmark labellingen_AU
dc.subjectgraph sketchen_AU
dc.subjectbreadth-first searchen_AU
dc.subjectalgorithmsen_AU
dc.titleQuery-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks**en_AU
dc.typeConference paperen_AU
local.bibliographicCitation.lastpage1958en_AU
local.bibliographicCitation.startpage1946en_AU
local.contributor.affiliationWang, Ye, College of Engineering and Computer Science, ANUen_AU
local.contributor.affiliationWang, Qing, College of Engineering and Computer Science, ANUen_AU
local.contributor.affiliationKoehler, Henning, Massey Universityen_AU
local.contributor.affiliationLin, Yu, College of Engineering and Computer Science, ANUen_AU
local.contributor.authoremailu1024708@anu.edu.auen_AU
local.contributor.authoruidWang, Ye, u6717084en_AU
local.contributor.authoruidWang, Qing, u5170295en_AU
local.contributor.authoruidLin, Yu, u1024708en_AU
local.description.embargo2099-12-31
local.description.notesImported from ARIESen_AU
local.description.refereedYes
local.identifier.absfor461305 - Data structures and algorithmsen_AU
local.identifier.ariespublicationa383154xPUB20111en_AU
local.identifier.doi10.1145/3448016.3452826en_AU
local.identifier.scopusID2-s2.0-85108960732
local.identifier.thomsonIDWOS:000747673800152
local.identifier.uidSubmittedBya383154en_AU
local.publisher.urlhttps://dl.acm.org/en_AU
local.type.statusPublished Versionen_AU

Downloads

Original bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
3448016.3452826.pdf
Size:
1.53 MB
Format:
Adobe Portable Document Format
Description:
Back to topicon-arrow-up-solid
 
APRU
IARU
 
edX
Group of Eight Member

Acknowledgement of Country

The Australian National University acknowledges, celebrates and pays our respects to the Ngunnawal and Ngambri people of the Canberra region and to all First Nations Australians on whose traditional lands we meet and work, and whose cultures are among the oldest continuing cultures in human history.


Contact ANUCopyrightDisclaimerPrivacyFreedom of Information

+61 2 6125 5111 The Australian National University, Canberra

TEQSA Provider ID: PRV12002 (Australian University) CRICOS Provider Code: 00120C ABN: 52 234 063 906