Efficient KNN processing over moving objects with uncertain velocity

ABSTRACT

Spatio-temporal databases aim at combining the spatial and temporal characteristics of data. The continuous K-Nearest Neighbor (CKNN) query is an important type of spatio-temporal query that finds the K-Nearest Neighbors (KNNs) of a moving query object at each time instant within a given time interval [t_s, t_e]. In this paper, we investigate how to process a CKNN query efficiently under the situation that each object moves with an uncertain velocity. This uncertainty on the velocity of each object inevitably results in high complexity of the CKNN problem. We propose a cost-effective PKNN algorithm to tackle the complicated problem incurred by this uncertainty.

REFERENCES

• 1: Glenn S. Iwerks , Hanan Samet , Ken Smith, Continuous K-nearest neighbor queries for continuously moving points with updates, Proceedings of the 29th international conference on Very large data bases, p.512-523, September 09-12, 2003, Berlin, Germany
• 2: Kyriakos Mouratidis , Dimitris Papadias , Marios Hadjieleftheriou, Conceptual partitioning: an efficient method for continuous nearest neighbor monitoring, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066230]
• 3: K. Raptopoulou , A. N. Papadopoulos , Y. Manolopoulos, Fast Nearest-Neighbor Query Processing in Moving-Object Databases, Geoinformatica, v.7 n.2, p.113-137, June 2003 [doi>10.1023/A:1023403908170]
• 4: Zhexuan Song , Nick Roussopoulos, K-Nearest Neighbor Search for Moving Query Point, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.79-96, July 12-15, 2001
• 5: Yufei Tao , Dimitris Papadias, Time-parameterized queries in spatio-temporal databases, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564730]
• 6: Yufei Tao , Dimitris Papadias , Qiongmao Shen, Continuous nearest neighbor search, Proceedings of the 28th international conference on Very Large Data Bases, p.287-298, August 20-23, 2002, Hong Kong, China
• 7: Xiaopeng Xiong , Mohamed F. Mokbel , Walid G. Aref, SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatio-temporal Databases, Proceedings of the 21st International Conference on Data Engineering, p.643-654, April 05-08, 2005 [doi>10.1109/ICDE.2005.128]
• 8: Xiaohui Yu , Ken Q. Pu , Nick Koudas, Monitoring k-Nearest Neighbor Queries over Moving Objects, Proceedings of the 21st International Conference on Data Engineering, p.631-642, April 05-08, 2005 [doi>10.1109/ICDE.2005.92]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Algorithms

Keywords:
K-nearest neighbors, continuous K-nearest neighbor query, moving objects, spatio-temporal databases