Importance

Loading Importance Indicators...

Abstract

A method and apparatus for determining distinct cardinality of a data sample using dual hash bitmaps. Two different bitmaps determine the distinct cardinality of the data sample (e.g., a column of data within a data table of a database). A small sized bitmap, M*sqrt(C*K), is used where M is a programmable value that reduces collision error, C is the size of the column ('data sample size'), and K is a key density value. Once selected, both M and K are constant. Sample entry values are hashed by a hash function and a modulo function determines an entry into the first bitmap. Based on the bitmap's bit entries, a first counter is updated, or not, to maintain a first distinct cardinality value. A large bitmap is used having a size, M*C, but only a small fraction is actually used, M*sqrt(C*K). Only hashed column entries falling inside the fraction are processed as above to maintain a second counter. At the end of the data sample entry processing, the second counter is extrapolated to the large bitmap size. Expected collision error compensation is computed and compensated for the first and second counters. Distribution error is computed for the second counter and added with its compensated collision error. The total errors of the first and second counters are compared to select an output distinct cardinality. The distinct cardinality measurement requires sub-linear increase in memory for each linear increase in sample size.

Loading the Abstract Image...

First Claim