Optimiertes Learned Count-Min Sketch beschleunigt Datenfrequenzschätzungen

Eine neue Veröffentlichung auf arXiv präsentiert das Optimized Learned Count‑Min Sketch (OptLCMS), eine Weiterentwicklung des beliebten Count‑Min Sketch (CMS). OptLCMS nutzt maschinelles Lernen, um die Schätzgenauigkeit bei gleicher Speichergröße zu erhöhen, und löst gleichzeitig die langsame Bauzeit und fehlende theoretische Fehlergrenzen des bisherigen Learned Count‑Min Sketch (LCMS).

Der Ansatz teilt den Eingabebereich in mehrere Partitionen auf und weist jeder Partition ein eigenes CMS‑Modul zu. Für jedes Modul werden die CMS‑Parameter analytisch berechnet, während die Grenzwerte für die Fehlerwahrscheinlichkeit mittels dynamischer Programmierung optimiert werden. Dadurch entfällt die bisher notwendige empirische Feinabstimmung, was die Konstruktion deutlich beschleunigt.

OptLCMS bietet zudem die Möglichkeit, die zulässige Fehlergrenze explizit festzulegen, was die praktische Flexibilität erhöht. Experimentelle Ergebnisse zeigen, dass OptLCMS schneller aufgebaut wird, die Wahrscheinlichkeit von intolerablen Fehlern reduziert und gleichzeitig die Schätzgenauigkeit des LCMS erreicht.