Estimating arbitrary subset sums with few probes
Summary: Preprocess items with weight-dependent random priorities so any subset sum can be estimated by probing only the q highest-priority items in the subset. Unbiased estimator with relative stddev O(1/√q) (hence O(1/ε^2) probes for 1±ε), no subset-size knowledge needed; can also estimate counts. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Noga Alon
- 2. Nick Duffield
- 3. Carsten Lund
- 4. Mikkel Thorup
Incoming Citations (Sorted by Pagerank)
Showing 5 of 5 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,807 | Optimal Sampling from Sliding Windows | 2009 | PODS | 8.096649e-05 |
| 3,930 | Tighter Estimation using Bottom-k Sketches | 2008 | VLDB | 6.6195837e-05 |
| 5,423 | Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments | 2009 | VLDB | 5.5143276e-05 |
| 11,028 | Sampling Methods for Inner Product Sketching | 2024 | VLDB | 4.1905499e-05 |
| 11,543 | FlashP: An Analytical Pipeline for Real-time Forecasting of Time-Series Relational Data | 2021 | VLDB | 4.1905499e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 5 of 5 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 14 | Online Aggregation | 1997 | SIGMOD | 0.0010813443 |
| 18 | On Random Sampling over Joins | 1999 | SIGMOD | 0.00092569117 |
| 184 | New Sampling-Based Summary Statistics for Improving Approximate Query Answers | 1998 | SIGMOD | 0.00036655704 |
| 431 | The Aqua Approximate Query Answering System | 1999 | SIGMOD | 0.00023397171 |
| 1,183 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS | 0.00013444058 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 398 | Mergeable Summaries | 2012 | PODS | 0.00024383201 |
| 3,792 | On Computing Functions with Uncertainty | 2001 | PODS | 6.7566071e-05 |
| 2,995 | A Sampling Algebra for Aggregate Estimation | 2013 | VLDB | 7.7606324e-05 |
| 380 | Towards Estimation Error Guarantees for Distinct Values | 2000 | PODS | 0.00024943236 |
| 12,576 | Online Estimation For Subset-Based SQL Queries | 2005 | VLDB | 4.1905499e-05 |
| 274 | Approximate Medians and other Quantiles in One Pass and with Limited Memory | 1998 | SIGMOD | 0.00029383266 |
| 5,423 | Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments | 2009 | VLDB | 5.5143276e-05 |
| 3,930 | Tighter Estimation using Bottom-k Sketches | 2008 | VLDB | 6.6195837e-05 |
| 3,273 | Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation | 2018 | SIGMOD | 7.2899198e-05 |
| 12,174 | Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information | 2011 | PODS | 4.1905499e-05 |