Online event-driven subsequence matching over financial data streams
Published 13 June 2004
Huanmei Wu, Betty Salzberg, Donghui Zhang
Citations128
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
This paper presents a new approximate approach for automatic online subsequence similarity matching over massive data streams with a simultaneous on-line segmentation and pruning algorithm over the incoming stream, which features high sensitivity and accuracy.
Abstract
Subsequence similarity matching in time series databases is an important research area for many applications. This paper presents a new approximate approach for automatic online subsequence similarity matching over massive data streams. With a simultaneous on-line segmentation and pruning algorithm over the incoming stream, the resulting piecewise linear representation of the data stream features high sensitivity and accuracy. The similarity definition is based on a permutation followed by a metric distance function, which provides the similarity search with flexibility, sensitivity and scalability. Also, the metric-based indexing methods can be applied for speed-up. To reduce the system burden, the event-driven similarity search is performed only when there is a potential event. The query sequence is the most recent subsequence of piecewise data representation of the incoming stream which is automatically generated by the system. The retrieved results can be analyzed in different ways according to the requirements of specific applications. This paper discusses an application for future data movement prediction based on statistical information. Experiments on real stock data are performed. The correctness of trend predictions is used to evaluate the performance of subsequence similarity matching.
Keywords
Computer ScienceEconomics, Econometrics and Finance
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.
Elsevier eBooksA Framework for Clustering Evolving Data Streams
1,781 Citations2003Charų C. Aggarwal, Philip S. Yu +2 more
A fundamentally different philosophy for data stream clustering is discussed which is guided by application-centered requirements and uses the concepts of a pyramidal time frame in conjunction with a microclustering approach.
Fast subsequence matching in time-series databases
1,720 Citations1994Christos Faloutsos, M. Ranganathan +1 more
Knowledge and Information SystemsDimensionality Reduction for Fast Similarity Search in Large Time Series Databases
1,572 Citations2001Eamonn Keogh, Kaushik Chakrabarti +2 more
This work introduces a new dimensionality reduction technique which it is called Piecewise Aggregate Approximation (PAA), and theoretically and empirically compare it to the other techniques and demonstrate its superiority.
M-tree: An Efficient Access Method for Similarity Search in Metric Spaces
1,534 Citations1997Paolo Ciaccia, Marco Patella +1 more
The results demonstrate that the Mtree indeed extends the domain of applicability beyond the traditional vector spaces, performs reasonably well in high-dimensional data spaces, and scales well in case of growing files.
An online algorithm for segmenting time series
1,109 Citations2002Eamonn Keogh, S. Chu +2 more
This paper undertake the first extensive review and empirical comparison of all proposed techniques for mining time-series data with fatal flaws and introduces a novel algorithm that is empirically show to be superior to all others in the literature.
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.
Symposium on Discrete AlgorithmsData structures and algorithms for nearest neighbor search in general metric spaces
984 Citations1993P.N. Yianilos
The up-tree (vantage point tree) is introduced in several forms, together‘ with &&ciated algorithms, as an improved method for these difficult search problems in general metric spaces.
ACM SIGMOD RecordIssues in data stream management
916 Citations2003Lukasz Golab, M. TAMER ÖZSU
The purpose of this paper is to review recent work in data stream management systems, with an emphasis on application requirements, data models, continuous query languages, and query evaluation.
IEEE Transactions on Knowledge and Data EngineeringClustering data streams: theory and practice
896 Citations2003Suvajyoti Guha, Adam Meyerson +3 more
This work describes a streaming algorithm that effectively clusters large data streams and provides empirical evidence of the algorithm's performance on synthetic and real data streams.
Locally adaptive dimensionality reduction for indexing large time series databases
873 Citations2001Eamonn Keogh, Kaushik Chakrabarti +2 more
This work introduces a new dimensionality reduction technique which it is shown how APCA can be indexed using a multidimensional index structure, and proposes two distance measures in the indexed space that exploit the high fidelity of APCA for fast searching.
SIAM Journal on ComputingMaintaining Stream Statistics over Sliding Windows
834 Citations2002Mayur Datar, Aristides Gionis +2 more
The problem of maintaining aggregates and statistics over data streams, with respect to the last N data elements seen so far, is considered, and it is shown that, using $O(\frac{1}{\epsilon} \log^2 N)$ bits of memory, the number of 1's can be estimated to within a factor of $1 + \ep silon$.
ACM SIGMOD RecordContinuous queries over data streams
724 Citations2001Shivnath Babu, Jennifer Widom
A general and flexible architecture for query processing in the presence of data streams is specified, which captures most previous work on continuous queries and data streams, as well as related concepts such as triggers and materialized views.
ACM SIGMOD RecordFast subsequence matching in time-series databases
713 Citations1994Christos Faloutsos, M. Ranganathan +1 more
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.
Information Processing LettersSatisfying general proximity / similarity queries with metric trees
698 Citations1991Jeffrey Uhlmann
Divide-and-conquer search strategies are described for satisfying proximity queries involving arbitrary distance metrics involving arbitrarydistance metrics.
Elsevier eBooksStatStream
655 Citations2002Yunyue Zhu, Dennis Shasha
This chapter solves the problem of maintaining multistream and time-delayed statistics in a scalable way that gives a guaranteed response time with high accuracy and Experiments conducted using synthetic and real data show that StatStream detects correlations efficiently and precisely.
Clustering data streams
628 Citations2002Suvajyoti Guha, Nita Mishra +2 more
This work gives constant-factor approximation algorithms for the k-median problem in the data stream model of computation in a single pass, and shows negative results implying that these algorithms cannot be improved in a certain sense.
Streaming-data algorithms for high-quality clustering
579 Citations2003Liadan O'Callaghan, Nita Mishra +3 more
This work describes a streaming algorithm that effectively clusters large data streams and provides empirical evidence of the algorithm's performance on synthetic and real data streams.
Efficiently supporting ad hoc queries in large datasets of time sequences
411 Citations1997Flip Korn, H. V. Jagadish +1 more
This paper shows how to compress a very large dataset comprising multiple distinct time sequences into a format that supports ad hoc querying, provided that a small error can be tolerated when the data is uncompressed.
Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries
379 Citations2001Anna C. Gilbert, Yannis Kotidis +2 more
This work presents general “sketch” based methods for capturing various linear projections of the data and use them to provide pointwise and rangesum estimation of data streams.
Similarity-based queries for time series data
346 Citations1997Davood Rafiei, Alberto O. Mendelzon
Distance-based indexing for high-dimensional metric spaces
332 Citations1997Tolga Bozkaya, Meral Özsoyoğlu
This paper introduces a distance based index structure called multi-vantage point (mvp) tree for similarity queries on high-dimensional metric spaces and shows that mvp-tree outperforms the vp-tree 20% to 80% for varying query ranges and different distance distributions.
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.
Indexing the Distance: An Efficient Method to KNN Processing
285 Citations2001Yu Cui, Beng Chin Ooi +2 more
An eAEcient method, called iDistance, for K-nearest neighbor (KNN) search in a high-dimensional space, which partitions the data and selects a reference point for each partition, and describes how appropriate choices here can adapt the index structure to the data distribution.
On computing correlated aggregates over continual data streams
278 Citations2001Johannes Gehrke, Flip Korn +1 more
This work proposes single-pass techniques for approximate computation of correlated aggregates over both landmark and sliding window views of a data stream of tuples, using a very limited amount of space and shows that this effectiveness is explained by the fact that these techniques exploit monotonicity and convergence properties of aggregate over data streams.
Symposium on Discrete AlgorithmsMaintaining stream statistics over sliding windows: (extended abstract)
256 Citations2002Mayur Datar, Aristides Gionis +2 more
Using the algorithm for the basic counting problem, one can adapt many other techniques to work for the sliding window model, with a multiplicative overhead of 1/εlog N) in memory and a 1 + ε factor loss in accuracy.
Content-Based Image Indexing
157 Citations1994Tzi‐cker Chiueh
This paper forms the content-based image indexing problem as a multi-dimensional nearest-neighbor search problem, and develops/implement an optimistic vantage-point tree algorithm that can dynamically adapt the indexed search process to the characteristics of given queries.
Using the fractal dimension to cluster datasets
144 Citations2000Daniel Barbará, Ping Chen
A new clustering algorithm, based in the fractal properties of the data sets, which is capable of recognizing clusters of arbitrary shape and which places points incrementally in the cluster for whic h the change in the Fractal dimension after adding the point is the least.
General match
141 Citations2002Yang‐Sae Moon, Kyu-Young Whang +1 more
General Match offers advantages of both methods: it can reduce window size effect by using large windows like FRM and, at the same time, can exploit point-filtering effect like Dual Match.
Lecture notes in computer scienceNews Sensitive Stock Trend Prediction
133 Citations2002Gabriel Pui Cheong Fung, Jeffrey Xu Yu +1 more
This paper investigates the immediate impact of news articles on the time series based on the Efficient Markets Hypothesis and proposes an algorithm, which is called guided clustering, to filter news articles with the help of the clusters that have been obtained from trends.
Segment-based approach for subsequence searches in sequence databases
91 Citations2001Sanghyun Park, Sang‐Wook Kim +1 more
The time warping distance can be applied to both whole sequence and subsequence searches and fits well with the databases where sequences are of different lengths.
Continually evaluating similarity-based pattern queries on a streaming time series
86 Citations2002Like Gao, X. Sean Wang
Fast Fourier Transform (FFT) is used to compute the cross correlations of the predicted series (with the values that have already arrived) and the database patterns, and to obtain predicted distances between the incoming time series at many future time positions and thedatabase patterns.
Series in machine perception and artificial intelligenceINDEXING OF COMPRESSED TIME SERIES
47 Citations2004Eugene Fink, Kevin Pratt
The effectiveness of the compression and retrieval for stock charts, meteorological data, and electroencephalograms is shown, and the user can control the trade-off between the speed and accuracy of retrieval.
Neural network technology for stock market index prediction
37 Citations2002Darmadi Komo, Chein‐I Chang +1 more
The experiments conducted in this study demonstrated that the RBF neural network is preferred over the multilayer perceptron network and is a promising candidate for stock market index predictions.
Lecture notes in computer scienceEfficient k-NN Search on Streaming Data Series
37 Citations2003Xiaoyan Liu, Hakan Ferhatosmanoğlu
This paper proposes efficient index structures and algorithms for various models of k nearest neighbor (k-NN) queries on multiple data streams and proposes index structures, called VA-Stream and VA + -Stream, which are built by dynamically quantizing the incoming dimensions.
Evaluating continuous nearest neighbor queries for streaming time series via pre-fetching
25 Citations2002Like Gao, Zhengrong Yao +1 more
Experiments show that pre-fetching improves the response time greatly over the direct use of traditional algorithms, even if the caching provided by the operating system is taken into consideration.