Patent ID: 8788506
Filing Date: 2014-07-22
Classification: G06F,H04L

Abstract:
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.