Fast Range-Summable Random Variables for Efficient Aggregate Estimation

Summary: Investigates range-summable 3- and 4-wise PRNGs for sketch-based aggregates; compares schemes, provides 3-wise implementations. Shows extended Hamming (3-wise) matches 4-wise AMS-sketch join-size performance, improving spatial-join size estimates. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h3b54c78a52e8910d
Venue: SIGMOD
Year: 2006
Pagerank: 5.6576492e-05
Overall Rank: 6,869 | 53.84%
DOI: 10.1145/1142473.1142496

Incoming Non-self Citations Over Time

Authors

1. Florin Rusu (University of Florida)
2. Alin Dobra (University of Florida)

BibTeX Citation

@inproceedings{rusu_sigmod06,
        title = {{Fast Range-Summable Random Variables for Efficient Aggregate Estimation}},
        author = {Rusu, Florin and Dobra, Alin},
        series = {{SIGMOD} '06},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1142473.1142496},
        url = {https://dl.acm.org/doi/10.1145/1142473.1142496},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,928	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.9160175e-05
4,866	Rectangle-Efficient Aggregation in Spatial Data Streams	2012	PODS	6.3733138e-05
6,119	Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments	2009	VLDB	5.8785289e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
743	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00014309723
843	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013534623
3,273	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD	7.469873e-05
3,761	Approximation Techniques for Spatial Data	2004	SIGMOD	7.0403969e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,125	Randomized Sketches for Quantile in LSM-tree based Store	2025	SIGMOD
2	7,470	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS
3	3,994	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS
4	13,020	Join-Distinct Aggregate Estimation over Update Streams	2005	PODS
5	2,738	Sketching Probabilistic Data Streams	2007	SIGMOD
6	3,132	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR
7	79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD
8	7,572	Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries	2024	SIGMOD
9	11,077	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB
10	843	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD