Efficient Dynamic Weighted Set Sampling and Its Extension
Fangyuan Zhang, Mengxu Jiang, Sibo Wang · Proceedings of the VLDB Endowment · 2023
Given a weighted setSofnelements,weighted set sampling (WSS)samples an element inSso that each elementai; is sampled with a probability proportional to its weightw(ai). The classic alias method pre-processes an index inO(n) time withO(n) space and handles WSS withO(1) time. Yet, the alias method does not support dynamic updates. By minor modifications of existing dynamic WSS schemes, it is possible to achieve an expectedO(1) update time and drawtindependent samples in expectedO(t) time with linear space, which is theoretically optimal. But such a method is impractical and even slower than a binary search tree-based solution. How to support both efficient sampling and updates in practice is still challenging. Motivated by this, we designBUS, an efficient scheme that handles an update inO(1) amortized time and drawstindependent samples inO(logn + t)time with linear space. A natural extension of WSS is theweighted independent range sampling (WIRS), where each element inSis a data point from R. Given an arbitrary rangeQ= [ℓ,r] at query time, WIRS aims to do weighted set sampling on the setSQof data points falling into rangeQ.We show that by integrating the theoretically optimal dynamic WSS scheme mentioned above, it can handle an update inO(logn) time and can drawtindependent samples for WIRS inO(logn + t) time, the same as the state-of-the-art static algorithm. Again, such a solution by integrating the optimal dynamic WSS scheme is still impractical to handle WIRS queries. We further propose WIRS-BUS to integrate BUS to handle WIRS queries, which handles each update inO(logn) time and drawstindependent samples inO(log2n + t) time with linear space. Extensive experiments show that our BUS and WIRS-BUS are efficient for both sampling and updates.