Banzhaf Values for Facts in Query Answering
Summary: Banzhaf values as a principled explanation metric for fact contributions to query answers; introduces exact, anytime-approximate, and top-k/ranking algorithms via lineage compilation and DP on Boolean functions. Also proves a tractability dichotomy for Banzhaf ranking (hierarchical vs. non-hierarchical queries) and shows large speedups over prior methods. (summarized by gpt-5.4-mini on May 24 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Omer Abramovich (Tel Aviv University)
- 2. Daniel Deutch (Tel Aviv University)
- 3. Nave Frost (eBay)
- 4. Ahmet Kara (University of Zurich)
- 5. Dan Olteanu (University of Zurich)
BibTeX Citation
@inproceedings{abramovich_sigmod24,
title = {{Banzhaf Values for Facts in Query Answering}},
author = {Abramovich, Omer and Deutch, Daniel and Frost, Nave and Kara, Ahmet and Olteanu, Dan},
series = {{SIGMOD} '24},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3654926},
url = {https://dl.acm.org/doi/10.1145/3654926},
year = {2024}
}Incoming Citations (Sorted by Pagerank)
Showing 5 of 5 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,382 | Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases | 2024 | PODS | 6.237788e-05 |
| 8,688 | Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms | 2025 | VLDB | 5.3847009e-05 |
| 9,809 | Shapley Revisited: Tractable Responsibility Measures for Query Answers | 2025 | PODS | 5.214913e-05 |
| 10,183 | Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries | 2026 | PODS | 5.093636e-05 |
| 10,198 | ASSS: Adaptive Stratified Sampling for Shapley-like Values | 2026 | SIGMOD | 5.093636e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 12 of 12 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 8,133 | Evaluating Top-k Queries with Inconsistency Degrees | 2020 | VLDB |
| 2 | 10,174 | A Unifying Algorithm for Hierarchical Queries | 2026 | PODS |
| 3 | 7,286 | Efficient Computation of Quantiles over Joins | 2023 | PODS |
| 4 | 9,009 | Efficient Approximations of Conjunctive Queries | 2012 | PODS |
| 5 | 5,382 | Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases | 2024 | PODS |
| 6 | 2,745 | Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries | 2020 | VLDB |
| 7 | 10,180 | Query Answering Under Volume-Based Diversity Functions | 2026 | PODS |
| 8 | 10,183 | Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries | 2026 | PODS |
| 9 | 2,424 | Computing the Shapley Value of Facts in Query Answering | 2022 | SIGMOD |
| 10 | 8,688 | Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms | 2025 | VLDB |