Adaptive distinct counting for network-traffic monitoring and other applications

摘要

In one embodiment, a counting method of the invention uses an adaptive sketching-update process to compress an unknown cardinality into a counter value that counts the number of binary ones in a hashed bitmap vector. The sketching-update process is probabilistic in nature and uses bit-flip probabilities that are adaptively decreased as the counter value increases. Parameters of the sketching-update process are selected so that the relative error of cardinality estimates obtained based on the counter values is relatively small and substantially constant over a relatively wide range of cardinalities, e.g., from one to about one million. Due to the latter property, the counting method can advantageously be implemented in the form of embedded software that relies on a relatively small, fixed amount of memory.

主权项

1. A device-implemented method of distinct counting, the method comprising:
(A) deriving a hash key for an item of a plurality of items; (B) applying a hash function to the hash key to identify a corresponding target bucket in a bitmap, wherein the bitmap has a plurality of buckets, each for storing a value; and (C1) if the target bucket has a first value, then probabilistically changing the first value to a second value, with a probability of the change depending on a total number of second values stored in the bitmap, wherein step (B) comprises:
(B1) generating a hash value by applying the hash function to the hash key;(B2) converting the generated hash value into a number that is different from said hash value, wherein said converting includes truncating the generated hash value to a selected number of most significant bits; and(B3) using the number produced at step (B2) to identify the target bucket.