TS2-tree - an efficient similarity based organization for trajectory data

ABSTRACT

The increasingly popular GPS technology and the growing amount of trajectory data it generates create the need for developing applications that efficiently store and query trajectories of moving objects. In this paper we introduce TS2 tree, a novel indexing structure for organizing trajectory data based on similarity between trajectories. TS2 tree provides lower and upper bounds on distance between trajectories, based on which we propose a general framework for effectively answering a wide range of similarity-based trajectory queries such as similarity threshold (ST) query and similarity best fit (SBF) query. The multifold reduction in query computation times and the number of I/O operations is demonstrated through an extensive experimental evaluation.

REFERENCES

• 1: Petko Bakalov , Marios Hadjieleftheriou , Eamonn Keogh , Vassilis J. Tsotras, Efficient trajectory joins using symbolic representations, Proceedings of the 6th international conference on Mobile data management, May 09-13, 2005, Ayia Napa, Cyprus [doi>10.1145/1071246.1071259]
• 2: 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
• 3: 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 ]
• 4: Bin Lin , Jianwen Su, Shapes based trajectory queries for moving objects, Proceedings of the 13th annual ACM international workshop on Geographic information systems, November 04-05, 2005, Bremen, Germany [doi>10.1145/1097064.1097069]
• 5: Jessica Lin , Eamonn Keogh , Stefano Lonardi , Bill Chiu, A symbolic representation of time series, with implications for streaming algorithms, Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, June 13-13, 2003, San Diego, California [doi>10.1145/882082.882086]
• 6: Yutaka Yanagisawa , Jun-ichi Akahani , Tetsuji Satoh, Shape-Based Similarity Query for Trajectory of Mobile Objects, Proceedings of the 4th International Conference on Mobile Data Management, p.63-77, January 21-24, 2003

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing

General Terms:
Algorithms, Experimentation, Performance

Keywords:
indexing, similarity, trajectory