A New Approach for Processing Ranked Subsequence Matching Based on Ranked Union

Summary: Models ranked subsequence matching as ranked union; introduces MSEQ and MSEQ-distance for lower-bounds and pruning. Cost-aware density-based PQ scheduling eliminates HLMJ overhead; yields up to 2–3 orders of magnitude speedups over HLMJ and PSM on real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4466
Venue: SIGMOD
Year: 2011
Pagerank: 5.5049255e-05
Overall Rank: 8,026 | 44.94%
DOI: 10.1145/1989323.1989371

Incoming Non-self Citations Over Time

Authors

1. Wook-Shin Han (Kyungpook National University)
2. Jinsoo Lee (Kyungpook National University)
3. Yang-Sae Moon (Kangwon National University)
4. Seung-won Hwang (Pohang University of Science and Technology)
5. Hwanjo Yu (Pohang University of Science and Technology)

BibTeX Citation

@inproceedings{han_sigmod11,
        title = {{A New Approach for Processing Ranked Subsequence Matching Based on Ranked Union}},
        author = {Han, Wook-Shin and Lee, Jinsoo and Moon, Yang-Sae and Hwang, Seung-won and Yu, Hwanjo},
        series = {{SIGMOD} '11},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1989323.1989371},
        url = {https://dl.acm.org/doi/10.1145/1989323.1989371},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,858	A Generic Framework for Efficient and Effective Subsequence Retrieval	2012	VLDB	5.7523396e-05
12,120	SMiLer: A Semi-Lazy Time Series Prediction System for Sensors	2015	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010828372
41	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00046675394
108	Optimizing Multi-Feature Queries for Image Databases	2000	VLDB	0.00033228866
468	Fast Time Sequence Indexing for Arbitrary Lp Norms	2000	VLDB	0.00017986163
601	Exact Indexing of Dynamic Time Warping	2002	VLDB	0.00015870156
973	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012874284
1,046	Warping Indexes with Envelope Transforms for Query by Humming	2003	SIGMOD	0.00012440091
2,928	A Decade of Progress in Indexing and Mining Large Time Series Databases	2006	VLDB	7.9526656e-05
3,125	General Match: A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows	2002	SIGMOD	7.7344198e-05
3,440	Approximate Embedding-Based Subsequence Matching of Time Series	2008	SIGMOD	7.4142918e-05
3,500	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD	7.3597562e-05
5,592	Ranked Subsequence Matching in Time-Series Databases	2007	VLDB	6.1552372e-05
8,107	Anticipatory DTW for Efficient Similarity Search in Time Series Databases	2009	VLDB	5.4851245e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,500	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD
2	6,780	Discovering Longest-lasting Correlation in Sequence Databases	2013	VLDB
3	7,692	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD
4	8,542	Online Windowed Subsequence Matching over Probabilistic Sequences	2012	SIGMOD
5	7,299	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD
6	10,086	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB
7	6,858	A Generic Framework for Efficient and Effective Subsequence Retrieval	2012	VLDB
8	8,780	The Inherent Time Complexity and An Efficient Algorithm for Subsequence Matching Problem	2022	VLDB
9	41	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD
10	5,592	Ranked Subsequence Matching in Time-Series Databases	2007	VLDB