Bagaimana cara kerja filter mekar yang dapat diskalakan?

Saya membaca tentang filter bloom yang dapat diukur dan tidak dapat memahami bagaimana setiap kali filter bloom konstituen terisi, filter bloom baru dengan ukuran lebih besar ditambahkan.

Elemen-elemen yang berkontribusi pada bit yang ditetapkan dalam filter yang dibuat awalnya tidak dapat dicari keberadaannya. Mungkin saya salah dalam memahami hal ini?

Saya mengerti filter dasar bloom. Namun, saya tidak bisa membungkus kepala saya di sekitar filter mekar dinamis.

Biarkan saya mencoba untuk mencoba ini untuk melihat seberapa banyak saya bisa membantai itu. :-)

Jadi, untuk memulai, Anda harus dapat membuat filter bloom reguler yang memungkinkan sejumlah elemen hingga dengan kemungkinan maksimum false positive. Penambahan fitur-fitur ini ke filter dasar Anda diperlukan sebelum mencoba membangun implementasi yang skalabel.

Sebelum kita mencoba mengendalikan dan mengoptimalkan berapa probabilitasnya, mari kita cari tahu berapa probabilitas untuk ukuran filter bloom yang diberikan.

Pertama kita membagi bitfield dengan berapa banyak fungsi hash yang kita miliki (jumlah total bit / jumlah fungsi hash = irisan) untuk mendapatkan k irisan bit yang mewakili masing-masing fungsi hash sehingga setiap elemen selalu dijelaskan oleh k bit.

Jika Anda menambah jumlah irisan atau jumlah bit per irisan, kemungkinan positif palsu akan berkurang.

Ini juga mengikuti bahwa ketika elemen ditambahkan, bit lebih banyak ditetapkan ke 1, sehingga positif palsu meningkat. Kami menyebut ini sebagai "rasio isian" dari setiap irisan.

Ketika filter memegang sejumlah besar data, kita dapat mengasumsikan bahwa probabilitas positif palsu untuk filter ini adalah rasio pengisian yang dinaikkan ke jumlah irisan (Jika kita benar-benar menghitung bit daripada menggunakan rasio, ini menyederhanakan menjadi permutasi dengan masalah pengulangan).

Jadi, bagaimana kita mengetahui cara memilih probabilitas positif palsu dalam filter mekar? Kita dapat memodifikasi jumlah irisan (yang akan mempengaruhi rasio isian).

Untuk mengetahui berapa banyak irisan yang harus kita miliki, kita mulai dengan mencari tahu rasio pengisian optimal untuk irisan. Karena rasio pengisian ditentukan oleh jumlah bit dalam slice yang 1 versus jumlah bit yang 0, kita dapat menentukan bahwa setiap bit akan tetap tidak disetel dengan probabilitas (100% - (1 / bit dalam slice) ). Karena kita akan memiliki beberapa item yang dimasukkan, kita memiliki permutasi lain dengan masalah reputasi dan kami memperluas hal-hal ke rasio isi yang diharapkan, yaitu (100% - ((100% - (1 / bit dalam sepotong)) ^ "elemen dimasukkan")). Nah, ternyata ini sangat mirip dengan persamaan lain. Dalam makalah, mereka menghubungkan rasio pengisian dengan persamaan lain sehingga cocok dengan baik ke seri taylor (1-e ^ (- n / m)). Setelah sedikit kesal dengan ini, ternyata rasio pengisian optimal selalu sekitar 50%,

Jadi, karena probabilitas filter adalah rasio pengisian yang dinaikkan ke jumlah irisan, kita dapat mengisi 50% dan mendapatkan P = (50%) ^ k atau k = log_2 (1 / P). Kita kemudian dapat menggunakan fungsi ini untuk menghitung jumlah irisan yang harus kita hasilkan untuk filter yang diberikan dalam daftar filter untuk filter bloom yang dapat diskalakan.

    def slices_count(false_positive_probability):
        return math.ceil(math.log(1 / false_positive_probability, 2))

Sunting: Setelah menulis ini, saya menemukan penyebutan "aturan lima puluh persen" ketika membaca tentang alokasi memori dinamis berbasis sistem buddy di TAoCP Vol 1, hlm 442-445 dengan alasan yang jauh lebih bersih dibandingkan dengan menyesuaikan kurva ke (1 -e ^ (- n / m)). Knuth juga mereferensikan sebuah makalah "Aturan lima puluh persen ditinjau kembali" dengan sedikit latar belakang konsep ( pdf tersedia di sini ).

Item ada di filter bloom yang dapat diskalakan jika ada filter yang mengembalikan true. Karenanya, Anda dapat menambahkan filter tanpa memengaruhi kueri keanggotaan untuk item sebelumnya.

Untuk memastikan Anda masih memiliki jaminan positif palsu kasus terburuk, filter baru ditambahkan dengan tingkat positif palsu yang menurun secara geometris. Sebagai contoh, filter pertama memiliki tingkat positif palsu p, kedua rp, ketiga r^2p, dll Probabilitas positif palsu atas filter mekar scalable kemudian dibatasi oleh serikat terikat: sum_{k>=0} r^k p = p/(1-r).

Saya membaca tentang filter bloom yang dapat diukur dan tidak bisa memahami bagaimana setiap kali filter bloom konstituen terisi, filter bloom baru dengan ukuran lebih besar ditambahkan.

Elemen-elemen yang berkontribusi pada bit yang ditetapkan dalam filter yang dibuat awalnya tidak dapat dicari keberadaannya. Mungkin saya salah dalam memahami hal ini?

Hai,
Ide dasarnya adalah menambahkan filter pertama hingga bidang bit filter level pertama jenuh. Menjadi jenuh tidak berarti setiap bit digunakan, tetapi itu berarti filter berisi begitu banyak entri sehingga entri tambahan akan membuat terlalu banyak false positive.

Dari titik saturasi, setiap item baru tidak akan ditambahkan ke filter jenuh, tetapi ke sub-filter segar dan lebih besar (filter level kedua).

Untuk menemukan nilai, Anda akan mencarinya di filter tingkat pertama, dan jika Anda tidak bisa menemukannya di sana, Anda akan mencarinya di filter tingkat kedua. Jika Anda dapat menemukannya di salah satu filter ini, ini (kemungkinan besar) "dikenal" oleh filter (positif palsu dapat terjadi sebagai akibat dari sifat filter Bloom). Jika Anda tidak dapat menemukan nilai di salah satu filter, filter dijamin tidak melihatnya. Ini, tentu saja, dapat dinyatakan sebagai struktur data rekursif.

Anda mungkin ingin membaca posting blog saya yang berisi implementasi filter Bloom yang dapat diskalakan di Jawa dan penjelasan cara kerjanya secara detail.