An efficient algorithm for predictive continuous nearest neighbor query processing and result maintenance

ABSTRACT

Predictive continuous nearest neighbor queries are concerned with finding the nearest neighbor objects for some future time period according to the current object and query locations and their motion information. Existing continuous query processing algorithms are not efficient enough, requiring multiple dataset lookups to evaluate the query results throughout the duration of a continuous query. More importantly, the complete result for the whole query time interval is only available at the moment when all object motion updates have been examined, based on which adjustment of the query result is made. In this paper, we propose an algorithm which requires only one dataset lookup to deliver a complete predictive result. We then apply a differential update technique to maintain the query results incrementally in the presence of object location and motion updates.

REFERENCES

• 1: Rimantas Benetis , Christian S. Jensen , Gytis Karciauskas , Simonas Saltenis, Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects, Proceedings of the 2002 International Symposium on Database Engineering & Applications, p.44-53, July 17-19, 2002
• 2: Gísli R. Hjaltason , Hanan Samet, Distance browsing in spatial databases, ACM Transactions on Database Systems (TODS), v.24 n.2, p.265-318, June 1999 [doi>10.1145/320248.320255]
• 3: G. S. Iwerks, H. Samet, and K. Smith. Continuous K-Nearest Neighbor Queries for Continuous Moving Points with Updates. In Proc. of VLDB, pages 512--523, 2003.
• 4: Hoda Mokhtar , Jianwen Su , Oscar Ibarra, On moving object queries: (extended abstract), Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543638]
• 5: 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]
• 6: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 7: Simonas Šaltenis , Christian S. Jensen , Scott T. Leutenegger , Mario A. Lopez, Indexing the positions of continuously moving objects, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.331-342, May 15-18, 2000, Dallas, Texas, United States
• 8: 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]
• 9: Y. Tao, D. Papadias, and Q. Shen. Continuous Nearest Neighbor Search. In Proc. of VLDB, pages 287--298, 2002.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Performance

Keywords:
continuous query, location management, mobile computing, nearest neighbor, predictive query processing, query processing