Towards scalable location-aware services: requirements and research issues

ABSTRACT

The emergence of location-aware services calls for new real time spatio-temporal query processing algorithms that deal with large numbers of mobile objects and queries. Online query response is an important characterization of location-aware services. A delay in the answer to a query gives invalid and obsolete results, simply because moving objects can change their locations before the query responds. To handle large numbers of spatio-temporal queries efficiently, we propose the idea of sharing as a means to achieve scalability. In this paper, we introduce several types of sharing in the context of continuous spatio-temporal queries. Examples of sharing in the context of real-time spatio-temporal database systems include sharing the execution, sharing the underlying space, sharing the sliding time windows, and sharing the objects of interest. We demonstrate how sharing can be integrated into query predicates, e.g., selection and spatial join processing. The goal of this paper is to outline research directions and approaches that will lead to scalable and efficient location-aware services.

REFERENCES

• 1: Swarup Acharya , Michael J. Franklin , Stanley B. Zdonik, Disseminating Updates on Broadcast Disks, Proceedings of the 22th International Conference on Very Large Data Bases, p.354-365, September 03-06, 1996
• 2: W. G. Aref, S. E. Hambrusch, and S. Prabhakar. Pervasive Location Aware Computing Environments (PLACE)http://www.cs.purdue.edu/place/.
• 3: Shivnath Babu , Jennifer Widom, Continuous queries over data streams, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603884]
• 4: 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
• 5: V. P. Chakka, A. Everspaugh, and J. M. Patel. Indexing Large Trajectory Data Sets with SETI. In Proc. of the Conf. on Innovative Data Systems Research, CIDR Asilomar, CA, Jan. 2003.
• 6: Upen S. Chakravarthy , Jack Minker, Multiple Query Processing in Deductive Databases using Query Graphs, Proceedings of the 12th International Conference on Very Large Data Bases, p.384-391, August 25-28, 1986
• 7: S. Chandrasekaran and M. J. Franklin. Streaming Queries over Streaming Data. In VLDB pages 203--214, Hong Kong, 2002.
• 8: J. Chen, D. J. DeWitt, and J. F. Naughton. Design and Evaluation of Alternative Selection Placement Strategies in Optimizing Continuous Queries. In ICDE San Jose, CA, 2002.
• 9: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, ACM SIGMOD Record, v.29 n.2, p.379-390, June 2000
• 10: James Clifford , Curtis Dyreson , Tomás Isakowitz , Christian S. Jensen , Richard Thomas Snodgrass, On the semantics of “now” in databases, ACM Transactions on Database Systems (TODS), v.22 n.2, p.171-214, June 1997 [doi>10.1145/249978.249980]
• 11: C. Faloutsos , S. Roseman, Fractals for secondary key retrieval, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.247-252, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73746]
• 12: 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
• 13: Susanne E. Hambrusch , Chuan-Ming Liu , Walid G. Aref , Sunil Prabhakar, Query Processing in Broadcasted Spatial Index Trees, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.502-521, July 12-15, 2001
• 14: M. A. Hammad, M. J. Franklin, W. G. Aref, and A. K. Elmagarmid. Scheduling for shared window joins over data streams. In VLDB Berlin, Germany, Sept. 2003.
• 15: Chris Carnes , J. B. Park , Albert Vernon, Scalable Trigger Processing, Proceedings of the 15th International Conference on Data Engineering, p.266, March 23-26, 1999
• 16: 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
• 17: Differential evaluation of continual queries, Proceedings of the 16th International Conference on Distributed Computing Systems (ICDCS '96), p.458, May 27-30, 1996
• 18: Ling Liu , Calton Pu , Wei Tang, Continual Queries for Internet Scale Event-Driven Information Delivery, IEEE Transactions on Knowledge and Data Engineering, v.11 n.4, p.610-628, July 1999 [doi>10.1109/69.790816]
• 19: Ling Liu , Calton Pu , Wei Tang , David Buttler , John Biggs , Tong Zhou , Paul Benninghoff , Wei Han , Fenghua Yu, CQ: a personalized update monitoring toolkit, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.547-549, June 01-04, 1998, Seattle, Washington, United States
• 20: Ming-Ling Lo , Chinya V. Ravishankar, Spatial hash-joins, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.247-258, June 04-06, 1996, Montreal, Quebec, Canada
• 21: Samuel Madden , Mehul Shah , Joseph M. Hellerstein , Vijayshankar Raman, Continuously adaptive continuous queries over streams, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564698]
• 22: M. F. Mokbel, T. M. Ghanem, and W. G. Aref. Spatio-temporal Access ethods. IEEE Data Engineering Bulletin 26(2):4--49, June 2003.
• 23: Jignesh M. Patel , David J. DeWitt, Partition based spatial-merge join, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.259-270, June 04-06, 1996, Montreal, Quebec, Canada
• 24: Dieter Pfoser , Christian S. Jensen , Yannis Theodoridis, Novel Approaches in Query Processing for Moving Object Trajectories, Proceedings of the 26th International Conference on Very Large Data Bases, p.395-406, September 10-14, 2000
• 25: 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]
• 26: Prasan Roy , S. Seshadri , S. Sudarshan , Siddhesh Bhobe, Efficient and extensible algorithms for multi query optimization, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.249-260, May 15-18, 2000, Dallas, Texas, United States
• 27: S. Saltenis and C. S. Jensen. Indexing of Moving Objects for Location-Based Services. In ICDE SanJose, CA, Feb. 2002.
• 28: 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
• 29: Timos K. Sellis, Multiple-query optimization, ACM Transactions on Database Systems (TODS), v.13 n.1, p.23-52, March 1988 [doi>10.1145/42201.42203]
• 30: Zhexuan Song , Nick Roussopoulos, Hashing Moving Objects, Proceedings of the Second International Conference on Mobile Data Management, p.161-172, January 08-10, 2001
• 31: 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
• 32: Yufei Tao , Dimitris Papadias, MV3R-Tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries, Proceedings of the 27th International Conference on Very Large Data Bases, p.431-440, September 11-14, 2001
• 33: Y. Tao, D. Papadias, and Q. Shen. Continuous Nearest Neighbor Search. In VLDB pages 287--298,Hong Kong, 2002.
• 34: Y. Tao, D. Papadias, and J. Sun. The TPR*-Tree: An Optimized Spatio-temporal Access Method for Predictive Queries. In VLDB Berlin, Germany, Sept. 2003.
• 35: J. Tayeb, Ö.Ulusoy, and O. Wolfson. A Quadtree-Based Dynamic Attribute Indexing Method. The Computer Journal 41(3):185--200, 1998.
• 36: Douglas Terry , David Goldberg , David Nichols , Brian Oki, Continuous queries over append-only databases, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.321-330, June 02-05, 1992, San Diego, California, United States
• 37: Yuni Xia , Sunil Prabhakar, Q+Rtree: Efficient Indexing for Moving Object Databases, Proceedings of the Eighth International Conference on Database Systems for Advanced Applications, p.175, March 26-28, 2003

INDEX TERMS

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

General Terms:
Design, Performance

Keywords:
location-aware services, moving objects, spatio-temporal databases