[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

A Multi-Hierarchical Representation for Similarity Measurement of Time Series

  • Conference paper
Advances in Knowledge Discovery and Data Mining (PAKDD 2006)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 3918))

Included in the following conference series:

  • 3136 Accesses

Abstract

In a large time series database, similarity searching is a frequent subroutine to find the similar time series of the given one. In the process, the performance of similarity measurement directly effects the usability of the searching results. The proposed methods mostly use the sum of the distances between the values on the time points, e.g. Euclidean Distance, dynamic time warping (DTW) etc. However, in measuring, they do not consider the hierarchy of each point in time series according to importance. This causes that they cannot accurately and efficiently measure similarity of time series. In the paper, we propose a Multi-Hierarchical Representation (MHR) to replace the original one based on the opinion that the points of one time series should be compared with the ones of another with the same importance in measuring. MHR gives the hierarchies of the points, and then the original one can be represented by the Multi-Hierarchical subseries, which consist of points in the same hierarchy. The distance between the representations can be computed as the measuring result. Finally, the synthetic and real data sets were used in the effectiveness experiments comparing ours with other major methods. And the comparison of their efficiencies was also performed on the real data set. All the results showed the superiority of ours in terms of effectiveness and efficiency.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Agrawal, R., Faloutsos, C., Swami, A.N.: Efficient similarity search in sequence databases. In: FODO 1993, pp. 69–84.

    Google Scholar 

  2. Chan, K.p., Fu, A.W.-C.: Efficient time series matching by wavelets. In: ICDE 1999, pp. 126–133 (1999)

    Google Scholar 

  3. Das, G., Lin, K.-I., Mannila, H., Renganathan, G., Smyth, P.: Rule discovery from time series. In: KDD 1998, pp. 16–22 (1998)

    Google Scholar 

  4. Lin, J., Keogh, E., Lonardi, S., Chiu, B.: A symbolic representation of time series, with implications for streaming algorithms. In: DMKD 2003, pp. 2–11 (2003)

    Google Scholar 

  5. Mörchen, F., Ultsch, A.: Optimizing time series discretization for knowledge discovery. In: KDD 2005, pp. 660–665 (2005)

    Google Scholar 

  6. Bagnall, A.J., Janacek, G.J.: Clustering time series from arma models with clipped data. In: KDD 2004, pp. 49–58 (2004)

    Google Scholar 

  7. Ratanamahatana, C.A., Keogh, E.J., Bagnall, A.J., Lonardi, S.: A novel bit level time series representation with implication of similarity search and clustering. In: Ho, T.-B., Cheung, D., Liu, H. (eds.) PAKDD 2005. LNCS (LNAI), vol. 3518, pp. 771–777. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  8. Megalooikonomou, V., Wang, Q., Li, G., Faloutsos, C.: A multiresolution symbolic representation of time series. In: ICDE 2005, pp. 668–679 (2005)

    Google Scholar 

  9. Korn, F., Jagadish, H.V., Faloutsos, C.: Efficiently supporting ad hoc queries in large datasets of time sequences. In: SIGMOD 1997, pp. 289–300 (1997)

    Google Scholar 

  10. Keogh, E., Pazzani, M.: An enhanced representation of time series which allows fast and accurate classification, clustering and relevance feedback. In: KDD 1998, pp. 239–241 (1998)

    Google Scholar 

  11. Yi, B.-K., Faloutsos, C.: Fast time sequence indexing for arbitrary lp norms. In: VLDB 2000, pp. 385–394 (2000)

    Google Scholar 

  12. Keogh, E., Pazzani, M.J.: Scaling up dynamic time warping for datamining applications. In: KDD 1999, pp. 285–289 (2000)

    Google Scholar 

  13. Keogh, E., Chakrabarti, K., Pazzani, M., Mehrotra, S.: Locally adaptive dimensionality reduction for indexing large time series databases. In: SIGMOD 2001, pp. 151–162 (2001)

    Google Scholar 

  14. Gavrilov, M., Anguelov, D., Indyk, P., Motwani, R.: Mining the stock market: which measure is best. In: KDD 2000, pp. 487–496 (2000)

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Zuo, X., Jin, X. (2006). A Multi-Hierarchical Representation for Similarity Measurement of Time Series. In: Ng, WK., Kitsuregawa, M., Li, J., Chang, K. (eds) Advances in Knowledge Discovery and Data Mining. PAKDD 2006. Lecture Notes in Computer Science(), vol 3918. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11731139_88

Download citation

  • DOI: https://doi.org/10.1007/11731139_88

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-33206-0

  • Online ISBN: 978-3-540-33207-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics