2024/07/06 by Seth Pettie, Pettie, Seth, Dingyu Wang +1 · 3 citations
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #Data Stream Mining Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2407.04931
openalex publication_date 2024/07/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
If G : ℝ+ → ℝ+, the G-moment of a vector x∈ℝ+n is G(x) = ∑v∈[n] G(x(v)) and the G-sampling problem is to select an index v_*∈ [n] according to its contribution to the G-moment, i.e., such that Pr(v_*=v) = G(x(v))/G(x). Approximate G-samplers may introduce multiplicative and/or additive errors to this probability, and some have a non-trivial probability of failure. In this paper we focus on the exact G-sampling problem, where G is selected from the class G of Laplace exponents of non-negative, one-dimensional Lévy processes, which includes several well studied classes such as pth moments G(z)=zp, p∈[0,1], logarithms G(z)=log(1+z), Cohen and Geri's soft concave sublinear functions, which are used to approximate concave sublinear functions, including cap statistics. We develop G-samplers for a vector x ∈ ℝ+n that is presented as an incremental stream of positive updates. In particular: * For any G\inG, we give a very simple G-sampler that uses 2 words of memory and stores at all times a v_*∈ [n], such that Pr(v_*=v) is exactly G(x(v))/G(x). * We give a ``universal'' G-sampler that uses O(log n) words of memory w.h.p., and given any G∈ G at query time, produces an exact G-sample. With an overhead of a factor of k, both samplers can be used to G-sample a sequence of k indices with or without replacement. Our sampling framework is simple and versatile, and can easily be generalized to sampling from more complex objects like graphs and hypergraphs.