Compact Frequency Estimators in Adversarial Environments
Abstract: Count-Min Sketch (CMS) and HeavyKeeper (HK) are two realizations of a compact frequency estimator (CFE). These are a class of probabilistic data structures that maintain a compact summary of (typically) high-volume streaming data, and provide approximately correct estimates of the number of times any particular element has appeared. CFEs are often the base structure