Bagaimana cara kerja algoritma HyperLogLog?

Saya telah belajar tentang berbagai algoritma di waktu luang saya baru-baru ini, dan yang saya temukan yang tampaknya sangat menarik disebut algoritma HyperLogLog - yang memperkirakan berapa banyak item unik dalam daftar.

Ini sangat menarik bagi saya karena membawa saya kembali ke hari-hari MySQL saya ketika saya melihat bahwa nilai "Kardinalitas" (yang saya selalu anggap sampai saat ini bahwa itu dihitung tidak diperkirakan).

Jadi saya tahu cara menulis algoritma dalam O ( n ) yang akan menghitung berapa banyak item unik dalam array. Saya menulis ini dalam JavaScript:

function countUniqueAlgo1(arr) {
    var Table = {};
    var numUnique = 0;
    var numDataPoints = arr.length;
    for (var j = 0; j < numDataPoints; j++) {
        var val = arr[j];
        if (Table[val] != null) {
            continue;
        }
        Table[val] = 1;
        numUnique++;
    }
    return numUnique;
}

Tapi masalahnya adalah algoritma saya, sementara O ( n ), menggunakan banyak memori (menyimpan nilai dalam Table).

Saya telah membaca makalah ini tentang bagaimana cara menghitung duplikat dalam daftar dalam waktu O ( n ) dan menggunakan memori minimal.

Ini menjelaskan bahwa dengan membuat dan menghitung bit atau sesuatu yang dapat diperkirakan dalam probabilitas tertentu (dengan asumsi daftar terdistribusi secara merata) jumlah item unik dalam daftar.

Saya sudah membaca koran, tapi sepertinya saya tidak bisa memahaminya. Dapatkah seseorang memberikan penjelasan yang lebih baik kepada orang awam? Saya tahu apa hash itu, tapi saya tidak mengerti bagaimana hash digunakan dalam algoritma HyperLogLog ini.

Trik utama di balik algoritma ini adalah bahwa jika Anda, mengamati aliran bilangan bulat acak, melihat bilangan bulat yang representasi binernya dimulai dengan beberapa awalan yang diketahui, ada kemungkinan lebih tinggi bahwa kardinalitas aliran adalah 2 ^ (ukuran awalan) .

Yaitu, dalam aliran bilangan bulat acak, ~ 50% dari angka (dalam biner) dimulai dengan "1", 25% dimulai dengan "01", 12,5% dimulai dengan "001". Ini berarti bahwa jika Anda mengamati aliran acak dan melihat "001", ada kemungkinan lebih tinggi bahwa aliran ini memiliki kardinalitas 8.

(Awalan "00..1" tidak memiliki arti khusus. Itu ada di sana hanya karena mudah untuk menemukan bit paling signifikan dalam bilangan biner di sebagian besar prosesor)

Tentu saja, jika Anda mengamati hanya satu bilangan bulat, kemungkinan nilai ini salah adalah tinggi. Itu sebabnya algoritma membagi aliran dalam "m" aliran independen dan menjaga panjang maksimum awalan "00 ... 1" yang terlihat dari setiap subtream. Kemudian, perkirakan nilai akhir dengan mengambil nilai rata-rata setiap subtipe.

Itulah ide utama dari algoritma ini. Ada beberapa detail yang hilang (koreksi untuk nilai estimasi rendah, misalnya), tetapi semuanya ditulis dengan baik di koran. Maaf untuk bahasa Inggris yang buruk.

HyperLogLog adalah struktur data probabilistik . Itu menghitung jumlah elemen berbeda dalam daftar. Tetapi dibandingkan dengan cara mudah untuk melakukannya (memiliki set dan menambahkan elemen ke set) itu melakukan ini dengan cara perkiraan.

Sebelum melihat bagaimana algoritma HyperLogLog melakukan ini, kita harus memahami mengapa Anda membutuhkannya. Masalahnya dengan cara langsung adalah bahwa ia menghabiskan O(distinct elements)ruang. Mengapa ada notasi O besar di sini, bukan hanya elemen yang berbeda? Ini karena elemen dapat memiliki ukuran yang berbeda. Satu elemen bisa menjadi 1elemen lain "is this big string". Jadi, jika Anda memiliki daftar besar (atau aliran elemen besar) itu akan memakan banyak memori.

Penghitungan Probabilistik

Bagaimana seseorang bisa mendapatkan estimasi yang masuk akal dari sejumlah elemen unik? Asumsikan bahwa Anda memiliki untaian panjangm yang terdiri dari {0, 1}dengan probabilitas yang sama. Berapa probabilitas bahwa ia akan mulai dengan 0, dengan 2 nol, dengan k nol? Ya 1/2, 1/4dan 1/2^k. Ini berarti bahwa jika Anda telah menemukan string dengan knol, Anda telah mendekati 2^kelemen. Jadi ini adalah titik awal yang baik. Memiliki daftar elemen yang didistribusikan secara merata 0dan 2^k - 1Anda dapat menghitung jumlah maksimum awalan nol terbesar dalam representasi biner dan ini akan memberi Anda perkiraan yang masuk akal.

Masalahnya adalah asumsi memiliki angka yang terdistribusi secara merata dari 0t 2^k-1terlalu sulit untuk dicapai (data yang kami temui sebagian besar bukan angka, hampir tidak pernah terdistribusi secara merata, dan dapat berada di antara nilai apa pun. Tetapi menggunakan fungsi hashing yang baik, Anda dapat mengasumsikan bahwa bit keluaran akan didistribusikan secara merata dan sebagian besar fungsi hashing memiliki keluaran di antaranya0 dan 2^k - 1( SHA1 memberi Anda nilai di antara 0dan 2^160). Jadi apa yang telah kami capai sejauh ini adalah bahwa kami dapat memperkirakan jumlah elemen unik dengan kardinalitas maksimum kbit dengan menyimpan hanya satu jumlah log(k)bit ukuran . Kelemahannya adalah kita memiliki variasi besar dalam perkiraan kita. Suatu hal yang keren yang hampir kita buatMakalah penghitungan probabilistik 1984 (ini sedikit lebih pintar dengan perkiraan, tapi kami masih dekat).

LogLog

Sebelum melangkah lebih jauh, kita harus memahami mengapa perkiraan pertama kita tidak terlalu bagus. Alasan di balik itu adalah bahwa satu kejadian acak elemen awalan 0 frekuensi tinggi dapat merusak segalanya. Salah satu cara untuk memperbaikinya adalah dengan menggunakan banyak fungsi hash, hitung maks untuk masing-masing fungsi hash dan pada akhirnya rata-rata keluar. Ini adalah ide yang bagus, yang akan meningkatkan estimasi, tetapi makalah LogLog menggunakan pendekatan yang sedikit berbeda (mungkin karena hashing agak mahal).

Mereka menggunakan satu hash tetapi membaginya menjadi dua bagian. Satu disebut ember (jumlah total ember 2^x) dan lainnya - pada dasarnya sama dengan hash kita. Sulit bagi saya untuk mendapatkan apa yang sedang terjadi, jadi saya akan memberikan contoh. Asumsikan Anda memiliki dua elemen dan fungsi hash Anda yang memberikan bentuk nilai 0untuk 2^10menghasilkan 2 nilai: 344dan 387. Anda memutuskan untuk memiliki 16 ember. Jadi kamu punya:

0101 011000  bucket 5 will store 1
0110 000011  bucket 6 will store 4

Dengan memiliki lebih banyak ember Anda mengurangi varians (Anda menggunakan sedikit lebih banyak ruang, tetapi masih kecil). Dengan menggunakan keterampilan matematika, mereka dapat mengukur kesalahan (yaitu 1.3/sqrt(number of buckets)).

HyperLogLog

HyperLogLog tidak memperkenalkan ide-ide baru, tetapi kebanyakan menggunakan banyak matematika untuk meningkatkan perkiraan sebelumnya. Para peneliti telah menemukan bahwa jika Anda menghapus 30% dari jumlah terbesar dari ember, Anda secara signifikan meningkatkan taksiran. Mereka juga menggunakan algoritma lain untuk rata-rata angka. Makalah ini sangat matematika.

Dan saya ingin menyelesaikan dengan makalah baru-baru ini, yang menunjukkan versi yang ditingkatkan dari algoritma hyperLogLog (sampai sekarang saya tidak punya waktu untuk sepenuhnya memahaminya, tapi mungkin nanti saya akan memperbaiki jawaban ini).

Intuisi adalah jika input Anda adalah satu set besar angka acak (misalnya nilai hash), mereka harus didistribusikan secara merata pada rentang. Katakanlah kisarannya hingga 10 bit untuk mewakili nilai hingga 1024. Kemudian amati nilai minimumnya. Katakanlah 10. Kardinalitas diperkirakan sekitar 100 (10 × 100 ≈ 1024).

Baca makalah untuk logika nyata tentu saja.

Penjelasan lain yang baik dengan kode sampel dapat ditemukan di sini:
Algoritma Damn Cool: Estimasi Kardinalitas - Blog Nick