Efficient Dynamic Weighted Set Sampling and Its Extension

Summary: BUS makes dynamic weighted set sampling practical: O(1) amortized updates and O(log n+t) time for t samples in linear space. WIRS-BUS extends this to weighted range sampling with O(log n) updates and O(log²n+t) queries, with strong empirical performance. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 13580
Venue: VLDB
Year: 2024
Pagerank: 5.6917227e-05
Overall Rank: 7,142 | 51.01%
DOI: 10.14778/3617838.3617840

Incoming Non-self Citations Over Time

Authors

1. Fangyuan Zhang (Chinese University of Hong Kong)
2. Mengxu Jiang (Chinese University of Hong Kong)
3. Sibo Wang (Chinese University of Hong Kong)

BibTeX Citation

@article{zhang_vldb24,
        title = {{Efficient Dynamic Weighted Set Sampling and Its Extension}},
        author = {Zhang, Fangyuan and Jiang, Mengxu and Wang, Sibo},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {1},
        pages = {15--27},
        doi = {10.14778/3617838.3617840},
        url = {https://doi.org/10.14778/3617838.3617840},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,695	GENTI: GPU-powered Walk-based Subgraph Extraction for Scalable Representation Learning on Dynamic Graphs	2024	VLDB	5.7990641e-05
7,455	Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks	2023	SIGMOD	5.6127752e-05
9,512	Poisson Sampling over Acyclic Joins	2026	SIGMOD	5.2571354e-05
10,244	FIRAS: A Framework for Interval Range Search and Sampling	2026	SIGMOD	5.093636e-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
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
173	Simple Random Sampling from Relational Databases	1986	VLDB	0.00027273858
508	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00017275873
802	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013907725
2,225	HubPPR: Effective Indexing for Approximate Personalized PageRank	2017	VLDB	8.9183159e-05
2,443	Independent Range Sampling	2014	PODS	8.5754434e-05
3,623	Fair Near Neighbor Search: Independent Range Sampling in High Dimensions	2020	PODS	7.2463734e-05
3,741	Spatial Online Sampling and Aggregation	2016	VLDB	7.1586403e-05
4,714	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	6.5497309e-05
5,068	Weighted Reservoir Sampling from Distributed Streams	2019	PODS	6.3770298e-05
5,527	Algorithmic Techniques for Independent Query Sampling	2022	PODS	6.1861709e-05
5,692	Spatial Independent Range Sampling	2021	SIGMOD	6.119196e-05
5,741	Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks	2018	SIGMOD	6.1029326e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,419	Structure-Aware Sampling: Flexible and Accurate Summarization	2011	VLDB
2	5,995	Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments	2009	VLDB
3	4,458	Random Sampling from Pseudo-Ranked B+ Trees	1992	VLDB
4	8,790	Practical Dynamic Extension for Sampling Indexes	2023	SIGMOD
5	4,229	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB
6	2,753	Sampling Time-Based Sliding Windows in Bounded Space	2008	SIGMOD
7	5,692	Spatial Independent Range Sampling	2021	SIGMOD
8	5,068	Weighted Reservoir Sampling from Distributed Streams	2019	PODS
9	9,513	Optimal Dynamic Parameterized Subset Sampling	2024	PODS
10	2,443	Independent Range Sampling	2014	PODS