Random Sampling for Data Intensive Computations
Dinkar Vasudevan, Milan Vojnović · 2010
Abstract –We consider estimation of arbitrary range partitioning of data values and ranking of frequently occurring items based on random sampling, within small number of samplings and prescribed accuracy. These problems arise in the context of parallel-processing of massive datasets, e.g. performed in data centers of Internet-scale cloud services and large-scale sci-entific computations. The range partitioning is a basic block of parallel-processing systems based on the paradigm of map and reduce. For the range partitioning, we consider a direct esti-mation method based on constructing an arbitrary-height histogram and characterize the estimation error. This approach provides substantial savings in constructing unbalanced range partitionings with respect to a standard approach based on equi-height histograms; our results extend previous work re-stricted to equi-height histograms. For the problem of ranking of frequently occurring items, we use a lumping of small frequency items that enables us to obtain tighter bounds that are independent of the total number of distinct items in a dataset. The analysis deploys the framework of large deviations that is well suited to typically large scale of data in the considered applications. We demonstrate tightness and benefits of our sam-pling methods using a large data set of an oper-ational cloud service that involves data at a scale of hundreds of billions of records. Our results pro-vides insights and inform design of practical sam-pling methods. 1.