Patent ID: 7987177

Claim:
A computer-based method to estimate distinct values in a partitioned dataset, said computer-based implemented in computer readable program code stored in computer memory, said computer-based method comprising the steps of: a. creating a synopsis of each partition in a partitioned dataset; b. combining created synopsis to construct distinct value (DV) estimations of a base partition or of a compound partition that is based on at least one of the following multiset operations: multiset-union, multiset-intersection, and multiset-difference; and c. outputting said constructed DV estimations in (b); and wherein said step of creating synopsis of a partition further comprises the steps of: selecting a hash function h with domain , which is a value domain of the partitioned dataset, and range {0, 1, . . . , M}, wherein M=O(| | 2 ) and | |is the number of distinct values in , said hash function h to be used for all synopses in said partitioned dataset; when a partition is a base partition A with domain (A): i. hashing each value in (A) using hash function h; ii. recording k smallest values h(v 1 ), h(v 2 ), . . . , h(v k ) among said hashed values, as well as recording the multiplicity of each of the values v 1 , v 2 , . . . , v k in A, and iii. creating said synopsis as an AKMV synopsis L A + =(L A ,c A ) based on said recorded k smallest values and said recorded multiplicities; or when a partition is a compound partition G=E op F, where op is one of ∪ m , ∩ m , and \ m , and E and F have respective AKMV synopses L E + =(L E , c E ) and L F + =(L F , c F ) of sizes k E and k F , creating said synopsis as an AKMV synopsis L G + =(L E ⊕ L F , c G ), where, for each w ∈ L E ⊕ L F , c G c G ⁡ ( w ) = { c E ⁡ ( w ) + c F ⁡ ( w ) if ⁢ ⁢ op = ⋃ m min ⁡ ( c E ⁡ ( w ) , c F ⁡ ( w ) ) if ⁢ ⁢ op = ⋂ m max ⁡ ( c E ⁡ ( w ) - c F ⁡ ( w ) , 0 ) if ⁢ ⁢ op = \ m .