Estimating the Size of Union of Sets in Streaming Models
Summary: APS-Estimator: simple sampling streaming algorithm for |⋃Si| under Delphic sets; uses O(ε^-2 log(M/δ)·log|Ω|) space (up to polylog factors) and polylog update time. Settles PODS'12 by giving the first streaming Klee measure with linear-in-d dependence, and also yields streaming algorithms for test-coverage estimation and DNF model counting. (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. N. V. Vinodchandran (University of Nebraska, Lincoln)
- 3. Sourav Chakraborty (Indian Statistical Institute, Kolkata)
BibTeX Citation
@inproceedings{meel_pods21,
address = {New York, NY, USA},
series = {{PODS} '21},
title = {{Estimating the Size of Union of Sets in Streaming Models}},
url = {https://dl.acm.org/doi/10.1145/3452021.3458333},
doi = {10.1145/3452021.3458333},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Meel, Kuldeep S. and Vinodchandran, N. V. and Chakraborty, Sourav},
year = {2021}
}Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7,363 | On the Feasibility of Forgetting in Data Streams | 2024 | PODS | 5.6199138e-05 |
| 11,586 | Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size | 2022 | PODS | 5.0723324e-05 |
| 11,688 | Model Counting meets F0 Estimation | 2021 | PODS | 5.0723324e-05 |
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 |
| 653 | Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure | 2001 | SIGMOD | 0.00015263667 |
| 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 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 11,578 | Approximately Counting Subgraphs in Data Streams | 2022 | PODS |
| 2 | 999 | Query Size Estimation by Adaptive Sampling (Extended Abstract) | 1990 | PODS |
| 3 | 11,688 | Model Counting meets F0 Estimation | 2021 | PODS |
| 4 | 8,700 | Efficient framework for operating on data sketches | 2023 | VLDB |
| 5 | 12,722 | A Simple and Efficient Estimation Method for Stream Expression Cardinalities | 2007 | VLDB |
| 6 | 4,205 | Towards Tight Bounds for the Streaming Set Cover Problem | 2016 | PODS |
| 7 | 11,432 | Set Cover in the One-pass Edge-arrival Streaming Model | 2023 | PODS |
| 8 | 7,732 | Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model | 2019 | PODS |
| 9 | 5,694 | Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem | 2017 | PODS |
| 10 | 11,586 | Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size | 2022 | PODS |