No Access

EFFICIENT SIMILARITY SEARCH FOR MULTI-DIMENSIONAL TIME SEQUENCES

SANGJUN LEE

School of Computing, Soongsil University, Seoul 156-743, Korea

Search for more papers by this author

and

JISOOK PARK

Department of Multimedia, Seoul Women's University, Seoul 139-774, Korea

Search for more papers by this author

https://doi.org/10.1142/S0219691310003511Cited by:1 (Source: Crossref)

Abstract

We address the problem of similarity search in large multi-dimensional time sequence databases. There has been a lot of attention in similarity search in time sequence databases. However, most of the previous work on time sequences focused on one-dimensional sequences. Many applications such as multimedia databases or weather databases, however, need to handle multi-dimensional time sequences. In this paper, we extend our previous work on the similarity search by considering query types in multi-dimensional time sequence databases and more intensive experimental results that were not reported in the previous paper are illustrated. The proposed method can efficiently reduce the search space and guarantees no false dismissals.

Keywords:

AMSC: 37M10, 42C40, 68P20

References

D. Rafiei and A. O. Mendelzon, Similarity-based queries for time series data, Proc. ACM SIGMOD Int. Conf. Management of Data (1997) pp. 13–25. Google Scholar
A. Ciancio, Int. J. Wavelets Multiresolut. Inf. Process. 5(2), 241 (2007), DOI: 10.1142/S0219691307001744. Link, Web of Science, Google Scholar
R. Agrawal, T. Imielinski and A. N. Swami, IEEE Trans. Knowl. Data Eng. 5(6), 914 (1993), DOI: 10.1109/69.250074. Crossref, Web of Science, Google Scholar
C. C. Chang, J. C. Chung and Y. S. Hu, Int. J. Wavelets Multiresolut. Inf. Process. 2(2), 111 (2004), DOI: 10.1142/S021969130400038X. Link, Google Scholar
Y. Ji, X. Cheng and N. Feng, Int. J. Wavelets Multiresolut. Inf. Process. 5(1), 213 (2007), DOI: 10.1142/S0219691307001720. Link, Web of Science, Google Scholar
A. B. Mabrouk, H. Kortas and Z. Dhifaoui, Int. J. Wavelets Multiresolut. Inf. Process. 6(6), 851 (2008), DOI: 10.1142/S0219691308002410. Link, Web of Science, Google Scholar
A. Guttman, R-trees: A dynamic index structure for spatial searching, Proc. ACM SIGMOD Int. Conf. Management of Data (1984) pp. 47–57. Google Scholar
N. Beckmannet al., The R*-tree: An efficient and robust access method for points and rectangles, Proc. ACM SIGMOD Int. Conf. Management of Data (1990) pp. 322–331. Google Scholar
S. Leeet al., Efficient pattern matching of multidimensional sequences, Proc. Int. Conf. Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing (2005) pp. 202–210. Google Scholar
S. Lee, J. Korea Information Processing Society 14D(7), 727 (2007). Google Scholar
R. Agrawal, C. Faloutsos and A. N. Swami, Efficient similarity search in sequence databases, Proc. Int. Conf. Foundations of Data Organization and Algorithms (1993) pp. 69–84. Google Scholar
D. Q. Goldin and P. C. Kanellakis, On similarity queries for time-series data: Constraint specification and implementation, Proc. Constraint Programming Conference (1995) pp. 137–153. Google Scholar
C. Faloutsos and K. I. Lin, Fastmap: A fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets, Proc. ACM SIGMOD Int. Conf. Management of Data (1995) pp. 163–174. Google Scholar
R. Agrawalet al., Fast similarity search in the presence of noise, scaling, and translation in time-series databases, Proc. Int. Conf. Very Large Data Bases (1995) pp. 490–501. Google Scholar
F. Korn, H. V. Jagadish and C. Faloutsos, Efficiently supporting ad hoc queries in large datasets of time sequences, Proc. ACM SIGMOD Int. Conf. Management of Data (1997) pp. 289–300. Google Scholar
G. Das, D. Gunopulos and H. Mannila, Finding similar time series, Proc. European Conf. Principles of Data Mining and Knowledge Discovery (1997) pp. 88–100. Google Scholar
T. Bozkaya, N. Yazdani and M. Ozsoyoglu, Matching and indexing sequences of different lengths, Proc. Int. Conf. Information and Knowledge Management (1997) pp. 128–135. Google Scholar
B. K. Yi, H. V. Jagadish and C. Faloutsos, Efficient retrieval of similar time sequences under time warping, Proc. Int. Conf. Data Engineering (1998) pp. 201–208. Google Scholar
S. K. Lam and M. H. Wong, Data Knowl. Eng. 28(3), 321 (1998), DOI: 10.1016/S0169-023X(98)00023-8. Crossref, Web of Science, Google Scholar
K. K. W. Chu and M. H. Wong, Fast time-series searching with scaling and shifting, Proc. ACM SIGACT-SIGMOD-SIGART Symp. Principles of Database Systems (1999) pp. 237–248. Google Scholar
D. Rafiei, On similarity-based queries for time series data, Proc. Int. Conf. Data Engineering (1999) pp. 410–417. Google Scholar
K. P. Chan and A. W.-C. Fu, Efficient time series matching by wavelets, Proc. Int. Conf. Data Engineering (1999) pp. 126–133. Google Scholar
J. M. Hellerstein, E. Koutsoupias and C. H. Papadimitriou, On the analysis of indexing schemes, Proc. ACM SIGACT-SIGMOD-SIGART Symp. Principles of Database Systems (1997) pp. 249–256. Google Scholar
E. J. Keoghet al., J. Knowl. Inf. Syst. 3(3), 263 (2001), DOI: 10.1007/PL00011669. Crossref, Web of Science, Google Scholar
C. S. Pernget al., Landmarks: A new model for similarity-based pattern querying in time series databases, Proc. Int. Conf. Data Engineering (2000) pp. 33–42. Google Scholar
B. K. Yi and C. Faloutsos, Fast time sequence indexing for arbitrary Lp norms, Proc. Int. Conf. Very Large Data Bases (2000) pp. 385–394. Google Scholar
S. Kim, S. Park and W. W. Chu, An index-based approach for similarity search supporting time warping in large sequence databases, Proc. Int. Conf. Data Engineering (2001) pp. 607–614. Google Scholar
E. J. Keoghet al., Locally adaptive dimensionality reduction for indexing large time series databases, Proc. ACM SIGMOD Int. Conf. Management of Data (2001) pp. 151–162. Google Scholar
S. Kang and S. Lee, Int. J. Wavelets Multiresolut. Inf. Process. 6(6), 869 (2008), DOI: 10.1142/S0219691308002720. Link, Web of Science, Google Scholar
P. Xie and J. He, Int. J. Wavelets Multiresolut. Inf. Process. 7(2), 243 (2009), DOI: 10.1142/S0219691309002891. Link, Web of Science, Google Scholar
C. Chiu, C. Chuang and C. Hsu, Int. J. Wavelets Multiresolut. Inf. Process. 7(3), 341 (2009), DOI: 10.1142/S0219691309002957. Link, Web of Science, Google Scholar
I. Popivanov and R. J. Miller, Similarity search over time-series using wavelets, Proc. Int. Conf. Data Engineering (2002) pp. 212–221. Google Scholar
E. J. Keogh, Exact indexing of dynamic time warping, Proc. Int. Conf. Very Large Data Bases (2002) pp. 406–417. Google Scholar
S. Leeet al., Similarity search for multidimensional data sequences, Proc. Int. Conf. Data Engineering (2000) pp. 599–608. Google Scholar
M. Vlachos, G. Kollios and D. Gunopulos, Discovering similar multidimensional trajectories, Proc. Int. Conf. Data Engineering (2002) pp. 673–684. Google Scholar
T. Kahveci, A. Singh and A. Gurel, Similarity searching for multi-attribute sequences, Proc. Int. Conf. Scientific and Statistical Database Management (2002) pp. 175–184. Google Scholar
M. Vlachoset al., Indexing multi-dimensional time series with support for multiple distance measures, Proc. ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (2003) pp. 216–225. Google Scholar