Tracking Join and Self-Join Sizes in Limited Storage
Summary: Approximate self-join sizes under insertions/deletions in tiny space; tug-of-war sketches outperform sample-and-count and plain sampling for skew detection and self-join estimation. Proves lower bounds showing sampling-based compact join signatures are essentially optimal absent assumptions, but proposes tug-of-war-based join signatures whose error scales with relations' self-join sizes and can significantly beat sampling. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Noga Alon (Tel Aviv University)
- 2. Phillip B. Gibbons (AT&T)
- 3. Yossi Matias (Tel Aviv University)
- 4. Mario Szegedy (AT&T)
BibTeX Citation
@inproceedings{alon_pods99,
address = {New York, NY, USA},
series = {{PODS} '99},
title = {{Tracking Join and Self-Join Sizes in Limited Storage}},
url = {https://dl.acm.org/doi/10.1145/303976.303978},
doi = {10.1145/303976.303978},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Alon, Noga and Gibbons, Phillip B. and Matias, Yossi and Szegedy, Mario},
year = {1999}
}Incoming Citations (Sorted by Pagerank)
Showing 42 of 42 citing papers.
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 13 of 13 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 91 | On the Propagation of Errors in the Size of Join Results | 1991 | SIGMOD |
| 2 | 57 | On Random Sampling over Joins | 1999 | SIGMOD |
| 3 | 7,471 | Reservoir Sampling over Joins | 2024 | SIGMOD |
| 4 | 1,467 | On the Relative Cost of Sampling for Join Selectivity Estimation | 1994 | PODS |
| 5 | 11,957 | Index-Based Join Size Estimation Using Adaptive Sampling | 2021 | SIGMOD |
| 6 | 3,994 | Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins | 2023 | PODS |
| 7 | 79 | Practical Selectivity Estimation through Adaptive Sampling | 1990 | SIGMOD |
| 8 | 749 | Join Size Estimation Subject to Filter Conditions | 2015 | VLDB |
| 9 | 1,011 | Query Size Estimation by Adaptive Sampling (Extended Abstract) | 1990 | PODS |
| 10 | 1,678 | Two-Level Sampling for Join Size Estimation | 2017 | SIGMOD |