Christian S. Jensen
Jan Kolářvr
Torben Bach Pedersen
ABSTRACT
With wireless communications and geo-positioning being widely available, it becomes possible to offer new e-services that provide mobile users with information about other mobile objects. This paper concerns active, ordered k-nearest neighbor queries for query and data objects that are moving in road networks. Such queries may be of use in many services.Specifically, we present an easily implementable data model that serves well as a foundation for such queries. We also present the design of a prototype system that implements the queries based on the data model. The algorithm used for the nearest neighbor search in the prototype is presented in detail. In addition, the paper reports on results from experiments with the prototype system.
- J. A$#241;ez, T. de la Barra, and B. Pérez. Dual Graph Representation of Transport Networks. Transportation Research 30(3):209--216, 1996.]]Google Scholar
- R. Benetis, C. S. Jensen, G. Karčiauskas, and S. Šaltenis. Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects. In Proc. IDEAS, pp. 44--53, 2002.]] Google ScholarDigital Library
- T. Brinkhoff. A Framework for Generating Network-Based Moving Objects. Geoinformatica 6(2):153-180, 2002.]] Google ScholarDigital Library
- K. L. Cheung and A. W. Fu. Enhanced Nearest Neighbour Search on the R-tree. SIGMOD Record 27(3):16-21, 1998.]] Google ScholarDigital Library
- H. D. Chon, D. Agrawal, and A. El Abbadi. FATES: Finding A Time dEpendent Shortest path. In Proc. MDM pp. 165--180, 2003.]] Google ScholarDigital Library
- E. W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik 1:269--271, 1959.]]Google ScholarDigital Library
- R. H. Güuting et al. A Foundation for Representing and Querying Moving Objects. ACM TODS 25(1):1--42, 2000.]] Google ScholarDigital Library
- K. Johnston, J. M. Ver Hoef, and K. Krivoruchko. Using ArcGIS Geostatistical Analyst. ESRI Press, 316 pp., 2001.]]Google Scholar
- D. E. Knuth. Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley Pub Co, 780 pp., 1998.]] Google ScholarDigital Library
- C. Murray. Oracle Spatial User Guide and Reference, Release 9.2. Oracle Corporation, 486 pp., 2002.]]Google Scholar
- D. Papadias, J. Zhang, N. Mamoulis, and Y. Tao. Query Processing in Spatial Network Databases. In Proc. VLDB 2003.]]Google ScholarDigital Library
- C. Shahabi, M. R. Kolahdouzan, and M. Sharifzadeh. A Road Network Embedding Technique for K-Nearest Neighbor Search in Moving Object Databases. In Proc. ACM GIS pp. 94--100, 2002.]] Google ScholarDigital Library
- Z. Song and N. Roussopoulos. K-Nearest Neighbor Search for Moving Query Point. In Proc. SSTD, pp. 79--96, 2001.]] Google ScholarDigital Library
- Y. Tao, D. Papadias, and Q. Shen. Continuous Nearest Neighbor Search. In Proc. VLDB, pp. 287--298, 2002.]]Google ScholarDigital Library
- O. Wolfson et al. Databases for Tracking Mobile Units in Real Time. In Proc. ICDT pp. 169--186, 1999.]] Google ScholarDigital Library
- B. Zheng, W.-C. Lee, and D. L. Lee. Search K Nearest Neighbors on Air. In Proc. MDM pp. 181--195, 2003.]] Google ScholarDigital Library
Index Terms
- Nearest neighbor queries in road networks
Recommendations
Ranked Reverse Nearest Neighbor Search
Given a set of data points P and a query point q in a multidimensional space, Reverse Nearest Neighbor (RNN) query finds data points in P whose nearest neighbors are q. Reverse k-Nearest Neighbor (RkNN) query (where k ≥ 1) generalizes RNN query to find ...
Probabilistic Group Nearest Neighbor Queries in Uncertain Databases
The importance of query processing over uncertain data has recently arisen due to its wide usage in many real-world applications. In the context of uncertain databases, previous work have studied many query types such as nearest neighbor query, range ...
Adaptive nearest neighbor queries in travel time networks
GIS '05: Proceedings of the 13th annual ACM international workshop on Geographic information systemsNearest neighbor (NN) searches represent an important class of queries in geographic information systems (GIS). Most nearest neighbor algorithms rely on static distance information to compute NN queries (e.g., Euclidean distance or spatial network ...
Comments