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)

Paper ID: 1364
Venue: PODS
Year: 2005
Pagerank: 6.5196044e-05
Overall Rank: 4,761 | 67.34%
DOI: 10.1145/1065167.1065209

Incoming Non-self Citations Over Time

Authors

1. Noga Alon (Tel Aviv University)
2. Nick Duffield (AT&T)
3. Carsten Lund (AT&T)
4. Mikkel Thorup (AT&T)

BibTeX Citation

@inproceedings{alon_pods05,
        address = {New York, NY, USA},
        series = {{PODS} '05},
        title = {{Estimating arbitrary subset sums with few probes}},
        url = {https://dl.acm.org/doi/10.1145/1065167.1065209},
        doi = {10.1145/1065167.1065209},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Alon, Noga and Duffield, Nick and Lund, Carsten and Thorup, Mikkel},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,576	Optimal Sampling from Sliding Windows	2009	PODS	8.3964437e-05
3,481	Tighter Estimation using Bottom k Sketches	2008	VLDB	7.376137e-05
5,995	Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments	2009	VLDB	6.0155431e-05
8,252	Sampling Methods for Inner Product Sketching	2024	VLDB	5.4574671e-05
11,736	FlashP: An Analytical Pipeline for Real-time Forecasting of Time-Series Relational Data	2021	VLDB	5.093636e-05

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
9	Online Aggregation	1997	SIGMOD	0.00077458002
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00029226907
327	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00021091539
1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00010482997

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	451	Mergeable Summaries	2012	PODS
2	3,923	On Computing Functions with Uncertainty	2001	PODS
3	2,413	A Sampling Algebra for Aggregate Estimation	2013	VLDB
4	288	Towards Estimation Error Guarantees for Distinct Values	2000	PODS
5	12,760	Online Estimation For Subset-Based SQL Queries	2005	VLDB
6	261	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD
7	5,995	Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments	2009	VLDB
8	3,481	Tighter Estimation using Bottom k Sketches	2008	VLDB
9	2,878	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD
10	12,362	Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information	2011	PODS