Mobile Information Systems · 2005 · 66 citations · 17 references
ComputingComputer ScienceGeoinformaticsComputational GeometryGeographic Information SystemsMobile ComputingMobile Geographic Information SystemsNearest Neighbor SearchShortest Path AlgorithmsSpatial Database SystemsSpatial PartitioningVoronoi DiagramsK-nearest Neighbor SearchK-nearest NeighborsMobile Spatial Query ProcessingNearest Neighbor QueriesShortest PathsSpatial NetworksSpatial Query ProcessingSpatial Search
A frequent type of query in a car navigation system is to find the k nearest neighbors (kNN) of a given query object (e.g., car) using the actual road network maps. With road networks (spatial networks), the distances between objects depend on their network connectivity and it is computationally expensive to compute the distances (e.g., shortest paths) between objects. In this paper, we propose a novel approach to efficiently and accurately evaluate kNN queries in a mobile information system that uses spatial network databases. The approach uses first order Voronoi diagram and Dijkstra′s algorithm. This approach is based on partitioning a large network to small Voronoi regions, and then pre‐computing distances across the regions. By performing across the network computation for only the border points of the neighboring regions, we avoid global pre‐computation between every object‐pair. Our empirical experiments with real‐world data sets show that our proposed solution outperforms approaches that are based on on‐line distance computation by up to one order of magnitude. In addition, our approach has better response times than approaches that are based on pre‐computation.
17
Nick Roussopoulos, Stephen Kelley, F. Vincent · 1995 · 1.4K citations · Full text
Indexing the positions of continuously moving objects
Simonas Šaltenis, Christian S. Jensen, Scott T. Leutenegger et al. · ACM SIGMOD Record · 2000 · 916 citations
Distance browsing in spatial databases
Gı́sli R. Hjaltason, Hanan Samet · ACM Transactions on Database Systems · 1999 · 877 citations · Full text