A new approach for processing ranked subsequence matching based on ranked union

Wook Shin Han, Jinsoo Lee, Yang Sae Moon, Seung Won Hwang, Hwanjo Yu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationProceedings of SIGMOD 2011 and PODS 2011
PublisherAssociation for Computing Machinery
Number of pages12
ISBN (Print)9781450306614
Publication statusPublished - 2011
Event2011 ACM SIGMOD and 30th PODS 2011 Conference - Athens, Greece
Duration: 2011 Jun 122011 Jun 16

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078


Other2011 ACM SIGMOD and 30th PODS 2011 Conference

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems


Dive into the research topics of 'A new approach for processing ranked subsequence matching based on ranked union'. Together they form a unique fingerprint.

Cite this