Abstract
Time sequences, which are ordered sets of observations, have been studied in various database applications. In this paper, we introduce a new class of time sequences of which each observation is represented by an interval rather than a number. Such sequences may arise in many situations. For instance, we may not be able to determine the exact value at a time point due to uncertainty or aggregation. In such a case, the observation may be represented better by a range of possible values. Similarity search for interval time sequences has not been studied to the best of our knowledge and poses a new challenge for research. We first address the issue of (dis)similarity measures for interval time sequences. We choose a \(\mathcal{L}_1\) norm-based measure because it is semantically better than other alternatives. We next propose an efficient indexing technique for fast retrieval of similar interval time sequences from large databases. More specifically, we propose: (1) to extract a segment-based feature vector for each sequence, and (2) to map each feature vector to either a point or a hyper-rectangle in a multi-dimensional feature space. We then show how we can use existing multi-dimensional index structures such as the R-tree for efficient query processing. Our proposed method guarantees that no false dismissals would occur.
This work was supported by the Brain Korea 21 Project in 2003.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, R., Faloutsos, C., Swami, A.: Efficient Similarity Search in Sequence Databases. In: Proc. FODO Conf., Evansotn, IL, USA (October 1993)
Agrawal, R., Lin, K.-I., Sawhney, H.S., Shim, K.: Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Database. In: Proc. VLDB Conf., Zürich, Switzerland (1995)
Beckmann, N., Kriegel, H.-P., Schneider, R., Seeger, B.: The R*-Tree: an Efficient and Robust Access Method for Points and Rectangles. In: Proc. ACM SIGMOD Conf., Atlantic City, NJ, May 1990, pp. 322–331 (1990)
Faloutsos, C., Jagadish, H.V., Mendelzon, A.O., Milo, T.: A Signature Technique for Similarity-Based Queries. In: Proc. SEQUENCES 1997, Salerno, Italy (June 1997)
Faloutsos, C., Ranganathan, M., Manolopoulos, Y.: Fast Subsequence Matching in Time-Series Databases. In: Proc. ACM SIGMOD Conf. (May 1994)
Goldin, D.Q., Kanellakis, P.C.: On Similarity Queries for Time-Series Data: Constraint Specification and Implementation. In: Proc. Constraint Programming 1995, Marseilles (September 1995)
Guttman, A.: R-Trees: a Dynamic Index Structure for Spatial Searching. In: Proc. ACM SIGMOD Conf., Boston, Mass, June 1984, pp. 47–57 (1984)
Kahveci, T., Singh, A.K., Gurel, A.: Similarity Searching for Multi-Attribute Sequences. In: Proc. of SSDBM, Edinburgh, Scotland (July 2002)
Keogh, E.J., Kaushik, K., Mehrotta, S., Pazzani, M.J.: Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases. In: Proc. of SIGMOD Conf., Santa Barbara, CA, May 2001, pp. 151–162 (2001)
Keogh, E.J., Pazzani, M.J.: A simple dimensionality reduction technique for fast similairity search in large time series databases. In: Proc. of the 4th Pacific-Asia Conf. on Knowledge Discovery and Data Mining, Kyoto, Japan (2000)
Lee, S.-L., Chun, S.-J., Kim, D.-H., Lee, J.-H., Chung, C.-W.: Similarity Search for Multidimensional Data Sequences. In: Proc. of ICDE, pp. 599–608 (2000)
Rafiei, D.: Similarity-Based Queries for Time Series Data. In: Proc. of ICDE, Sydney, Australia, March 1999, pp. 410–417 (1999)
Rafiei, D., Mendelzon, A.: Similarity-Based Queries for Time Series Data. In: Proc. ACM SIGMOD Conf., Tucson, AZ (May 1997)
Sellis, T., Roussopoulos, N., Faloutsos, C.: The R+ Tree: a Dynamic Index for Multi-Dimensional Objects. In: Proc. VLDB Conf., pp. 507–518 (1987)
Vlachos, M., Hadjieleftheriou, M., Gunopulos, D., Keogh, E.: Indexing Multi-dimensional Time-Series with Support for Multiple Distance Measures. In: Proc. of SIGKDD, Washington, DC (August 2003)
Vlachos, M., Kollois, G., Gunopulo, D.: Discovering Similar Multidimensional Trajectories. In: Proc. of ICDE, San Jose, CA, pp. 673–684 (2002)
Yi, B.-K., Faloutsos, C.: Fast Time Sequence Indexing for Arbitrary L p Nomrs. In: Proc. of VLDB Conf., Cairo, Egypt, September 2000, pp. 385–394 (2000)
Yi, B.-K., Jagadish, H.V., Faloutsos, C.: Efficient Retrieval of Similar Time Sequences under Time Warping. In: IEEE Proc. of ICDE (February 1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yi, BK., Roh, JW. (2004). Similarity Search for Interval Time Sequences. In: Lee, Y., Li, J., Whang, KY., Lee, D. (eds) Database Systems for Advanced Applications. DASFAA 2004. Lecture Notes in Computer Science, vol 2973. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24571-1_21
Download citation
DOI: https://doi.org/10.1007/978-3-540-24571-1_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21047-4
Online ISBN: 978-3-540-24571-1
eBook Packages: Springer Book Archive