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)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Sumit Ganguly
- 2. Minos Garofalakis
- 3. Amit Kumar
- 4. Rajeev Rastogi
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 60 | Sampling-Based Estimation of the Number of Distinct Values of an Attribute | 1995 | VLDB | 0.00064450997 |
| 316 | Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports | 2001 | VLDB | 0.00027981848 |
| 344 | Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries | 2001 | VLDB | 0.00026698826 |
| 380 | Towards Estimation Error Guarantees for Distinct Values | 2000 | PODS | 0.00024943236 |
| 550 | Tracking Join and Self-Join Sizes in Limited Storage | 1999 | PODS | 0.00020346247 |
| 955 | How to Summarize the Universe: Dynamic Maintenance of Quantiles | 2002 | VLDB | 0.00015069776 |
| 1,065 | Processing Complex Aggregate Queries over Data Streams | 2002 | SIGMOD | 0.00014344675 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 549 | Hash-Partitioned Join Method Using Dynamic Destaging Strategy | 1988 | VLDB | 0.00020348047 |
| 3,047 | Sketching Probabilistic Data Streams | 2007 | SIGMOD | 7.6537004e-05 |
| 6,852 | On Joining and Caching Stochastic Streams | 2005 | SIGMOD | 4.9027621e-05 |
| 1,712 | Approximate Join Processing Over Data Streams | 2003 | SIGMOD | 0.00010786152 |
| 4,139 | Memory-Limited Execution of Windowed Stream Joins | 2004 | VLDB | 6.4126764e-05 |
| 7,545 | Sketching Unaggregated Data Streams for Subpopulation-Size Queries | 2007 | PODS | 4.7099128e-05 |
| 8,695 | Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries | 2024 | SIGMOD | 4.461508e-05 |
| 11,841 | Streaming Algorithms for Robust Distinct Elements | 2016 | SIGMOD | 4.1905499e-05 |
| 1,065 | Processing Complex Aggregate Queries over Data Streams | 2002 | SIGMOD | 0.00014344675 |
| 3,108 | Processing Set Expressions over Continuous Update Streams | 2003 | SIGMOD | 7.5547127e-05 |