Method and apparatus for determining distinct cardinality dual h

Details Method and apparatus for determining distinct cardinality dual h Method and apparatus for determining distinct cardinality dual h

1996-10-07

1998-09-01

Black, Thomas G.

Data processing: database and file management or data structures

Database design

Data structure types

707 1, 707 2, 707 7, 707100, 39520031, G06F 700

Patent

active

058025219

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.

REFERENCES:
patent: 5557785 (1996-09-01), Lacquit et al.
patent: 5625773 (1997-04-01), Bespalko et al.
patent: 5673252 (1997-09-01), Johnson et al.

Affiliated with

Also associated with

Rating

Method and apparatus for determining distinct cardinality dual h does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for determining distinct cardinality dual h, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determining distinct cardinality dual h will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-284202