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_9: We consider the problem of estimating the number of distinct values in a data stream with repeated values. Distinct-values estimation was one of the first data stream problems studied: In the mid-1980’s, Flajolet and Martin gave an effective algorithm that uses only logarithmic space. Recent work has built upon their technique, improving the accuracy guarantees on the estimation, proving lower bounds, and considering other settings such as sliding windows, distributed streams, and sensor networks.
  @cite_10: Methods for Approximate Query Processing (AQP) are essential for dealing with massive data. They are often the only means of providing interactive response times when exploring massive datasets, and are also needed to handle high speed data streams. These methods proceed by computing a lossy, compact synopsis of the data, and then executing the query of interest against the synopsis rather than the entire dataset. We describe basic principles and recent developments in AQP. We focus on four key synopses: random samples, histograms, wavelets, and sketches. We consider issues such as accuracy, space and time efficiency, optimality, practicality, range of applicability, error bounds on query answers, and incremental maintenance. We also discuss the trade-offs between the different synopsis types.
summary: Many early works in the database literature tried to address the problem of estimating the cardinality from small samples; until the mid 1990s, this was the prevalent approach @cite_9 . A sample of the data was collected and sophisticated estimators applied on the distributions of the values (see @cite_10 @cite_9 for relevant references). However, because these estimators were sensitive to the order of the elements and their repetition pattern, they failed to provide accurate estimates (see pages 19-21 in @cite_10 ).