Paper Info
Title
Ranked subsequence matching in time-series databases
Abstract
Existing work on similar sequence matching has focused on either whole matching or range subsequence matching. In this paper, we present novel methods for ranked subsequence matching under time warping, which finds top-k subsequences most similar to a query sequence from data sequences. To the best of our knowledge, this is the first and most sophisticated subsequence matching solution mentioned in the literature. Specifically, we first provide a new notion of the minimum-distance matching-window pair (MDMWP) and formally define the mdmwp-distance, a lower bound between a data subsequence and a query sequence. The mdmwp-distance can be computed prior to accessing the actual subsequence. Based on the mdmwp-distance, we then develop a ranked subsequence matching algorithm to prune unnecessary subsequence accesses. Next, to reduce random disk I/Os and bad buffer utilization, we develop a method of deferred group subsequence retrieval. We then derive another lower bound, the window-group distance, that can be used to effectively prune unnecessary subsequence accesses during deferred group-subsequence retrieval. Through extensive experiments with many data sets, we showcase the superiority of the proposed methods.
Year
Venue
Keywords
2007
VLDB
deferred group subsequence retrieval,data subsequence,unnecessary subsequence access,range subsequence matching,query sequence,time-series databases,actual subsequence,sophisticated subsequence,top-k subsequence,subsequence matching,ranked subsequence,subsequence matching algorithm,time series,lower bound
Field
DocType
Citations 
Data set,Longest common subsequence problem,Longest increasing subsequence,Dynamic time warping,Ranking,Computer science,Upper and lower bounds,Algorithm,Subsequence,Database,Blossom algorithm
Conference
33
PageRank 
References 
Authors
0.91
22
4
Name
Order
Citations
PageRank
Wook-Shin Han180557.85
Jinsoo Lee21276.95
Yang-sae Moon348945.58
Haifeng Jiang477134.60