# Navigating the Maps: Euclidean vs. Road Network Distances in Spatial Queries
## 1 Introduction  
The utilization of spatial data in mobile applications has experienced significant growth, thereby enabling users to search for locations easily, navigate unfamiliar areas, identify transportation routes, employ geomarketing techniques, and model environmental factors [1]. To illustrate, users can search for nearby hospitals using map applications or GPS navigation (Figure 1). To meet users' requirements, spatial databases play a vital role in storing, retrieving, and manipulating spatial data. These databases are designed to operate efficiently and effectively with spatial data, thereby ensuring that users can quickly and accurately retrieve the data. There are two main types of spatial queries: k-nearest neighbors (kNN) and range search. K-nearest neighbors aim to find a specific number of nearest points of interest (POIs) based on the user's location, while range search retrieves objects within a certain distance radius. For instance, if a user searches for the six nearest hospitals, the user's location serves as a query point, and the map application will provideonly six hospitals closest to the query point. On the other hand, range search differs from kNN, as it is limited by distance rather than the number of spatial objects. For example, a user can search for hospitals within a 10 km radius, and the application will return all the hospitals within that range. As the use of map applications continues to increase, spatial databases encounter the challenge of effectively managing a substantial amount of spatial queries. This poses a considerable computational burden in retrieving spatial objects due to the need for the database to measure the distance between the query point and all spatial objects, thus identifying those that align with the user's requirements. This process results in heightened computational costs. The road network distance method is employed to ensure the accuracy of retrieved spatial objects. This method utilizes [PERSON]'s algorithm to find the shortest path based on the actual road distance. The database can accurately retrieve the desired objects by calculating the shortest route from the query point to the POIs. However, using [PERSON]'s algorithm introduces high computational time due to the complexity of finding the shortest distance. The time complexity of [PERSON]'s algorithm for cost functions based on vertices is approximately \(\text{O}(|E|+|V|log|V|)\)[2], where \(E\) represents the set of edges in the graph, and \(V\) represents the set of vertices. Moreover, when dealing with an extensive road network, the calculations required for determining the shortest paths can impose a considerable demand on both time and memory resources [3]. In scenarios such as kNN, where the total number of objects far exceeds k, computing the shortest paths for all objects to identify the k-nearest neighbors becomes impractical [4]. This presents challenges, as it conflicts with the primary objective of the database, which is to enhance the retrieval process by ensuring efficiency and accuracy in data retrieval. The Euclidean distance method is a better choice to address this issue and reduce the computational complexity of retrieving POIs from spatial databases. This method calculates the straight-line distance between the query point and spatial objects without finding the shortest path. As a result, the computational complexity of calculating Euclidean distance is relatively simple, with a constant time complexity of O(1) [2]. Additionally, Open Source Routing Machine (OSRM) has emerged as a high-performance routing service designed for use with geographic data. As an open-source project, OSRM provides routing functionality, thereby allowing users to extract and calculate the shortest or fastest route between locations using [PERSON]'s algorithm. The capabilities of OSRM further enhance the efficiency and accuracy of spatial query processing in spatial databases.