Methods and systems for estimating a count of unique items

A non-transitory computer-readable storage medium for managing memory usage when counting unique items, the storage medium having recorded and embodied thereon instructions that, when executed by one or more processors of a computer system, cause the computer system to:

• receive a request from a computing system for an estimated count of the unique items for a particular key value;
• receive a unique estimator mask associated with the particular key value from a memory device, the unique estimator mask having a number of bits, at least some of the bits being non-zero and at least some of the bits being zero based on fingerprints calculated from previously encountered items, the non-zero bits and the zero bits forming a pattern;
• calculate a first probability that a particular number of encountered items created the pattern of non-zero bits and zero bits of the mask;
• determine whether the first probability for the particular number is less than a first probability for another number that is one less than the particular number;
• identify the another number as an estimated count of unique items when it is determined that the first probability for the particular number is less than the first probability for the another number;
• and
• provide the estimated count of unique items to the computing system as a response to the request.

A system for managing memory usage when counting unique items comprising:

• a memory configured to store executable code;
• and
• a processor operably coupled to the memory, the processor configured to execute the code to:
• receive a request from a computing system for an estimated count of the unique items for a particular key value;
• receive a unique estimator mask associated with the particular key value from a memory, the unique estimator mask having a number of bits, at least some of the bits being non-zero and at least some of the bits being zero based on fingerprints calculated from previously encountered items, the non-zero bits and the zero bits forming a pattern,
• calculate a first probability that a particular number of encountered items created the pattern of non-zero bits and zero bits;
• determine whether the first probability for the particular number is less than a first probability for another number that is one less than the particular number,
• identify the another number as the estimated count of the unique items when it is determined that the first probability for the particular number is less than the first probability for the another number;
• and
• provide the estimated count of the unique items to the computing system as a response to the request.