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
Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,901 | On the Feasibility of Forgetting in Data Streams | 2024 | PODS | 4.427232e-05 |
| 11,329 | Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size | 2022 | PODS | 4.1945683e-05 |
| 11,433 | Model Counting meets F0 Estimation | 2021 | PODS | 4.1945683e-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 |
|---|---|---|---|---|
| 383 | An Optimal Algorithm for the Distinct Elements Problem | 2010 | PODS | 0.00024820873 |
| 647 | Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure | 2001 | SIGMOD | 0.00018668224 |
| 4,382 | Rectangle-Efficient Aggregation in Spatial Data Streams | 2012 | PODS | 6.2386853e-05 |
| 11,433 | Model Counting meets F0 Estimation | 2021 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 11,321 | Approximately Counting Subgraphs in Data Streams | 2022 | PODS | 4.1945683e-05 |
| 762 | Query Size Estimation by Adaptive Sampling (Extended Abstract) | 1990 | PODS | 0.00017036868 |
| 11,433 | Model Counting meets F0 Estimation | 2021 | PODS | 4.1945683e-05 |
| 8,451 | Efficient framework for operating on data sketches | 2023 | VLDB | 4.5086031e-05 |
| 12,475 | A Simple and Efficient Estimation Method for Stream Expression Cardinalities | 2007 | VLDB | 4.1945683e-05 |
| 2,749 | Towards Tight Bounds for the Streaming Set Cover Problem | 2016 | PODS | 8.1773535e-05 |
| 11,167 | Set Cover in the One-pass Edge-arrival Streaming Model | 2023 | PODS | 4.1945683e-05 |
| 7,145 | Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model | 2019 | PODS | 4.8179617e-05 |
| 5,066 | Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem | 2017 | PODS | 5.7223891e-05 |
| 11,329 | Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size | 2022 | PODS | 4.1945683e-05 |