Data Mining in Time Series Databases
Series in machine perception and artificial intelligencePublished 1 June 2004
Mark Last, Abraham Kandel, Horst Bunke
Citations227
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 Survey of Recent Methods for Efficient Retrieval of Similar Time Sequences and Change Detection in Classification Models of Data Mining.
Abstract
A Survey of Recent Methods for Efficient Retrieval of Similar Time Sequences (H M Lie) Indexing of Compressed Time Series (E Fink & K Pratt) Boosting Interval-Based Literal: Variable Length and Early Classification (J J Rodriguez Diez) Segmenting Time Series: A Survey and Novel Approach (E Keogh et al) Indexing Similar Time Series under Conditions of Noise (M Vlachos et al) Classification of Events in Time Series of Graphs (H Bunke & M Kraetzl) Median Strings - A Review (X Jiang et al) Change Detection in Classification Models of Data Mining (G Zeira et al).
Keywords
Computer Science
Modern Information Retrieval
11,544 Citations1999Ricardo Baeza‐Yates, Berthier Ribeiro‐Neto
NatureExploring complex networks
8,339 Citations2001Steven H. Strogatz
This work aims to understand how an enormous network of interacting dynamical systems — be they neurons, power stations or lasers — will behave collectively, given their individual dynamics and coupling architecture.
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.
Introduction to Graph Theory
5,792 Citations2010
This chapter discusses graph theory's roots in Euler's Formula, and some examples of k-chromatic and k-connected Graphs, as well as some of the more extreme examples, including Ramsey Theory and Random Graphs.
Cartographica The International Journal for Geographic Information and GeovisualizationALGORITHMS FOR THE REDUCTION OF THE NUMBER OF POINTS REQUIRED TO REPRESENT A DIGITIZED LINE OR ITS CARICATURE
4,207 Citations1973David H. Douglas, Thomas K. Peucker
IEEE Transactions on Pattern Analysis and Machine IntelligenceMedical image analysis: progress over two decades and the challenges ahead
4,160 Citations2000James S. Duncan, Nicholas Ayache
A look at progress in the field over the last 20 years is looked at and some of the challenges that remain for the years to come are suggested.
Springer texts in statisticsIntroduction to Time Series and Forecasting
3,830 Citations2002Peter J. Brockwell, Richard A. Davis
Algorithms on strings, trees, and sequences: computer science and computational biology
3,529 Citations1997Dan Gusfield
Journal of the Autonomic Nervous SystemElectroencephalography—Basic principles, clinical applications and related fields
3,452 Citations1982
Similarity Search in High Dimensions via Hashing
3,108 Citations1999Aristides Gionis, Piotr Indyk +1 more
Experimental results indicate that the novel scheme for approximate similarity search based on hashing scales well even for a relatively large number of dimensions, and provides experimental evidence that the method gives improvement in running time over other methods for searching in highdimensional spaces based on hierarchical tree decomposition.
Journal of the ACMThe String-to-String Correction Problem
3,063 Citations1974Robert A. Wagner, Michael J. Fischer
An algorithm is presented which solves the string-to-string correction problem in time proportional to the product of the lengths of the two strings.
Cambridge University Press eBooksAlgorithms on Strings, Trees and Sequences
3,045 Citations1997Dan Gusfield
Ukkonen’s method is the method of choice for most problems requiring the construction of a suffix tree, and it will be presented first because it is easier to understand.
Knowledge Discovery and Data MiningUsing dynamic time warping to find patterns in time series
2,900 Citations1994Donald J. Berndt, James Clifford
Preliminary experiments with a dynamic programming approach to pattern detection in databases, based on the dynamic time warping technique used in the speech recognition field, are described.
Computer Vision Graphics and Image ProcessingA survey of thresholding techniques
2,658 Citations1988Prasanna K. Sahoo, Soheil Soltani +1 more
This paper presents a survey of thresholding techniques and attempts to evaluate the performance of some automatic global thresholding methods using the criterion functions such as uniformity and shape measures.
IEEE Transactions on Knowledge and Data EngineeringData mining: an overview from a database perspective
2,221 Citations1996Ming-Syan Chen⋆, Jiawei Han +1 more
This article provides a survey, from a database researcher's point of view, on the data mining techniques developed recently, a classification of the available data mining Techniques, and a comparative study of such techniques is presented.
Mining high-speed data streams
2,180 Citations2000Pedro Domingos, Geoff Hulten
This paper describes and evaluates VFDT, an anytime system that builds decision trees using constant memory and constant time per example, and applies it to mining the continuous stream of Web access data from the whole University of Washington main campus.
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.
Knowledge and Information SystemsExact indexing of dynamic time warping
1,949 Citations2004Eamonn Keogh, Chotirat Ann Ratanamahatana
This work introduces a novel technique for the exact indexing of Dynamic time warping and proves its vast superiority over all competing approaches in the largest and most comprehensive set of time series indexing experiments ever undertaken.
Introduction to Wavelets and Wavelet Transforms: A Primer
1,805 Citations1997C.S. Burrus, Ramesh A. Gopinath +3 more
This work describes the development of the Basic Multiresolution Wavelet System and some of its components, as well as some of the techniques used to design and implement these systems.
Machine LearningKnowledge Acquisition Via Incremental Conceptual Clustering
1,754 Citations1987Douglas Fisher
COBWEB is a conceptual clustering system that organizes data so as to maximize inference ability, and is incremental and computationally economical, and thus can be flexibly applied in a variety of domains.
Mining time-changing data streams
1,725 Citations2001Geoff Hulten, Laurie Spencer +1 more
An efficient algorithm for mining decision trees from continuously-changing data streams, based on the ultra-fast VFDT decision tree learner is proposed, called CVFDT, which stays current while making the most of old data by growing an alternative subtree whenever an old one becomes questionable, and replacing the old with the new when the new becomes more accurate.
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.
A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces
1,513 Citations1998Roger Weber, Hans‐Jörg Schek +1 more
It is shown formally that partitioning and clustering techniques for similarity search in HDVSs exhibit linear complexity at high dimensionality, and that existing methods are outperformed on average by a simple sequential scan if the number of dimensions exceeds around 10.
Machine LearningLearning in the Presence of Concept Drift and Hidden Contexts
1,432 Citations1996Gerhard Widmer, Miroslav Kubát
A family of learning algorithms that flexibly react to concept drift and can take advantage of situations where contexts reappear are described, including a heuristic that constantly monitors the system's behavior.
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.
A brief introduction to boosting
1,208 Citations1999Robert E. Schapire
The boosting algorithm AdaBoost is introduced, and the underlying theory of boosting is explained, including an explanation of why boosting often does not suffer from overfitting.
IEEE Transactions on Systems Man and CyberneticsA distance measure between attributed relational graphs for pattern recognition
988 Citations1983Alberto Sanfeliu, King‐Sun Fu
A method to determine a distance measure between two nonhierarchical attributed relational graphs is presented and an application of this distance measure to the recognition of lower case handwritten English characters is presented.
Journal of Computational BiologyOn the Complexity of Multiple Sequence Alignment
932 Citations1994Lusheng Wang, Tao Jiang
It is shown that the first problem is NP-complete and the second is MAX SNP-hard; the complexity of tree alignment with a given phylogeny is also considered.
ACM SIGMOD RecordIndexing the positions of continuously moving objects
916 Citations2000Simonas Šaltenis, Christian S. Jensen +2 more
IBM Systems JournalQuery-by-Example: A data base language
874 Citations1977Moshé M. Zloof
Discussed is a high-level data base management language that provides the user with a convenient and unified interface to query, update, define, and control a data base.
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.
Scaling up dynamic time warping for datamining applications
822 Citations2000Eamonn Keogh, Michael J. Pazzani
This paper introduces a modification of DTW which operates on a higher level abstraction of the data, in particular, a Piecewise Aggregate Approximation (PAA) which allows us to outperform DTW by one to two orders of magnitude, with no loss of accuracy.
WaveCluster: A Multi-Resolution Clustering Approach for Very Large Spatial Databases
753 Citations1998Gholamhosein Sheikholeslami, Surojit Chatterjee +1 more
WaveCluster is proposed, a novel clustering approach based on wavelet transforms which can effectively identify arbitrary shape clusters at different degrees of accuracy and is highly efficient in terms of time complexity.
IEEE Transactions on Pattern Analysis and Machine IntelligenceAn eigendecomposition approach to weighted graph matching problems
718 Citations1988Shinji Umeyama
An approximate solution to the weighted-graph-matching problem is discussed for both undirected and directed graphs and an analytic approach is used instead of a combinatorial or iterative approach to the optimum matching problem.
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.
Lecture notes in computer scienceThe power of decision tables
707 Citations1995Ron Kohavi
Experimental results show that on artificial and real-world domains containing only discrete features, IDTM, an algorithm inducing decision tables, can sometimes outperform state-of-the-art algorithms such as C4.5.
Research Showcase @ Carnegie Mellon University (Carnegie Mellon University)Fast Time Sequence Indexing for Arbitrary Lp Norms
664 Citations2018Byoung-Kee Yi, Christos Faloutsos
This paper presents a novel and fast indexing scheme for time sequences, when the distance function is any of arbitrary Lp norms including the popular Euclidean distance (L2 norm), and achieves significant speedups over the state of the art.
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.
Rule discovery from time series
627 Citations1998Gautam Das, King-Ip Lin +3 more
Lecture notes in computer scienceCapturing the Uncertainty of Moving-Object Representations
482 Citations1999Dieter Pfoser, Christian S. Jensen
On-going research in the representation of the positions of moving-point objects is reported on, where object positions are sampled using the Global Positioning System, and interpolation is applied to determine positions in-between the samples.
Event detection from time series data
479 Citations1999Valery Guralnik, Jaideep Srivastava
An iterative algorithm is proposed that fits a model to a time segment, and uses a likelihood criterion to determine if the segment should be partitioned further, i.e. if it contains a new changepoint.
Trajectory clustering with mixtures of regression models
445 Citations1999Scott Gaffney, Padhraic Smyth
This paper addresses the problem of clustering trajectories, namely sets of short quences of data measured as a function of a dependent variable such as time, and develops generalizations of the method to handle non-parametric (kernel) regression components as well as multi-dimensional outputs.
Computer Vision and Image UnderstandingAverage Brain Models: A Convergence Study
421 Citations2000Alexandre Guimond, Jean Meunier +1 more
A completely automatic method to build stable average anatomical models of the human brain using a set of magnetic resonance (MR) images and results showing convergence toward the centroid of the image set used for the computation of the model are provided.
Finding surprising patterns in a time series database in linear time and space
399 Citations2002Eamonn Keogh, Stefano Lonardi +1 more
A novel technique is introduced that defines a pattern surprising if the frequency of its occurrence differs substantially from that expected by chance, given some previously seen data.
On indexing mobile objects
392 Citations1999George Kollios, Dimitrios Gunopulos +1 more
A lower bound on the number of I/O’s needed to answer the d-dimensional problem is given and a practical approximation algorithm also in the dynamic, external memory setting, which has linear space and expected logarithmic query time is given.
IEEE Transactions on Visualization and Computer GraphicsVisualizing network data
385 Citations1995Richard A. Becker, Stephen G. Eick +1 more
This work introduces direct manipulation techniques that permit the graphs to continue to reveal relationships in the context of much more data, and parameterized the static displays so that interesting views may easily be discovered interactively.
IEEE Transactions on Knowledge and Data EngineeringMobile computing and databases-a survey
384 Citations1999Daniel Barbará
This paper is an effort to survey these techniques and to classify this research in a few broad areas in the area of data management in mobile computing.
SIAM ReviewAn Overview of Sequence Comparison: Time Warps, String Edits, and Macromolecules
350 Citations1983Joseph B. Kruskal
This paper surveys the applications, methods and theory of sequence comparison, which incorporate two basic ideas a systematic concept of distance between sequences, and elegant recursive algorithms for doing the necessary computations.
Similarity-based queries for time series data
346 Citations1997Davood Rafiei, Alberto O. Mendelzon
IEEE Transactions on Pattern Analysis and Machine IntelligenceA new algorithm for error-tolerant subgraph isomorphism detection
335 Citations1998Bettina Messmer, Horst Bunke
A new algorithm for error-correcting subgraph isomorphism detection from a set of model graphs to an unknown input graph is proposed based on a compact representation of the model graphs that can be combined with a future cost estimation method that greatly improves its run-time performance.
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.
IEEE Transactions on Pattern Analysis and Machine IntelligenceComputation of normalized edit distance and applications
327 Citations1993Andrés Marzal, Enrique Vidal
Experiments in hand-written digit recognition are presented, revealing that the normalized edit distance consistently provides better results than both unnormalized or post-normalized classical edit distances.
An index-based approach for similarity search supporting time warping in large sequence databases
309 Citations2002Sang‐Wook Kim, Sanghyun Park +1 more
A new distance function D/sub tw-lb/ that consistently underestimates the time warping distance and also satisfies the triangular inequality is devised and achieves significant speedup up to 43 times with real-world S&P 500 stock data and up to 720 times with very large synthetic data.
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.
Landmarks: a new model for similarity-based pattern querying in time series databases
300 Citations2002Chang-Shing Perng, Houqiao Wang +2 more
The landmark model is presented, a model for time series that yields new techniques for similarity-based time series pattern querying and a generalized approach for removing noise from raw time series without smoothing out the peaks and bottoms.
ACM Transactions on Database SystemsIndexing large metric spaces for similarity search queries
275 Citations1999Tolga Bozkaya, Meral Özsoyoğlu
The multivantage point tree structure (mvp-tree) that uses more than one vantage point to partiton the space into spherical cuts at each level is introduced and generalize the idea of using multiple vantage points and the results show that, after all, it may be best to use a large number of vantage points in an internal node in order to end up with a single directory node and keep as many of the precomputed distances as possible to provide more efficient filtering during search operations.
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.
IEEE Transactions on Knowledge and Data EngineeringHaar wavelets for efficient similarity search of time-series: with and without time warping
258 Citations2003Fai Chan, A.W.-C. Fu +1 more
A Haar wavelet-based approximation function for time warping distance is suggested, called Low Resolution Time Warping, which results in less computation by trading off a small amount of accuracy, and is highly effective in suppressing the number of false alarms in similarity search.
A comparison of DFT and DWT based similarity search in time-series databases
252 Citations2000Yi-Leh Wu, Divyakant Agrawal +1 more
The feasibility of replacing DFT by DWT is explored with a comprehensive analysis of the DFT and DWT as matching functions in time-series databases and the results show that although the DWT based technique has several advantages, it does not reduce relativ e matching error and does not increase query precision in similarity searc h as suggested by previous works.
Lecture notes in computer scienceA Simple Dimensionality Reduction Technique for Fast Similarity Search in Large Time Series Databases
251 Citations2000Eamonn Keogh, Michael J. Pazzani
A novel-dimensionality reduction technique is introduced that supports an indexing algorithm that is more than an order of magnitude faster than the previous best known method and has numerous other advantages.
Theory of Computing SystemsOn covering problems of codes
251 Citations1997M. Frances, Ami Litman
The main result is that the decision problem associated with the Covering Radius of arbitrary binary codes is NP-complete and the 3SAT problem is polynomially reducible to the Radius decision problem.
Querying Shapes of Histories
247 Citations1995Rakesh Agrawal, Giuseppe Psaila +2 more
The SDL operators are designed to be greedy to reduce non-determinism, which in turn substantially reduces the amount of back-tracking in the implementation and transformation rules for rewriting an SDL expression into a more e cient form as well as an index structure for speeding up the execution of SDL queries.
Applied IntelligenceIncremental Feature Selection
239 Citations1998Huan Liu, Rudy Setiono
Experimental results suggest that the probabilistic algorithm is effective in obtaining optimal/suboptimal feature subsets and its incremental version expedites feature selection further when the number of patterns is large and can scale up without sacrificing the quality of selected features.
Journal of Computer and System SciencesIndexing Moving Points
235 Citations2003Pankaj K. Agarwal, Lars Arge +1 more
An efficient indexing scheme to answer approximate nearest-neighbor queries among moving points, and a tradeoff between the query time and the number of times the index needs to be updated as the points move is obtained.
IEEE Transactions on Pattern Analysis and Machine IntelligenceAn median graphs: properties, algorithms, and applications
233 Citations2001Xiaoyi Jiang, Andreas Münger +1 more
This work extends the median concept to the domain of graphs and introduces the novel concepts of set median and generalized median of a set of graphs, and studies properties of both types of median graphs.
Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces
230 Citations2000Kaushik Chakrabarti, Sharad Mehrotra
Local Dimensionality Reduction (LDR) is proposed that tries to find local correlations in the data and performs dimensionality reduction on the locally correlated clusters of data individually and an index structure is developed that exploits the correlated clusters to efficiently support point, range and k-nearest neighbor queries over high dimensional datasets.
Discrete MathematicsLaplace eigenvalues of graphs—a survey
229 Citations1992Bojan Mohar
Several applications of Laplace eigenvalues of graphs in graph theory and combinatorial optimization are outlined.
IEEE Transactions on Pattern Analysis and Machine IntelligenceSymbol recognition by error-tolerant subgraph matching between region adjacency graphs
224 Citations2001Josep Lladós, Enric Martı́ +1 more
An error-tolerant subgraph isomorphism algorithm formulated in terms of region adjacency graphs, which allows matching computing under distorted inputs and also reaching a solution in a near polynomial time.
Quantitative measures of change based on feature organization: eigenvalues and eigenvectors
215 Citations1996Sudeep Sarkar, Kim L. Boyer
Lecture notes in computer scienceScaling up Dynamic Time Warping to Massive Datasets
207 Citations1999Eamonn Keogh, Michael J. Pazzani
This paper introduces a modification of DTW which operates on a higher level abstraction of the data, in particular, a piecewise linear representation and demonstrates that this approach allows us to outperform DTW by one to three orders of magnitude.
The Quest Data mining System
196 Citations1996Rakesh Agrawal, Manish Mehta +4 more
The goal of the Quest project at the IBM Almaden Research center is to develop technology to enable a new breed of data-intensive decision-support applications.
IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics)Knowledge discovery in time series databases
191 Citations2001Mark Last, Yaron Klein +1 more
This correspondence introduces a general methodology for knowledge discovery in TSDB, based on signal processing techniques and the information-theoretic fuzzy approach to knowledge discovery, and demonstrates it on two types of time series: stock-market data and weather data.
Fast time-series searching with scaling and shifting
165 Citations1999Kelvin Kam Wing Chu, Man Hon Wong
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.
Similarity search for multidimensional data sequences
156 Citations2002Seok‐Lyong Lee, Seok-Ju Chun +3 more
To prune irrelevant sequences in a database, correct and efficient similarity functions are introduced and 73-94 percent of irrelevant sequences are pruned using the proposed method, resulting in 16-28 times faster response time compared with that of the sequential search.
SIAM Journal on Matrix Analysis and ApplicationsOn the Quality of Spectral Separators
149 Citations1998Stephen Guattery, Gary L. Miller
This work considers two popular spectral separator algorithms and provides counterexamples showing that these algorithms perform poorly on certain graphs, and introduces some facts about the structure of eigenvectors of certain types of Laplacian and symmetric matrices.
Elsevier eBooksA Comparative Evaluation of Voting and Meta-learning on Partitioned Data
148 Citations1995Philip K. Chan, Salvatore J. Stolfo
This paper evaluates different techniques for learning from partitioned data and the meta-learning approach is empirically compared with techniques in the literature that aim to combine multiple evidence to arrive at one prediction.
International Journal of Image and GraphicsSEARCH FOR PATTERNS IN COMPRESSED TIME SERIES
147 Citations2002Kevin Pratt, Eugene Fink
Experiments show the effectiveness of this technique for indexing of stock prices, weather data, electroencephalograms and electroencephalograms for indexing a database of time series.
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.
Time-Series Similarity Queries Employing a Feature-Based Approach
143 Citations1999R.J. Alcock
This paper transforms sequences into a feature vector and the Euclidean distance between the feature vectors is then calculated, and shows that this approach is superior for finding similar sequences.
Variable length queries for time series data
141 Citations2002Tamer Kahveci, Ambuj K. Singh
A new indexing technique that works well for variable length queries that is to store index structures at different resolutions for a given dataset by exploiting the power of wavelets.
IEEE Transactions on Biomedical EngineeringScan-Along Polygonal Approximation for Data Compression of Electrocardiograms
136 Citations1983Masa Ishijima, Soon-Bum Shin +2 more
Three fast and efficient "scan-along" algorithms for compressing digitized electrocardiographic data are described, based on the minimum perimeter polygonal approximation for digitized curves.
Cambridge University Press eBooksApplications to graph theory
135 Citations2018Cheryl E. Praeger, Csaba Schneider
An overview of the applications of graph theory in various fields to some extent is given but mainly focuses on the computer discipline applications that uses graph theoretical concepts.
Space-time modeling with long-memory dependence:Assessing Ireland's wind power resource.
132 Citations1989John Haslett
Pattern RecognitionHierarchical attributed graph representation and recognition of handwritten chinese characters
120 Citations1991Si Wei Lu, Ying Ren +1 more
A new method of recognizing handwritten Chinese characters using a structural representation called hierarchical attributed graph representation (HAGR) which can tolerate the variations of HAGR which reflect the instabilities or variabilities of handwrittenChinese characters resulting from different writing styles.
International Journal of Computer VisionOn Averaging Rotations
113 Citations2001Claus Gramkow
Two common approaches to averaging rotations are compared and it is shown that the two approximative methods can be derived from natural approximations to the Riemannian metric, and that the subsequent corrections are inherent in the least squares estimation.
Theoretical Computer ScienceTopology of strings: Median string is NP-complete
110 Citations2000Colin de la Higuera, Francisco Casacuberta
It is proved that computing the median string corresponds to a NP-complete decision problems, thus proving that this problem is NP-hard.
Relevance feedback retrieval of time series data
109 Citations1999Eamonn Keogh, Michael J. Pazzani
A novel approach to retrieval of time series data is described by using relevance feedback from the user to adjust the similarity metric by introducing a profile that encodes the user's subjective notion of similarity in a domain.
IEEE Transactions on Knowledge and Data EngineeringQuerying time series data based on similarity
102 Citations2000Davood Rafiei, Alberto O. Mendelzon
This work presents a query processing algorithm that uses the underlying multidimensional index built over the data set to efficiently answer similarity queries and proposes a generalization of this algorithm for simultaneously handling multiple transformations at a time.
Pattern RecognitionSyntactic recognition of ECG signals by attributed finite automata
101 Citations1995Antti Koski, Martti Juhola +1 more
A syntactic pattern recognition method of electrocardiograms (ECG) is described in which attributed automata are used to execute the analysis of ECG signals.
Studies in fuzziness and soft computingData Mining and Computational Intelligence
101 Citations2001Janusz Kacprzyk, Abraham Kandel +1 more
This volume focuses on some of the hardest, and yet unsolved, issues of data mining like understandability of patterns, finding complex relationships between attributes, handling missing and noisy data, mining very large datasets, change detection in time series and integration of the discovery process with database management systems.
Supporting content-based searches on time series via approximation
96 Citations2002Changzhou Wang, Xuezhao Wang
The paper introduces two specific approximation methods, one is wavelet based and the other line-fitting based, and shows that both approximation methods significantly reduce the query processing time without introducing intolerable errors.
International Journal of Computer VisionRelaxing the Triangle Inequality in Pattern Matching
94 Citations1998Ronald Fagin, Larry Stockmeyer
This paper shows that one of the measures used for distances between shapes in (an experimental version of) IBM's QBIC1 ("Query by Image Content") system satisfies a relaxed triangle inequality, although it does not satisfy the triangle inequality.
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.
Lecture notes in computer scienceKnowledge-Based Event Detection in Complex Time Series Data
89 Citations1999Jim Hunter, Neil McIntosh
This paper describes an approach to the detection of events in complex, multi-channel, high frequency data and the preliminary results are encouraging, with an accuracy of identification of 89%.
Pattern RecognitionVideo indexing and similarity retrieval by largest common subgraph detection using decision trees
86 Citations2001Kim Shearer, Horst Bunke +1 more
A new algorithm based on similar principles to solve the largest common subgraph problem is presented, which significantly reduces the computational complexity of detection of the LCSG between a known database of models, and a query given on-line.
Knowledge discovery and data mining : the info-fuzzy network (IFN) methodology
79 Citations2000Oded Maimon
This work presents an Information-Theoretic Approach to Knowledge Discovery with a focus on data pre-processing and post-processing, and describes the development of information-theoretic Connectionist Networks.
Evaluating a class of distance-mapping algorithms for data mining and clustering
77 Citations1999Jason Tsong-Li Wang, Xiong Wang +4 more
Five distance-mapping algorithms are presented and experiments show the superiority of three hybrid heuristics that combine the two algorithms in different ways, implying that FastMap and MetricMap capture complementary information about distance metrics and therefore can be used together to great benefit.
…