Abstract
We are concerned with estimating alphabet size N from a stream of symbols taken uniformly at random from that alphabet. We define and analyze a memory-restricted variant of an algorithm that have been earlier proposed for this purpose. The alphabet size N can be estimated in O(N−−√) time and space by the memory-restricted variant of this algorithm.
| Original language | English |
|---|---|
| Publisher | arXiv.org |
| Publication status | Published - 2017 |
| MoE publication type | D4 Published development or research report or study |