Method and system for estimating the cardinality of information
AssigneeThe Nielsen Company (US), LLC
InventorsMichael Sheppard, Edward Murphy, Jonathan Sullivan
Life of this patent
Estimating the term…
Abstract
A computer-implemented method for efficiently estimating the number of unique elements in a collection of elements comprises generating, via hash logic, hash values for each element of the collection of elements. The method further comprises specifying, in a sketch-frequency table, a set of discrete statistical values associated with the hash values and, for each discrete statistical value of the set of discrete statistical values, information indicative of a frequency at which binary representations of the hash values are associated with the discrete statistical value. The cardinality of the collection of elements is estimated based on the sketch-frequency table.
Claims20
A computer-implemented method for efficiently estimating a number of unique elements in a collection of elements, the method comprising:
- generating, via hash logic, hash values for each element of the collection of elements;
- specifying, in a sketch-frequency table, a set of discrete statistical values associated with the hash values and, for each discrete statistical value of the set of discrete statistical values, information indicative of a frequency at which the hash values are associated with the discrete statistical value;
- and
- estimating a cardinality of the collection of elements based on the sketch-frequency table, wherein estimating the cardinality of the collection of elements based on the sketch-frequency table comprises (i) generating a plurality of cardinality estimates associated with a plurality of different orders of the set of discrete statistical values specified in the sketch-frequency table, (ii) selecting, according to a Monte Carlo analysis and without replacement, at least some of the generated plurality of cardinality estimates, and (iii) estimating the cardinality of the collection of elements as an arithmetic average of selected cardinality estimates.
A computing system comprising:
- one or more processors;
- and
- a memory in communication with the one or more processors, wherein the memory stores instruction code that, when executed by the one or more processors, causes the computing system to perform operations comprising:
- generating, via hash logic, hash values for each element of a collection of elements;
- specifying, in a sketch-frequency table, a set of discrete statistical values associated with the hash values and, for each discrete statistical value of the set of discrete statistical values, information indicative of a frequency at which the hash values are associated with the discrete statistical value;
- and
- estimating a cardinality of the collection of elements based on the sketch-frequency table, wherein estimating the cardinality of the collection of elements based on the sketch-frequency table comprises (i) generating a plurality of cardinality estimates associated with a plurality of different orders of the set of discrete statistical values specified in the sketch-frequency table, (ii) selecting, according to a Monte Carlo analysis and without replacement, at least some of the generated plurality of cardinality estimates;
- and (iii) estimating the cardinality of the collection of elements as an arithmetic average of selected cardinality estimates.
A non-transitory computer-readable medium having stored thereon instruction code that, when executed by one or more processors of a computing system, causes the computing system to perform operations comprising:
- generating, via hash logic, hash values for each element of a collection of elements;
- specifying, in a sketch-frequency table, a set of discrete statistical values associated with binary representations of the hash values and, for each discrete statistical value of the set of discrete statistical values, information indicative of a frequency at which binary representations of the hash values are associated with the discrete statistical value;
- and
- estimating a cardinality of the collection of elements based on the sketch-frequency table, wherein estimating the cardinality of the collection of elements based on the sketch-frequency table comprises (i) generating a plurality of cardinality estimates associated with a plurality of different orders of the set of discrete statistical values specified in the sketch-frequency table, (ii) selecting, according to a Monte Carlo analysis and without replacement, at least some of the generated plurality of cardinality estimates, and (iii) estimating the cardinality of the collection of elements as an arithmetic average of selected cardinality estimates.
Dependencies are inferred from the claim text.