12
Frequency Count Query Probabilistic Data Structures
12.1 Introduction
This category concerns for estimating the count of a particular items in a set. For example, search engine uses frequency estimators for extracting frequently searched queries and network routers uses them for locating common source and destination addresses. One proposed solution to this randomly extract a sample from the set that shows properties of complete set. However, achieving true randomness is a quite unfavorable task. So, sampling also is not a useful solution to our problem. Also with hash tables, memory requirement becomes high (linear space requirements) as more items are added. Majority algorithm [52] and Misra-Gries [144] algorithms are two popular deterministic ...
