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)

Paper ID: 1157
Venue: PODS
Year: 1999
Pagerank: 0.00020346247
Overall Rank: 550 | 96.18%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 41 of 41 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
43	Models and Issues in Data Stream Systems	2002	PODS	0.00072660894
344	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00026698826
430	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00023406426
481	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.000221538
503	Worst-case Optimal Join Algorithms	2012	PODS	0.00021517145
874	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.0001568356
1,065	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00014344675
1,194	Join Size Estimation Subject to Filter Conditions	2015	VLDB	0.00013411666
1,372	Random Sampling over Joins Revisited	2018	SIGMOD	0.0001233325
1,394	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012218557
1,466	Space Efficient Mining of Multigraph Streams	2005	PODS	0.00011838607
1,756	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00010659753
2,254	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.1871115e-05
2,934	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	7.8628636e-05
2,971	Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models	2017	VLDB	7.7935535e-05
3,047	Sketching Probabilistic Data Streams	2007	SIGMOD	7.6537004e-05
3,108	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD	7.5547127e-05
3,491	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.0436671e-05
3,540	Approximation Techniques for Spatial Data	2004	SIGMOD	6.9922652e-05
3,618	Persistent Data Sketching	2015	SIGMOD	6.9080647e-05
4,139	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB	6.4126764e-05
5,222	Similarity Join Size Estimation using Locality Sensitive Hashing	2011	VLDB	5.6180462e-05
5,886	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	5.2847297e-05
5,983	Understanding Cardinality Estimation using Entropy Maximization	2010	PODS	5.240797e-05
7,150	Histograms Revisited: When are histograms the best approximation method for aggregates over joins?	2005	PODS	4.8128138e-05
7,163	SKT: A One-Pass Multi-Sketch Data Analytics Accelerator	2021	VLDB	4.808534e-05
7,329	Streaming in a Connected World: Querying and Tracking Distributed Data Streams	2007	SIGMOD	4.7559363e-05
7,573	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	4.7034681e-05
7,697	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB	4.6701245e-05
7,725	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	4.6621296e-05
7,833	Containment Join Size Estimation: Models and Methods	2003	SIGMOD	4.6367487e-05
8,695	Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries	2024	SIGMOD	4.461508e-05
8,715	Scotch: Generating FPGA-Accelerators for Sketching at Line Rate	2021	VLDB	4.4571724e-05
9,041	TreeSensing: Linearly Compressing Sketches with Flexibility	2023	SIGMOD	4.3997447e-05
9,628	Approximate Sketches	2024	SIGMOD	4.3102157e-05
10,627	Data-Agnostic Cardinality Learning from Imperfect Workloads	2025	VLDB	4.1905499e-05
10,986	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	4.1905499e-05
11,028	Sampling Methods for Inner Product Sketching	2024	VLDB	4.1905499e-05
11,171	Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation	2023	PODS	4.1905499e-05
11,965	Monitoring Distributed Streams using Convex Decompositions	2015	VLDB	4.1905499e-05
12,540	Join-Distinct Aggregate Estimation over Update Streams	2005	PODS	4.1905499e-05

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.

Rank	Cited Paper	Year	Venue	Pagerank
14	Online Aggregation	1997	SIGMOD	0.0010813443
37	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00075597514
60	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00064450997
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051431888
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036655704
212	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033997204
216	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00033560137
270	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029648047
274	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00029383266
328	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027301497
553	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00020272747
736	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00017414831
1,254	Fixed-Precision Estimation of Join Selectivity	1993	PODS	0.00013018797

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
100	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050033475
18	On Random Sampling over Joins	1999	SIGMOD	0.00092569117
8,964	Reservoir Sampling over Joins	2024	SIGMOD	4.4163852e-05
803	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00016438972
11,449	Index-Based Join Size Estimation Using Adaptive Sampling	2021	SIGMOD	4.1905499e-05
5,085	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	5.7040225e-05
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051431888
1,194	Join Size Estimation Subject to Filter Conditions	2015	VLDB	0.00013411666
751	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00017155121
2,254	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.1871115e-05