Bounds for Frequency Estimation of Packet Streams.

摘要: We consider the problem of approximating frequency frequently occurring elements in a stream length n using only memory size m n. This models process gathering statistics on Internet packet streaming that is small relative to number classes (e.g. IP addresses) packets. show when some data item occurs αn times n, FREQUENT algorithm Demaine et al. [4], can approximate a’s with an error no more than (1−α)n/m. also give lower-bound (1−α)n/(m+1) accuracy any deterministic counting algorithm, which implies nearly optimal. Finally, we randomized algorithms not be significantly accurate since there lower bound (1−α)Ω(n/m) expected algorithm.