Time-series similarity problems and well-separated geometric sets
作者： Dimitrios Gunopulos , Gautam Das , Heikki Mannila , Béla Bollobás
DOI:
关键词:
摘要: Given a pair of nonidentical complex objects, defining (and determining) how similar they are to each other is nontrivial problem. In data mining applications, one frequently needs determine the similarity between two time series. We analyze model time-series that allows outliers, different scaling functions, and variable sampling rates. present several deterministic randomized algorithms for computing this notion similarity. The based on tools methods from computational geometry. particular, we use properties families well-separated geometric sets. algorithm has provably good performance also works extremely efficiently in practice.
参考文章(15)
H. V. Jagadish, Alberto O. Mendelzon, Tova Milo, Similarity-based queries Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems - PODS '95. pp. 36- 45 ,(1995) , 10.1145/212433.212444
Bernard Chazelle, Cutting hyperplanes for divide-and-conquer Discrete and Computational Geometry. ,vol. 9, pp. 145- 158 ,(1993) , 10.1007/BF02189314
Béla Bollobás, Gautam Das, Dimitrios Gunopulos, Heikki Mannila, Time-series similarity problems and well-separated geometric sets symposium on computational geometry. pp. 454- 456 ,(1997) , 10.1145/262839.263080
N. Yazdani, Z.M. Ozsoyoglu, Sequence matching of images statistical and scientific database management. pp. 53- 62 ,(1996) , 10.1109/SSDM.1996.505915
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 - SIGMOD '94. ,vol. 23, pp. 419- 429 ,(1994) , 10.1145/191839.191925
H. Shatkay, S.B. Zdonik, Approximate queries and representations for large data sequences international conference on data engineering. pp. 536- 545 ,(1996) , 10.1109/ICDE.1996.492204
Thomas T. Cormen, Ronald L. Rivest, Charles E. Leiserson, Introduction to Algorithms ,(1990)
Raj Jain, Derek White, Algorithms and strategies for similarity retrieval Storage and Retrieval for Image and Video Databases. ,(1996)
Rakesh Agrawal, Christos Faloutsos, Arun Swami, None, Efficient Similarity Search In Sequence Databases FODO '93 Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms. pp. 69- 84 ,(1993) , 10.1007/3-540-57301-1_5
Gautam Das, Dimitrios Gunopulos, Heikki Mannila, Finding Similar Time Series european conference on principles of data mining and knowledge discovery. pp. 88- 100 ,(1997) , 10.1007/3-540-63223-9_109