Tracking set-expression cardinalities over continuous update streams

A computer-readable medium for obtaining an estimate of a set-expression cardinality relating to two or more data-streams, comprising instructions for:

• creating a first and a second hash-sketch synopsis comprising a first and a second random hash-table and a first-level hash table for each hash-bucket of said random hash-tables;
• 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.

A computing device for estimating a set-expression cardinality over one or more update streams, comprising:

• a computer-readable medium comprising instructions for:
• randomly hashing one or more data elements from said update streams to on or more random hash tables having random hash buckets;
• logarithmically hashing said data elements from said random hash buckets to a logarithmic hash table;
• measuring a probability of corresponding logarithmic hash bins being singleton union at a selected logarithmic hash table index level;
• estimating a set-union cardinality over said one or more data-streams using said probability of a said corresponding logarithmic hash bins being singleton union and said index level;
• measuring the probability of said corresponding hash bins being singleton set-expressions and singleton union at a second selected logarithmic hash table index level;
• and
• estimating said set-expression cardinality over said one or more data-streams using said probability of said corresponding hash bins being singleton set-expression and singleton union and said set-union cardinality.