GPAC: generic and progressive processing of mobile queries over mobile data

ABSTRACT

This paper introduces a new family of Generic and Progressive algorithms (GPAC, for short) for continuous mobile queries over mobile objects. GPAC provides a general skeleton that can be tuned through a set of methods to behave as various continuous queries (e.g., continuous range queries and continuous k-nearest-neighbor queries). GPAC algorithms aim to provide three goals: (1) Online evaluation through an in-memory processing of the incoming mobile data. (2) Progressive evaluation through employing an incremental evaluation paradigm. (3) Fast query response through employing an anticipation paradigm. Query answer is anticipated and is cached in memory to allow for fast evaluation. GPAC algorithms are encapsulated in physical pipelined query operators. GPAC pipelined operators can be combined with traditional query operators in a query execution plan to support a wide variety of continuous queries. Experimental results based on a real implementation inside a prototype streaming database engine show the efficiency of GPAC operators in providing incremental and fast response for continuous queries.

REFERENCES

• 1: Daniel J. Abadi , Don Carney , Ugur Çetintemel , Mitch Cherniack , Christian Convey , Sangdon Lee , Michael Stonebraker , Nesime Tatbul , Stan Zdonik, Aurora: a new model and architecture for data stream management, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.2, p.120-139, August 2003 [doi>10.1007/s00778-003-0095-z]
• 2: Walid G. Aref , Ihab F. Ilyas, SP-GiST: An Extensible Database Index for Supporting Space Partitioning Trees, Journal of Intelligent Information Systems, v.17 n.2-3, p.215-240, December 2001
• 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: Thomas Brinkhoff, A Framework for Generating Network-Based Moving Objects, Geoinformatica, v.6 n.2, p.153-180, June 2002 [doi>10.1023/A:1015231126594 ]
• 5: S. Chandrasekaran. et. al. TelegraphCQ: Continuous Dataflow Processing for an Uncertain World. In Proceedings of the International Conference of Innovative Innovative Data Systems Research, CIDR, 2003.
• 6: Sirish Chandrasekaran , Michael J. Franklin, PSoup: a system for streaming queries over streaming data, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.2, p.140-156, August 2003 [doi>10.1007/s00778-003-0096-y]
• 7: 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
• 8: B. Gedik and L. Liu. MobiEyes: Distributed Processing of Continuously Moving Queries on Moving Objects in a Mobile System. In Proceedings of the International Conference on Extending Database Technology, EDBT, 2004.
• 9: M. A. Hammad, T. M. Ghanem, W. G. Aref, A. K. Elmagarmid, and M. F. Mokbel. Efficient execution of sliding-window queries over data streams. Technical Report CSD-03-035, Department of Computer Science, Purdue University, 2004.
• 10: M. A. Hammad , M. F. Mokbel , M. H. Ali , W. G. Aref , A. C. Catlin , A. K. Elmagarmid , M. Eltabakh , M. G. Elfeky , T. M. Ghanem , R. Gwadera , I. F. Ilyas , M. Marzouk , X. Xiong, Nile: A Query Processing Engine for Data Streams, Proceedings of the 20th International Conference on Data Engineering, p.851, March 30-April 02, 2004
• 11: Joseph M. Hellerstein , Jeffrey F. Naughton , Avi Pfeffer, Generalized Search Trees for Database Systems, Proceedings of the 21th International Conference on Very Large Data Bases, p.562-573, September 11-15, 1995
• 12: G. S. Iwerks, H. Samet, and K. Smith. Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates. In VLDB, 2003.
• 13: C. S. Jensen, D. Lin, and B. C. Ooi. Query and Update Efficient B+-Tree Based Indexing of Moving Objects. In VLDB, 2004.
• 14: Dongseop Kwon , Sangjun Lee , Sukho Lee, Indexing the Current Positions of Moving Objects Using the Lazy Update R-tree, Proceedings of the Third International Conference on Mobile Data Management, p.113-120, January 08-11, 2002
• 15: Iosif Lazaridis , Kriengkrai Porkaew , Sharad Mehrotra, Dynamic Queries over Mobile Objects, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.269-286, March 25-27, 2002
• 16: M.-L. Lee, W. Hsu, C. S. Jensen, and K. L. Teo. Supporting Frequent Updates in R-Trees: A Bottom-Up Approach. In VLDB, 2003.
• 17: B. Lin and J. Su. On Bulk Loading TPR-Tree. In Mobile Data Management, MDM, 2004.
• 18: Mohamed F. Mokbel , Walid G. Aref , Susanne E. Hambrusch , Sunil Prabhakar, Towards scalable location-aware services: requirements and research issues, Proceedings of the 11th ACM international symposium on Advances in geographic information systems, p.110-117, November 07-08, 2003, New Orleans, Louisiana, USA [doi>10.1145/956676.956691]
• 19: 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]
• 20: M. F. Mokbel, X. Xiong, W. G. Aref, S. Hambrusch, S. Prabhakar, and M. Hammad. PLACE: A Query Processor for Handling Real-time Spatio-temporal Data Streams (Demo). In VLDB, 2004.
• 21: M. F. Mokbel, X. Xiong, M. A. Hammad, and W. G. Aref. Continuous Query Processing of Spatio-temporal Data Streams in PLACE. In STDBM, 2004.
• 22: R. Motwani. et. al. Query Processing, Approximation, and Resource Management in a Data Stream Management System. In Proceedings of the International Conference of Innovative Innovative Data Systems Research, CIDR, 2003.
• 23: T. Nadeem, S. Dashtinezhad, C. Liao, and L. Iftode. Traffic View: A Scalable Traffic Monitoring System. In Mobile Data Management, MDM, 2004.
• 24: Dimitris Papadias , Qiongmao Shen , Yufei Tao , Kyriakos Mouratidis, Group Nearest Neighbor Queries, Proceedings of the 20th International Conference on Data Engineering, p.301, March 30-April 02, 2004
• 25: Hyun Kyoo Park , Jin Hyun Son , Myoung-Ho Kim, An Efficient Spatiotemporal Indexing Method for Moving Objects in Mobile Communication Environments, Proceedings of the 4th International Conference on Mobile Data Management, p.78-91, January 21-24, 2003
• 26: 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]
• 27: 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 ]
• 28: S. Saltenis and C. S. Jensen. Indexing of Moving Objects for Location-Based Services. In ICDE, 2002.
• 29: 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
• 30: 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
• 31: Zhexuan Song , Nick Roussopoulos, SEB-tree: An Approach to Index Continuously Moving Objects, Proceedings of the 4th International Conference on Mobile Data Management, p.340-344, January 21-24, 2003
• 32: 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]
• 33: Y. Tao, D. Papadias, and Q. Shen. Continuous Nearest Neighbor Search. In VLDB, 2002.
• 34: Y. Tao, D. Papadias, and J. Sun. The TPR*-Tree: An Optimized Spatio-temporal Access Method for Predictive Queries. In VLDB, 2003.
• 35: 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]
• 36: Scalable Spatio-temporal Continuous Query Processing for Location-aware Services, Proceedings of the 16th International Conference on Scientific and Statistical Database Management (SSDBM'04), p.317, June 21-23, 2004 [doi>10.1109/SSDBM.2004.61]
• 37: 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]
• 38: Baihua Zheng , Dik Lun Lee, Semantic Caching in Location-Dependent Query Processing, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.97-116, July 12-15, 2001

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

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

General Terms:
Algorithms, Management, Performance

Keywords:
continuous query processing, mobile queries, moving objects, pipelined query operators, spatio-temporal data streams