Indexing spatio-temporal trajectories with Chebyshev polynomials

ABSTRACT

In this paper, we attempt to approximate and index a d- dimensional (d ≥ 1) spatio-temporal trajectory with a low order continuous polynomial. There are many possible ways to choose the polynomial, including (continuous)Fourier transforms, splines, non-linear regressino, etc. Some of these possiblities have indeed been studied beofre. We hypothesize that one of the best possibilities is the polynomial that minimizes the maximum deviation from the true value, which is called the minimax polynomial. Minimax approximation is particularly meaningful for indexing because in a branch-and-bound search (i.e., for finding nearest neighbours), the smaller the maximum deviation, the more pruning opportunities there exist. However, in general, among all the polynomials of the same degree, the optimal minimax polynomial is very hard to compute. However, it has been shown thta the Chebyshev approximation is almost identical to the optimal minimax polynomial, and is easy to compute [16]. Thus, in this paper, we explore how to use the Chebyshev polynomials as a basis for approximating and indexing d-dimenstional trajectories.The key analytic result of this paper is the Lower Bounding Lemma. that is, we show that the Euclidean distance between two d-dimensional trajectories is lower bounded by the weighted Euclidean distance between the two vectors of Chebyshev coefficients. this lemma is not trivial to show, and it ensures that indexing with Chebyshev cofficients aedmits no false negatives. To complement that analystic result, we conducted comprehensive experimental evaluation with real and generated 1-dimensional to 4-dimensional data sets. We compared the proposed schem with the Adaptive Piecewise Constant Approximation (APCA) scheme. Our preliminary results indicate that in all situations we tested, Chebyshev indexing dominates APCA in pruning power, I/O and CPU costs.

REFERENCES

• 1: Rakesh Agrawal , King-Ip Lin , Harpreet S. Sawhney , Kyuseok Shim, Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.490-501, September 11-15, 1995
• 2: D. J. Berndt and J. Clifford. Using dynamic time warping to find patterns in time series. Working Notes of the Knowledge Discovery in Databases Workshop, pp. 359--370, 1994.
• 3: Kaushik Chakrabarti , Sharad Mehrotra, Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces, Proceedings of the 26th International Conference on Very Large Data Bases, p.89-100, September 10-14, 2000
• 4: Efficient Time Series Matching by Wavelets, Proceedings of the 15th International Conference on Data Engineering, p.126, March 23-26, 1999
• 5: Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.419-429, May 24-27, 1994, Minneapolis, Minnesota, United States
• 6: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 7: Dimitrios Gunopulos , Gautam Das, Time series similarity measures and time series indexing (abstract only), Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.624, May 21-24, 2001, Santa Barbara, California, United States
• 8: 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
• 9: Tamer Kahveci , Ambuj K. Singh, Variable Length Queries for Time Series Data, Proceedings of the 17th International Conference on Data Engineering, p.273-282, April 02-06, 2001
• 10: K. V. Ravi Kanth , Divyakant Agrawal , Ambuj Singh, Dimensionality reduction for similarity searching in dynamic databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.166-176, June 01-04, 1998, Seattle, Washington, United States
• 11: Eamonn Keogh , Kaushik Chakrabarti , Michael Pazzani , Sharad Mehrotra, Locally adaptive dimensionality reduction for indexing large time series databases, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.151-162, May 21-24, 2001, Santa Barbara, California, United States
• 12: E. Keogh, K. Chakrabarti, M. Pazzani S. Mehrotra. Dimensionality reduction for fast similarity search in large time series databases. Journal of Knowledge and Information Systems. 2000, pp. 263--286.
• 13: E. Keogh and P. Smyth. A probabilisitc approach to fast pattern matching in time series databases. Proc. 1997 KDD, pp. 20--24.
• 14: 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]
• 15: Flip Korn , H. V. Jagadish , Christos Faloutsos, Efficiently supporting ad hoc queries in large datasets of time sequences, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.289-300, May 11-15, 1997, Tucson, Arizona, United States
• 16: J. C. Mason and D. Handscomb. Chebyshev Polynomials. Chapman & Hall, 2003.
• 17: Landmarks: A New Model for Similarity-Based Pattern Querying in Time Series Databases, Proceedings of the 16th International Conference on Data Engineering, p.33, February 28-March 03, 2000
• 18: Similarity Search Over Time-Series Data Using Wavelets, Proceedings of the 18th International Conference on Data Engineering, p.212, February 26-March 01, 2002
• 19: William H. Press , Brian P. Flannery , Saul A. Teukolsky , William T. Vetterling, Numerical recipes: the art of scientific computing, Cambridge University Press, New York, NY, 1986
• 20: D. Rafiei and A. Mendelzon. Efficient Retrieval of Similar Time Sequences Using DFT. Proc. 1998 FODO.
• 21: 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
• 22: Indexing of Moving Objects for Location-Based Services, Proceedings of the 18th International Conference on Data Engineering, p.463, February 26-March 01, 2002
• 23: Hagit Shatkay , Stanley B. Zdonik, Approximate Queries and Representations for Large Data Sequences, Proceedings of the Twelfth International Conference on Data Engineering, p.536-545, February 26-March 01, 1996
• 24: Dimitrios Gunopoulos, Discovering Similar Multidimensional Trajectories, Proceedings of the 18th International Conference on Data Engineering, p.673, February 26-March 01, 2002
• 25: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
• 26: 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]
• 27: Yi-Leh Wu , Divyakant Agrawal , Amr El Abbadi, A comparison of DFT and DWT based similarity search in time-series databases, Proceedings of the ninth international conference on Information and knowledge management, p.488-495, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354857]
• 28: 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