Discovering longest-lasting correlation in sequence databases
Authors:
Open Access
- 1 September 2013
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 6 (14) , 1666-1677
Abstract
Most existing work on sequence databases use correlation (e.g., Euclidean distance and Pearson correlation) as a core function for various analytical tasks. Typically, it requires users to set a length for the similarity queries. However, there is no steady way to define the proper length on different application needs. In this work we focus on discovering longest-lasting highly correlated subsequences in sequence databases, which is particularly useful in helping those analyses without prior knowledge about the query length. Surprisingly, there has been limited work on this problem. A baseline solution is to calculate the correlations for every possible subsequence combination. Obviously, the brute force solution is not scalable for large datasets. In this work we study a space-constrained index that gives a tight correlation bound for subsequences of similar length and offset by intra-object grouping and inter-object grouping techniques. To the best of our knowledge, this is the first index to support normalized distance metric of arbitrary length subsequences. Extensive experimental evaluation on both real and synthetic sequence datasets verifies the efficiency and effectiveness of our proposed methods.Keywords
This publication has 26 references indexed in Scilit:
- Embedding-based subsequence matching in time-series databasesACM Transactions on Database Systems, 2011
- Supporting exact indexing of arbitrarily rotated shapes and periodic time series under Euclidean and warping distance measuresThe VLDB Journal, 2008
- Using multiple indexes for efficient subsequence matching in time-series databasesInformation Sciences, 2007
- Experiencing SAX: a novel symbolic representation of time seriesData Mining and Knowledge Discovery, 2007
- Clustering of time series data—a surveyPattern Recognition, 2005
- High-resolution QRS fiducial point corrections in sparsely sampled ECG recordingsPhysiological Measurement, 2005
- Data clusteringACM Computing Surveys, 1999
- Fast subsequence matching in time-series databasesACM SIGMOD Record, 1994
- The R*-tree: an efficient and robust access method for points and rectanglesACM SIGMOD Record, 1990
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975