2023/07/21 by Jinchao Huang, Sibo Wang, Huang, Jinchao +1 · 1 citation
Computer Science · #Advanced Image and Video Retrieval Techniques #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2307.11585
openalex publication_date 2023/07/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper studies the subset sampling problem. The input is a set S of n records together with a function p that assigns each record v\inS a probability p(v). A query returns a random subset X of S, where each record v\inS is sampled into X independently with probability p(v). The goal is to store S in a data structure to answer queries efficiently. If S fits in memory, the problem is interesting when S is dynamic. We develop a dynamic data structure with O(1+μS) expected query time, O(n) space and O(1) amortized expected update, insert and delete time, where μS=∑v\inSp(v). The query time and space are optimal. If S does not fit in memory, the problem is difficult even if S is static. Under this scenario, we present an I/O-efficient algorithm that answers a query in O((log^*B n)/B+(μS/B)logM/B (n/B)) amortized expected I/Os using O(n/B) space, where M is the memory size, B is the block size and log^*B n is the number of iterative log2(.) operations we need to perform on n before going below B. In addition, when each record is associated with a real-valued key, we extend the subset sampling problem to the range subset sampling problem, in which we require that the keys of the sampled records fall within a specified input range [a,b]. For this extension, we provide a solution under the dynamic setting, with O(log n+μS∩[a,b]) expected query time, O(n) space and O(log n) amortized expected update, insert and delete time.