Apakah ada filter anti-Bloom?

Sebuah Bloom Filter memungkinkan untuk efisien melacak apakah berbagai nilai telah ditemui selama pengolahan. Ketika ada banyak item data maka filter Bloom dapat menghasilkan penghematan memori yang signifikan di atas tabel hash. Fitur utama dari filter Bloom, yang dibagikan dengan tabel hash, adalah selalu mengatakan "bukan baru" jika suatu item bukan barang baru, tetapi ada probabilitas bukan nol bahwa suatu barang akan ditandai sebagai "bukan barang baru" "Bahkan ketika itu baru.

Apakah ada "filter anti-Bloom", yang memiliki perilaku sebaliknya?

Dengan kata lain: apakah ada struktur data yang efisien yang mengatakan "baru" jika suatu barang baru, tetapi yang juga bisa mengatakan "baru" untuk beberapa item yang bukan barang baru?

Menyimpan semua item yang terlihat sebelumnya (misalnya, dalam daftar tertaut yang disortir) memenuhi persyaratan pertama tetapi mungkin menggunakan banyak memori. Saya berharap itu juga tidak perlu, mengingat persyaratan kedua yang santai.

Bagi mereka yang lebih menyukai perlakuan yang lebih formal, tulis jika filter Bloom menganggap adalah baru, b (x) = 0 sebaliknya, dan tulis n (x) = 1 jika x benar-benar baru dan n (x) ) = 0 sebaliknya.$b(x) = 1$$x$$b(x) = 0$$n(x) = 1$$x$$n(x) = 0$

Kemudian $Pr[b(x) = 0 | n(x) = 0] = 1$ ; $Pr[b(x) = 0 | n(x) = 1] = \alpha$ ; $Pr[b(x) = 1 | n(x) = 0] = 0$ ; $Pr[b(x) = 1 | n(x) = 1] = 1 - \alpha$ , untuk beberapa $0 < \alpha < 1$ .

Saya bertanya: apakah ada struktur data yang efisien, menerapkan fungsi $b'$ dengan beberapa $0 < \beta < 1$ , sehingga $Pr[b'(x) = 0 | n(x) = 0] = \beta$ ; $Pr[b'(x) = 0 | n(x) = 1] = 0$ ; $Pr[b'(x) = 1 | n(x) = 0] = 1 - \beta$ ; $Pr[b'(x) = 1 | n(x) = 1] = 1$ ?

Sunting: Sepertinya pertanyaan ini telah ditanyakan sebelumnya di StackExchange, seperti /programming/635728 dan /cstheory/6596 dengan serangkaian jawaban dari "tidak bisa dilakukan "melalui" dapat dilakukan, dengan biaya "ke" itu sepele untuk dilakukan, dengan membalikkan nilai-nilai ". Belum jelas bagi saya apa jawaban "benar" itu. Apa yang jelas adalah bahwa skema LRU caching dari beberapa macam (seperti yang disarankan oleh Ilmari Karonen) bekerja cukup baik, mudah untuk menerapkan, dan menghasilkan pengurangan 50% dalam waktu yang dibutuhkan untuk menjalankan kode saya.$b$

Sesuai dengan ide hash Patrick87, berikut ini adalah konstruksi praktis yang hampir memenuhi persyaratan Anda - kemungkinan salah mengira nilai baru untuk yang lama tidak cukup nol, tetapi dapat dengan mudah dibuat menjadi sangat kecil.

Pilih parameter dan ; nilai praktis mungkin, katakanlah, dan . Biarkan menjadi fungsi hash kriptografi aman yang menghasilkan (setidaknya) bit output.k n = 128 k = 16 H n + $n$$k$$n = 128$$k = 16$$H$$n+k$

Biarkan menjadi array -bit bitstrings. Array ini menyimpan status filter, menggunakan total bit . (Tidak masalah bagaimana array ini diinisialisasi; kita bisa mengisinya dengan nol, atau dengan bit acak.)$a$ n n 2 $2^k$ $n$$n2^k$

• Untuk menambahkan nilai baru ke filter, hitung , di mana menunjukkan bit pertama dan menunjukkan bit . Biarkan .$x$i k j n H ( x ) a i = $i \,\|\, j = H(x)$$i$$k$$j$$n$$H(x)$$a_{i} = j$

• Untuk menguji apakah nilai telah ditambahkan ke filter, hitung , seperti di atas, dan periksa apakah . Jika ya, kembalikan benar; jika tidak, kembalikan false.i $x'$a i ′ = j $i' \,\|\, j' = H(x')$$a_{i'} = j'$

Klaim 1: Probabilitas false positive (= nilai baru yang diklaim palsu telah terlihat) adalah . Ini dapat dibuat sewenang-wenang kecil, dengan biaya sederhana dalam ruang penyimpanan, dengan meningkatkan ; khususnya, untuk , probabilitas ini pada dasarnya dapat diabaikan, karena, dalam praktiknya, jauh lebih kecil daripada probabilitas positif palsu karena kegagalan fungsi perangkat keras. n n ≥ $1/2^{n+k}$$n$$n \ge 128$

Secara khusus, setelah nilai yang berbeda telah diperiksa dan ditambahkan ke filter, probabilitas setidaknya satu false positive terjadi adalah . Misalnya, dengan dan , jumlah nilai berbeda yang diperlukan untuk mendapatkan false positive dengan probabilitas 50% adalah sekitar .( N 2 - N ) / 2 n + k + 1 n = 128 k = 16 2 ( n + k ) / 2 = 2 $N$$(N^2-N) / 2^{n+k+1}$$n=128$$k=16$$2^{(n+k)/2} = 2^{72}$

Klaim 2: Probabilitas negatif palsu (= nilai tambah sebelumnya yang diklaim palsu sebagai baru) tidak lebih besar dari , di mana adalah jumlah nilai berbeda yang ditambahkan ke filter (atau, lebih khusus, jumlah nilai berbeda yang ditambahkan setelah nilai spesifik yang diuji paling baru ditambahkan ke filter).$1-(1-2^{-k})^N \approx 1-\exp(-N/2^k) < N/2^k$$N$

Ps. Untuk menempatkan "sangat kecil" ke dalam perspektif, enkripsi 128-bit umumnya dianggap tidak dapat dipecahkan dengan teknologi yang saat ini dikenal. Mendapatkan false positive dari skema ini dengan adalah sama mungkin dengan seseorang yang menebak kunci enkripsi 128-bit rahasia Anda dengan benar pada upaya pertama mereka . (Dengan dan , sebenarnya sekitar 65.000 kali lebih kecil dari itu.)n = 128 k = $n+k=128$$n=128$$k=16$

Tetapi jika itu masih membuat Anda merasa gugup secara tidak rasional, Anda selalu dapat beralih ke ; itu akan dua kali lipat kebutuhan penyimpanan Anda, tapi aku bisa bertaruh Anda setiap jumlah yang anda akan peduli untuk nama yang tak seorang pun akan pernah melihat positif palsu dengan - dengan asumsi bahwa fungsi hash tidak rusak, anyway.n = 256$n=256$$n=256$

Tidak, tidak mungkin untuk memiliki struktur data yang efisien dengan properti ini, jika Anda ingin memiliki jaminan bahwa struktur data akan mengatakan "baru" jika itu benar-benar baru (itu tidak akan pernah, pernah akan mengatakan "tidak baru" jika ini sebenarnya baru; tidak boleh ada negatif palsu). Setiap struktur data semacam itu harus menyimpan semua data agar selalu merespons "bukan baru". Lihat jawaban pents90 pada cerita untuk pembenaran yang tepat.

Sebaliknya, filter Bloom bisa mendapatkan jaminan bahwa struktur data akan mengatakan "bukan baru" jika bukan baru, dengan cara yang efisien. Secara khusus, filter Bloom dapat lebih efisien daripada menyimpan semua data: setiap item individual mungkin cukup panjang, tetapi ukuran filter Bloom berskala dengan jumlah item, bukan total panjangnya. Setiap struktur data untuk masalah Anda harus berskala dengan panjang total data, bukan jumlah item data.

Bagaimana dengan tabel hash saja? Ketika Anda melihat item baru, periksa tabel hash. Jika tempat item kosong, kembalikan "baru" dan tambahkan item. Jika tidak, periksa untuk melihat apakah tempat barang tersebut ditempati oleh barang tersebut. Jika demikian, kembalikan "bukan baru". Jika spot ditempati oleh item lain, kembalikan "baru" dan timpa spot dengan item baru.

Anda pasti akan selalu mendapatkan "Baru" dengan benar jika Anda belum pernah melihat hash item sebelumnya. Anda pasti akan selalu mendapatkan "Bukan Baru" dengan benar jika Anda hanya melihat hash item ketika Anda melihat item yang sama. Satu-satunya waktu Anda akan mendapatkan "Baru" ketika jawaban yang benar adalah "Bukan Baru" adalah jika Anda melihat item A, lalu melihat item B, lalu melihat item A lagi, dan kedua hash A dan B untuk hal yang sama. Yang penting, Anda tidak akan pernah mendapatkan "Bukan Baru" secara salah.

Dalam kasus di mana alam semesta item terbatas, maka ya: cukup gunakan filter mekar yang merekam elemen mana yang di luar set, bukan di set. (Yaitu, gunakan filter bloom yang mewakili komplemen dari set bunga.)

Tempat di mana ini berguna adalah untuk memungkinkan penghapusan bentuk terbatas. Anda menyimpan dua filter mekar. Mereka mulai kosong. Saat Anda memasukkan elemen, Anda memasukkannya ke filter bloom A. Jika nanti Anda ingin menghapus elemen, Anda memasukkan elemen ke filter bloom B. Tidak ada cara untuk membatalkan penghapusan. Untuk melakukan pencarian Anda pertama kali mencari di filter bloom A. Jika Anda tidak menemukan yang cocok, item tersebut tidak pernah dimasukkan (dengan probabilitas 1). Jika Anda menemukan kecocokan, elemen mungkin (atau mungkin tidak) telah dimasukkan. Dalam hal ini Anda melakukan pencarian di filter mekar B. Jika Anda tidak menemukan kecocokan, item itu tidak pernah dihapus. Jika Anda menemukan kecocokan dalam filter mekar B, item itu mungkin dimasukkan dan kemudian dihapus.

Ini tidak benar-benar menjawab pertanyaan Anda, tetapi, dalam kasus terbatas ini, filter bloom B melakukan persis perilaku "filter anti-bloom" yang Anda cari.

Peneliti filter Bloom Nyata menggunakan cara yang jauh lebih efisien untuk mewakili penghapusan, lihat halaman publikasi Mike Mitzenmacher .

Saya hanya ingin menambahkan di sini, bahwa jika Anda berada dalam situasi beruntung, bahwa Anda tahu semua nilai-nilai yang mungkin Anda mungkin melihat; maka Anda dapat menggunakan penghitungan filter bloom.$v_i$

Contohnya mungkin alamat ip, dan Anda ingin tahu setiap kali ada yang muncul yang belum pernah Anda lihat sebelumnya. Tetapi ini masih merupakan perangkat yang terbatas, sehingga Anda tahu apa yang dapat Anda harapkan.

Solusi sebenarnya sederhana:

1. Tambahkan semua item Anda ke filter bloom penghitungan.
2. Saat Anda melihat item baru, item itu akan memiliki nilai di semua slot.$\ge1$
3. Setelah melihat item baru yang sebenarnya, kurangi dari filter.

Jadi, Anda mungkin memiliki nilai 'false positive' yang sebenarnya sudah lama, tetapi diakui sebagai baru. Namun Anda tidak akan pernah mendapatkan 'bukan baru' untuk nilai baru, karena nilainya masih di semua slot, dan tidak ada orang lain yang bisa mengambilnya.