Jaka jest różnica między HyperLogLog a Count-Min Sketch?

HyperLogLog szacuje liczbę unikalnych elementów (kardynalność), Count-Min Sketch — częstotliwość konkretnych elementów. HLL używa rejestrów z wiodącymi zerami, CMS — tabeli liczników z minimum.

Ile pamięci zużywają te struktury?

HyperLogLog: 1 KB dla 1024 rejestrów niezależnie od objętości. Count-Min Sketch: 200 KB przy width=10k, depth=5.

Czy potrzebne są muteksy w implementacji?

Tak, dla dostępu asynchronicznego. W przykładzie struktury thread-unsafe, dodaj sync.Mutex lub operacje atomowe.

HyperLogLog i Count-Min Sketch w Go dla Big Data

# Efektywne probabilistyczne struktury danych w Go: HyperLogLog i Count-Min Sketch

HyperLogLog pozwala szacować liczbę unikalnych elementów w strumieniu danych z błędem rzędu 1-3% przy zużyciu zaledwie 1 KB pamięci. Algorytm przekształca elementy w hashe, analizuje liczbę wiodących zer w reprezentacji binarnej i przechowuje statystyki w tablicy rejestrów. Zapewnia to czas dodawania O(1) i szacowania O(m), gdzie m — liczba rejestrów (zazwyczaj 1024).

Kluczowe parametry:

m = 1024 rejestry (8 bitów na rejestr)
b = 8 bitów do indeksowania rejestrów
Funkcje haszujące: fnv64a z mieszaniem bitów

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)
}

Dla 1 mln unikalnych elementów względny błąd wyniósł 0,84%, wypełniono 100% rejestrów. Pamięć: 1 KB.

Count-Min Sketch do liczenia częstotliwości

Count-Min Sketch szacuje częstotliwość elementów w strumieniu za pomocą dwuwymiarowej tabeli liczników (depth × width). Każdy wiersz używa oddzielnej funkcji haszującej z solą. Podczas dodawania element zwiększa liczniki we wszystkich wierszach, przy zapytaniu bierze się minimum — to minimalizuje efekt kolizji.

Parametry implementacji:

width = 10 000 kolumn
depth = 5 wierszy
Hash: fnv64a z mieszaniem seed

Metody zapytania:

Minimum — podstawowa, dokładna przy pozytywnych aktualizacjach
Średnia — odporna na usuwanie
Count-mean-min — koryguje przesunięcie

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])
    }
}

Dla 5 mln wstawek pamięć: 200 KB. Operacje O(depth) zarówno przy dodawaniu, jak i przy zapytaniu.

Porównanie struktur danych

| Charakterystyka | HyperLogLog | Count-Min Sketch |

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

| Zadanie | Kardynalność | Częstotliwość |

| Pamięć | O(log(log N))| O(d×w) |

| Błąd | 1-3% | Zależy od d,w |

| Dodawanie | O(1) | O(depth) |

| Zapytanie | O(m) | O(depth) |

Co ważne:

Obie struktury nadają się do strumieniowego przetwarzania milionów elementów
HyperLogLog ma pamięć stałą niezależnie od objętości danych
Count-Min Sketch zawyża częstotliwości z powodu kolizji, ale umożliwia zapytania punktowe
W systemach rozproszonych dodaj mutexy lub użyj operacji atomowych
Testuj na rzeczywistych danych: błąd zależy od rozkładu hashów

— Editorial Team