Efficient Dynamic Weighted Set Sampling and Its Extension

Summary: Proposes BUS, a practical dynamic weighted-set sampler with O(1) amortized updates and O(log n + t) sampling time for t draws using linear space, outperforming impractical “optimal” schemes. Extends to WIRS-BUS for range sampling with O(log n) updates and O(log^2 n + t) queries; empirically fast. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13393
Venue: VLDB
Year: 2024
Pagerank: 4.4810481e-05
Overall Rank: 8,609 | 40.17%
DOI: 10.14778/3617838.3617840

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,450	Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks	2023	SIGMOD	4.7218383e-05
7,750	GENTI: GPU-powered Walk-based Subgraph Extraction for Scalable Representation Learning on Dynamic Graphs	2024	VLDB	4.6565447e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
18	On Random Sampling over Joins	1999	SIGMOD	0.00092569117
46	Simple Random Sampling from Relational Databases	1986	VLDB	0.00071588702
531	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.0002079072
1,372	Random Sampling over Joins Revisited	2018	SIGMOD	0.0001233325
2,110	HubPPR: Effective Indexing for Approximate Personalized PageRank	2017	VLDB	9.5280826e-05
2,207	Independent Range Sampling	2014	PODS	9.2896559e-05
4,032	Spatial Online Sampling and Aggregation	2016	VLDB	6.5131946e-05
4,599	Fair Near Neighbor Search: Independent Range Sampling in High Dimensions	2020	PODS	6.0532073e-05
4,716	Weighted Reservoir Sampling from Distributed Streams	2019	PODS	5.9692227e-05
5,666	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	5.3824583e-05
5,955	Spatial Independent Range Sampling	2021	SIGMOD	5.2539404e-05
6,310	Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks	2018	SIGMOD	5.111823e-05
6,457	Algorithmic Techniques for Independent Query Sampling	2022	PODS	5.0488247e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,602	Structure-Aware Sampling: Flexible and Accurate Summarization	2011	VLDB	4.4822166e-05
5,423	Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments	2009	VLDB	5.5143276e-05
3,965	Random Sampling from Pseudo-Ranked B+ Trees	1992	VLDB	6.5786424e-05
9,760	Practical Dynamic Extension for Sampling Indexes	2023	SIGMOD	4.2838028e-05
4,347	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB	6.2588401e-05
2,881	Sampling Time-Based Sliding Windows in Bounded Space	2008	SIGMOD	7.9671512e-05
5,955	Spatial Independent Range Sampling	2021	SIGMOD	5.2539404e-05
4,716	Weighted Reservoir Sampling from Distributed Streams	2019	PODS	5.9692227e-05
10,924	Optimal Dynamic Parameterized Subset Sampling	2024	PODS	4.1905499e-05
2,207	Independent Range Sampling	2014	PODS	9.2896559e-05