On Efficient Top-k Empirical Variance Computation: A Once-For-All Progressive Sampling Approach

The empirical variance estimation and its corresponding top-k query is a fundamental problem in the data mining and data analytics and serves as an inherent building block for many clustering and feature selection algorithms. Since the exact computation requires scanning the whole dataset which will be prohibitively expensive for many real-time applications, all existing studies in the literature are dedicated to find the approximate solutions by using the sampling techniques. For the top-k query processing, we observe that all existing studies analyze the error of the estimated variance of each selected attribute independently by using the traditional centrality inequality (e.g., Chernoff bounds/Hoeffding’s inequality) and then adopt the traditional union bound to estimate the aggregate error of the k selected attributes. As such, the bound is significantly loose and renders their algorithm sensitive to the parameter k. Motivated by this, in this paper, we propose a once-for-all progressive sampling algorithm, namely Top-k Empirical Variance Computation with Rademacher Average (EVA), for jointly analyzing the aggregate error of the variances of all attributes one-for-all. In our algorithm, the tuples are sampled iteratively in batches. In each iteration, we estimate the accuracy currently achieved with the tuples already being sampled and derive the error bound by adopting a key concept called Rademacher Average from the statistical machine learning theory. Our error estimation algorithm enjoys two features. Firstly, it is data-dependent which fully makes use of the tuples already sampled and help us terminate the algorithm earlier once our desired accuracy is achieved. Secondly and more importantly, it estimates the aggregate error of the selected attributes simultaneously once-for-all which considers their inter-relation and as such, it is tighter than the traditional union bound-based method. Our empirical study shows that our algorithm outperforms the state-of-the-art algorithms by orders of magnitudes in terms of the efficiency with the same accuracy guarantee.