text: A computer implemented method of estimating a cardinality of a stream, comprising: receiving a query for estimating a cardinality of a stream comprising a plurality of elements, obtaining a sample comprising a group of the plurality of elements randomly sampled from the respective stream, computing a first and second data structures for the sample used to compute an estimated sample cardinality of the sample and a ratio indicative of a proportion between the estimated sample cardinality and the estimated cardinality of the stream and computing the estimated cardinality of the stream by applying the ratio to the estimated sample cardinality. Where the first data structure comprises a plurality of maximal hash values computed for the sample using a plurality of hash functions and the second data structure comprises a fixed- size subset of the elements having a minimal hash value among the elements of the group.
  @cite_15: Linguists and speech researchers who use statistical methods often need to estimate the frequency of some type of item in a population containing items of various types. A common approach is to divide the number of cases observed in a sample by the size of the sample; sometimes small positive quantities are added to divisor and dividend in order to avoid zero estimates for types missing from the sample. These approaches are obvious and simple, but they lack principled justification, and yield estimates that can be wildly inaccurate. I.J. Good and Alan Turing developed a family of theoretically well-founded techniques appropriate to this domain. Some versions of the Good–Turing approach are very demanding computationally, but we define a version, the Simple Good–Turing estimator, which is straightforward to use. Tested on a variety of natural-language-related data sets, the Simple Good–Turing estimator performs well, absolutely and relative both to the approaches just discussed and to other, more sophisticated techniques.
summary: Although sampling techniques provide greater scalability, they also make it more difficult to infer the characteristics of the original stream. One of the first relevant works is the Good-Turing frequency estimation, a statistical technique proposed by Alan Turing and his assistant I.J. Good, for estimating the probability of encountering a hitherto unseen element in a stream, given a set of past samples. For a recent paper on the Good-Turing technique, see @cite_15 .