Optimal Dynamic Subset Sampling: Theory and Applications

We study the fundamental problem of sampling independent events, called subset sampling. Specifically, consider a set of 𝑛 distinct events 𝑆 = 𝑥 1 , . . . , 𝑥 𝑛 , in which each event 𝑥 𝑖 has an associated probability 𝑝 (𝑥 𝑖 ). The subset sampling problem aims to sample a subset 𝑇 ⊆ 𝑆, such that every 𝑥 𝑖 is independently included in 𝑇 with probability 𝑝 (𝑥 𝑖 ). A naive solution is to flip a coin for each event, which takes 𝑂 (𝑛) time. However, an ideal solution is a data structure that allows drawing a subset sample in time proportional to the expected output size 𝜇 = 𝑛 𝑖=1 𝑝 (𝑥 𝑖 ), which can be significantly smaller than 𝑛 in many applications. The subset sampling problem serves as an important building block in many tasks and has been the subject of various research for more than a decade. However, the majority of existing subset sampling methods are designed for a static setting, where the events in set 𝑆 or their associated probabilities remain unchanged over time. These algorithms incur either large query time or update time in a dynamic setting despite the ubiquitous time-evolving events with varying probabilities in real life. Therefore, it is a pressing need, but still, an open problem, to design efficient dynamic subset sampling algorithms. In this paper, we propose ODSS, the first optimal dynamic subset sampling algorithm. The expected query time and update time of ODSS are both optimal, matching the lower bounds of the subset sampling problem. We present a nontrivial theoretical analysis to demonstrate the superiority of ODSS. We also conduct comprehensive experiments to empirically evaluate the performance of ODSS. Moreover, we apply ODSS to a concrete application: Influence Maximization. We empirically show that our ODSS can improve the complexities of existing Influence Maximization algorithms on large real-world evolving social networks.