Bounds for Frequency Estimation of Packet Streams

We consider the problem of approximating the frequency of frequently occurring elements in a stream of length n using only a memory of size n. This models the process of gathering statistics on Internet packet streaming using a memory that is small relative to the number of classes (e.g. IP addresses) of packets. We show that when some data item a occurs an times in a stream of length n, the FREQUENT algorithm of Demaine et al