Satu set probabilistik tanpa positif palsu?

35

Jadi, filter Bloom cukup keren - mereka adalah set yang mendukung pemeriksaan keanggotaan tanpa negatif palsu, tetapi kemungkinan kecil positif palsu. Namun baru-baru ini, saya menginginkan "filter Bloom" yang menjamin yang sebaliknya: tidak ada positif palsu, tetapi berpotensi negatif palsu.

Motivasi saya sederhana: diberi aliran besar barang untuk diproses (dengan duplikat), kami ingin menghindari memproses barang yang telah kami lihat sebelumnya. Tidak ada salahnya memproses duplikat, itu hanya buang-buang waktu. Namun, jika kita lalai memproses suatu elemen, itu akan menjadi bencana besar. Dengan "reverse Bloom filter", seseorang dapat menyimpan barang-barang yang terlihat dengan sedikit overhead ruang, dan menghindari pemrosesan duplikat dengan probabilitas tinggi dengan menguji keanggotaan dalam set tersebut.

Namun sepertinya saya tidak dapat menemukan hal semacam itu. Yang paling dekat yang saya temukan adalah " filter Bloom retouched ", yang memungkinkan seseorang untuk bertukar positif palsu yang dipilih dengan tingkat negatif palsu yang lebih tinggi. Saya tidak tahu seberapa baik kinerja struktur data mereka ketika seseorang ingin menghapus semua positif palsu.

Adakah yang melihat hal seperti ini? :)

Christopher Monsanto
sumber
3
Komplemen dari set yang saya minati tidak terbatas. Bagaimana saya menyimpannya?
Christopher Monsanto
11
Saya melihat masalahnya (disk modern belum cukup besar).
Dave Clarke
8
Jika Anda memiliki struktur data seperti itu, Anda bisa menggunakannya untuk "menipu" dengan menggunakannya bersamaan dengan filter bloom biasa dan menyimpan keanggotaan yang ditetapkan dengan tepat.
Mark Reitblatt
1
@MarkReitblatt, filter dan cache Bloom adalah probabilistik, dan setiap kombinasi darinya akan probabilistik, yaitu tidak dapat mencapai pengujian keanggotaan yang ditetapkan dengan tepat. :)
awdz9nld

Jawaban:

25

Satu jawaban adalah dengan menggunakan tabel hash besar dan ketika diisi mulai ganti elemen di dalamnya daripada menemukan (tidak ada) slot kosong di tempat lain untuk mereka. Anda tidak mendapatkan tingkat tetap dari jawaban salah yang Anda lakukan dengan filter Bloom, tetapi lebih baik daripada tidak sama sekali. Saya percaya ini standar misalnya dalam perangkat lunak catur untuk melacak posisi yang telah dicari.

David Eppstein
sumber
Terima kasih atas jawabannya. Ya, itu adalah solusi yang jelas - jika itu juga solusi standar , sepertinya saya kurang beruntung. Baiklah.
Christopher Monsanto
2
Ini disebut cache yang dipetakan langsung, dan umumnya digunakan dalam CPU. (Setiap cache atau hash set lossy cocok dengan persyaratan untuk berbagai derajat). Tingkat kesalahan adalah fungsi dari distribusi fungsi hash (longsoran salju) dan jumlah slot yang tersedia di cache / set - sesuaikan. :)
awdz9nld
Perhatikan juga bahwa hanya kunci kata demi kata yang dapat disimpan tanpa memasukkan positif palsu (mis. Menyimpan kunci hash)
awdz9nld
20

Jawaban untuk pertanyaan ini adalah "tidak". Untuk mengetahui alasannya, kita dapat berpikir tentang kasus yang sangat ekstrem, dan bagaimana filter bloom biasa bekerja vs.

Apa yang hebat tentang filter mekar adalah bahwa Anda dapat melakukan tes satu sisi untuk keanggotaan item (dengan false positive) menggunakan struktur data yang memiliki ukuran tetap sehubungan dengan probabilitas kesalahan dan jumlah item yang disimpan. The ukuran dari produk yang sebenarnya tidak penting sama sekali. Misalnya, jika kami memiliki filter mekar yang diatur untuk menyimpan hingga 1.000 item dengan kesalahan kurang dari 3%, maka kami dapat menyimpan 1.000 versi yang sedikit berbeda dari seluruh kumpulan Wikipedia, dengan satu huruf diubah di masing-masing, dan kami masih akan tetap dapatkan metrik yang kita inginkan, dan struktur data akan sangat kecil (kurang dari satu kilobyte). Tentu saja, menghitung hash itu akan menjadi tantangan, tetapi prinsipnya tetap berlaku.

Sekarang, pertimbangkan untuk menyimpan string masif yang sama itu di filter suram! Kami hanya dapat memiliki negatif palsu sekarang. Jadi jika kita mengatakan "ya, versi seluruh kumpulan Wikipedia ada di set ini", maka kita harus benar tentang itu. Itu berarti hashing tidak akan membantu kita, karena akan selalu ada beberapa string lain yang hash dengan nilai yang sama. Satu-satunya cara untuk mengatakan "ya" dan pastikan adalah menyimpan seluruh string, atau beberapa data yang setara dengan panjang yang sama. Kami selalu tidak bisa menyimpannya dan berkata "tidak", tetapi akhirnya tingkat kesalahan akan menyusul kami. Yang terbaik yang bisa kita lakukan adalah kompresi, mendapatkan ukuran struktur ke produk entropi data yang disimpan dan akurasi yang kita inginkan.

Jadi, sayangnya filter suram tidak ada. Caching adalah satu-satunya solusi, tetapi sebenarnya bukan kebalikan dari filter bloom, karena ukurannya akan sebanding dengan produk dari jumlah informasi yang disimpan dan tingkat akurasi yang diinginkan dari filter. Tentu saja, dalam banyak skenario dunia nyata, data besar dapat diwakili oleh ID, sehingga caching masih dapat diterima. Tapi secara fundamental berbeda dari filter mekar yang perkasa.

pents90
sumber
checkout somethingsimilar.com/2012/05/21/the-opposite-of-a-bloom-filter - ada apa implementasi ini /
Yehosef
@Yehosef baik-baik saja dan dapat bekerja untuk kebutuhan Anda, tetapi Anda akan melihat bahwa penulis berbicara tentang adanya "beberapa ID yang sepenuhnya mengidentifikasi acara". Jadi, apa yang diimplementasikan secara efektif masih menyimpan seluruh objek. Jadi, ini adalah varian dari cache. "Kebalikan dari filter mekar" nyata, jika ada, tidak perlu menyimpan seluruh objek.
pents90
Dia menyebutkan beberapa id yang mengidentifikasi peristiwa - bukan keseluruhan objek. Saya hanya perlu menyimpan "cache" di session_id - bukan seluruh catatan interaksi. Tapi saya dengar itu bukan jenis pendekatan yang sama dengan bloom atau hyperloglog.
Yehosef
Dalam "bukti" Anda, Anda menganggap bahwa ada kemungkinan entri yang tidak terbatas. Namun, ada kasus di mana set entri yang mungkin diketahui sebelumnya. Misalnya, untuk pengumpulan sampah halaman memori: Anda tahu entri mana yang dikandungnya. Sekarang Anda membuat "filter kesuraman" yang memetakan setiap entri yang mungkin ke indeks 0..n. Sekarang ketika sebuah entri dihapus, atur bit a index itu. Ketika semua bit diatur, Anda dapat mengumpulkan sampah halaman. "Filter suram" adalah MPHF. Untuk memungkinkan false negative, ubah MPHF sedemikian rupa sehingga beberapa entri dipetakan ke n +1.
Thomas Mueller
@ThomasMueller Benar, saya mengasumsikan kasus terburuk / permusuhan, yang merupakan sudut pandang teori CS standar. Memang benar bahwa jika Anda hanya memiliki satu set N entri yang memungkinkan, maka ada banyak solusi langsung, dengan hanya mencatat ruang N yang diperlukan untuk setiap item. Filter bloom tidak memiliki batasan seperti itu.
pents90
13

Anda hanya ingin cache , tetapi memikirkannya dengan cara yang aneh.

Craig Gidney
sumber
1
... peduli untuk menjelaskan? Tentu saja cache akan berfungsi, tetapi itu tidak ideal, maka pertanyaan tentang keadaan seni dalam struktur data probabilistik. Untuk lebih spesifik: teknik caching yang saya tahu membutuhkan banyak penyimpanan. Semakin banyak level cache, semakin banyak penyimpanan yang digunakan. Seseorang dapat menempatkan batasan pada elemen yang disimpan dalam cache, melakukan trik dengan pola penggunaan, dll, tetapi itu masih tidak mendekati efisiensi ruang hingga rasio jawaban salah yang disediakan oleh filter Bloom.
Christopher Monsanto
1
(lanjutan) Yang sedang berkata, saya bisa melupakan tentang teknik caching yang jelas yang menyelesaikan semua masalah saya. Jika demikian, Anda dapat membuat teknik itu secara eksplisit alih-alih memberi saya tautan ke kategori umum di Wikipedia?
Christopher Monsanto
2

PENOLAKAN: Saya bukan ahli dalam cache sehingga ini mungkin ide yang naif, dan juga mungkin ide yang dikenal yang belum pernah saya dengar sebelumnya. Jadi maafkan saya jika saya gagal mengutip referensi (jika ada); dan tolong beri tahu saya jika ada referensi untuk mengedit posting dan menambahkannya. (Saya curiga ini mungkin memiliki referensi karena sangat intuitif).

cc

M. Alaggan
sumber
0

Saya telah menggunakan pohon AVL (dan terkadang merah-hitam) dengan item parsial untuk bertindak sebagai filter tanpa negatif palsu. Gunakan hanya byte X pertama dari item saat memasukkan atau menanyakan pohon. Karena struktur data tidak probabilistik dalam bentuk, tidak ada risiko false-positive oleh bit collision. Dan tidak seperti caching seluruh item, pendekatan ini memberi Anda ruang maksimum yang dapat dihitung. Anda dapat menyesuaikan tingkat positif palsu dengan mempertimbangkan panjang awalan / kedalaman pohon yang berbeda dibandingkan dengan biaya positif palsu dan ruang.

JRideout
sumber
Saya juga ingin mencoba mencoba dengan data string, tetapi data saya cenderung dikemas struktur biner.
JRideout
0

Saya pikir seseorang dapat membuktikan batas bawah yang menyatakan bahwa struktur data di atas tidak ada. Pada dasarnya, jika struktur data menggunakan m bit, maka bit-vektor tetap (representasi input) dapat sesuai dengan paling banyak ((un) + n eps) \ pilih (tidak)) ditetapkan oleh argumen penghitungan. Mengingat bahwa 2 ^ m kali angka ini harus setidaknya (u \ select n) (semua set harus diwakili), kita mendapatkan batas bawah yang pada dasarnya sangat dekat dengan menyimpan set S secara tepat.

Mayank
sumber