Phase transition in count approximation by Count-Min sketch with conservative updates - Archive ouverte HAL Access content directly
Reports Year : 2022

Phase transition in count approximation by Count-Min sketch with conservative updates

(1) ,
1
Gregory Kucherov
  • Function : Author
  • PersonId : 1192453

Abstract

Count-Min sketch is a hash-based data structure to represent a dynamically changing associative array of counters. Here we analyse the counting version of Count-Min under a stronger update rule known as \textit{conservative update}, assuming the uniform distribution of input keys. We show that the accuracy of conservative update strategy undergoes a phase transition, depending on the number of distinct keys in the input as a fraction of the size of the Count-Min array. We prove that below the threshold, the relative error is asymptotically o(1) (as opposed to the regular Count-Min strategy), whereas above the threshold, the relative error is Θ(1). The threshold corresponds to the peelability threshold of random k-uniform hypergraphs. We demonstrate that even for small number of keys, peelability of the underlying hypergraph is a crucial property to ensure the o(1) error. Finally, we provide an experimental evidence that the phase transition does not extend to non-uniform distributions, in particular to the popular Zipf's distribution.
Fichier principal
Vignette du fichier
FusyKucherov-arxiv_v2.pdf (1.13 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03867568 , version 1 (23-11-2022)

Identifiers

Cite

Éric Fusy, Gregory Kucherov. Phase transition in count approximation by Count-Min sketch with conservative updates. LIGM/CNRS. 2022. ⟨hal-03867568⟩
0 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More