Tracking set-expression cardinalities over continuous update streams
View Patent ↗A method of estimating set-expression cardinalities over data streams with guaranteed small maintenance time per data-element update. The method only examines each data element once and uses a limited amount of memory. The time-efficient stream synopsis extends 2-level hash-sketches by randomly, but uniformly, pre-hashing data-elements prior to logarithmically hashing them to a first-level hash-table. This generates a set of independent 2-level hash-sketches. The set-union cardinality can be estimated by determining the smallest hash-bucket index j at which only a predetermined fraction of the b hash-buckets has a non-empty union |A∪B|. Once a set-union cardinality is estimated, general set-expression cardinalities may be estimated by counting witness elements for the set-expression, i.e., those first-level hash-buckets that are both a singleton for the set-expression and a set-union singleton. The set-expression cardinality is the set-union cardinality times the number of witness elements divided by the number of hash-buckets.
1. A method of obtaining an estimate of a set-expression cardinality relating to at least a first and second data-stream, the method comprising the steps of:
using a database management system comprising a computer for:
creating a first hash-sketch synopsis for the first data stream and a second hash-sketch synopsis for the second data stream, each hash-sketch synopsis comprising a random hash-table and a 2-level hash sketch for each hash-bucket of said random hash-tables, said 2-level hash sketch comprising a first-level hash-table and a counter away for each hash-bucket of said first-level hash-table;
pre-hashing said first and second data-streams into said first and second random hash tables, respectively;
hashing individual buckets of said random hashing tables to the corresponding 2-level hash sketch for each of those buckets;
maintaining said first and said second hash-sketch synopsis using one or more data elements from said first and second data-streams respectively;
obtaining a set-expression singleton count over said first and second hash-sketch; and
estimating said set-expression cardinality estimate using said set-expression singleton count.
2. The method of claim 1 wherein said maintaining said step of first and second hash-sketch synopsis comprises the steps of:
randomly hashing said data element from the data-element domain to said random hash-bucket; and
logarithmically hashing said data-element from said random hash-bucket to said first-level hash-bucket, and wherein the probability of logarithmically hashing said data-elements to said first-level hash-bucket decreases exponentially with the index of said first-level hash-bucket.
3. The method of claim 2 wherein said step of logarithmically hashing comprises mapping to a logarithmic hash-bucket using a least significant bit of a binary representation of a logarithmic hash image of said data-element.
4. The method of claim 3 wherein said 2-level hash structure counter allay comprises a total element count and one or more bit-location counts.
5. The method of claim 4 wherein said step of obtaining a set-expression singleton count over said first and second hash-sketch comprises the steps of:
determining if said first-level hash bucket contains a singleton by comparing said total element count to one or more of said bit-location counts.
6. The method of claim 5 wherein said determining if said first level hash bucket contains a singleton further comprises checking if all of said bit-location counts are either zero or equal to said total element count.
7. The method of claim 2 wherein said set expression is a union of said first and second data-streams; and wherein said step of obtaining a set-expression singleton count over said first and second hash-sketch comprises the steps of:
determining a smallest first-level hash-bucket index i at which the number of non-empty hash-buckets is less than or equal to a predetermined value; and
generating a set-union cardinality estimate of said first and second data-streams using said index i and said number of none empty hash buckets.
8. The method of claim 7 wherein said number of non-empty hash-buckets is given by a count c of corresponding pairs of said first-level hash-buckets in which either hash-bucket is non-empty.
9. The method of claim 8 wherein said predetermined value is (1+ε)b/8, where ε represents a relative error guarantee, b is the number of hash buckets in the random hash table; and wherein said estimate of cardinality of said union is log(1−c/b)/log(1−1/2i1).
10. The method of claim 2 further comprises the step of:
calculating an estimate of set-union cardinality over said first and second data-streams;
selecting an hash index level of said first-level hash-table using said estimate of set-union cardinality;
discovering a first number of said first-level hash-buckets at said hash index level which are singletons for set-union over said first and second data-streams;
counting a second number of said first-level hash-buckets at said hash index level which are set-union singletons and which are also set-expression witness elements for said first and second data streams; and
using said set-union cardinality estimate and said first and second number of first-level hash-buckets to provide said set-expression cardinality estimate.
11. The method of claim 10 wherein said set-expression cardinality estimate is provided by said number of said set-union cardinality estimate multiplied by said second number of first-level hash buckets and divided by said first number of hash buckets.
12. The method of claim 11 wherein said set-expression witness elements are selected from said first-level hash-buckets having an index higher than the log of said set-union cardinality estimate; and wherein said corresponding pair of first-level hash-buckets are singleton-union and singleton set-expression hash-buckets.
13. The method of claim 12 wherein said set-expression is one of a set-difference and a set-intersection.
14. The method of claim 13 wherein said set-expression is a set-difference; and wherein said corresponding pair of first-level hash-buckets is a set-difference singleton by virtue of said first-level hash-bucket of said first data-stream being a singleton hash-bucket while said first-level hash-bucket of said second data stream is an empty hash-bucket.
15. The method of claim 13 wherein said set-expression is a set-intersection; and wherein said corresponding pair of first-level hash-buckets is a set-intersection singleton by virtue of both being a singleton hash-bucket.
16. The method of claim 2 wherein said first and second data-streams are update streams having data elements inserted and deleted.
17. A computer program product recorded on computer-readable storage medium for obtaining an estimate of a set-expression cardinality relating to two or more data-streams, comprising instructions for:
computer-readable means for creating a first hash-sketch synopsis for the first data stream and a second hash-sketch synopsis for the second data stream, each hash-sketch synopsis comprising a random hash-table and a 2-level hash sketch for each hash-bucket of said random hash-tables, said 2-level hash sketch comprising a first-level hash-table and a counter array for each hash-bucket of said first-level hash-table;
computer-readable means for pre-hashing said first and second data-streams into said first and second random hash tables, respectively;
computer-readable means for hashing individual buckets of said random hashing tables to the corresponding 2-level hash sketch for each of for those buckets;
computer-readable means for maintaining said first and said second hash-sketch synopsis using one or more data elements from said first and second data-streams respectively;
computer-readable means for obtaining a set-expression singleton count over said first and second hash-sketch; and
computer-readable means for estimating said set-expression cardinality estimate using said set-expression singleton count.