¿Cuál es la diferencia entre HyperLogLog y Count-Min Sketch?

HyperLogLog estima el número de elementos únicos (cardinalidad), Count-Min Sketch — la frecuencia de elementos específicos. HLL usa registros con ceros iniciales, CMS — una tabla de contadores con mínimo.

¿Cuánta memoria consumen estas estructuras?

HyperLogLog: 1 KB para 1024 registros independientemente del volumen. Count-Min Sketch: 200 KB con width=10k, depth=5.

¿Son necesarios los mutexes en la implementación?

Sí, para acceso asíncrono. En el ejemplo, las estructuras no son seguras para hilos, agrega sync.Mutex o operaciones atómicas.

HyperLogLog y Count-Min Sketch en Go para Big Data

Estructuras de datos probabilísticas eficientes en Go: HyperLogLog y Count-Min Sketch

HyperLogLog estima el número de elementos únicos en un flujo de datos con un error del 1-3% utilizando solo 1 KB de memoria. El algoritmo hashea los elementos, analiza el número de ceros a la izquierda en su representación binaria y almacena estadísticas en un array de registros. Esto proporciona un tiempo de inserción O(1) y O(m) para la estimación, donde m es el número de registros (típicamente 1024).

Parámetros clave:

m = 1024 registros (8 bits por registro)
b = 8 bits para indexación de registro
Funciones hash: fnv64a con shuffling de bits

package main

import (
	"fmt"
	"hash/fnv"
	"math"
	"math/rand"
	"strconv"
)

const (
	m = 1024 // count registtrov. This osnovnoy parametr, vliyayuschiy on tochnost.
	b = 8  // number bit, ispolzuemykh for opredeleniya indexa register from hash.
)

type HyperLogLog struct {
    // when asynchronous interaction worth think about mutexes
	registers [m]byte
}

func NewHyperLogLog() *HyperLogLog {
	return &HyperLogLog{}
}

// hash returns dva 32-bitnykh numbers from stroki
func hash(s string) (uint32, uint32) {
	h := fnv.New64a()
	h.Write([]byte(s))
	v := h.Sum64()

	// Shuffling bits, so that uluchshit raspredelenie
	w := uint32(v >> 32)
	z := uint32(v)

	// Dobavlyaem peremeshivanie, uluchshaet kachestvo sluchaynosti and pomogaet izbezhat problem with plokhim raspredeleniem hashes
	w ^= z<<13 | z>>(32-13)
	z ^= w<<7 | w>>(32-7)
	w ^= z<<17 | z>>(32-17)

	return w, z
}

// Withchitaet count zeros left in dvoichnoy record numbers,
// if all bits — nuli, vozvraschaetsya 32.
func countLeadingZeros(x uint32) byte {
	for i := 0; i < 32; i++ {
		if (x>>(31-i))&1 == 1 {
			return byte(i)
		}
	}
	return 32
}

// Kheshiruem stroku.
// Beryom chast hash h1, so that define, in kakoy registtr popadyot element.
// By vtoroy chasti h2 schitaem, how many veduschikh zeros (rho), pribavlyaem 1.
// If eto wartość greater, than uzhe est in registtre — update ego.
func (hll *HyperLogLog) Add(s string) {
	h1, h2 := hash(s)

	// opredelyaem index register
	idx := h1 % m

	// vychislyaem wartość for update register
	rho := countLeadingZeros(h2) + 1

	if rho > hll.registers[idx] {
		hll.registers[idx] = rho
	}
}

// Withlozhnye formuly, by essence eta function
// delaet otsenku kolichestva unique elements
func (hll *HyperLogLog) Estimate() float64 {
	sum := 0.0
	for _, val := range hll.registers {
		sum += 1 / math.Pow(2, float64(val))
	}
	estimate := alpha(m) * m * m / sum

	// korrektsiya for malykh znacheniy, usessya metod
	// Linear Counting : than greater nulevykh registtrov — then
	// menshe realnaya kardinalnost.
	if estimate <= 5*m/2 {
		zeros := 0
		for _, val := range hll.registers {
			if val == 0 {
				zeros++
			}
		}
		if zeros != 0 {
			estimate = float64(m) * math.Log(float64(m)/float64(zeros))
		}
	}

	return estimate
}

// alpha — popravochnyy koeffitsient, kompensiruyuschiy systemticheskuyu oshibku
func alpha(m int) float64 {
	switch m {
	case 16:
		return 0.673
	case 32:
		return 0.697
	case 64:
		return 0.709
	default:
		return 0.7213 / (1 + 1.079/float64(m))
	}
}

func main() {
	// Withzdayom HLL.
	hll := NewHyperLogLog()

	seen := make(map[string]struct{})
	for i := 0; i < 1_000_000; i++ {
		key := strconv.Itoa(rand.Intn(1_000_000))
		seen[key] = struct{}{}
		hll.Add(key)
	}

  	nonZero := 0
	for _, r := range hll.registers {
		if r > 0 {
			nonZero++
		}
	}
  
	fmt.Printf("Realnoe count unique elements: %d\n", len(seen))
	fmt.Printf("Otsenka unique elements: %.2f\n", hll.Estimate())
	fmt.Printf("Zapolnennykh registtrov: %d/%d\n", nonZero, m)
}

Para 1 millón de elementos únicos, el error relativo fue del 0.84%, con el 100% de registros llenos. Memoria: 1 KB.

Count-Min Sketch para conteo de frecuencias

Count-Min Sketch estima las frecuencias de elementos en un flujo utilizando una tabla 2D de contadores (profundidad × ancho). Cada fila usa una función hash separada con un salt. En la inserción, el elemento incrementa los contadores en todas las filas; en la consulta, se toma el mínimo, lo que minimiza los efectos de colisión.

Parámetros de implementación:

ancho = 10.000 columnas
profundidad = 5 filas
Hash: fnv64a con shuffling de seed

Métodos de consulta:

Mínimo — básico, preciso para actualizaciones positivas
Promedio — robusto ante eliminaciones
Count-mean-min — corrige el sesgo

package main

import (
    "fmt"
    "hash/fnv"
    "math"
)

type CountMinSketch struct {
    width  int
    depth  int
    // when asynchronous interaction worth think about mutexes
    table  [][]int
    hashes []uint64
}

func NewCountMinSketch(width, depth int) *CountMinSketch {
    return &CountMinSketch{
        width:  width,
        depth:  depth,
        table:  make([][]int, depth),
        hashes: make([]uint64, depth),
    }
}

func (cms *CountMinSketch) Init() {
    for i := range cms.table {
        cms.table[i] = make([]int, cms.width)
        cms.hashes[i] = uint64(i+1) // prostye soli for raznykh hashes
    }
}

// getHashIndex generiruet khesh and returns index in table
func (cms *CountMinSketch) getHashIndex(s string, seed uint64) int {
    h := fnv.New64a()
    h.Write([]byte(s))
    v := h.Sum64()

    // Shuffling bits with seed
    mixed := v ^ seed ^ (seed << 32)

    return int(mixed % uint64(cms.width))
}

// Add uvelichivaet schetchik for element
func (cms *CountMinSketch) Add(s string, count int) {
    for i := 0; i < cms.depth; i++ {
        idx := cms.getHashIndex(s, cms.hashes[i])
        cms.table[i][idx] += count
    }
}

// Count returns otsenochnoe number vkhozhdeniy element
func (cms *CountMinSketch) Count(s string) int {
    min := math.MaxInt32
    for i := 0; i < cms.depth; i++ {
        idx := cms.getHashIndex(s, cms.hashes[i])
        if cms.table[i][idx] < min {
            min = cms.table[i][idx]
        }
    }
    return min
}

func main() {
    width := 10_000
    depth := 5

    cms := NewCountMinSketch(width, depth)
    cms.Init()

    seen := make(map[string]int)
	for i := 0; i < 5_000_000; i++ {
		key := fmt.Sprintf("item-%d", i%1100)
		seen[key]++
		cms.Add(key, 1)
	}

  
    // vyvodim frequency
    for _, word := range []string{"item-1", "item-0", "item-1000", "item--1"} {
        fmt.Printf("Withglasno cms slovo '%s' meetingsaetsya primerno %d raz\t By faktu: %d\n", word, cms.Count(word), seen[word])
    }
}

Para 5 millones de inserciones, memoria: 200 KB. Las operaciones son O(profundidad) tanto para inserción como para consulta.

Comparación de estructuras de datos

| Característica | HyperLogLog | Count-Min Sketch |

|---------------|-------------|------------------|

| Tarea | Cardinalidad | Frecuencia |

| Memoria | O(log(log N)) | O(d×w) |

| Error | 1-3% | Depende de d,w |

| Inserción | O(1) | O(profundidad) |

| Consulta | O(m) | O(profundidad) |

Puntos clave:

Ambas estructuras son adecuadas para el procesamiento en streaming de millones de elementos
HyperLogLog usa memoria fija independientemente del volumen de datos
Count-Min Sketch sobreestima las frecuencias debido a colisiones, pero proporciona consultas puntuales
Para sistemas distribuidos, agregar mútices o usar operaciones atómicas
Prueba con datos reales: el error depende de la distribución del hash

— Editorial Team