Adaptive location constraint processing

ABSTRACT

An important problem for many location-based applications is the continuous evaluation of proximity relations among moving objects. These relations express whether a given set of objects is in a spatial constellation or in a spatial constellation relative to a given point of demarcation in the environment. We represent proximity relations as location constraints, which resemble standing queries over continuously changing location position information. The challenge lies in the continuous processing of large numbers of location constraints as the location of objects and the constraint load change. In this paper, we propose an adaptive location constraint indexing approach which adapts as the constraint load and movement pattern of the objects change. The approach takes correlations between constraints into account to further reduce processing time. We also introduce a new location update policy that detects constraint matches with fewer location update requests. Our approach stabilizes system performance, avoids oscillation, reduces constraint matching time by 70% for in-memory processing, and reduces secondary storage accesses by 80% for I/O-incurring environments.

REFERENCES

• 1: New and Enhanced Features of FedEx InSight, http://www.fedex.com/us/
• 2: Radio Frequency Identification Systems (RFID), http://www.ti.com/rfid/
• 3: P. K. Agarwal and L. Arge and J. Erickson, Indexing Moving Points, In Proc. ACM PODS, 2000.
• 4: Julien Basch, Kinetic Data Structures, Ph.D. thesis, Stanford University, Computer Science Dept., 1999.
• 5: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 6: Elisa Bertino, Barbara Catania, and Boris Chidlovskii. Indexing Constraint Databases by Using a Dual Representation. In Proc. ICDE, 1999.
• 7: Richard L. Burden and J. Douglas Faires. Numerical analysis. Brooks/Cole Publishing Company, 2000.
• 8: Antonio Corral , Yannis Manolopoulos , Yannis Theodoridis , Michael Vassilakopoulos, Closest pair queries in spatial databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.189-200, May 15-18, 2000, Dallas, Texas, United States
• 9: Haibo Hu, Jianliang Xu, and Dik Lun Lee. A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects. In Proc. ACM SIGMOD, 2005.
• 10: David R. Karger , Matthias Ruhl, Finding nearest neighbors in growth-restricted metrics, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510013]
• 11: George Kollios , Dimitrios Gunopulos , Vassilis J. Tsotras, On indexing mobile objects, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.261-272, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304002]
• 12: Gabriel Kuper, Leonid Libkin, and Jan Paredaens. Constraint databases. Springer Verlag, 2000.
• 13: J. Nievergelt, H. Hinterberger, and K. C. Sevcik. The grid file: An adaptable, symmetric multikey file structure. In ACM Trans. Database systems, 1984.
• 14: 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]
• 15: 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
• 16: 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
• 17: T. K. Sellis, N. Roussopoulos, and C. Faloutsos. The R-Tree: A Dynamic Index for Multi-Dimensional Objects. In The VLDB Journal, 1987.
• 18: A. Amir. A. Efrat. J. Myllymaki. L. Palaniappan. K. Wampler. Buddy tracking - efficient proximity detection among mobile friends. In INFOCOM, 2004.
• 19: Roy Want , Andy Hopper , Veronica Falcão , Jonathan Gibbons, The active badge location system, ACM Transactions on Information Systems (TOIS), v.10 n.1, p.91-102, Jan. 1992 [doi>10.1145/128756.128759]
• 20: E. Welzl. Smallest Enclosing Disks (Balls and Ellipsoids). In New Results and New Trends in Computer Science. Springer, 1991.
• 21: Kun-Lung Wu, Shyh-Kwei Chen, and Philip S. Yu. Efficient Processing of Continual Range Queries for Location-Aware Mobile Services. In Information Systems Frontiers, 2005.
• 22: Z. Xu and H. A. Jacobsen. Evaluating proximity relations under uncertainty. In Proc. ICDE, 2007.
• 23: Z. Xu and H. A. Jacobsen. Efficient constraint processing for highly personalized location based services. In Proc. VLDB04, 2004.
• 24: Zhengdao Xu , Hans-Arno Jacobsen, Efficient constraint processing for location-aware computing, Proceedings of the 6th international conference on Mobile data management, May 09-13, 2005, Ayia Napa, Cyprus [doi>10.1145/1071246.1071248]
• 25: Z. Xu and H. A. Jacobsen. Proximity Relation Processing With Evolving Environment. Technical Report, University of Toronto, www.cs.toronto.edu/~zhengdao/report/CSRG-552.pdf, 2007.
• 26: X. Yu, K. Q. Pu, and N. Koudas. Monitoring k-Nearest Neighbor Queries over Moving Objects. In Proc. ICDE, 2005.
• 27: 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]
• 28: Y. Zhao. Standardization of mobile phone positioning for 3G systems. IEEE Communication Magazine, 2002.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.0 General

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
adaptive indexing, constraint matching, continuous location query, location constraint processing, location query, location update policy, location-based services, moving object indexing, standing query