Paper "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm" introduce an efficient algorithm which can help to estimate distinct items in large data set.
I am thinking about few related question:
Given a large data set (total data size is known), how to find top k frequent items? better to use less space. Simple approach(count frequency of each item in data set, and sort) requires lots of space
What about finding top k frequent items in data stream?
Is there any near-optimal algorithms avaiable? or, can we prove relationship between space requirement and error ratio?