Methods and systems for estimating a count of unique items

摘要

According to one general aspect, a method is provided for managing memory when counting unique items, the method using a pattern of bits in a unique estimator mask. The method may create a unique estimator mask based on fingerprints calculated for previously encountered items, and determine a number with the highest probability for creating the pattern of bits in the mask. When the number with the highest probability is determined, it may be returned as the estimated count of unique items.

主权项

1. A computer-implemented method for managing memory usage when counting unique items, comprising:
receiving a request from a computing system for an estimated count of the unique items for a particular key value receiving 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; calculating, by one or more processors, a first probability that a particular number of encountered items created the pattern of non-zero bits and zero bits of the mask; determining 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; identifying 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 providing the estimated count of the unique items to the computing system as a response to the request.