research-article

Finding nearest neighbors in road networks: a tree decomposition method

Author:

Fang Wei-KleinerAuthors Info & Claims

EDBT '13: Proceedings of the Joint EDBT/ICDT 2013 Workshops

Pages 233 - 240

https://doi.org/10.1145/2457317.2457355

Published: 18 March 2013 Publication History

Get Access

Abstract

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 neighbors of u in S. Classic Dijkstra's algorithm offers an optimal solution if S = V holds, but the performance deteriorates as S is of smaller size. Other approaches such as pre-computing and storing all the shortest distances require too much storage, thus suffer from drawbacks of scalability.

To address these problems, we propose TIkNN (stands for Tree decomposition-based Indexing for kNN), an indexing and query processing scheme for kNN query answering. TIkNN is based on the tree decomposition methodology. The graph is first decomposed into a tree in which each node (a.k.a. bag) contains more than one vertex from graph. The shortest paths are stored in such bags and these local paths together with the tree are the components of the index of the graph. Based on this index, step-wise query processing over the tree can be executed to find the nearest neighbors.

Our experimental results show that TIkNN offers orders-of-magnitude performance improvement over Dijkstra's algorithm on query answering, while the storage requirement for the index structure is relatively small.

References

[1]

T. Akiba, C. Sommer, and K.-i. Kawarabayashi. Shortest-path queries for complex networks: exploiting low tree-width outside the core. In Proceedings of the 15th International Conference on Extending Database Technology, EDBT '12, pages 144--155, New York, NY, USA, 2012. ACM.

Digital Library

Google Scholar

[2]

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

Digital Library

Google Scholar

[3]

G. N. Frederickson. Planar graph decomposition and all pairs shortest paths. J. ACM, 38(1):162--204, Jan. 1991.

Digital Library

Google Scholar

[4]

C. S. Jensen, J. Kolářvr, T. B. Pedersen, and I. Timko. Nearest neighbor queries in road networks. In Proceedings of the 11th ACM international symposium on Advances in geographic information systems, GIS '03, 2003.

Digital Library

Google Scholar

[5]

N. Jing, Y.-W. Huang, and E. A. Rundensteiner. Hierarchical encoded path views for path query processing: An optimal model and its performance evaluation. IEEE Trans. on Knowl. and Data Eng., 10(3):409--432, May 1998.

Digital Library

Google Scholar

[6]

D. Papadias, J. Zhang, N. Mamoulis, and Y. Tao. Query processing in spatial network databases. In Proceedings of the 29th international conference on Very large data bases - Volume 29, VLDB '03, pages 802--813. VLDB Endowment, 2003.

Digital Library

Google Scholar

[7]

H. Samet, J. Sankaranarayanan, and H. Alborzi. Scalable network distance browsing in spatial databases. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, SIGMOD '08, 2008.

Digital Library

Google Scholar

[8]

P. Sanders and D. Schultes. Highway hierarchies hasten exact shortest path queries. In Proceedings of the 13th annual European conference on Algorithms, ESA'05, pages 568--579, Berlin, Heidelberg, 2005. Springer-Verlag.

Digital Library

Google Scholar

[9]

P. Sanders and D. Schultes. Engineering fast route planning algorithms. In Proceedings of the 6th international conference on Experimental algorithms, WEA'07, pages 23--36, Berlin, Heidelberg, 2007. Springer-Verlag.

Digital Library

Google Scholar

[10]

S. Shekhar and J. S. Yoo. Processing in-route nearest neighbor queries: a comparison of alternative approaches. In Proceedings of the 11th ACM international symposium on Advances in geographic information systems, GIS '03, 2003.

Digital Library

Google Scholar

[11]

F. Wei. Tedi: efficient shortest path query answering on graphs. In SIGMOD. ACM, 2010.

Digital Library

Google Scholar

[12]

L. Wu, X. Xiao, D. Deng, G. Cong, A. D. Zhu, and S. Zhou. Shortest path and distance queries on road networks: an experimental evaluation. Proc. VLDB Endow., 5(5):406--417, Jan. 2012.

Digital Library

Google Scholar

[13]

F. B. Zhan and C. E. Noon. Shortest path algorithms: An evaluation using real road networks. Transportation Science, 32(1):65--73, Jan. 1998.

Digital Library

Google Scholar

Cited By

View all

Yang YLi HWang JHu QWang XLeng MXu J(2019)A Novel Index Method for K Nearest Object Query over Time-Dependent Road NetworksComplexity10.1155/2019/48291642019Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1155/2019/4829164
Sato HNakayama Y(2018)Multi-criteria based Geographical Query Processing in Road Networks複数評価尺度に基づく道路網上での地理情報問合せ処理IEEJ Transactions on Electronics, Information and Systems10.1541/ieejeiss.138.1508138:12(1508-1516)Online publication date: 1-Dec-2018
https://doi.org/10.1541/ieejeiss.138.1508
Leng MYang YWang JHu QWang X(2018)Finding the K Nearest Objects over Time Dependent Road NetworksWeb and Big Data10.1007/978-3-319-96893-3_25(334-349)Online publication date: 19-Jul-2018
https://doi.org/10.1007/978-3-319-96893-3_25
Show More Cited By

Index Terms

Finding nearest neighbors in road networks: a tree decomposition method
1. Information systems
  1. Information retrieval

Recommendations

Progressive Top-K Nearest Neighbors Search in Large Road Networks
SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data

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 ...
TEDI: efficient shortest path query answering on graphs
SIGMOD '10: Proceedings of the 2010 ACM SIGMOD International Conference on Management of data

Efficient shortest path query answering in large graphs is enjoying a growing number of applications, such as ranked keyword search in databases, social networks, ontology reasoning and bioinformatics. A shortest path query on a graph finds the shortest ...
Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs

We propose TEDI, an indexing for solving shortest path, and k Nearest Neighbors (kNN) problems. TEDI is based on the tree decomposition methodology. The graph is first decomposed into a tree in which the node contains vertices. The shortest paths are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

EDBT '13: Proceedings of the Joint EDBT/ICDT 2013 Workshops

March 2013

423 pages

ISBN:9781450315999

DOI:10.1145/2457317

General Chair:
Giovanna Guerrini
Università di Genova, Italy

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 March 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EDBT/ICDT '13

EDBT/ICDT '13: Joint 2013 EDBT/ICDT Conferences

March 18 - 22, 2013

Genoa, Italy

Acceptance Rates

EDBT '13 Paper Acceptance Rate 7 of 10 submissions, 70%;

Overall Acceptance Rate 7 of 10 submissions, 70%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
153
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Yang YLi HWang JHu QWang XLeng MXu J(2019)A Novel Index Method for K Nearest Object Query over Time-Dependent Road NetworksComplexity10.1155/2019/48291642019Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1155/2019/4829164
Sato HNakayama Y(2018)Multi-criteria based Geographical Query Processing in Road Networks複数評価尺度に基づく道路網上での地理情報問合せ処理IEEJ Transactions on Electronics, Information and Systems10.1541/ieejeiss.138.1508138:12(1508-1516)Online publication date: 1-Dec-2018
https://doi.org/10.1541/ieejeiss.138.1508
Leng MYang YWang JHu QWang X(2018)Finding the K Nearest Objects over Time Dependent Road NetworksWeb and Big Data10.1007/978-3-319-96893-3_25(334-349)Online publication date: 19-Jul-2018
https://doi.org/10.1007/978-3-319-96893-3_25
Lu CChen A(2017)Finding the Shortest Path with User RequirementsProceedings of the 2017 International Conference on Data Mining, Communications and Information Technology10.1145/3089871.3089894(1-6)Online publication date: 25-May-2017
https://dl.acm.org/doi/10.1145/3089871.3089894

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.

Cited By

Index Terms

Recommendations

Progressive Top-K Nearest Neighbors Search in Large Road Networks

TEDI: efficient shortest path query answering on graphs

Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs