Time relaxed spatiotemporal trajectory joins

ABSTRACT

Many spatiotemporal applications store moving object data in the form of trajectories. Various recent works have addressed interesting queries on trajectorial data, mainly focusing on range queries and Nearest Neighbor queries. Here we examine another interesting query, the Time Relaxed Spatiotemporal Trajectory Join (TRSTJ) which effectively finds groups of moving objects that have followed similar movements in different times. We first attempt to address the TRSTJ problem using a symbolic representation algorithm, which we have recently proposed for trajectory joins. However we show experimentally that this solution produces false positives that grow rapidly with the increase of the problem size. As a result, it is inefficient for TRSTJ queries as it leads to large query time overhead. In order to improve query performance, we propose two important heuristics that turn the symbolic represenation approach effective for TRSTJ queries. Our first improvement, allows the use of multiple origins when processing strings representing trajectories. The experimental evaluation shows that the multiple-origin approach drastically reduces query performance. We then present a ``divide and conquer'' approach to further reduce false positives through symbolic class separation. The proposed solutions can be combined together, which leads to even better query performance. We present an experimental study revealing the advantages of using these approaches for solving Time Relaxed Spatiotemporal Trajectory Join queries.

REFERENCES

• 1: Spatio-temporal Generators, http://www.cs.ucr.edu/~marioh/generators/index.html
• 2: Walid Aref , Daniel Barbará, Supporting electronic ink databases, Information Systems, v.24 n.4, p.303-326, June 1999 [doi>10.1016/S0306-4379(99)00020-4]
• 3: 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]
• 4: Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Efficient processing of spatial joins using R-trees, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.237-246, May 25-28, 1993, Washington, D.C., United States
• 5: V. P. Chakka, A. Everspaugh, J. M. Patel. Indexing Large Trajectory Data Sets With SETI. In Proc. of Biennial Conference on Innovative Data Systems Research (CIDR), 2003.
• 6: Lei Chen , M. Tamer Özsu , Vincent Oria, Symbolic representation and retrieval of moving object trajectories, Proceedings of the 6th ACM SIGMM international workshop on Multimedia information retrieval, October 15-16, 2004, New York, NY, USA [doi>10.1145/1026711.1026749]
• 7: 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
• 8: 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]
• 9: 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
• 10: Yun-Wu Huang , Ning Jing , Elke A. Rundensteiner, Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations, Proceedings of the 23rd International Conference on Very Large Data Bases, p.396-405, August 25-29, 1997
• 11: Eamonn J. Keogh , Michael J. Pazzani, A Simple Dimensionality Reduction Technique for Fast Similarity Search in Large Time Series Databases, Proceedings of the 4th Pacific-Asia Conference on Knowledge Discovery and Data Mining, Current Issues and New Applications, p.122-133, April 18-20, 2000
• 12: 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]
• 13: Nick Koudas , Kenneth C. Sevcik, Size separation spatial join, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.324-335, May 11-15, 1997, Tucson, Arizona, United States
• 14: 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]
• 15: Ming-Ling Lo , Chinya V. Ravishankar, Spatial joins using seeded trees, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.209-220, May 24-27, 1994, Minneapolis, Minnesota, United States
• 16: M. Nascimento, J. Silva. In Proc. of ACM Symp. on Applied Computing (SAC), 1998.
• 17: D. Papadias, Y. Tao, J. Zhang, N. Mamoulis, Q. Shen, J. Sun. Indexing and Retrieval of Historical Aggregate Information about Moving Objects. IEEE Data Engineering Bulletin, 25(2), June 2002.
• 18: 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
• 19: P. Rigaux, M. Scholl, A. Voisard. Spatial Databases With Application to GIS. Morgan Kaufman, 2001.
• 20: Jochen Schiller , Agnès Voisard, Location Based Services, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 21: J. Shan, D. Zhang, B. Salzberg. On Spatial-Range Closest-Pair Query. In Proc. of Symposium on Advances in Spatial and Temporal Databases (SSTD), pages 252--269, 2003.
• 22: S. Shekhar, S. Chawla. Spatial Databases: A Tour. Prentice Hall, 2003.
• 23: 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
• 24: 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
• 25: Michail Vlachos , Marios Hadjieleftheriou , Dimitrios Gunopulos , Eamonn Keogh, Indexing multi-dimensional time-series with support for multiple distance measures, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956777]
• 26: Dimitrios Gunopoulos, Discovering Similar Multidimensional Trajectories, Proceedings of the 18th International Conference on Data Engineering, p.673, February 26-March 01, 2002
• 27: Byoung-Kee Yi , Christos Faloutsos, Fast Time Sequence Indexing for Arbitrary Lp Norms, Proceedings of the 26th International Conference on Very Large Data Bases, p.385-394, September 10-14, 2000
• 28: Hongjun Zhu , Jianwen Su , Oscar H. Ibarra, Trajectory queries and octagons in moving object databases, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584860]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
indexing, join, trajectory