Transducing Markov Sequences

Summary: Studies Markov-sequence queries via finite-state transducers: computing answer probabilities and top-k/ordered enumeration. Shows sub-exponential-approximate enumeration is intractable (even for fixed transducers), gives a matching heuristic, and isolates tractable regex-like extractor subclasses. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1503
Venue: PODS
Year: 2010
Pagerank: 4.1905499e-05
Overall Rank: 12,221 | 15.07%
DOI: -

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Benny Kimelfeld
2. Christopher Ré

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,331	Optimizing and Parallelizing Ranked Enumeration	2011	VLDB	5.5642069e-05
8,377	Probabilistic Management of OCR Data using an RDBMS	2012	VLDB	4.5277353e-05
9,429	Database Principles in Information Extraction	2014	PODS	4.3399748e-05

Outgoing Citations (Sorted by Pagerank)

Showing 20 of 20 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
8	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015436578
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057797415
149	Trio: A System for Integrated Management of Data, Accuracy, and Lineage	2005	CIDR	0.00041085859
432	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023349408
463	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.00022497894
477	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00022205608
702	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00017848789
1,072	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS	0.00014256848
1,123	A Transducer-Based XML Query Processor	2002	VLDB	0.00013836955
1,269	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012911894
1,972	Approximate Lineage for Probabilistic Databases	2008	VLDB	9.8937766e-05
2,883	MayBMS: A Probabilistic Database Management System	2009	SIGMOD	7.9665191e-05
3,395	Event Queries on Correlated Probabilistic Streams	2008	SIGMOD	7.1402267e-05
3,929	Maximally Joining Probabilistic Data	2007	PODS	6.620459e-05
4,439	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.1806955e-05
5,301	Running Tree Automata on Probabilistic XML	2009	PODS	5.5749031e-05
5,767	Indexing Correlated Probabilistic Databases	2009	SIGMOD	5.3341473e-05
6,682	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	4.9596732e-05
6,837	Capturing Data Uncertainty in High-Volume Stream Processing	2009	CIDR	4.9063121e-05
13,560	Lahar Demonstration: Warehousing Markovian Streams	2009	VLDB	-

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,703	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010820803
6,284	Probabilistic XML via Markov Chains	2010	VLDB	5.1232186e-05
3,256	On Probabilistic Fixpoint and Markov Chain Query Languages	2010	PODS	7.3135363e-05
12,050	E-Matching: Event Processing over Noisy Sequences in Real Time	2013	SIGMOD	4.1905499e-05
5,807	Finding Frequent Items in Probabilistic Data	2008	SIGMOD	5.3189104e-05
4,065	Similarity-Based Queries	1995	PODS	6.4759059e-05
9,365	Probabilistic Nearest Neighbor Queries on Uncertain Moving Object Trajectories	2014	VLDB	4.3468776e-05
2,297	Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation	2019	PODS	9.0812384e-05
8,146	Approximate Substring Matching over Uncertain Strings	2011	VLDB	4.5724134e-05
8,300	Online Windowed Subsequence Matching over Probabilistic Sequences	2012	SIGMOD	4.5392079e-05