Patent ID: 11934399
Assignee: THE NIELSEN COMPANY (US), LLC
Field: Computer technology (Electrical engineering)
Classification: CPC G | IPC G

Claim 7:
8. A computing system:
one or more processors; and
a memory in communication with the one or more processors, wherein the memory stores instruction code that, when executed by the one or more processors, causes the computing system to perform operations comprising:
generating, via hash logic, hash values associated with a collection of elements, wherein the hash values specify bit positions within an array of bits, wherein hash values output from the hash logic conform to a geometric distribution of bits such that bit positions of the array of bits corresponding to lower orders bits are more likely to be generated than bit positions corresponding to higher-order bits;
setting bits of the array of bits corresponding to the bit positions;
counting a number of bits of the array of bits that are set;

estimating, by estimation logic, a number of unique elements of the collection of elements as a function of the number of bits of the array of bits that are set,
wherein bit position L(xj) associated with a particular element xj, is determined according to the function:, L
   ⁡
   (
   
    x
    j
   
   )
  
  =
  
   ⌈
   
    
     log
     ⁡
     (
     
      1
      -
      
       h
       ⁡
       (
       
        x
        j
       
       )
      
     
     )
    
    
     log
     ⁡
     (
     
      1
      -
      ρ
     
     )
    
   
   ⌉
  
 

where h corresponds to a hash function that hashes each xj uniformly at random to values in the unit interval and ρ specifies a geometric distribution of the bits across the array of bits.