Indexing the past, present, and anticipated future positions of moving objects

ABSTRACT

With the proliferation of wireless communications and geo-positioning, e-services are envisioned that exploit the positions of a set of continuously moving users to provide context-aware functionality to each individual user. Because advances in disk capacities continue to outperform Moore's Law, it becomes increasingly feasible to store online all the position information obtained from the moving e-service users. With the much slower advances in I/O speeds and many concurrent users, indexing techniques are of the essence in this scenario.Existing indexing techniques come in two forms. Some techniques capture the position of an object up until the time of the most recent position sample, while other techniques represent an object's position as a constant or linear function of time and capture the position from the current time and into the (near) future. This article offers an indexing technique capable of capturing the positions of moving objects at all points in time. The index substantially modifies partial persistence techniques, which support transaction time, to support valid time for monitoring applications. The performance of a timeslice query is independent of the number of past position samples stored for an object. No existing indices exist with these characteristics.

REFERENCES

• 1: Pankaj K. Agarwal , Lars Arge , Jeff Erickson, Indexing moving points (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.175-186, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335220]
• 2: Pankaj K. Agarwal , Sariel Hal-Peled, Maintaining approximate extent measures of moving points, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.148-157, January 07-09, 2001, Washington, D.C., United States
• 3: Julien Basch , Leonidas J. Guibas , John Hershberger, Data structures for mobile data, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.747-756, January 05-07, 1997, New Orleans, Louisiana, United States
• 4: Bruno Becker , Stephan Gschwind , Thomas Ohler , Bernhard Seeger , Peter Widmayer, An asymptotically optimal multiversion B-tree, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.4, p.264-275, December 1996 [doi>10.1007/s007780050028]
• 5: 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
• 6: 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]
• 7: Cai, M. and Revesz, P. Z. 2000. Parametric R-tree: An index structure for moving objects. In Proceedings of the 10th International Conference on Management of Data (COMAD).
• 8: Chakka, V. P., Everspaugh, A., and Patel, J. M. 2003. Indexing large trajectory data sets with SETI. In Online Proceedings of the 1st Biennial Conference on Innovative Data Systems Research (CIDR).
• 9: Hae Don Chon , Divyakant Agrawal , Amr El Abbadi, Query Processing for Moving Objects with Space-Time Grid Storage Model, Proceedings of the Third International Conference on Mobile Data Management, p.121, January 08-11, 2002
• 10: Čivilis, A., Jensen, C. S., Nenortaitė, J., and Pakalnis, S. 2004. Efficient tracking of moving objects with precision guarantees. In Proceedings of the 1st International Conference on Mobile and Ubiquitous Systems: Networking and Services. 164--173.
• 11: Alminas Civilis , Christian S. Jensen , Stardas Pakalnis, Techniques for Efficient Road-Network-Based Tracking of Moving Objects, IEEE Transactions on Knowledge and Data Engineering, v.17 n.5, p.698-712, May 2005 [doi>10.1109/TKDE.2005.80]
• 12: James R. Driscoll , Neil Sarnak , Daniel D. Sleator , Robert E. Tarjan, Making data structures persistent, Journal of Computer and System Sciences, v.38 n.1, p.86-124, February 1989 [doi>10.1016/0022-0000(89)90034-2]
• 13: Marios Hadjieleftheriou , George Kollios , Vassilis J. Tsotras , Dimitrios Gunopulos, Efficient Indexing of Spatiotemporal Objects, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.251-268, March 25-27, 2002
• 14: Jensen, C. S., Lin, D., and Ooi, B. C. 2004. Query and update efficient B+-tree based indexing of moving objects. In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB). 768--779.
• 15: Theodore Johnson , Dennis Shasha, B-trees with inserts and deletes: why free-at-empty is better than merge-at-half, Journal of Computer and System Sciences, v.47 n.1, p.45-76, Aug. 1993
• 16: 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]
• 17: George Kollios , Vassilis J. Tsotras , Dimitrios Gunopulos , Alex Delis , Marios Hadjieleftheriou, Indexing Animated Objects Using Spatiotemporal Access Methods, IEEE Transactions on Knowledge and Data Engineering, v.13 n.5, p.758-777, September 2001 [doi>10.1109/69.956099]
• 18: Curtis P. Kolovson , Michael Stonebraker, Segment indexes: dynamic indexing techniques for multi-dimensional interval data, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.138-147, May 29-31, 1991, Denver, Colorado, United States
• 19: Anil Kumar , Vassilis J. Tsotras , Christos Faloutsos, Designing Access Methods for Bitemporal Databases, IEEE Transactions on Knowledge and Data Engineering, v.10 n.1, p.1-20, January 1998 [doi>10.1109/69.667079]
• 20: Dan Lin , Christian S. Jensen , Beng Chin Ooi , Simonas Šaltenis, Efficient indexing of the historical, present, and future positions of moving objects, Proceedings of the 6th international conference on Mobile data management, May 09-13, 2005, Ayia Napa, Cyprus [doi>10.1145/1071246.1071256]
• 21: David B. Lomet, Grow and Post Index Trees: Roles, Techniques and Future Potential, Proceedings of the Second International Symposium on Advances in Spatial Databases, p.183-206, August 28-30, 1991
• 22: Dimitris Papadopoulos , George Kollios , Dimitrios Gunopulos , Vassilis J. Tsotras, Indexing Mobile Objects on the Plane, Proceedings of the 13th International Workshop on Database and Expert Systems Applications, p.693-697, September 02-06, 2002
• 23: 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]
• 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: Kriengkrai Porkaew , Iosif Lazaridis , Sharad Mehrotra, Querying Mobile Objects in Spatio-Temporal Databases, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.59-78, July 12-15, 2001
• 26: Cecilia Magdalena Procopiuc , Pankaj K. Agarwal , Sariel Har-Peled, STAR-Tree: An Efficient Self-Adjusting Index for Moving Objects, Revised Papers from the 4th International Workshop on Algorithm Engineering and Experiments, p.178-193, January 04-05, 2002
• 27: 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
• 28: Indexing of Moving Objects for Location-Based Services, Proceedings of the 18th International Conference on Data Engineering, p.463, February 26-March 01, 2002
• 29: A. Prasad Sistla , Ouri Wolfson , Sam Chamberlain , Son Dao, Modeling and Querying Moving Objects, Proceedings of the Thirteenth International Conference on Data Engineering, p.422-432, April 07-11, 1997
• 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, 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: Jimeng Sun , Dimitris Papadias , Yufei Tao , Bin Liu, Querying about the Past, the Present, and the Future in Spatio-Temporal Databases, Proceedings of the 20th International Conference on Data Engineering, p.202, March 30-April 02, 2004
• 33: 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
• 34: Tao. Y., Papadias, D., and Sun, J. 2003. The TPR*-tree: An optimized spatio-temporal access method for predictive queries. In Proceedings of the 29th International Conference on Very Large Data Bases (VLDB). 790--801.
• 35: Yufei Tao , Dimitris Papadias , Jun Zhang, Cost models for overlapping and multiversion structures, ACM Transactions on Database Systems (TODS), v.27 n.3, p.299-342, September 2002 [doi>10.1145/581751.581754]
• 36: Tayeb, J., Ulusoy, Ö., and Wolfson, O. 1998. A quadtree based dynamic attribute indexing method. Computer J. 41, 3, 185--200.
• 37: Jochen Van den Bercken , Bernhard Seeger, Query Processing Techniques for Multiversion Access Methods, Proceedings of the 22th International Conference on Very Large Data Bases, p.168-179, September 03-06, 1996
• 38: Ouri Wolfson , Bo Xu , Sam Chamberlain , Liqin Jiang, Moving Objects Databases: Issues and Solutions, Proceedings of the 10th International Conference on Scientific and Statistical Database Management, p.111-122, July 01-03, 1998 [doi>10.1109/SSDM.1998.688116]
• 39: Ouri Wolfson , Sam Chamberlain , Son Dao , Liqin Jiang , Gisela Mendez, Cost and Imprecision in Modeling the Position of Moving Objects, Proceedings of the Fourteenth International Conference on Data Engineering, p.588-596, February 23-27, 1998
• 40: Ouri Wolfson , A. Prasad Sistla , Sam Chamberlain , Yelena Yesha, Updating and Querying Databases that Track Mobile Units, Distributed and Parallel Databases, v.7 n.3, p.257-387, July 1999 [doi>10.1023/A:1008782710752]
• 41: Yao, A. C.-C. 1978. On random 2-3 trees. Acta Inf. 9, 2, 159--170.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

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

General Terms:
Algorithms, Performance

Keywords:
Continuous variable, indexing, moving object, polyline, querying, trajectory, update