Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size
Summary: First streaming algorithm that (ε,δ)-approximates |⋃ S_i| for Delphic-family sets (captures Klee’s Measure, test-coverage, hypervolume) with space/update time poly(log|Ω|, ε^{-1}, log δ^{-1}) independent of stream length M. Extends to approximate-Delphic families, resolving two PODS‑21 open problems. (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. Kuldeep S. Meel (National University of Singapore)
- 2. Sourav Chakraborty (Indian Statistical Institute)
- 3. N. V. Vinodchandran (University of Nebraska-Lincoln)
BibTeX Citation
@inproceedings{meel_pods22,
address = {New York, NY, USA},
series = {{PODS} '22},
title = {{Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size}},
url = {https://dl.acm.org/doi/10.1145/3517804.3526222},
doi = {10.1145/3517804.3526222},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Meel, Kuldeep S. and Chakraborty, Sourav and Vinodchandran, N. V.},
year = {2022}
}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 4 of 4 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 483 | An Optimal Algorithm for the Distinct Elements Problem | 2010 | PODS | 0.00017698899 |
| 4,771 | Rectangle-Efficient Aggregation in Spatial Data Streams | 2012 | PODS | 6.4954035e-05 |
| 11,688 | Model Counting meets F0 Estimation | 2021 | PODS | 5.0723324e-05 |
| 11,697 | Estimating the Size of Union of Sets in Streaming Models | 2021 | PODS | 5.0723324e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 3,209 | Processing Set Expressions over Continuous Update Streams | 2003 | SIGMOD |
| 2 | 10,213 | Unbiased Insights: Optimal Streaming Algorithms for l_p Sampling, the Forget Model, and Beyond | 2026 | PODS |
| 3 | 8,700 | Efficient framework for operating on data sketches | 2023 | VLDB |
| 4 | 12,722 | A Simple and Efficient Estimation Method for Stream Expression Cardinalities | 2007 | VLDB |
| 5 | 11,432 | Set Cover in the One-pass Edge-arrival Streaming Model | 2023 | PODS |
| 6 | 7,732 | Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model | 2019 | PODS |
| 7 | 11,578 | Approximately Counting Subgraphs in Data Streams | 2022 | PODS |
| 8 | 4,205 | Towards Tight Bounds for the Streaming Set Cover Problem | 2016 | PODS |
| 9 | 5,694 | Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem | 2017 | PODS |
| 10 | 11,697 | Estimating the Size of Union of Sets in Streaming Models | 2021 | PODS |