Name
Abstract | ||
|---|---|---|
Ranked subsequence matching finds top-k subsequences most similar to a given query sequence from data sequences. Recently, Han et al. [12] proposed a solution (referred to here as HLMJ) to this problem by using the concept of the minimum distance matching window pair (MDMWP) and a global priority queue. By using the concept of MDMWP, HLMJ can prune many unnecessary accesses to data subsequences using a lower bound distance. However, we notice that HLMJ may incur serious performance overhead for important types of queries. In this paper, we propose a novel systematic framework to solve this problem by viewing ranked subsequence matching as ranked union. Specifically, we propose a notion of the matching subsequence equivalence class (MSEQ) and a novel lower bound called the MSEQ-distance. To completely eliminate the performance problem of HLMJ, we also propose a cost-aware density-based scheduling technique, where we consider both the density and cost of the priority queue. Extensive experimental results with many real datasets show that the proposed algorithm outperforms HLMJ and the adapted PSM [22], a state-of-the-art index-based merge algorithm supporting non-monotonic distance functions, by up to two to three orders of magnitude, respectively. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/1989323.1989371 | SIGMOD Conference |
Keywords | Field | DocType |
minimum distance,performance problem,non-monotonic distance function,data sequence,matching subsequence equivalence class,top-k subsequence,novel systematic framework,global priority queue,new approach,lower bound distance,ranked subsequence matching,lower bound,priority queue,distance function,indexation,time series data | Merge algorithm,Data mining,Longest increasing subsequence,Ranking,Upper and lower bounds,Scheduling (computing),Computer science,Priority queue,Equivalence class,Subsequence | Conference |
Citations | PageRank | References |
13 | 0.55 | 21 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wook-Shin Han | 1 | 805 | 57.85 |
| Jinsoo Lee | 2 | 127 | 6.95 |
| Yang-sae Moon | 3 | 489 | 45.58 |
| Seung-Won Hwang | 4 | 1111 | 90.50 |
| Hwanjo Yu | 5 | 1715 | 114.02 |