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: h9109d78967d7787d
Venue: PODS
Year: 2005
Pagerank: 4.9793485e-05
Overall Rank: 13,014 | 12.51%
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
77	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00036828234
267	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022722971
295	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00021914399
312	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021311793
428	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.0001845349
842	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013540697
862	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013396995

Semantically Similar Papers

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