Partition-based lazy updates for continuous queries over moving objects

ABSTRACT

Continuous spatial queries posted within an environment of moving objects produce as their results a time-varying set of objects. In the most ambitious case both queries and data objects are dynamic, making it very challenging to find an efficient query evaluation strategy. The significant overhead related to frequent location updates from moving objects often results in poor performance. The most advanced existing techniques use the concept of simple geometric safe regions to delay or avoid location updates. We introduce a Partition-based Lazy Update (PLU) algorithm that elevates this idea further by adopting Location Information Tables (LIT) which (a) allow each moving object to estimate possible query movements and issue a location update only when it may affect any query results and (b) enable smart server probing that results in fewer messages. Among the significant advantages, our technique performs well even in very highly dynamic environments (with up to 100% mobility) where many other techniques deteriorate. PLU can be efficiently implemented and we demonstrate its query performance improvement of up to 28% over the current state-of-the-art.

REFERENCES

• 1: Ying Cai , Kien A. Hua , Guohong Cao , Toby Xu, Real-Time Processing of Range-Monitoring Queries in Heterogeneous Mobile Databases, IEEE Transactions on Mobile Computing, v.5 n.7, p.931-942, July 2006 [doi>10.1109/TMC.2006.105]
• 2: Reynold Cheng , Kam-Yiu Lam , Sunil Prabhakar , Biyu Liang, An efficient location update mechanism for continuous queries over moving objects, Information Systems, v.32 n.4, p.593-620, June, 2007 [doi>10.1016/j.is.2006.03.002]
• 3: Bugra Gedik and Ling Liu. MobiEyes: Distributed Processing of Continuously Moving Queries on Moving Objects in a Mobile System. In EDBT, 2004.
• 4: Haibo Hu , Jianliang Xu , Dik Lun Lee, A generic framework for monitoring continuous spatial queries over moving objects, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066212]
• 5: Christian S. Jensen , Dan Lin , Beng Chin Ooi, Query and update efficient B⁺-tree based indexing of moving objects, Proceedings of the Thirtieth international conference on Very large data bases, p.768-779, August 31-September 03, 2004, Toronto, Canada
• 6: Andrew Bruce Mcdonald , Taieb Zanati, A mobility-based framework for adaptive dynamic cluster-based hybrid routing in wireless ad hoc networks, University of Pittsburgh, Pittsburgh, PA, 2000
• 7: Mohamed F. Mokbel , Xiaopeing Xiong , Walid G. Aref, SINA: scalable incremental processing of continuous queries in spatio-temporal databases, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007638]
• 8: 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]
• 9: Sunil Prabhakar , Yuni Xia , Dmitri V. Kalashnikov , Walid G. Aref , Susanne E. Hambrusch, Query Indexing and Velocity Constrained Indexing: Scalable Techniques for Continuous Queries on Moving Objects, IEEE Transactions on Computers, v.51 n.10, p.1124-1140, October 2002 [doi>10.1109/TC.2002.1039840]
• 10: 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
• 11: Yufei Tao , Dimitris Papadias , Jimeng Sun, The TPR*-tree: an optimized spatio-temporal access method for predictive queries, Proceedings of the 29th international conference on Very large data bases, p.790-801, September 09-12, 2003, Berlin, Germany
• 12: 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]
• 13: Xiaopeng Xiong , Mohamed F. Mokbel , Walid G. Aref, LUGrid: Update-tolerant Grid-based Indexing for Moving Objects, Proceedings of the 7th International Conference on Mobile Data Management, p.13, May 10-12, 2006 [doi>10.1109/MDM.2006.102]
• 14: 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.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

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

General Terms:
Algorithms

Keywords:
mobile computing and location-based services