research-article

Progressive Top-K Nearest Neighbors Search in Large Road Networks

Authors:

Xuemin LinAuthors Info & Claims

SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data

Pages 1781 - 1795

https://doi.org/10.1145/3318464.3389746

Published: 31 May 2020 Publication History

Abstract

Computing top-k nearest neighbors (kNN) is a fundamental problem in road networks. Existing solutions either need a complicated parameter configuration in index construction or incur high costs when scanning an unbounded number of vertices in query processing. In this paper, we propose a novel parameter-free index-based solution for the kNN query based on the concept of tree decomposition in large road networks. Based on our index structure, we propose an efficient and progressive algorithm that returns each result in a bounded delay. We also optimize the index structure, which improves the efficiency of both index construction and index maintenance in large road networks. We conduct extensive experiments to show the efficiency of our proposed algorithms and the effectiveness of our optimization techniques in real-world road networks from ten regions.

Supplementary Material

MP4 File (3318464.3389746.mp4)

Presentation Video

Download
131.17 MB

References

[1]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to algorithms. MIT press, 2009.

Digital Library

[2]

U. Demiryurek, F. B. Kashani, and C. Shahabi. Efficient continuous nearest neighbor query in spatial networks using euclidean restriction. In Advances in Spatial and Temporal Databases, 11th International Symposium, SSTD 2009, Aalborg, Denmark, July 8--10, 2009, Proceedings, pages 25--43, 2009.

[3]

E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik, 1(1):269--271, 1959.

Digital Library

[4]

R. Geisberger, P. Sanders, D. Schultes, and D. Delling. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In International Workshop on Experimental and Efficient Algorithms, pages 319--333, 2008.

Digital Library

[5]

R. Halin. S-functions for graphs. Journal of geometry, 8(1--2):171--186, 1976.

[6]

D. He, S. Wang, X. Zhou, and R. Cheng. An efficient framework for correctness-aware knn queries on road networks. In ICDE, 2019.

[7]

C. S. Jensen, D. Lin, and B. C. Ooi. Query and update efficient b

[8]

-tree based indexing of moving objects. In (e)Proceedings of the Thirtieth International Conference on Very Large Data Bases, VLDB 2004, Toronto, Canada, August 31 - September 3 2004, pages 768--779, 2004.

[9]

D. S. Johnson, M. Yannakakis, and C. H. Papadimitriou. On generating all maximal independent sets. Information Processing Letters, 27(3):119--123, 1988.

Digital Library

[10]

A. M. Koster, H. L. Bodlaender, and S. P. Van Hoesel. Treewidth: computational experiments. Electronic Notes in Discrete Mathematics, 8:54--57, 2001.

[11]

S. Luo, B. Kao, G. Li, J. Hu, R. Cheng, and Y. Zheng. Toain: a throughput optimizing adaptive index for answering dynamic knn queries on road networks. PVLDB, 11(5):594--606, 2018.

[12]

M. F. Mokbel, X. Xiong, and W. G. Aref. SINA: scalable incremental processing of continuous queries in spatio-temporal databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data, Paris, France, June 13--18, 2004, pages 623--634, 2004.

Digital Library

[13]

K. Mouratidis, S. Bakiras, and D. Papadias. Continuous monitoring of spatial queries in wireless broadcast environments. IEEE Trans. Mob. Comput., 8(10):1297--1311, 2009.

Digital Library

[14]

D. Ouyang, L. Qin, L. Chang, X. Lin, Y. Zhang, and Q. Zhu. When hierarchy meets 2-hop-labeling: efficient shortest distance queries on road networks. In SIGMOD, pages 709--724, 2018.

Digital Library

[15]

N. Robertson and P. D. Seymour. Graph minors. iii. planar tree-width. Journal of Combinatorial Theory, Series B, 36(1):49--64, 1984.

[16]

S. Saltenis. Indexing the positions of continuously moving objects. In Encyclopedia of GIS., pages 538--543. 2008.

[17]

B. Shen, Y. Zhao, G. Li, W. Zheng, Y. Qin, B. Yuan, and Y. Rao. V-tree: Efficient knn search on moving objects with road-network constraints. In ICDE, pages 609--620, 2017.

[18]

D. Sidlauskas, S. Saltenis, and C. S. Jensen. Parallel main-memory indexing for moving-object query and update workloads. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2012, Scottsdale, AZ, USA, May 20--24, 2012, pages 37--48, 2012.

Digital Library

[19]

F. Wei. Tedi: efficient shortest path query answering on graphs. In Graph Data Management: Techniques and Applications, pages 214--238. 2012.

[20]

X. Xiong, M. F. Mokbel, and W. G. Aref. SEA-CNN: scalable processing of continuous k-nearest neighbor queries in spatio-temporal databases. In Proceedings of the 21st International Conference on Data Engineering, ICDE 2005, 5--8 April 2005, Tokyo, Japan, pages 643--654, 2005.

[21]

X. Yu, K. Q. Pu, and N. Koudas. Monitoring k-nearest neighbor queries over moving objects. In Proceedings of the 21st International Conference on Data Engineering, ICDE 2005, 5--8 April 2005, Tokyo, Japan, pages 631--642, 2005.

[22]

B. Zheng, J. Xu, W. Lee, and D. L. Lee. Grid-partition index: a hybrid method for nearest-neighbor queries in wireless location-based services. VLDB J., 15(1):21--39, 2006.

Digital Library

[23]

R. Zhong, G. Li, K. Tan, L. Zhou, and Z. Gong. G-tree: An efficient and scalable index for spatial search on road networks. IEEE Trans. Knowl. Data Eng., 27(8):2175--2189, 2015.

Digital Library

Cited By

Feng QZhang JZhang WQin LZhang YLin X(2024) Efficient k NN Search in Public Transportation Networks Proceedings of the VLDB Endowment10.14778/3681954.368200917:11(3402-3414)Online publication date: 30-Aug-2024
https://doi.org/10.14778/3681954.3682009
Song ZGu YSun QLi TZhang YLi YJensen CYu G(2024)DynaHB: A Communication-Avoiding Asynchronous Distributed Framework with Hybrid Batches for Dynamic GNN TrainingProceedings of the VLDB Endowment10.14778/3681954.368200817:11(3388-3401)Online publication date: 30-Aug-2024
https://doi.org/10.14778/3681954.3682008
Chan TZang RZhu BU LWu DXu J(2024)LION: Fast and High-Resolution Network Kernel Density VisualizationProceedings of the VLDB Endowment10.14778/3648160.364816817:6(1255-1268)Online publication date: 3-May-2024
https://doi.org/10.14778/3648160.3648168
Show More Cited By

Index Terms

Progressive Top-K Nearest Neighbors Search in Large Road Networks
1. Information systems
  1. Information systems applications
    1. Data mining
      1. Nearest-neighbor search
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Dynamic graph algorithms
      2. Shortest paths
    2. Streaming, sublinear and near linear time algorithms
      1. Nearest neighbor algorithms

Recommendations

Search K Nearest Neighbors on Air
MDM '03: Proceedings of the 4th International Conference on Mobile Data Management

While the K-Nearest-Neighbor (KNN) problem is well studied in the traditional wired, disk-based client-server environment, it has not been tackled in a wireless broadcast environment. In this paper, the problem of organizing location dependent data and ...
Finding nearest neighbors in road networks: a tree decomposition method
EDBT '13: Proceedings of the Joint EDBT/ICDT 2013 Workshops

Finding k Nearest Neighbors in one category of POIs (point of interests) belongs to the most frequently issued queries in the navigating systems or online maps. This problem can be formulated as given a graph G(V, E), a vertex u and S ⊆ V, finding k ...
Nearest neighbours search using the PM-Tree
DASFAA'05: Proceedings of the 10th international conference on Database Systems for Advanced Applications

We introduce a method of searching the k nearest neighbours (k-NN) using PM-tree. The PM-tree is a metric access method for similarity search in large multimedia databases. As an extension of M-tree, the structure of PM-tree exploits local dynamic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data

June 2020

2925 pages

ISBN:9781450367356

DOI:10.1145/3318464

General Chairs:
David Maier
Portland State University, USA
,
Rachel Pottinger
University of British Columbia, Canada
,
Program Chairs:
AnHai Doan
University of Wisconsin, USA
,
Wang-Chiew Tan
Megagon Labs, USA
,
Publications Chairs:
Abdussalam Alawini
University of Illinois at Urbana-Champaign, USA
,
Hung Q. Ngo
RelationalAI, USA

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 May 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Key Research and Development Program of China Stem Cell and Translational Research
Australian Research Council
Search Results Web results National Natural Science Foundation

Conference

SIGMOD/PODS '20

Sponsor:

SIGMOD

SIGMOD/PODS '20: International Conference on Management of Data

June 14 - 19, 2020

OR, Portland, USA

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
939
Total Downloads

Downloads (Last 12 months)143
Downloads (Last 6 weeks)12

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Feng QZhang JZhang WQin LZhang YLin X(2024) Efficient k NN Search in Public Transportation Networks Proceedings of the VLDB Endowment10.14778/3681954.368200917:11(3402-3414)Online publication date: 30-Aug-2024
https://doi.org/10.14778/3681954.3682009
Song ZGu YSun QLi TZhang YLi YJensen CYu G(2024)DynaHB: A Communication-Avoiding Asynchronous Distributed Framework with Hybrid Batches for Dynamic GNN TrainingProceedings of the VLDB Endowment10.14778/3681954.368200817:11(3388-3401)Online publication date: 30-Aug-2024
https://doi.org/10.14778/3681954.3682008
Chan TZang RZhu BU LWu DXu J(2024)LION: Fast and High-Resolution Network Kernel Density VisualizationProceedings of the VLDB Endowment10.14778/3648160.364816817:6(1255-1268)Online publication date: 3-May-2024
https://doi.org/10.14778/3648160.3648168
Gong QChen HCao HLiu J(2024)Backbone Index and GNN Models for Skyline Path Query Evaluation over Multi-cost Road NetworksACM Transactions on Spatial Algorithms and Systems10.1145/366063210:4(1-45)Online publication date: 23-Apr-2024
https://dl.acm.org/doi/10.1145/3660632
Yu ZYu XZhou TChen YLiu YLi B(2024)ODIN: Object Density Aware Index for C k NN Queries Over Moving Objects on Road NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.334466236:11(6758-6772)Online publication date: Nov-2024
https://doi.org/10.1109/TKDE.2023.3344662
Hu MChen LChen GMu YDeng R(2024)A Pruned Pendant Vertex Based Index for Shortest Distance Query Under Structured Encrypted GraphIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.341415619(6351-6363)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3414156
Zhu RJia YYang XZheng BWang BZong C(2024)Multiple Continuous Top-K Queries Over Data Stream2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00129(1575-1588)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00129
Jiang WNing BLi GBai MJia XWei F(2024)Graph-decomposed k-NN searching algorithm on road networkFrontiers of Computer Science10.1007/s11704-023-3626-318:3Online publication date: 8-Feb-2024
https://doi.org/10.1007/s11704-023-3626-3
Jiang WLi GBai MNing BWang XWei F(2023)Graph-Indexed kNN Query Optimization on Road NetworkElectronics10.3390/electronics1221453612:21(4536)Online publication date: 3-Nov-2023
https://doi.org/10.3390/electronics12214536
Li WCai MGao MWen DQin LWang W(2023)Expanding Reverse Nearest NeighborsProceedings of the VLDB Endowment10.14778/3636218.363622017:4(630-642)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.14778/3636218.3636220
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents