Paper 2023/1366
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 provides approximately correct estimates of the number of times any particular element has appeared. CFEs are often the base structure in systems looking for the highest-frequency elements (i.e., top-
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Published elsewhere. Major revision. Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security (CCS '23)
- DOI
- 10.1145/3576915.3623216
- Keywords
- probabilistic data structureCount-min sketchHeavyKeeperCount-Keeper
- Contact author(s)
-
smarkelon @ ufl edu
mia filic @ inf ethz ch
teshrim @ ufl edu - History
- 2023-09-25: revised
- 2023-09-12: received
- See all versions
- Short URL
- https://ia.cr/2023/1366
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1366, author = {Sam A. Markelon and Mia Filić and Thomas Shrimpton}, title = {Compact Frequency Estimators in Adversarial Environments}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1366}, year = {2023}, doi = {10.1145/3576915.3623216}, url = {https://eprint.iacr.org/2023/1366} }