Efficient Processing of All Nearest Neighbor Queries in Dynamic Road Networks

Aavash Bhandari, Aziz Hasanov, Muhammad Attique, Hyung-Ju Cho and Tae-Sun Chung
Additional contact information
Aavash Bhandari: Department of Artificial Intelligence, Ajou University, Suwon-Si 16499, Korea
Aziz Hasanov: Department of Computer Engineering, Ajou University, Suwon-Si 16499, Korea
Muhammad Attique: Department of Software, Sejong University, Seoul 05006, Korea
Hyung-Ju Cho: Department of Software, Kyungpook National University, Sangju-Si 37224, Korea
Tae-Sun Chung: Department of Artificial Intelligence, Ajou University, Suwon-Si 16499, Korea

Mathematics, 2021, vol. 9, issue 10, 1-21

Abstract: The increasing trend of GPS-enabled smartphones has led to the tremendous usage of Location-Based Service applications. In the past few years, a significant amount of studies have been conducted to process All nearest neighbor (ANN) queries. An ANN query on a road network extracts and returns all the closest data objects for all query objects. Most of the existing studies on ANN queries are performed either in Euclidean space or static road networks. Moreover, combining the nearest neighbor query and join operation is an expensive procedure because it requires computing the distance between each pair of query objects and data objects. This study considers the problem of processing the ANN queries on a dynamic road network where the weight, i.e., the traveling distance and time varies due to various traffic conditions. To address this problem, a shared execution-based approach called standard clustered loop (SCL) is proposed that allows efficient processing of ANN queries on a dynamic road network. The key concept behind the shared execution technique is to exploit the coherence property of road networks by clustering objects that share common paths and processing the cluster as a single path. In an empirical study, the SCL method achieves significantly better performance than competitive methods and efficiently reduces the computational cost to process ANN queries in various problem settings.

Keywords: all nearest neighbor queries; spatial query processing; spatial road networks; shared execution; graph algorithms (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/10/1137/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/10/1137/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:10:p:1137-:d:556289

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().