EXTENDED HITCOUTING TO ESTIMATE CARDINALTY.

A new algorithm is introduced to estimate the number n of distinct elements in a multi set. This information has many applications in network monitoring and network security, as detecting Denial Of Service attacks. It is an extended version of the Hit Counting [WZT90]. Its combination with a recently introduced algorithm, Mincount*[Gi05], gives an algorithm, that estimates the number n within few percents while using a very small auxiliary memory, for any size of files, from few units to millions (e.g. 96 kB is sufficient to attain a precision of 2%). For some cardinalities, the precision is increased by a factor close to 4, compared to the classical hit counting. The algorithm has been validated by simulations. [ABSTRACT FROM AUTHOR]