2005/09/09 by Nick Duffield, Duffield, Nick, Carsten Lund +3 · 2 citations
Computer Science · #Algorithms and Data Compression #C.2.3 #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #E.1 #F.2 #FOS: Computer and information sciences #G.3 #H.3 #Optimization and Search Problems #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0509026
arxiv created 2005/09/09 · openalex publication_date 2005/09/09 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Starting with a set of weighted items, we want to create a generic sample of a certain size that we can later use to estimate the total weight of arbitrary subsets. For this purpose, we propose priority sampling which tested on Internet data performed better than previous methods by orders of magnitude. Priority sampling is simple to define and implement: we consider a steam of items i=0,...,n-1 with weights wi. For each item i, we generate a random number ri in (0,1) and create a priority qi=wi/ri. The sample S consists of the k highest priority items. Let t be the (k+1)th highest priority. Each sampled item i in S gets a weight estimate Wi=maxwi,t, while non-sampled items get weight estimate Wi=0. Magically, it turns out that the weight estimates are unbiased, that is, E[Wi]=wi, and by linearity of expectation, we get unbiased estimators over any subset sum simply by adding the sampled weight estimates from the subset. Also, we can estimate the variance of the estimates, and surpricingly, there is no co-variance between different weight estimates Wi and Wj. We conjecture an extremely strong near-optimality; namely that for any weight sequence, there exists no specialized scheme for sampling k items with unbiased estimators that gets smaller total variance than priority sampling with k+1 items. Very recently Mario Szegedy has settled this conjecture.