Fast time-series searching with scaling and shifting
Published 1 May 1999Open access
Kelvin Kam Wing Chu, Man Hon Wong
Citations165
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A definition of similarity based on scaling and shifting transformations and a geometrical view of the problem are presented so that the scaling factor and the shifting offset can be determined and sequence searching based on tree-based indexing structure can be performed.
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.
Keywords
Computer Science
R-trees
6,543 Citations1984Antonin Guttman
A dynamic index structure called an R-tree is described which meets this need, and algorithms for searching and updating it are given and it is concluded that it is useful for current database systems in spatial applications.
The R*-tree: an efficient and robust access method for points and rectangles
4,176 Citations1990Norbert Beckmann, Hans‐Peter Kriegel +2 more
The R*-tree is designed which incorporates a combined optimization of area, margin and overlap of each enclosing rectangle in the directory which clearly outperforms the existing R-tree variants.
Lecture notes in computer scienceEfficient similarity search in sequence databases
1,972 Citations1993Rakesh Agrawal, Christos Faloutsos +1 more
An indexing method for time sequences for processing similarity queries using R * -trees to index the sequences and efficiently answer similarity queries and provides experimental results which show that the method is superior to search based on sequential scanning.
Fast subsequence matching in time-series databases
1,720 Citations1994Christos Faloutsos, M. Ranganathan +1 more
Very Large Data BasesThe R+-Tree: A Dynamic Index for Multi-Dimensional Objects
1,263 Citations2018Timos Sellis, Nick Roussopoulos +1 more
A variation to Guttman’s Rtrees (R+-trees) that avoids overlapping rectangles in intermediate nodes of the tree is introduced and analytical results indicate that R+-Trees achieve up to 50% savings in disk accesses compared to an R-tree when searching files of thousands of rectangles.
Elsevier eBooksThe X-tree: An Index Structure for High-Dimensional Data Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.
1,127 Citations2002Stefan Berchtold, Daniel A. Keim +1 more
A new organization of the directory is introduced which uses a split algorithm minimizing overlap and additionally utilizes the concept of supernodes to keep the directory as hierarchical as possible, and at the same time to avoid splits in the directory that would result in high overlap.
Efficient time series matching by wavelets
1,030 Citations1999Kin-Pong Chan, Ada Wai-Chee Fu
This paper proposes to use Haar Wavelet Transform for time series indexing and shows that Haar transform can outperform DFT through experiments, and proposes a two-phase method for efficient n-nearest neighbor query in time series databases.
The SR-tree
819 Citations1997Norio Katayama, Shin’ichi Satoh
This paper proposes a new index structure called the SR-tree (Sphere/Rectangle-tree) which integrates bounding spheres and bounding rectangles which enhances the performance on nearest neighbor queries especially for high-dimensional and non-uniform data which can be practical in actual image/video similarity indexing.
Efficient retrieval of similar time sequences under time warping
713 Citations2002Byoung-Kee Yi, H. V. Jagadish +1 more
This work proposes a modification of the so called "FastMap", to map sequences into points, with little compromise of "recall" (typically zero), and a fast linear test, to help to discard quickly many of the false alarms that FastMap will typically introduce.
Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases
655 Citations1995Rakesh Agrawal, King-Ip Lin +2 more
A new model of similarity of time sequences is introduced that captures the intuitive notion that two sequences should be considered similar if they have enough non-overlapping time-ordered pairs of subsequences thar are similar.
3D Computer Graphics
388 Citations1993Alan Watt
The third edition of Alan Watt's 3D Computer Graphics, a bible of computer graphics, includes a CD-ROM full of examples and updated information on graphics and rendering algorithms, including methods for linked structures, collision detection, and particle animation.
Similarity-based queries for time series data
346 Citations1997Davood Rafiei, Alberto O. Mendelzon
Lecture notes in computer scienceOn similarity queries for time-series data: Constraint specification and implementation
333 Citations1995Dina Goldin, Paris C. Kanellakis
The intuitive notions of exact and approximate similarity between time-series patterns and data are formalized and the definition of similarity extends the distance metric used in [2, 7] with invariance under a group of transformations.
Lecture notes in computer scienceFinding similar time series
308 Citations1997Gautam Das, Dimitrios Gunopulos +1 more
This paper presents an intuitive model for measuring the similarity between two time series that takes into account outliers, different scaling functions, and variable sampling rates, and shows the naturalness of this notion of similarity.
Approximate queries and representations for large data sequences
260 Citations2002Hagit Shatkay, Stanley B. Zdonik
This work introduces a new notion of generalized approximate queries and a general divide and conquer approach that supports them, which uses families of real-valued functions as an approximate representation.
Dimensionality reduction for similarity searching in dynamic databases
259 Citations1998K. V. Ravi Kanth, Divyakant Agrawal +1 more
This paper proposes novel techniques for performing SVD-based dimensionality reduction in dynamic databases and proposes a novel technique that uses aggregate data from the existing index rather than the entire data.
Similarity-based queries
147 Citations1995H. V. Jagadish, Alberto O. Mendelzon +1 more
A domain-independent framework for defining qneries in terms of similarity of objects, which shows that even when the pattern/query languages chosen are not too powerful, the approximation framework obtained is very strong.
American Mathematical MonthlyIntroduction to Vector Analysis.
107 Citations1962H. E. Chrestenson, Harry F. Davis
This book aims to meet the professional needs of the engineer or scientist, and to give the mathematician an understanding of the three-dimensional versions of the theorems of higher geometry.
Matching and indexing sequences of different lengths
86 Citations1997Tolga Bozkaya, Nasser Yazdani +1 more
This paper proposes an indexing scheme which is totally based on lengths and relative distances between sequences, and uses vp-trees as the underlying distance-based index structures in its method.
HierarchyScan: a hierarchical similarity search algorithm for databases of long sequences
81 Citations2002Chung‐Sheng Li, Philip S. Yu +1 more
Data & Knowledge EngineeringA fast projection algorithm for sequence data searching
23 Citations1998Sze Kin Lam, Man Hon Wong
A new definition on sequence similarity and a novel algorithm, Projection Algorithm, for sequence data searching are proposed and it is shown that the proposed algorithm can outperform the traditional sequential searching algorithm up to 96 times in terms of speed up.
The Computer JournalAn Efficient Hash-Based Algorithm for Sequence Data Searching
16 Citations1998Kam-Wing Chu
A definition of sequence similarity based on the shape of sequences is introduced to handle sequence matching with linear scaling in both amplitude and time dimensions and a fast sequence searching algorithm based on extendable hashing is proposed.