# US 8,788,506 B1 · Methods and systems for estimating a count of unique items > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,788,506 B1 - Document ID: US8788506B1 - Status: Granted - Kind: B1 - Application number: 13/476,726 - Filed: 2012-05-21 - Granted: 2014-07-22 - Earliest claimed: 2012-05-21 - Assignees: Google Inc. - Applicants: Peter Dornbach - Inventors: Peter Dornbach - Web page: https://patentgrep.com/patent/US8788506B1 ## CPC - G06F 16/951: Indexing; Web crawling techniques - H04L 2209/04: Masking or blinding - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract 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. ## Claims ### Claim 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. ### Claim 2 (depends on 1) The method of claim 1, wherein calculating the first probability includes: initializing the first probability to 1; and repeating, by the one or more processors, for each bit position in the mask, the operations of: calculating a second probability that a bit at the position has a non-zero value, when the bit at the position has a non-zero value, multiplying the first probability by (1 minus the second probability), and when the bit at the position has a zero value, multiplying the first probability by the second probability. ### Claim 3 (depends on 2) The method of claim 2, wherein calculating the second probability (pi) for each bit position in the mask includes determining that pi is equal to (1−0.5i+1)n, where i is the bit position and n is the particular number. ### Claim 4 (depends on 1) The method of claim 1, wherein a bit of the mask is non-zero when a position of the bit matches a position of the first occurrence of a non-zero bit of a fingerprint for one of the previously encountered items. ### Claim 5 (depends on 1) The method of claim 1, wherein the previously encountered items are uniform resource locators (URLs). ### Claim 6 (depends on 5) The method of claim 5, wherein the fingerprints are calculated from characters of the URLs. ### Claim 7 (depends on 1) The method of claim 1, wherein after receiving the mask, calculating the first probability and the determining are repeated, beginning with the particular number being zero and increasing the particular number each time the calculating and determining are repeated. ### Claim 8 (depends on 7) The method of claim 7, wherein the identifying further includes: terminating the repeating of the calculating and the determining. ### Claim 9 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. ### Claim 10 (depends on 9) The storage medium of claim 9, wherein calculating the first probability includes: initializing the first probability to 1, and repeating, for each bit position in the mask, the operations of: calculating a second probability that a bit at the position has a non-zero value, when the bit at the position has a non-zero value, multiplying the first probability by (1 minus the second probability), and when the bit at the position has a zero value, multiplying the first probability by the second probability. ### Claim 11 (depends on 10) The storage medium of claim 10, wherein calculating the second probability (pi) for each bit position in the mask includes determining that pi is equal to (1−0.5i+1)n, where i is the bit position and n is the particular number. ### Claim 12 (depends on 9) The storage medium of claim 9, wherein a bit of the mask is non-zero when a position of the bit matches a position of the first occurrence of a non-zero bit of a fingerprint for one of the previously encountered items. ### Claim 13 (depends on 9) The storage medium of claim 9, wherein the previously encountered items are uniform resource locators (URLs). ### Claim 14 (depends on 9) The storage medium of claim 9, wherein after receiving the mask, the instructions further cause the one or more processors to repeat calculating the first probability and determining whether the first probability for the particular number is less than the first probability for the another number, beginning with the particular number being zero and increasing the particular number each time the calculating and determining are repeated. ### Claim 15 (depends on 14) The storage medium of claim 14, wherein as part of the identifying the instructions further cause the one or more processors to: terminate the repeating of the calculating and the determining. ### Claim 16 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. ### Claim 17 (depends on 16) The system of claim 16, wherein calculating the first probability includes: initializing the first probability to 1; and repeating, for each bit position in the mask, the operations of: calculating a second probability that a bit at the position has a non-zero value, when the bit at the position has a non-zero value, multiplying the first probability by (1 minus the second probability), and when the bit at the position has a zero value, multiplying the first probability by the second probability. ### Claim 18 (depends on 17) The system of claim 17, wherein as part of calculating the second probability (pi) for each bit position in the mask the processor executes code to determine that pi is equal to (1−0.5i+1)n, where i is the bit position and n is the particular number. ### Claim 19 (depends on 16) The system of claim 16, wherein a bit of the mask is non-zero when a position of the bit matches a position of the first occurrence of a non-zero bit of a fingerprint for one of the previously encountered items. ### Claim 20 (depends on 16) The system of claim 16, wherein after receiving the mask, the processor is further configured to execute the code to repeat calculating the first probability and determining whether the first probability is less than the first probability for the another number, beginning with the particular number being zero and increasing the particular number each time the calculating and determining are repeated. ### Claim 21 (depends on 20) The system of claim 20, wherein as part of the identifying, the processor is further configured to execute the code to terminate the repeating of the calculating and the determining.