Finding distance-preserving subgraphs in large road networks
Refereed conference paper presented and published in conference proceedings


Times Cited
Altmetrics Information
.

Other information
AbstractGiven two sets of points, S and T, in a road network, G, a distance-preserving subgraph (DPS) query returns a subgraph of G that preserves the shortest path from any point in S to any point in T. DPS queries are important in many real world applications, such as route recommendation systems, logistics planning, and all kinds of shortest-path-related applications that run on resource-limited mobile devices. In this paper, we study efficient algorithms for processing DPS queries in large road networks. Four algorithms are proposed with different tradeoffs in terms of DPS quality and query processing time, and the best one is a graph-partitioning based index, called RoadPart, that finds a high quality DPS with short response time. Extensive experiments on large road networks demonstrate the merits of our algorithms, and verify the efficiency of RoadPart for finding a high-quality DPS. © 2013 IEEE.
All Author(s) ListYan D., Cheng J., Ng W., Liu S.
Name of Conference29th International Conference on Data Engineering, ICDE 2013
Start Date of Conference08/04/2013
End Date of Conference11/04/2013
Place of ConferenceBrisbane, QLD
Country/Region of ConferenceAustralia
Year2013
Month8
Day15
Pages625 - 636
ISBN9781467349086
ISSN1084-4627
LanguagesEnglish-United Kingdom

Last updated on 2020-14-10 at 01:59