Patent ID: 7496584

Claim:
A method performed on a computer system for estimating a cardinality value for a set of data values, the method comprising: initializing a data structure for representing an array of counts, wherein a given entry in the array of counts indicates a number of data values that have hashed to a position of the given entry; obtaining a data value from said set of data values; transforming said data value into a transformed string; modifying said data structure with said transformed string; obtaining a summary statistic value from said modified data structure, wherein the summary statistic value is based on the array of counts; and generating said estimated cardinality value using said summary statistic value, wherein said generating step is performed for each distinct occurrence of a hashing function within a plurality of hashing functions, and wherein said generating step further comprises: generating a cardinality estimate value associated with each instance of said hashing function, wherein said cardinality estimate value generating step further comprises computing a result of 2n/q, wherein n is equal to said summary statistic value and q is less than one; summing said cardinality estimate values; averaging said cardinality estimate values to produce a raw cardinality estimate value; and adjusting said raw cardinality estimate value for data value collisions to produce a final cardinality estimate value.