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,789 | Optimal Sampling from Sliding Windows | 2009 | PODS | 8.1249652e-05 |
| 3,928 | Tighter Estimation using Bottom-k Sketches | 2008 | VLDB | 6.6254568e-05 |
| 5,415 | Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments | 2009 | VLDB | 5.5196338e-05 |
| 11,025 | Sampling Methods for Inner Product Sketching | 2024 | VLDB | 4.1945683e-05 |
| 11,539 | FlashP: An Analytical Pipeline for Real-time Forecasting of Time-Series Relational Data | 2021 | VLDB | 4.1945683e-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.0010801504 |
| 18 | On Random Sampling over Joins | 1999 | SIGMOD | 0.00092385438 |
| 184 | New Sampling-Based Summary Statistics for Improving Approximate Query Answers | 1998 | SIGMOD | 0.00036625711 |
| 429 | The Aqua Approximate Query Answering System | 1999 | SIGMOD | 0.00023476494 |
| 1,182 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS | 0.00013455963 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 402 | Mergeable Summaries | 2012 | PODS | 0.00024196343 |
| 3,801 | On Computing Functions with Uncertainty | 2001 | PODS | 6.7570059e-05 |
| 2,995 | A Sampling Algebra for Aggregate Estimation | 2013 | VLDB | 7.7587199e-05 |
| 378 | Towards Estimation Error Guarantees for Distinct Values | 2000 | PODS | 0.0002497492 |
| 12,567 | Online Estimation For Subset-Based SQL Queries | 2005 | VLDB | 4.1945683e-05 |
| 275 | Approximate Medians and other Quantiles in One Pass and with Limited Memory | 1998 | SIGMOD | 0.00029364901 |
| 5,415 | Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments | 2009 | VLDB | 5.5196338e-05 |
| 3,928 | Tighter Estimation using Bottom-k Sketches | 2008 | VLDB | 6.6254568e-05 |
| 3,271 | Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation | 2018 | SIGMOD | 7.2968732e-05 |
| 12,166 | Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information | 2011 | PODS | 4.1945683e-05 |