Davood Rafiei
Alberto Mendelzon
Abstract
We study a set of linear transformations on the Fourier series representation of a sequence that can be used as the basis for similarity queries on time-series data. We show that our set of transformations is rich enough to formulate operations such as moving average and time warping. We present a query processing algorithm that uses the underlying R-tree index of a multidimensional data set to answer similarity queries efficiently. Our experiments show that the performance of this algorithm is competitive to that of processing ordinary (exact match) queries using the index, and much faster than sequential scanning. We relate our transformations to the general framework for similarity queries of Jagadish et al.
- AFS93 Rakesh Agrawal, Christos Faloutsos, and Arun Swami. Efficient similarity search in sequence databases. In Foundations (9} Data Organizations and algorithms (FODO} conference, October 1993. Google Scholar
Digital Library
- ALSS95 Rakesh Agrawal, King-Ip Lin, Harpreet S. Sawhney, and Kyuseok Shim. Fast similarity search in the presence of noise, scaling, and translation in time-series databases. In Proceedings of the 21st VLDB Conference, pages 490-501, Zurich, Switzerland, 1995. Google ScholarDigital Library
- APWZ95 R. Agrawal, G. Psaila, E. L. Wimmers, and M. Zait. Querying shapes of histories. In Proceedings of the 21st VLDB Conference, pages 502-514, Zurich, Switzerland, 1995. Google ScholarDigital Library
- BKSS90 N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R* tree: an efficient and robust index method for points and rectangles. In A CM SIGMOD Conf. on the Management Of Data, pages 322-331. ACM, 1990. Google ScholarDigital Library
- EM69 R.D. Edwards and J. Magee. Technical analysis of stock trends. John Magee, Springfield, Massachsetts, 1969.Google Scholar
- FJMM95 C. Faloutsos, H. V. Jagadish, A. O. Mendelzon, and T. Milo. A signature technique for similarity-based queries, technical report 112530-951110-16TM, AT&T, Murray Hill, NJ, November 1995.Google Scholar
- FRM94 C. Faloutsos, M. Ranganathan, and Y. Manolopoutos. Fast subsequence matching in time-series databases. In Intl. Conf. on Management of Data- SIGMOD 9~, pages 419-429, Minneapolis, May 1994. Google ScholarDigital Library
- GK95 D.Q. Goldin and P. C. Kanellakis. On similarity queries for time-series data: constraint specification and implementation. In 1st Intl. Con}. on the Principles and Practice of Constraint Programming, pages 137- 153. LNCS 976, Sept. 1995. Google ScholarDigital Library
- Gut84 Antonin Guttman. R-trees: a dynamic index structure for spatial searching. In A CM SIGMOD Conf. on the Management Of Data, pages 47-57. ACM, 1984. Google ScholarDigital Library
- Jag91 H.V. Jagadish. A retrieval technique for similar shapes. In A CM SIGMOD Syrup. on the Management Of Data, pages 208-217, 1991. Google ScholarDigital Library
- JMM95 H. V. Jagadish, A. O. Mendelzon, and T. Milo. Similarity-based queries. PODS, 1995. Google ScholarDigital Library
- OS75 A.V. Oppenheim and R. W. Schafer. Digital Signal Processing. Prentice-Hall, Englewood Cliffs, N.J., 1975. Google ScholarDigital Library
- RKV95 N. Roussopoulos, S. Kelley, and F. Vincent. Nearest neighbor queries. In Proceedings of the A CM SIGMOD Annual Conference, San Jose, CA, 1995. Google ScholarDigital Library
- Rot93 William G. Roth. MIMSY: A system for analyzing time series data in the stock market domain. University of Wisconsin, Madison, 1993. Master Thesis.Google Scholar
- RS92 Raghu Ramakrishnan and Divesh Srivastava. CORAL: Control, relations and logic. in Proceedings of the Int. Conf. on VLDB, 1992. Google ScholarDigital Library
- SK83 David Sankoff and Joseph B. Kruskal. Time Warps, String Edits, and Macromolecules: The Theory and Practice o.f Sequence Comparison. Addison-Wesley Publishing Company, 1983.Google Scholar
Index Terms
- Similarity-based queries for time series data
Recommendations
Similarity-based queries for time series data
SIGMOD '97: Proceedings of the 1997 ACM SIGMOD international conference on Management of dataWe study a set of linear transformations on the Fourier series representation of a sequence that can be used as the basis for similarity queries on time-series data. We show that our set of transformations is rich enough to formulate operations such as ...
Querying Time Series Data Based on Similarity
We study similarity queries for time series data where similarity is defined, in a fairly general way, in terms of a distance function and a set of affine transformations on the Fourier series representation of a sequence. We identify a safe set of ...
On Similarity-Based Queries for Time Series Data
ICDE '99: Proceedings of the 15th International Conference on Data EngineeringWe study similarity queries for time series data where similarity is defined in terms of a set of linear transformations on the Fourier series representation of a sequence. We have shown in an earlier work that this set of transformations is rich enough ...
Comments