A generic framework for monitoring continuous spatial queries over moving objects

ABSTRACT

This paper proposes a generic framework for monitoring continuous spatial queries over moving objects. The framework distinguishes itself from existing work by being the first to address the location update issue and to provide a common interface for monitoring mixed types of queries. Based on the notion of safe region, the client location update strategy is developed based on the queries being monitored. Thus, it significantly reduces the wireless communication and query reevaluation costs required to maintain the up-to-date query results. We propose algorithms for query evaluation/reevaluation and for safe region computation in this framework. Enhancements are also proposed to take advantage of two practical mobility assumptions: maximum speed and steady movement. The experimental results show that our framework substantially outperforms the traditional periodic monitoring scheme in terms of monitoring accuracy and CPU time while achieving a close-to-optimal wireless communication cost. The framework also can scale up to a large monitoring system and is robust under various object mobility patterns.

REFERENCES

• 1: S. Babu and J. Widom. Continuous queries over data streams. In Proc. SIGMOD, 2001.
• 2: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 3: 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
• 4: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 5: Y. Cai, K. A. Hua, and G. Cao. Processing range-monitoring queries on heterogeneous mobile objects. In Proc. Mobile Data Management, 2004.
• 6: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.379-390, May 15-18, 2000, Dallas, Texas, United States
• 7: Hae Don Chon , Divyakant Agrawal , Amr El Abbadi, Range and kNN query processing for moving objects in grid model, Mobile Networks and Applications, v.8 n.4, p.401-412, August 2003 [doi>10.1023/A:1024535730539]
• 8: B. Gedik and L. Liu. MobiEyes: Distributed processing of continuously moving queries on moving objects in a mobile system. In Proc. EDBT, 2004.
• 9: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 10: 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]
• 11: G. S. Iwerks, H. Samet, and K. Smith. Continuous k-nearest neighbor queries for continuously moving points with updates. In Proc. VLDB, 2003.
• 12: G. S. Iwerks, H. Samet, and K. Smith. Maintenance of spatial semijoin queries on moving points. In Proc. VLDB, 2004.
• 13: C. S. Jensen, D. Lin, and B. C. Ooi. Query and update efficient B+-tree based indexing of moving objects. In Proc. VLDB, pages 768--779, 2004.
• 14: Dmitri V. Kalashnikov , Sunil Prabhakar , Susanne E. Hambrusch, Main Memory Evaluation of Monitoring Queries Over Moving Objects, Distributed and Parallel Databases, v.15 n.2, p.117-135, March 2004 [doi>10.1023/B:DAPD.0000013068.25976.88]
• 15: M.-L. Lee, W. Hsu, C. S. Jensen, B. Cui, and K. L. Teo. Supporting frequent updates in R-trees: A bottom-up approach. In VLDB Conference, Berlin, Germany, pages 608--619, 2003.
• 16: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for Ad-Hoc sensor networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060303]
• 17: 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]
• 18: Jignesh M. Patel , Yun Chen , V. Prasad Chakka, STRIPES: an efficient index for predicted trajectories, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007639]
• 19: 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]
• 20: 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]
• 21: 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
• 22: 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
• 23: Yufei Tao , Christos Faloutsos , Dimitris Papadias , Bin Liu, Prediction and indexing of moving objects with unknown motion patterns, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007637]
• 24: Y. Tao, D. Papadias, and Q. Shen. Continuous nearest neighbor search. In Proc. VLDB, 2002.
• 25: Y. Tao, D. Papadias, and J. Sun. The TPR*-tree: An optimized spatio-temporal access method for predictive queries. In Proc. VLDB, 2003.
• 26: 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 (ICDE'05), p.643-654, April 05-08, 2005 [doi>10.1109/ICDE.2005.128]
• 27: Jianliang Xu , Xueyan Tang , Dik Lun Lee, Performance Analysis of Location-Dependent Cache Invalidation Schemes for Mobile Environments, IEEE Transactions on Knowledge and Data Engineering, v.15 n.2, p.474-488, February 2003 [doi>10.1109/TKDE.2003.1185846]
• 28: Xiaohui Yu , Ken Q. Pu , Nick Koudas, Monitoring k-Nearest Neighbor Queries over Moving Objects, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.631-642, April 05-08, 2005 [doi>10.1109/ICDE.2005.92]
• 29: Jun Zhang , Manli Zhu , Dimitris Papadias , Yufei Tao , Dik Lun Lee, Location-based spatial queries, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872812]