Optimal Dynamic Parameterized Subset Sampling
Summary: Optimal DPSS in Word RAM: O(n) preprocessing, O(1+mu_S) per-query, O(1) updates, linear space. Hardness: deletion-only DPSS with float weights would imply sorting; also presents O(1) expected-time Bernoulli and truncated-geometric variate generation. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Junhao Gan
- 2. Seeun William Umboh
- 3. Hanzhi Wang
- 4. Anthony Wirth
- 5. Zhuo Zhang
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 2 of 2 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,664 | Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened | 2020 | SIGMOD | 8.3512717e-05 |
| 5,702 | Efficient Estimation of Heat Kernel PageRank for Local Clustering | 2019 | SIGMOD | 5.36473e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,796 | Finding Frequent Items in Probabilistic Data | 2008 | SIGMOD | 5.3240234e-05 |
| 8,203 | SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model | 2022 | VLDB | 4.5596344e-05 |
| 11,162 | Towards Better Bounds for Finding Quasi-Identifiers * | 2023 | PODS | 4.1945683e-05 |
| 1,094 | Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems | 2011 | PODS | 0.00014129658 |
| 2,878 | Sampling Time-Based Sliding Windows in Bounded Space | 2008 | SIGMOD | 7.9706235e-05 |
| 10,000 | A Bouquet of Results on Maximum Range Sum: General Techniques and Hardness Reductions | 2026 | PODS | 4.1945683e-05 |
| 4,718 | Weighted Reservoir Sampling from Distributed Streams | 2019 | PODS | 5.9749691e-05 |
| 2,789 | Optimal Sampling from Sliding Windows | 2009 | PODS | 8.1249652e-05 |
| 2,203 | Independent Range Sampling | 2014 | PODS | 9.2981095e-05 |
| 8,610 | Efficient Dynamic Weighted Set Sampling and Its Extension | 2024 | VLDB | 4.4853485e-05 |