×

Method and apparatus for determining distinct cardinality dual hash bitmaps

  • US 5,802,521 A
  • Filed: 10/07/1996
  • Issued: 09/01/1998
  • Est. Priority Date: 10/07/1996
  • Status: Expired due to Term
First Claim
Patent Images

1. In a computer system having a processor coupled to a bus and a computer readable memory unit coupled to said bus, a method for determining distinct cardinality of a data sample, said method comprising the steps of:

  • (a) receiving said data sample, said data sample containing C entries;

    (b) determining a first distinct cardinality value of said data sample using a hashing function and a first bitmap, said first bitmap comprising x entries;

    (c) determining a second distinct cardinality value of said data sample using a hashing function and a fractional bitmap that is a fraction of a second bitmap, said second bitmap comprising y logical entries and said fractional bitmap comprising z entries wherein y is larger than x; and

    (d) selecting between said first distinct cardinality value and said second distinct cardinality value as said distinct cardinality of said data sample, wherein said first bitmap and said fractional bitmap are separate bitmaps and are stored within said computer readable memory unit.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×