Digital Symposium Collection 2000

Fast Time-Series Searching with Scaling and Shifting Kelvin Kam Wing Chu and Man Hon Wong   View Paper (PDF)   Return to Novel Data Abstract Recently, it has been found that the technique of searching for similar patterns among time series data is very important in a wide range of scientific and business applications. In this paper, we first propose a definition of similarity based on scaling and shifting transformations. Sequence A is defined to be similar to sequence B if suitable scaling and shifting transformations can be found to transform A to B. Then, we present a geometrical view of the problem so that the scaling factor and the shifting offset can be determined. Moreover, sequence searching based on tree-based indexing structure can be performed. Finally, some technical aspects are discussed and some experiments are performed on real data (stock price movement) to measure the performance of our algorithm. References Note: References link to DBLP on the Web. [1] Rakesh Agrawal , Christos Faloutsos , Arun N. Swami : Efficient Similarity Search In Sequence Databases. FODO 1993 : 69-84 [2] Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos : Fast Subsequence Matching in Time-Series Databases. SIGMOD Conference 1994 : 419-429 [3] Rakesh Agrawal , King-Ip Lin , Harpreet S. Sawhney , Kyuseok Shim : Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases. VLDB 1995 : 490-501 [4] H. V. Jagadish , Alberto O. Mendelzon , Tova Milo : Similarity-Based Queries. PODS 1995 : 36-45 [5] Davood Rafiei , Alberto O. Mendelzon : Similarity-Based Queries for Time Series Data. SIGMOD Conference 1997 : 13-25 [6] Dina Q. Goldin , Paris C. Kanellakis : On Similarity Queries for Time-Series Data: Constraint Specification and Implementation. CP 1995 : 137-153 [7] Hagit Shatkay , Stanley B. Zdonik : Approximate Queries and Representations for Large Data Sequences. ICDE 1996 : 536-545 [8] Chung-Sheng Li , Philip S. Yu , Vittorio Castelli : HierarchyScan: A Hierarchical Similarity Search Algorithm for Databases of Long Sequences. ICDE 1996 : 546-553 [9] Tolga Bozkaya , Nasser Yazdani , Z. Meral Özsoyoglu : Matching and Indexing Sequences of Different Lengths. CIKM 1997 : 128-135 [10] Byoung-Kee Yi , H. V. Jagadish , Christos Faloutsos : Efficient Retrieval of Similar Time Sequences Under Time Warping. ICDE 1998 : 201-208 [11] Sze Kin Lam , Man Hon Wong : A Fast Signature Algorithm for Sequence Data Searching. NGITS 1997 : 0- [12] Sze Kin Lam , Man Hon Wong : A Fast Projection Algorithm for Sequence Data Searching. DKE 28(3) : 321-339(1998) [13] Kelvin Kam Wing Chu , Sze Kin Lam , Man Hon Wong : An Efficient Hash-Based Algorithm for Sequence Data Searching. The Computer Journal 41(6) : 402-415(1998) [14] Kin-pong Chan , Ada Wai-Chee Fu : Efficient Time Series Matching by Wavelets. ICDE 1999 : 126-133 [15] Béla Bollobás , Gautam Das , Dimitrios Gunopulos , Heikki Mannila : Time-Series Similarity Problems and Well-Separated Geometric Sets. Symposium on Computational Geometry 1997 : 454-456 [16] Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger : The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990 : 322-331 [17] ... [18] Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos : The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987 : 507-518 [19] Gautam Das , Dimitrios Gunopulos , Heikki Mannila : Finding Similar Time Series. PKDD 1997 : 88-100 [20] Kothuri Venkata Ravi Kanth , Divyakant Agrawal , Ambuj K. Singh : Dimensionality Reduction for Similarity Searching in Dynamic Databases. SIGMOD Conference 1998 : 166-176 [21] ... [22] Antonin Guttman : R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984 : 47-57 [23] Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel : The X-tree : An Index Structure for High-Dimensional Data. VLDB 1996 : 28-39 [24] ... [25] ... [26] Norio Katayama , Shin'ichi Satoh : The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries. SIGMOD Conference 1997 : 369-380 BIBTEX @inproceedings{DBLP:conf/pods/ChuW99,   author    = {Kelvin Kam Wing Chu and                 Man Hon Wong},    title     = {Fast Time-Series Searching with Scaling and Shifting},    booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium                 on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,                 Pennsylvania},    publisher = {ACM Press},    year      = {1999},    isbn      = {1-58113-062-7},    pages     = {237-248},    crossref  = {DBLP:conf/pods/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM