In multimedia, text or bioinformatics databases, applicat ions query sequences of n consecutive symbols called n-grams. Estimating the number of distinct n-grams is a view-size estimation problem. While view sizes can be estimated by sampling under statistical assumptions, we desire an unassuming algorithm with universally valid accuracy bounds. Most related work has focused on repeatedly hashing the data, which is prohibitive for large data sources. We prove that a one-pass one-hash algorithm is suffi cient for accurate estimates if the hashing is sufficiently independent. T o reduce costs further, we investigate recursive random hashing algorithms and show that they are sufficiently independent in practice. We compare our run ning times with exact counts using suffix arrays and show that, while we use ha rdly any storage, we are an order of magnitude faster. The approach further is extended to a one-pass one-hash computation of n-gram entropy and iceberg counts. The experiments use a large collection of English text from the Gutenberg Project as well as synthetic data.
@cite_61: We introduce fast algorithms for selecting a random sample of n records without replacement from a pool of N records, where the value of N is unknown beforehand. The main result of the paper is the design and analysis of Algorithm Z; it does the sampling in one pass using constant space and in O ( n (1 + log( N n ))) expected time, which is optimum, up to a constant factor. Several optimizations are studied that collectively improve the speed of the naive version of the algorithm by an order of magnitude. We give an efficient Pascal-like implementation that incorporates these modifications and that is suitable for general use. Theoretical and empirical results indicate that Algorithm Z outperforms current methods by a significant margin.
@cite_77: We present a simple algorithm that allows sampling from a stream of data items without knowing the number of items in advance and without having to store all items in main memory. The sampling distribution may be general, that is, the probability of selecting a data item i may depend on the individual item. The main advantage of the algorithms is that they have to pass through the data items only once to produce a sample of arbitrary size n.We give different variants of the algorithm for sampling with and without replacement and analyze their complexity. We generalize earlier results of Knuth on reservoir sampling with a uniform sampling distribution. The general distribution considered here allows us to sample an item with a probability equal to the relative weight (or fitness) of the data item within the whole set of items. Applications include heuristic optimization procedures such as genetic algorithms where solutions are sampled from a population with probability proportional to their fitness.
@cite_72: 
@cite_74: One-pass algorithms for sampling n records without replacement from a population of unknown size n are known as reservoir-sampling algorithms. In this article, Vitter's reservoir-sampling algorithm, algorithm Z, is modified to give a more efficient algorithm, algorithm K. Additionally, two new algorithms, algorithm L and algorithm M, are proposed. If the time for scanning the population is ignored, all the four algorithms have expected CPU time O ( n (1 + log( N n ))), which is optimum up to a constant factor. Expressions of the expected CPU time for the algorithms are presented. Among the four, algorithm L is the simplest, and algorithm M is the most efficient when n and N n are large and N is O ( n 2 ).
We can choose randomly, without replacement, @math samples in a sequence of unknown length using a single pass through the data by . Reservoir sampling @cite_61 @cite_77 @cite_74 was introduced by Knuth @cite_72 . All reservoir sampling algorithms begin by appending the first @math samples to an array. In their linear time ( @math ) form, reservoir sampling algorithms sequentially visit every symbol choosing it as a possible sample with probability @math where @math is the number of symbols read so far. The chosen sample is simply appended at the end of the array while an existing sample is flagged as having been removed. The array has an average size of @math samples at the end of the run. In their sublinear form ( @math expected time), the algorithms skip a random number of data points each time. While these algorithms use a single pass, they assume that the number of required samples @math is known a priori, but this is difficult without any knowledge of the data distribution.