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
Authors
- 1. Junhao Gan (University of Melbourne)
- 2. Seeun William Umboh (Australian Research Council Training Centre in Optimisation Technologies, Integrated Methodologies, and Applications; University of Melbourne)
- 3. Hanzhi Wang (University of Copenhagen)
- 4. Anthony Wirth (University of Sydney)
- 5. Zhuo Zhang (University of Melbourne)
BibTeX Citation
@inproceedings{gan_pods24,
address = {New York, NY, USA},
series = {{PODS} '24},
title = {{Optimal Dynamic Parameterized Subset Sampling}},
url = {https://dl.acm.org/doi/10.1145/3695827},
doi = {10.1145/3695827},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Gan, Junhao and Umboh, Seeun William and Wang, Hanzhi and Wirth, Anthony and Zhang, Zhuo},
year = {2024}
}
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,719 | Subset Sampling over Joins | 2026 | PODS | 5.2319816e-05 |
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,320 | Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened | 2020 | SIGMOD | 8.7576221e-05 |
| 5,913 | Efficient Estimation of Heat Kernel PageRank for Local Clustering | 2019 | SIGMOD | 6.0439971e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 8,106 | SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model | 2022 | VLDB |
| 2 | 11,368 | Towards Better Bounds for Finding Quasi-Identifiers * | 2023 | PODS |
| 3 | 777 | Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems | 2011 | PODS |
| 4 | 2,753 | Sampling Time-Based Sliding Windows in Bounded Space | 2008 | SIGMOD |
| 5 | 10,168 | Tight Lower Bounds for l2 Sampling | 2026 | PODS |
| 6 | 10,173 | A Bouquet of Results on Maximum Range Sum: General Techniques and Hardness Reductions | 2026 | PODS |
| 7 | 5,068 | Weighted Reservoir Sampling from Distributed Streams | 2019 | PODS |
| 8 | 2,576 | Optimal Sampling from Sliding Windows | 2009 | PODS |
| 9 | 2,443 | Independent Range Sampling | 2014 | PODS |
| 10 | 7,142 | Efficient Dynamic Weighted Set Sampling and Its Extension | 2024 | VLDB |