Flajolet-Martin Algorithm
Flajolet-Martin algorithm approximates the number of unique objects in a stream or a database in one pass. If the stream containselements with
of them unique, this algorithm runs in
time and needs
memory. So the real innovation here is the memory usage, in that an exact, brute-force algorithm would need
memory (e.g. think “hash map”).