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: 13392
Venue: VLDB
Year: 2024
Pagerank: 4.4853485e-05
Overall Rank: 8,610 | 40.11%
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,451	Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks	2023	SIGMOD	4.7263711e-05
7,749	GENTI: GPU-powered Walk-based Subgraph Extraction for Scalable Representation Learning on Dynamic Graphs	2024	VLDB	4.6610143e-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.00092385438
46	Simple Random Sampling from Relational Databases	1986	VLDB	0.00070894702
530	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00020803682
1,369	Random Sampling over Joins Revisited	2018	SIGMOD	0.00012339777
2,203	Independent Range Sampling	2014	PODS	9.2981095e-05
2,242	HubPPR: Effective Indexing for Approximate Personalized PageRank	2017	VLDB	9.218875e-05
4,029	Spatial Online Sampling and Aggregation	2016	VLDB	6.51315e-05
4,596	Fair Near Neighbor Search: Independent Range Sampling in High Dimensions	2020	PODS	6.0590268e-05
4,718	Weighted Reservoir Sampling from Distributed Streams	2019	PODS	5.9749691e-05
5,655	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	5.387631e-05
5,953	Spatial Independent Range Sampling	2021	SIGMOD	5.2589924e-05
6,309	Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks	2018	SIGMOD	5.1167347e-05
6,462	Algorithmic Techniques for Independent Query Sampling	2022	PODS	5.0536751e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,605	Structure-Aware Sampling: Flexible and Accurate Summarization	2011	VLDB	4.4865144e-05
5,415	Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments	2009	VLDB	5.5196338e-05
3,966	Random Sampling from Pseudo-Ranked B+ Trees	1992	VLDB	6.580483e-05
9,758	Practical Dynamic Extension for Sampling Indexes	2023	SIGMOD	4.2879116e-05
4,350	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB	6.2645054e-05
2,878	Sampling Time-Based Sliding Windows in Bounded Space	2008	SIGMOD	7.9706235e-05
5,953	Spatial Independent Range Sampling	2021	SIGMOD	5.2589924e-05
4,718	Weighted Reservoir Sampling from Distributed Streams	2019	PODS	5.9749691e-05
10,920	Optimal Dynamic Parameterized Subset Sampling	2024	PODS	4.1945683e-05
2,203	Independent Range Sampling	2014	PODS	9.2981095e-05