STRIPES: an efficient index for predicted trajectories

ABSTRACT

Moving object databases are required to support queries on a large number of continuously moving objects. A key requirement for indexing methods in this domain is to efficiently support both update and query operations. Previous work on indexing such databases can be broadly divided into categories: indexing the past positions and indexing the future predicted positions. In this paper we focus on an efficient indexing method for indexing the future positions of moving objects.In this paper we propose an indexing method, called STRIPES, which indexes predicted trajectories in a dual transformed space. Trajectories for objects in d-dimensional space become points in a higher-dimensional 2d-space. This dual transformed space is then indexed using a regular hierarchical grid decomposition indexing structure. STRIPES can evaluate a range of queries including time-slice, window, and moving queries. We have carried out extensive experimental evaluation comparing the performance of STRIPES with the best known existing predicted trajectory index (the TPR*-tree), and show that our approach is significantly faster than TPR*-tree for both updates and search queries.

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: 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: Bellman, R. Adaptive Control Processes. Princeton University Press., Princeton, NJ, 1961.
• 4: Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.28-39, September 03-06, 1996
• 5: Kevin S. Beyer , Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft, When Is ''Nearest Neighbor'' Meaningful?, Proceeding of the 7th International Conference on Database Theory, p.217-235, January 10-12, 1999
• 6: Mengchu Cai , Dinesh Keshwani , Peter Z. Revesz, Parametric Rectangles: A Model for Querying and Animation of Spatiotemporal Databases, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.430-444, March 27-31, 2000
• 7: Michael J. Carey , David J. DeWitt , Michael J. Franklin , Nancy E. Hall , Mark L. McAuliffe , Jeffrey F. Naughton , Daniel T. Schuh , Marvin H. Solomon , C. K. Tan , Odysseas G. Tsatalos , Seth J. White , Michael J. Zwilling, Shoring up persistent applications, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.383-394, May 24-27, 1994, Minneapolis, Minnesota, United States
• 8: Chakka, V. P., Everspaugh, A. C. and Patel, J. M., Indexing Large Trajectory Data Sets with SETI. In First Biennial Conf. on Innovative Data Systems Research (CIDR), 2003, 164--175.
• 9: Hae Don Chon , Divyakant Agrawal , Amr El Abbadi, Storage and Retrieval of Moving Objects, Proceedings of the Second International Conference on Mobile Data Management, p.173-184, January 08-10, 2001
• 10: Irene Gargantini, An effective way to represent quadtrees, Communications of the ACM, v.25 n.12, p.905-910, Dec 1982 [doi>10.1145/358728.358741]
• 11: Ralf Hartmut Güting , Michael H. Böhlen , Martin Erwig , Christian S. Jensen , Nikos A. Lorentzos , Markus Schneider , Michalis Vazirgiannis, A foundation for representing and querying moving objects, ACM Transactions on Database Systems (TODS), v.25 n.1, p.1-42, March 2000 [doi>10.1145/352958.352963]
• 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: Gisli R. Hjaltason , Hanan Samet, Speeding up construction of PMR quadtree-based spatial indexes, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.2, p.109-137, October 2002 [doi>10.1007/s00778-002-0067-8]
• 14: H. V. Jagadish, On Indexing Line Segments, Proceedings of the 16th International Conference on Very Large Data Bases, p.614-625, August 13-16, 1990
• 15: 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]
• 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: Lee, M.-L., Hsu, W., Jensen, C. S., Cui, B. and Teo, K. L., Supporting Frequent Updates in R-Trees: A Bottom-Up Approach. In VLDB, 2003, 608--619.
• 18: Scott T. Leutenegger , Mario A. López, The Effect of Buffering on the Performance of R-Trees, IEEE Transactions on Knowledge and Data Engineering, v.12 n.1, p.33-44, January 2000 [doi>10.1109/69.842248]
• 19: Mokbel, M. F., Ghanem, T. M. and Aref, W. G. Spatio-Temporal Access Methods. IEEE Data Engineering Bulletin, 26 (2) 2003, 40--49.
• 20: Mario A. Nascimento , Jefferson R. O. Silva, Towards historical R-trees, Proceedings of the 1998 ACM symposium on Applied Computing, p.235-240, February 27-March 01, 1998, Atlanta, Georgia, United States [doi>10.1145/330560.330692]
• 21: Mario A. Nascimento , Jefferson R. O. Silva , Yannis Theodoridis, Evaluation of Access Structures for Discretely Moving Points, Proceedings of the International Workshop on Spatio-Temporal Database Management, p.171-188, September 10-11, 1999
• 22: Indexing Spatio-Temporal Data Warehouses, Proceedings of the 18th International Conference on Data Engineering, p.166, February 26-March 01, 2002
• 23: 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
• 24: Evaggelia Pitoura , George Samaras, Locating Objects in Mobile Computing, IEEE Transactions on Knowledge and Data Engineering, v.13 n.4, p.571-592, July 2001 [doi>10.1109/69.940733]
• 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: 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]
• 27: 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
• 28: Saltenis, S. and Jensen, C. S., Indexing of Moving Objects for Location-Based Service. 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: Hanan Samet, The Quadtree and Related Hierarchical Data Structures, ACM Computing Surveys (CSUR), v.16 n.2, p.187-260, June 1984 [doi>10.1145/356924.356930]
• 31: Zhexuan Song , Nick Roussopoulos, Hashing Moving Objects, Proceedings of the Second International Conference on Mobile Data Management, p.161-172, January 08-10, 2001
• 32: 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
• 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., The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries. In VLDB, 2003, 790--801.
• 35: Tayeb, J., Ulusoy, O. and Wolfson, O. A Quadtree-based Dynamic Attribute Indexing Method. Computer Journal, 41 (3) 1998, 185--200.
• 36: Theodoridis, Y., Vazirgiannis, M. and Sellis, T. K., Spatio-Temporal Indexing for Large Multimedia Application. In IEEE Intl. Conf. on Multimedia Computing and Systems, 1996, 441--448.
• 37: 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]
• 38: Xu, X., Han, J. and Lu, W., RT-tree: An Improved R-Tree Index Structure for Spatiotemporal Databases. In Intl. Sym. on Spatial Data Handling, 1990, 1040--1049.