Adaptive sampling

Adaptive sampling [a1] is a probabilistic algorithm invented by M. Wegman (unpublished) around 1980. It provides an unbiased estimator of the number of distinct elements (the "cardinality" ) of a file (a sequence of data items) of potentially large size that contains unpredictable replications. The algorithm is useful in data-base query optimization and in information retrieval. By standard hashing techniques [a3], [a6] the problem reduces to the following.

A sequence $ ( h _ {1} \dots h _ {n} ) $ of real numbers is given. The sequence has been formed by drawing independently and randomly an unknown number $ N $ of real numbers from $ [ 0,1 ] $, after which the elements are replicated and permuted in some unknown fashion. The problem is to estimate the cardinality $ N $ in a computationally efficient manner.

Three algorithms can perform this task.

1) Straight scan computes incrementally the sets $ U _ {j} = \{ h _ {1} \dots h _ {j} \} $, where replications are eliminated on the fly. (This can be achieved by keeping the successive $ U _ {j} $ in sorted order.) The cardinality is then determined exactly by $ N = { \mathop{\rm card} } ( U _ {n} ) $ but the auxiliary memory needed is $ N $, which may be as large as $ n $, resulting in a complexity that is prohibitive in many applications.

2) Static sampling is based on a fixed sampling ratio $ p $, where $ 0 < p \leq 1 $( e.g., $ p = {1 / {100 } } $). One computes sequentially the samples $ U _ {j} ^ {*} = \{ h _ {1} \dots h _ {j} \} \cap [ 0,p ] $. The cardinality estimate returned is $ N ^ {*} = { {{ \mathop{\rm card} } ( U _ {n} ^ {*} ) } / p } $. The estimator $ N ^ {*} $ is unbiased and the memory used is $ Np $ on average.

3) Adaptive sampling is based on a design parameter $ b \geq 2 $( e.g., $ b = 100 $) and it maintains a dynamically changing sampling rate $ p $ and a sequence of samples $ U _ {j} ^ {** } $. Initially, $ p = 1 $ and $ U _ {0} ^ {** } = \emptyset $. The rule is like that of static sampling, but with $ p $ divided by $ 2 $ each time the cardinality of $ U _ {j} ^ {** } $ would exceed $ b $ and with $ U _ {j} ^ {** } $ modified accordingly in order to contain only $ U _ {j} \cap [ 0,p ] $. The estimator $ N ^ {** } = { {{ \mathop{\rm card} } ( U _ {n} ^ {** } ) } / p } $( where the final value of $ p $ is used) is proved to be unbiased and the memory used is at most $ b $.

The accuracy of any such unbiased estimator $ {\widetilde{N} } $ of $ N $ is measured by the standard deviation of $ {\widetilde{N} } $ divided by $ N $. For adaptive sampling, the accuracy is almost constant as a function of $ N $ and asymptotically close to

$$ { \frac{1.20 }{\sqrt b } } , $$

a result established in [a1] by generating functions and Mellin transform techniques. An alternative algorithm, called probabilistic counting [a2], provides an estimator $ N ^ {*** } $ of cardinalities that is unbiased only asymptotically but has a better accuracy, of about $ { {0.78 } / {\sqrt b } } $.

Typically, the adaptive sampling algorithm can be applied to gather statistics on word usage in a large text. Well-designed hashing transformations are then known to fulfill practically the uniformity assumption [a4]. A general perspective on probabilistic algorithms may be found in [a5].

References

[a1]	P. Flajolet, "On adaptive sampling" Computing , 34 (1990) pp. 391–400
[a2]	P. Flajolet, G.N. Martin, "Probabilistic counting algorithms for data base applications" J. Comp. System Sci. , 31 : 2 (1985) pp. 182–209
[a3]	D.E. Knuth, "The art of computer programming" , 3. Sorting and Searching , Addison-Wesley (1973)
[a4]	V.Y. Lum, P.S.T. Yuen, M. Dodd, "Key to address transformations: a fundamental study based on large existing format files" Commun. ACM , 14 (1971) pp. 228–239
[a5]	R. Motwani, P. Raghavan, "Randomized algorithms" , Cambridge Univ. Press (1995)
[a6]	R. Sedgewick, "Algorithms" , Addison-Wesley (1988) (Edition: Second)