Similarity searching for multi-attribute sequences
Proceedings 14th International Conference on Scientific and Statistical Database Management - Trang 175-184
Tóm tắt
We investigate the problem of searching similar multiattribute time sequences. Such sequences arise naturally in a number of medical, financial, video, weather forecast, and stock market databases where more than one attribute is of interest at a time instant. We first solve the simple case in which the distance is defined as the Euclidean distance. Later we extend it to shift and scale invariance. We formulate a new symmetric scale and shift invariant notion of distance for such sequences. We also propose a new index structure that transforms the data sequences and clusters them according to their shiftings and scalings. This clustering improves the efficiency considerably. According to our experiments with real and synthetic datasets, the index structure's performance is 5 to 45 times better than competing techniques, the exact speedup based on other optimizations such as caching and replication.
Từ khóa
#Weather forecasting #Databases #Discrete Fourier transforms #Stock markets #Economic forecasting #Euclidean distance #Wavelet transforms #Computer science #Mathematics #IndexesTài liệu tham khảo
kahveci, 2001, An efficient index structure for string databases, VLDB, 351
10.1109/ICDE.2001.914838
kahveci, 2001, Technical Report
lee, 2000, Similarity search for multidimensional data sequences, ICDE
10.1109/ICDE.2000.839385
10.1109/ICDE.1999.754957
10.1145/253260.253264
rafiei, 1998, Efficient retrieval of similar time sequences using DFT, FODO
seeger, 1993, Reading a set of disk pages, VLDB, 592
shahabi, 2000, TSA-tree: A wavelet-based approach to improve the efficieny of multi-level surprise and trend queries, SSDBM
chan, 1999, Efficient time series matching by wavelets, ICDE
10.1145/93597.98741
das, 1997, Finding similar time series, PKDD, 88
10.1145/303976.304000
goldin, 1995, On similarity queries for time-series data: Constraint specification and implementation, CP, 137
10.1145/191839.191925
agrawal, 1995, Fast similarity search in the presence of noise, scaling, and translation in time-series databases, VLDB
agrawal, 1993, Efficient similarity search in sequence databases, FODO
10.1145/971697.602266
10.1109/ICDE.2002.994784
white, 1996, Similarity indexing: Algorithms and performance, SPIE Storage and Retrieval for Image and Video Databases, 10.1117/12.234810