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.3965098e-05
Overall Rank: 9,077 | 36.92%
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,300	Online Windowed Subsequence Matching over Probabilistic Sequences	2012	SIGMOD	4.5392079e-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,825	Space-efficient Substring Occurrence Estimation	2011	PODS	5.3119504e-05
7,707	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD	4.6676985e-05
13,285	On the String Matching with k Differences in DNA Databases	2021	VLDB	-
10,373	The Complexity of Maximal Common Subsequence Enumeration	2025	PODS	4.1905499e-05
8,037	A New Approach for Processing Ranked Subsequence Matching Based on Ranked Union	2011	SIGMOD	4.5965282e-05
65	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00061977022
3,418	General Match: A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows	2002	SIGMOD	7.1129681e-05
8,775	The Inherent Time Complexity and An Efficient Algorithm for Subsequence Matching Problem	2022	VLDB	4.4500701e-05
5,883	Ranked Subsequence Matching in Time-Series Databases	2007	VLDB	5.2865165e-05
8,300	Online Windowed Subsequence Matching over Probabilistic Sequences	2012	SIGMOD	4.5392079e-05