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,902 | On the Feasibility of Forgetting in Data Streams | 2024 | PODS | 4.4229886e-05 |
| 11,331 | Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size | 2022 | PODS | 4.1905499e-05 |
| 11,436 | Model Counting meets F0 Estimation | 2021 | PODS | 4.1905499e-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 |
|---|---|---|---|---|
| 449 | An Optimal Algorithm for the Distinct Elements Problem | 2010 | PODS | 0.00022914472 |
| 649 | Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure | 2001 | SIGMOD | 0.00018652362 |
| 4,379 | Rectangle-Efficient Aggregation in Spatial Data Streams | 2012 | PODS | 6.2326895e-05 |
| 11,436 | Model Counting meets F0 Estimation | 2021 | PODS | 4.1905499e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 11,323 | Approximately Counting Subgraphs in Data Streams | 2022 | PODS | 4.1905499e-05 |
| 751 | Query Size Estimation by Adaptive Sampling (Extended Abstract) | 1990 | PODS | 0.00017155121 |
| 11,436 | Model Counting meets F0 Estimation | 2021 | PODS | 4.1905499e-05 |
| 8,445 | Efficient framework for operating on data sketches | 2023 | VLDB | 4.5042806e-05 |
| 12,484 | A Simple and Efficient Estimation Method for Stream Expression Cardinalities | 2007 | VLDB | 4.1905499e-05 |
| 2,755 | Towards Tight Bounds for the Streaming Set Cover Problem | 2016 | PODS | 8.1694565e-05 |
| 11,170 | Set Cover in the One-pass Edge-arrival Streaming Model | 2023 | PODS | 4.1905499e-05 |
| 7,146 | Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model | 2019 | PODS | 4.8133378e-05 |
| 5,064 | Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem | 2017 | PODS | 5.716891e-05 |
| 11,331 | Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size | 2022 | PODS | 4.1905499e-05 |