Abstract
This paper addresses the problem of finding k nearest neighbors for moving query point (we call it k-NNMP). It is an important issue in both mobile computing research and real-life applications. The problem assumes that the query point is not static, as in k-nearest neighbor problem, but varies its position over time. In this paper, four different methods are proposed for solving the problem. Discussion about the parameters affecting the performance of the algorithms is also presented. A sequence of experiments with both synthetic and real point data sets are studied. In the experiments, our algorithms always outperform the existing ones by fetching 70% less disk pages. In some settings, the saving can be as much as one order of magnitude.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Berchtold, B. Ertl, D. Keim, H. Kriegel, and T. Seidl. Fast nearest neighbor search in high-dimensional space. In Proceedings of International Conference on Data Engineering, Orlando, USA, 1998.
U. C. Bereau. Tiger(r) topologically integrated geographic encoding and referencing system, 1998.
S. Chaudhuri and L. Gravona. Evaluating top-k selection queries. In Proceedings of International Conference on Very Large Database, Edinburgh, Scotland, 1999.
A. Corral, Y. Manolopoulos, Y. Theodoridis, and M. Vassilakopoulos. Closest pair queries in spatial databases. In Proceedings of ACM SIGMOD International Conference on Management of Data, Dallas, USA, 2000.
M. de Berg, M. van Dreveld, M. Overmars, and O. Schwarzkop. Computational Geometry: Algorithms and Applications. Springer-Verlag, 1997.
U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy. Advances in Knowledge Discovery and Data Mining. AAAI Press/MIT Press, 1996.
V. Gaede and O. Guenther. Multidimensional access methods. ACM Computer Surveys, 30, 1998.
T. Kanungu, D. Mount, N. Netanyahu, C. Piatko, R. Silverman, and A. Wu. Computing nearest neighbors for moving points and applications to clustering. In Proceedings of 10th ACM-SIAM Symposium on Discrete Algorithms, 1999.
F. Korn, N. Sidiropoulos, C. Faloutsos, E. Siegel, and Z. Protopapas. Fast nearest neighbor search in medical image databases. In Proceedings of International Conference on Very Large Database, Mumbai, India, 1996.
H. Kriegel. S3: Similarity search in cad database systems. In Proceedings of ACM SIGMOD International Conference on Management of Data, Tucson, USA, 1997.
A. Papadopoulos and Y. Manolopoulos. Performance of nearest neighbor queries in r-trees. In Proceedings of International Conference on Database Theory, Delphi, Greece, 1997.
D. Pfoser and C. Jensen. Capturing the uncertainty of moving-object representations. In Proceedings of International Symposium on Large Spatial Databases, 1999.
N. Roussopoulos, S. Kelley, and F. Vincent. Nearest neighbor queries. In Proceedings of ACM SIGMOD International Conference on Management of Data, San Jose, USA, 1995.
T. Seidl and H. Kriegel. Optimal multi-step k-nearest neighbor search. In Proceedings of ACM SIGMOD International Conference on Management of Data, Seattle, USA, 1998.
T. Seidl and H. Kriegel. Efficient user-adaptable similarity search in large multimedia database. In Proceedings of International Conference on Very Large Database, Athens, Greece, Athens.
P. Sistla and O. Wolfson. Research issues in moving objects database. In Proceedings of ACM SIGMOD International Conference on Management of Data, Dallas, USA, 2000.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Song, Z., Roussopoulos, N. (2001). K-Nearest Neighbor Search for Moving Query Point. In: Jensen, C.S., Schneider, M., Seeger, B., Tsotras, V.J. (eds) Advances in Spatial and Temporal Databases. SSTD 2001. Lecture Notes in Computer Science, vol 2121. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47724-1_5
Download citation
DOI: https://doi.org/10.1007/3-540-47724-1_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42301-0
Online ISBN: 978-3-540-47724-2
eBook Packages: Springer Book Archive