Counting distinct elements in a data stream. (English) Zbl 1028.68949
Rolim, José D. P. (ed.) et al., Randomization and approximation techniques in computer science. 6th international workshop, RANDOM 2002, Cambridge, MA, USA, September 13-15, 2002. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2483, 1-10 (2002).
Summary: We present three algorithms to count the number of distinct elements in a data stream to within a factor of \(1 \pm \epsilon\). Our algorithms improve upon known algorithms for this problem, and offer a spectrum of time/space tradeoffs.
For the entire collection see [Zbl 1001.00041].
For the entire collection see [Zbl 1001.00041].
MSC:
| 68W25 | Approximation algorithms |
