US 11,537,594 B2 · Approximate estimation of number of distinct keys in a multiset using a sample

Abstract

Herein are quantitative analytics to increase the accuracy of cardinality estimation without increasing sample size. In an embodiment, a computer selects a few sample values from a multiset. A high-frequency exact count of distinct values that have at least a threshold amount of occurrences in the sample values is counted. A low-frequency exact count of distinct values in the sample that do not have at least the threshold amount of occurrences in the sample is counted. Based on multiple binomial probabilities, an upper bound of a count of missing distinct values in the multiset that are not in the sample is calculated. A total count of distinct values (NDV) in the multiset is estimated based on: a) the high-frequency exact count of distinct values, b) the low-frequency exact count of distinct values, and c) the upper bound of the count of missing distinct values in the multiset that are not in the sample.

Claims20

Dependent claims

A method comprising:

selecting a sample plurality of values from a multiset;
determining a high-frequency exact count of distinct values that have at least a threshold amount of occurrences in the sample plurality of values;
determining a low-frequency exact count of distinct values in the sample plurality of values that do not have at least said threshold amount of occurrences in the sample plurality of values;
calculating, based on a plurality of binomial probabilities, an upper bound of a count of missing distinct values in said multiset that are not in said sample plurality of values;
estimating a total count of distinct values in the multiset based on:
said high-frequency exact count of distinct values,
said low-frequency exact count of distinct values, and
said upper bound of said count of missing distinct values in said multiset that are not in said sample plurality of values.

5 more elements

One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause:

selecting a sample plurality of values from a multiset;
determining a high-frequency exact count of distinct values that have at least a threshold amount of occurrences in the sample plurality of values;
determining a low-frequency exact count of distinct values in the sample plurality of values that do not have at least said threshold amount of occurrences in the sample plurality of values;
calculating, based on a plurality of binomial probabilities, an upper bound of a count of missing distinct values in said multiset that are not in said sample plurality of values;
estimating a total count of distinct values in the multiset based on:
said high-frequency exact count of distinct values,
said low-frequency exact count of distinct values, and
said upper bound of said count of missing distinct values in said multiset that are not in said sample plurality of values.

5 more elements

Dependencies are inferred from the claim text.

Approximate estimation of number of distinct keys in a multiset using a sample

Life of this patent

Approximate estimation of number of distinct keys in a multiset using a sample

Life of this patent

Abstract

Claims20