Database Paper Browser

Back to papers

Approximate Lineage for Probabilistic Databases

Summary: Approximate lineage for probabilistic databases replaces full Boolean lineage with compact, query-guided derivations. Two variants: sufficient lineage (conservative) and polynomial lineage (Fourier-based) with definitions, algorithms, and validation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
9716
Venue
VLDB
Year
2008
Pagerank
9.8937766e-05
Overall Rank
1,972 | 86.30%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank Citing Paper Year Venue Pagerank
213 Scorpion: Explaining Away Outliers in Aggregate Queries 2013 VLDB 0.0003371037
1,698 Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases 2011 SIGMOD 0.00010857033
3,054 Partial Results in Database Systems 2014 SIGMOD 7.6478475e-05
4,853 Provenance for Natural Language Queries 2017 VLDB 5.8711821e-05
5,706 Putting Things into Context: Rich Explanations for Query Answers using Join Graphs 2021 SIGMOD 5.3633001e-05
6,167 Approximate Lifted Inference with Probabilistic Databases 2015 VLDB 5.1725053e-05
6,837 Capturing Data Uncertainty in High-Volume Stream Processing 2009 CIDR 4.9063121e-05
7,275 I4E: Interactive Investigation of Iterative Information Extraction 2010 SIGMOD 4.7743779e-05
7,481 Provenance-Enabled Explainable AI 2024 SIGMOD 4.7135369e-05
7,754 Lineage Processing over Correlated Probabilistic Databases 2010 SIGMOD 4.6556861e-05
8,377 Probabilistic Management of OCR Data using an RDBMS 2012 VLDB 4.5277353e-05
8,392 Hypothetical Reasoning via Provenance Abstraction 2019 SIGMOD 4.5234647e-05
8,501 Distributed Time-aware Provenance 2013 VLDB 4.4918817e-05
8,578 Anytime Approximation in Probabilistic Databases via Scaled Dissociations 2019 SIGMOD 4.4879347e-05
8,790 Database Optimization for the Cloud: Where Costs, Partial Results, and Consumer Choice Meet 2015 CIDR 4.4464049e-05
10,429 Unified Lineage System: Tracking Data Provenance at Scale 2025 SIGMOD 4.1905499e-05
11,182 Probabilistic Reasoning at Scale: Trigger Graphs to the Rescue 2023 SIGMOD 4.1905499e-05
11,436 Model Counting meets F0 Estimation 2021 PODS 4.1905499e-05
12,178 Schema-As-You-Go: On Probabilistic Tagging and Querying of Wide Tables 2011 SIGMOD 4.1905499e-05
12,221 Transducing Markov Sequences 2010 PODS 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank Cited Paper Year Venue Pagerank
20 C-Store: A Column-oriented DBMS 2005 VLDB 0.00086163998
31 Provenance Semirings 2007 PODS 0.00078516827
67 The Merge/Purge Problem for Large Databases 1995 SIGMOD 0.00061419648
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
275 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00029381206
279 Eliminating Fuzzy Duplicates in Data Warehouses 2002 VLDB 0.00029141798
373 Selectivity Estimation using Probabilistic Models 2001 SIGMOD 0.00025354685
572 The Complexity of Query Reliability 1998 PODS 0.00019888988
702 MYSTIQ: A system for finding more answers by using probabilities 2005 SIGMOD 0.00017848789
2,073 Orchestra: Facilitating Collaborative Data Sharing 2007 SIGMOD 9.6287026e-05
2,529 Provenance Management in Curated Databases 2006 SIGMOD 8.5944731e-05
2,906 SPARTAN: A Model-Based Semantic Compression System for Massive Data Tables 2001 SIGMOD 7.9324961e-05
6,610 bdbms – A Database Management System for Biological Data 2007 CIDR 4.990718e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,182 Querying Data Provenance 2010 SIGMOD 9.3596252e-05
6,187 On Provenance Minimization 2011 PODS 5.1611195e-05
103 ULDBs: Databases with Uncertainty and Lineage 2006 VLDB 0.00049520051
74 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB 0.00057797415
7,151 Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases 2020 PODS 4.8127652e-05
8,850 Efficient Approximations of Conjunctive Queries 2012 PODS 4.4324268e-05
7,162 Probabilistic Query Evaluation: The Combined FPRAS Landscape 2023 PODS 4.8085863e-05
6,996 Tractable Lineages on Treelike Instances: Limits and Extensions 2016 PODS 4.8629707e-05
4,439 Approximating Predicates and Expressive Queries on Probabilistic Databases 2008 PODS 6.1806955e-05
7,754 Lineage Processing over Correlated Probabilistic Databases 2010 SIGMOD 4.6556861e-05