Join-Distinct Aggregate Estimation over Update Streams

Summary: First space-efficient algorithms for Join-Distinct (distinct-projection over joins) on general update streams (inserts+deletes), introducing JD sketches — a new class of hash-based synopses that are built per stream and combinable. Probabilistic estimators yield low-error, high-confidence estimates with small per-update time and space, backed by near-optimal lower bounds and empirical validation. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1358
Venue: PODS
Year: 2005
Pagerank: 5.093636e-05
Overall Rank: 12,724 | 12.71%
DOI: 10.1145/1065167.1065200

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Sumit Ganguly (Indian Institute of Technology Kanpur)
2. Minos Garofalakis (AT&T)
3. Amit Kumar (Indian Institute of Technology Delhi)
4. Rajeev Rastogi (AT&T)

BibTeX Citation

@inproceedings{ganguly_pods05,
        address = {New York, NY, USA},
        series = {{PODS} '05},
        title = {{Join-Distinct Aggregate Estimation over Update Streams}},
        url = {https://dl.acm.org/doi/10.1145/1065167.1065200},
        doi = {10.1145/1065167.1065200},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ganguly, Sumit and Garofalakis, Minos and Kumar, Amit and Rastogi, Rajeev},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
75	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00037277061
255	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00023174541
288	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00022296371
311	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021760621
418	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018812821
817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013823702
842	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013671191

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	844	Hash-Partitioned Join Method Using Dynamic Destaging Strategy	1988	VLDB
2	2,697	Sketching Probabilistic Data Streams	2007	SIGMOD
3	7,001	On Joining and Caching Stochastic Streams	2005	SIGMOD
4	1,397	Approximate Join Processing Over Data Streams	2003	SIGMOD
5	3,657	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB
6	7,815	Sketching Unaggregated Data Streams for Subpopulation-Size Queries	2007	PODS
7	7,747	Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries	2024	SIGMOD
8	12,034	Streaming Algorithms for Robust Distinct Elements	2016	SIGMOD
9	817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
10	3,197	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD