Local Structure and Determinism in Probabilistic Databases

Summary: Efficient probabilistic query evaluation over correlated databases via factor graphs and local structure. Proposes annotated arithmetic circuits with update support to exploit determinism, yielding fast inference and substantial speedups in experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4600
Venue: SIGMOD
Year: 2012
Pagerank: 5.6499367e-05
Overall Rank: 7,306 | 49.88%
DOI: 10.1145/2213836.2213879

Incoming Non-self Citations Over Time

Authors

1. Theodoros Rekatsinas (University of Maryland)
2. Amol Deshpande (University of Maryland)
3. Lise Getoor (University of Maryland)

BibTeX Citation

@inproceedings{rekatsinas_sigmod12,
        title = {{Local Structure and Determinism in Probabilistic Databases}},
        author = {Rekatsinas, Theodoros and Deshpande, Amol and Getoor, Lise},
        series = {{SIGMOD} '12},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2213836.2213879},
        url = {https://dl.acm.org/doi/10.1145/2213836.2213879},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
323	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021264788
7,556	ReStore - Neural Data Completion for Relational Databases	2021	SIGMOD	5.5997742e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00043596705
337	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00020783399
699	Data Integration with Uncertainty	2007	VLDB	0.0001487423
820	BayesStore: Managing Large, Uncertain Data Repositories with Probabilistic Graphical Models	2008	VLDB	0.00013814535
1,986	Scalable Probabilistic Databases with Factor Graphs and MCMC	2010	VLDB	9.3519536e-05
3,229	Computing Query Probability with Incidence Algebras	2010	PODS	7.6209731e-05
4,136	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.8810237e-05
4,301	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	6.7737212e-05
5,450	Indexing Correlated Probabilistic Databases	2009	SIGMOD	6.2142725e-05
8,032	Lineage Processing over Correlated Probabilistic Databases	2010	SIGMOD	5.5041098e-05
8,585	Probabilistic Management of OCR Data using an RDBMS	2012	VLDB	5.4075213e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,986	Scalable Probabilistic Databases with Factor Graphs and MCMC	2010	VLDB
2	7,706	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS
3	3,698	Optimizing MPF Queries: Decision Support and Probabilistic Inference	2007	SIGMOD
4	4,680	Probabilistic Databases with MarkoViews	2012	VLDB
5	4,098	Aggregation in Probabilistic Databases via Knowledge Compilation	2012	VLDB
6	2,687	Answering Queries from Statistics and Probabilistic Views	2005	VLDB
7	50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
8	4,301	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB
9	2,460	Exploiting Shared Correlations in Probabilistic Databases	2008	VLDB
10	5,450	Indexing Correlated Probabilistic Databases	2009	SIGMOD