Some extensions of DLT priority sampling: Covariance and Sliding Window

摘要

Duffield，Lund，Thorupが提案した優先サンプリングは、nアイテムからなる重み付きの大きなストリームの任意の部分集合の重みを、限られた数k個のサンプルだけから推定する。この手法は同じサンプル数たの手法の中で推定量の分散の合計の意味で準最適であることが、Szegedyにより示されている。本報告では、優先サンプリングの二つの拡張を与える。まず、ベクトルで重み付けられたストリームに対するサンプリング手法を与える。これは、ある準最適性を満たす。この手法の応用として、一つのアイテムに関連づけられた2種類の重みの共分散を推定する優先サンプリングを与える。そして、最近のある一定数のアイテムからなるスライディング窓の中の任意の重み部分和を推定する変形された優先サンプリングを与える。これら提案手法に対して実験的解析を行う。%The priority sampling scheme, proposed by Duffield, Lund, and Thorup, estimates the weight of an arbitrary subset of a large weighted stream of n items, using only a limited number k of samples. Szegedy showed that the scheme is almost optimal in terms of the total variance of the estimators among schemes of the same sample size k. In this report, we present two extensions of priority sampling. First, we present a sampling scheme for a vector weighted stream, which satisfies some near-optimality. As an application of the scheme, we present a priority sampling scheme to estimate the covariance of two kinds of weights associated to an item. Then we present a modified version of priority sampling that estimates an arbitrary subset sum of weights in the sliding window, a set of recent items of a fixed size. We analyze the proposed schemes experimentally.