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)
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,927 | Statistical Analysis of Sketch Estimators | 2007 | SIGMOD | 6.9192361e-05 |
| 4,865 | Rectangle-Efficient Aggregation in Spatial Data Streams | 2012 | PODS | 6.3763323e-05 |
| 6,118 | Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments | 2009 | VLDB | 5.8813101e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 742 | Dynamic Multidimensional Histograms | 2002 | SIGMOD | 0.0001431602 |
| 842 | Processing Complex Aggregate Queries over Data Streams | 2002 | SIGMOD | 0.00013540697 |
| 3,272 | Processing Set Expressions over Continuous Update Streams | 2003 | SIGMOD | 7.4734096e-05 |
| 3,758 | Approximation Techniques for Spatial Data | 2004 | SIGMOD | 7.0437238e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 11,116 | Randomized Sketches for Quantile in LSM-tree based Store | 2025 | SIGMOD |
| 2 | 7,466 | Probabilistic Query Evaluation: The Combined FPRAS Landscape | 2023 | PODS |
| 3 | 3,992 | Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins | 2023 | PODS |
| 4 | 13,014 | Join-Distinct Aggregate Estimation over Update Streams | 2005 | PODS |
| 5 | 2,738 | Sketching Probabilistic Data Streams | 2007 | SIGMOD |
| 6 | 3,131 | 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,566 | Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries | 2024 | SIGMOD |
| 9 | 11,068 | Towards Efficient Random-Order Enumeration for Join Queries | 2026 | VLDB |
| 10 | 842 | Processing Complex Aggregate Queries over Data Streams | 2002 | SIGMOD |