HyperLogLog
2024-02-18
count distinct * bằng bao nhiêu? bằng 10. sai mà! nhưng nhanh.
Khái niệm
Đếm unique user. count distinct.
Flajolet-Martin Algorithm: nếu id là ngẫu nhiên thì
- gặp hơn 10 id thì sẽ có khả năng gặp một id có 1 số 0 ở đầu
- gặp hơn 10 id thì sẽ có khả năng gặp một id có 2 số 0 ở đầu …
- gặp hơn 10^n id thì sẽ có khả năng gặp một id có n số 0 ở đầu …
Hash id ra thành chuỗi bit để phân phối đều hơn. theo xác suất tính được sai số 0,77351 -> 2^n/0,77351
LogLog
Vấn đề: phân phối lệch của id (ngoại lệ) -> cần hash nhiều lần để tính trung bình. tuy nhiên hash tốn công
LogLog: dùng 1 hash, chia bucket
Số lượng bucket càng tăng thì sai số càng giảm
SuperLogLog
Vấn đề: độ chính xác
SuperLogLog: loại bỏ một số giá trị lớn nhất của bucket.
Hệ số sai số giảm từ 1.3 (LogLog) xuống 1.05 (SuperLogLog)
HyperLogLog
Vấn đề: độ chính xác
HyperLogLog: xử dụng trung bình điều hòa thay vì trung bình cộng. lí do: tốt trong việc xử lý các ngoại lệ lớn.
Hệ số sai số giảm xuống 1.04 :v
Ứng dụng
- unique visitor, view counting