Window-Accumulated Subsequence matching Problem is linear

Summary: Tackle window-accumulated subsequence matching: count all length-w text windows that contain pattern p as a subsequence, via a KMP-style automaton generalized to subsequences. Introduce MP-RAMs (a microprocessor-reflective RAM model) and give an online O(n) algorithm for the problem on MP-RAMs. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1186
Venue: PODS
Year: 1999
Pagerank: 4.400728e-05
Overall Rank: 9,081 | 36.83%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,306	Online Windowed Subsequence Matching over Probabilistic Sequences	2012	SIGMOD	4.5435639e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,813	Space-efficient Substring Occurrence Estimation	2011	PODS	5.3170565e-05
7,708	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD	4.6721808e-05
13,272	On the String Matching with k Differences in DNA Databases	2021	VLDB	-
10,361	The Complexity of Maximal Common Subsequence Enumeration	2025	PODS	4.1945683e-05
8,035	A New Approach for Processing Ranked Subsequence Matching Based on Ranked Union	2011	SIGMOD	4.6009403e-05
65	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00062029383
3,417	General Match: A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows	2002	SIGMOD	7.1195863e-05
8,778	The Inherent Time Complexity and An Efficient Algorithm for Subsequence Matching Problem	2022	VLDB	4.4543399e-05
5,878	Ranked Subsequence Matching in Time-Series Databases	2007	VLDB	5.2916009e-05
8,306	Online Windowed Subsequence Matching over Probabilistic Sequences	2012	SIGMOD	4.5435639e-05