Lineage Processing over Correlated Probabilistic Databases

Summary: Scalable conjunctive-query evaluation over correlated probabilistic DBs via junction-tree forests encoding correlations. Lwidth bounds lineage complexity; exact inference for low lwidth, Monte Carlo for high, batch-lineage sharing for efficiency. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4346
Venue: SIGMOD
Year: 2010
Pagerank: 5.5041098e-05
Overall Rank: 8,032 | 44.90%
DOI: 10.1145/1807167.1807241

Incoming Non-self Citations Over Time

Authors

1. Bhargav Kanagal (University of Maryland)
2. Amol Deshpande (University of Maryland)

BibTeX Citation

@inproceedings{kanagal_sigmod10,
        title = {{Lineage Processing over Correlated Probabilistic Databases}},
        author = {Kanagal, Bhargav and Deshpande, Amol},
        series = {{SIGMOD} '10},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1807167.1807241},
        url = {https://dl.acm.org/doi/10.1145/1807167.1807241},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,594	Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases	2011	SIGMOD	0.00010252583
4,680	Probabilistic Databases with MarkoViews	2012	VLDB	6.5675814e-05
7,306	Local Structure and Determinism in Probabilistic Databases	2012	SIGMOD	5.6499367e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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
359	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.0002023153
680	Creating Probabilistic Databases from Information Extraction Models	2006	VLDB	0.0001504854
699	Data Integration with Uncertainty	2007	VLDB	0.0001487423
1,752	Approximate Lineage for Probabilistic Databases	2008	VLDB	9.8358116e-05
1,873	A Web of Concepts	2009	PODS	9.5751398e-05
2,460	Exploiting Shared Correlations in Probabilistic Databases	2008	VLDB	8.5505905e-05
3,050	Event Queries on Correlated Probabilistic Streams	2008	SIGMOD	7.8140428e-05
3,973	Uncertainty Management in Rule-Based Information Extraction Systems	2009	SIGMOD	6.9810029e-05
5,450	Indexing Correlated Probabilistic Databases	2009	SIGMOD	6.2142725e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,306	Local Structure and Determinism in Probabilistic Databases	2012	SIGMOD
2	4,301	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB
3	3,514	On-the-Fly Entity-Aware Query Processing in the Presence of Linkage	2010	VLDB
4	7,430	Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases	2020	PODS
5	2,936	Materialized Views in Probabilistic Databases: For Information Exchange and Query Optimization	2007	VLDB
6	7,640	Tractable Lineages on Treelike Instances: Limits and Extensions	2016	PODS
7	7,317	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS
8	7,706	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS
9	5,450	Indexing Correlated Probabilistic Databases	2009	SIGMOD
10	1,752	Approximate Lineage for Probabilistic Databases	2008	VLDB