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,668 | Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened | 2020 | SIGMOD | 8.3432296e-05 |
| 5,713 | Efficient Estimation of Heat Kernel PageRank for Local Clustering | 2019 | SIGMOD | 5.3595796e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,807 | Finding Frequent Items in Probabilistic Data | 2008 | SIGMOD | 5.3189104e-05 |
| 8,203 | SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model | 2022 | VLDB | 4.5552628e-05 |
| 11,165 | Towards Better Bounds for Finding Quasi-Identifiers * | 2023 | PODS | 4.1905499e-05 |
| 1,117 | Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems | 2011 | PODS | 0.0001386123 |
| 2,881 | Sampling Time-Based Sliding Windows in Bounded Space | 2008 | SIGMOD | 7.9671512e-05 |
| 9,999 | A Bouquet of Results on Maximum Range Sum: General Techniques and Hardness Reductions | 2026 | PODS | 4.1905499e-05 |
| 4,716 | Weighted Reservoir Sampling from Distributed Streams | 2019 | PODS | 5.9692227e-05 |
| 2,807 | Optimal Sampling from Sliding Windows | 2009 | PODS | 8.096649e-05 |
| 2,207 | Independent Range Sampling | 2014 | PODS | 9.2896559e-05 |
| 8,609 | Efficient Dynamic Weighted Set Sampling and Its Extension | 2024 | VLDB | 4.4810481e-05 |