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: 1502
Venue: PODS
Year: 2010
Pagerank: 5.093636e-05
Overall Rank: 12,408 | 14.87%
DOI: 10.1145/1807085.1807090

Incoming Non-self Citations Over Time

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

Authors

1. Benny Kimelfeld (IBM)
2. Christopher Ré (University of Wisconsin)

BibTeX Citation

@inproceedings{kimelfeld_pods10,
        address = {New York, NY, USA},
        series = {{PODS} '10},
        title = {{Transducing Markov Sequences}},
        url = {https://dl.acm.org/doi/10.1145/1807085.1807090},
        doi = {10.1145/1807085.1807090},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kimelfeld, Benny and Ré, Christopher},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,431	Database Principles in Information Extraction	2014	PODS	6.7088601e-05
8,013	Optimizing and Parallelizing Ranked Enumeration	2011	VLDB	5.5073426e-05
8,585	Probabilistic Management of OCR Data using an RDBMS	2012	VLDB	5.4075213e-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
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010828372
50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00043596705
125	Trio: A System for Integrated Management of Data, Accuracy, and Lineage	2005	CIDR	0.00030932014
337	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00020783399
359	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.0002023153
414	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00018893507
683	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00015005338
1,041	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012453494
1,082	A Transducer-Based XML Query Processor	2002	VLDB	0.00012257574
1,429	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS	0.00010811133
1,752	Approximate Lineage for Probabilistic Databases	2008	VLDB	9.8358116e-05
2,775	MayBMS: A Probabilistic Database Management System	2009	SIGMOD	8.1359291e-05
3,050	Event Queries on Correlated Probabilistic Streams	2008	SIGMOD	7.8140428e-05
4,136	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.8810237e-05
4,187	Maximally Joining Probabilistic Data	2007	PODS	6.8456588e-05
5,346	Running Tree Automata on Probabilistic XML	2009	PODS	6.257995e-05
5,450	Indexing Correlated Probabilistic Databases	2009	SIGMOD	6.2142725e-05
6,712	Capturing Data Uncertainty in High-Volume Stream Processing	2009	CIDR	5.7962014e-05
6,917	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	5.7400564e-05
13,746	Lahar Demonstration: Warehousing Markovian Streams	2009	VLDB	-

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,986	Querying Graph Patterns	2011	PODS
2	6,508	Probabilistic XML via Markov Chains	2010	VLDB
3	3,590	On Probabilistic Fixpoint and Markov Chain Query Languages	2010	PODS
4	12,240	E-Matching: Event Processing over Noisy Sequences in Real Time	2013	SIGMOD
5	6,120	Finding Frequent Items in Probabilistic Data	2008	SIGMOD
6	4,077	Similarity-Based Queries	1995	PODS
7	9,431	Probabilistic Nearest Neighbor Queries on Uncertain Moving Object Trajectories	2014	VLDB
8	3,472	Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation	2019	PODS
9	8,114	Approximate Substring Matching over Uncertain Strings	2011	VLDB
10	8,542	Online Windowed Subsequence Matching over Probabilistic Sequences	2012	SIGMOD