More Web Proxy on the site http://driver.im/

article

Free access

Similarity-based queries for time series data

Authors:

Alberto MendelzonAuthors Info & Claims

ACM SIGMOD Record, Volume 26, Issue 2

Pages 13 - 25

https://doi.org/10.1145/253262.253264

Published: 01 June 1997 Publication History

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.

References

[1]

Rakesh Agrawal, Christos Faloutsos, and Arun Swami. Efficient similarity search in sequence databases. In Foundations (9} Data Organizations and algorithms (FODO} conference, October 1993.

Digital Library

[2]

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.

Digital Library

[3]

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.

Digital Library

[4]

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.

Digital Library

[5]

R.D. Edwards and J. Magee. Technical analysis of stock trends. John Magee, Springfield, Massachsetts, 1969.

[6]

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.

[7]

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.

Digital Library

[8]

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.

Digital Library

[9]

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.

Digital Library

[10]

H.V. Jagadish. A retrieval technique for similar shapes. In A CM SIGMOD Syrup. on the Management Of Data, pages 208-217, 1991.

Digital Library

[11]

H. V. Jagadish, A. O. Mendelzon, and T. Milo. Similarity-based queries. PODS, 1995.

Digital Library

[12]

A.V. Oppenheim and R. W. Schafer. Digital Signal Processing. Prentice-Hall, Englewood Cliffs, N.J., 1975.

Digital Library

[13]

N. Roussopoulos, S. Kelley, and F. Vincent. Nearest neighbor queries. In Proceedings of the A CM SIGMOD Annual Conference, San Jose, CA, 1995.

Digital Library

[14]

William G. Roth. MIMSY: A system for analyzing time series data in the stock market domain. University of Wisconsin, Madison, 1993. Master Thesis.

[15]

Raghu Ramakrishnan and Divesh Srivastava. CORAL: Control, relations and logic. in Proceedings of the Int. Conf. on VLDB, 1992.

Digital Library

[16]

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.

Cited By

Shaikh SKitagawa HMatono A(2024)Distributed, Continuous and Real-time Trajectory Similarity Search2024 23rd International Symposium on Parallel and Distributed Computing (ISPDC)10.1109/ISPDC62236.2024.10705397(1-8)Online publication date: 8-Jul-2024
https://doi.org/10.1109/ISPDC62236.2024.10705397
Azizi IEchihabi KPalpanas T(2023)ELPIS: Graph-Based Similarity Search for Scalable Data ScienceProceedings of the VLDB Endowment10.14778/3583140.358316616:6(1548-1559)Online publication date: 1-Feb-2023
https://dl.acm.org/doi/10.14778/3583140.3583166
Echihabi KPalpanas T(2022)Scalable Analytics on Large Sequence Collections2022 23rd IEEE International Conference on Mobile Data Management (MDM)10.1109/MDM55031.2022.00022(5-8)Online publication date: Jun-2022
https://doi.org/10.1109/MDM55031.2022.00022
Show More Cited By

Recommendations

Similarity-based queries for time series data
SIGMOD '97: Proceedings of the 1997 ACM SIGMOD international conference on Management of data

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 ...
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 Engineering

We 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMOD Record

ACM SIGMOD Record Volume 26, Issue 2

June 1997

583 pages

ISSN:0163-5808

DOI:10.1145/253262

Chairman:
Sudha Ram
Univ. of Arizona, Tucson
,
Editor:
Joan M. Peckham
Univ. of Rhode Island, Kingston

Issue’s Table of Contents

SIGMOD '97: Proceedings of the 1997 ACM SIGMOD international conference on Management of data
June 1997
594 pages
ISBN:0897919114
DOI:10.1145/253260
Editors:
Joan M. Peckman
Univ. of Rhode Island, Kingston
,
Sudha Ram
Univ. of Arizona, Tucson
,
Michael Franklin

Copyright © 1997 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1997

Published in SIGMOD Volume 26, Issue 2

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

245
Total Citations
View Citations
2,121
Total Downloads

Downloads (Last 12 months)310
Downloads (Last 6 weeks)65

Reflects downloads up to 07 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Shaikh SKitagawa HMatono A(2024)Distributed, Continuous and Real-time Trajectory Similarity Search2024 23rd International Symposium on Parallel and Distributed Computing (ISPDC)10.1109/ISPDC62236.2024.10705397(1-8)Online publication date: 8-Jul-2024
https://doi.org/10.1109/ISPDC62236.2024.10705397
Azizi IEchihabi KPalpanas T(2023)ELPIS: Graph-Based Similarity Search for Scalable Data ScienceProceedings of the VLDB Endowment10.14778/3583140.358316616:6(1548-1559)Online publication date: 1-Feb-2023
https://dl.acm.org/doi/10.14778/3583140.3583166
Echihabi KPalpanas T(2022)Scalable Analytics on Large Sequence Collections2022 23rd IEEE International Conference on Mobile Data Management (MDM)10.1109/MDM55031.2022.00022(5-8)Online publication date: Jun-2022
https://doi.org/10.1109/MDM55031.2022.00022
Lee SPark C(2021)Novel Features for Binary Time Series Based on Branch Length Similarity EntropyEntropy10.3390/e2304048023:4(480)Online publication date: 18-Apr-2021
https://doi.org/10.3390/e23040480
Siddiqui TChaudhuri SNarasayya V(2021)COMPAREProceedings of the VLDB Endowment10.14778/3476249.347629114:11(2419-2431)Online publication date: 27-Oct-2021
https://dl.acm.org/doi/10.14778/3476249.3476291
Peng BFatourou PPalpanas T(2021)SING: Sequence Indexing Using GPUs2021 IEEE 37th International Conference on Data Engineering (ICDE)10.1109/ICDE51399.2021.00171(1883-1888)Online publication date: Apr-2021
https://doi.org/10.1109/ICDE51399.2021.00171
Li JIzakian HPedrycz WJamal I(2020)Clustering-based anomaly detection in multivariate time series dataApplied Soft Computing10.1016/j.asoc.2020.106919(106919)Online publication date: Nov-2020
https://doi.org/10.1016/j.asoc.2020.106919
Echihabi KZoumpatianos KPalpanas TBenbrahim H(2019)Return of the Lernaean HydraProceedings of the VLDB Endowment10.14778/3368289.336830313:3(403-420)Online publication date: 1-Nov-2019
https://dl.acm.org/doi/10.14778/3368289.3368303
Inphadung NKamonsantiroj SPipanmaekaporn L(2019)Similarity-Preserving Hashing for Stock AnalysisProceedings of the 2019 5th International Conference on E-Business and Applications10.1145/3317614.3317622(94-99)Online publication date: 25-Feb-2019
https://dl.acm.org/doi/10.1145/3317614.3317622
Teng XGiri PDwyer MSun JTrajcevski G(2019)Local Temporal Compression for (Globally) Evolving Spatial SurfacesBig Data Analytics10.1007/978-3-030-37188-3_19(324-340)Online publication date: 12-Dec-2019
https://doi.org/10.1007/978-3-030-37188-3_19
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents