# Optimized Learned Count-Min Sketch

arXiv: https://arxiv.org/abs/2512.12252 · HTML: https://mlsanity.com/paper/2512.12252/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 26 references that are in the map.
- First posted on arXiv 13 Dec 2025.

## Builds on (most cited first, 11 of 11)

- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [ALEX: An Updatable Adaptive Learned Index](https://mlsanity.com/paper/1905.08898/) (2019)
- [RadixSpline: A Single-Pass Learned Index](https://mlsanity.com/paper/2004.14541/) (2020)
- [Learning Multi-dimensional Indexes](https://mlsanity.com/paper/1912.01668/) (2019)
- [Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads](https://mlsanity.com/paper/2006.13282/) (2020)
- [Adaptive Learned Bloom Filter (Ada-BF): Efficient Utilization of the Classifier](https://mlsanity.com/paper/1910.09131/) (2019)
- [MISSION: Ultra Large-Scale Feature Selection using Count-Sketches](https://mlsanity.com/paper/1806.04310/) (2018)
- [Improved Frequency Estimation Algorithms with and without Predictions](https://mlsanity.com/paper/2312.07535/) (2023)
- [Scaling Graph-based Semi Supervised Learning to Large Number of Labels Using Count-Min Sketch](https://mlsanity.com/paper/1310.2959/) (2013)
- [Fast Partitioned Learned Bloom Filter](https://mlsanity.com/paper/2306.02846/) (2023)
- [FlexFlood: Efficiently Updatable Learned Multi-dimensional Index](https://mlsanity.com/paper/2411.09205/) (2024)

## Abstract (arXiv)

Count-Min Sketch (CMS) is a memory-efficient data structure for estimating the frequency of elements in a multiset. Learned Count-Min Sketch (LCMS) enhances CMS with a machine learning model to reduce estimation error under the same memory usage, but suffers from slow construction due to empirical parameter tuning and lacks theoretical guarantees on intolerable error probability. We propose Optimized Learned Count-Min Sketch (OptLCMS), which partitions the input domain and assigns each partition to its own CMS instance, with CMS parameters analytically derived for fixed thresholds, and thresholds optimized via dynamic programming with approximate feasibility checks. This reduces the need for empirical validation, enabling faster construction while providing theoretical guarantees under these assumptions. OptLCMS also allows explicit control of the allowable error threshold, improving flexibility in practice. Experiments show that OptLCMS builds faster, achieves lower intolerable error probability, and matches the estimation accuracy of LCMS.