Menjawab pertanyaan tentang data yang lebih besar daripada yang bisa Anda simpan.

Bloom filter, Count-Min sketch, dan HyperLogLog masing-masing menjawab satu pertanyaan tentang aliran data — tanpa menyimpan datanya. Situs ini menjalankannya berdampingan dengan struktur exact, jadi Anda bisa melihat kedua jawaban sekaligus dan tahu persis berapa harga jalan pintasnya.

Set exact berisi satu miliar URL berukuran puluhan gigabyte dan tinggal di disk. Filter yang menjawab pertanyaan tentang satu miliar URL yang sama berukuran beberapa ratus megabyte dan tinggal di memory. Itulah seluruh pertukarannya, dan itu dilakukan dengan sengaja.

Mulai dari Bloom filter →yang paling sederhana dari keempatnya, dan di sanalah asimetrinya paling jelas

Bit arrayilustrasi — 128 bit

Satu item → tiga slot, dialamatkan oleh tiga hash. Salah satunya sudah diset oleh item sebelumnya — itulah sebabnya “ya” selalu hanya petunjuk, sedangkan “tidak” adalah bukti.

Set exact — modelled: 76.29 MiB
Bloom filter — teralokasi: 1.14 MiB

1,000,000 URL pada false-positive rate 1%, 7 hash. Angka filter adalah yang dialokasikan rumus sizing; angka exact adalah model per-entry dari lib/exact, dan diberi label modelled karena jejak memory Set yang sebenarnya adalah urusan engine.

Struktur

atau pilih salah satu di bawah

Bloom filter

Apakah ini ada di dalam set?

Uji keanggotaan yang tidak menyimpan anggotanya. Tanyakan apakah sesuatu ada di dalam set, dan ia menjawab “pasti tidak ada” atau “mungkin ada” — dan ia hanya bisa salah pada arah yang kedua.

Jaminannya

Tidak pernah false negative. False positive pada rate yang Anda pilih.

Buka →Count-Min sketch

Sudah berapa kali saya melihat ini?

Penghitung frekuensi yang tidak menyimpan key. Tanyakan sudah berapa kali ia melihat sesuatu, dan jawabannya tidak pernah terlalu rendah — kadang terlalu tinggi, sebanyak yang Anda tentukan di muka.

Jaminannya

Tidak pernah underestimate. Overestimate dibatasi ε·N dengan probabilitas 1−δ.

Buka →HyperLogLog

Berapa banyak item yang distinct?

Penghitung nilai berbeda yang tidak menyimpan satu pun di antaranya. Ia menjawab “berapa banyak yang berbeda?” dengan ketelitian sekitar satu persen, memakai memory yang tidak ikut membesar bersama jawabannya.

Jaminannya

Standard error ≈ 1.04/√m, tanpa menyimpan satu item pun.

Buka →Cuckoo filter

Apakah ini ada di dalam set — dan bisakah saya menghapusnya?

Uji keanggotaan seperti Bloom filter, dengan satu tambahan: item bisa dikeluarkan lagi. Sebagai gantinya, jaminan tanpa-false-negative jadi bersyarat, dan syaratnya layak dibaca.

Jaminannya

Penghapusan, yang tidak bisa ditawarkan Bloom. Sebagai gantinya, jaminan tanpa-false-negative jadi bersyarat.

Buka →

Tawarannya

Setiap struktur di sini menawar hal yang sama: hash ke array berukuran tetap, terima bahwa collision menimbulkan kerusakan yang terbatas, lalu berhenti menyimpan itemnya sama sekali.

Memory berhenti tumbuh mengikuti data. Harganya adalah error rate — yang bisa dihitung di muka, sehingga ia parameter desain, bukan cacat.

Asimetri

Setiap jaminan bersifat satu arah, dan arahnya penting. Jawaban “tidak” dari Bloom filter adalah bukti; jawaban “ya” hanyalah petunjuk. Asimetri itulah sebabnya sebuah database bisa memakainya untuk melewati pembacaan disk dengan aman — “ya” yang salah hanya membuang satu pembacaan, “tidak” yang salah akan kehilangan data, dan “tidak” yang salah tidak mungkin terjadi.

Alat

Banding & merge

Dua struktur ini, yang dibangun terpisah, bisa digabungkan menjadi satu — dan hasilnya persis struktur yang akan Anda dapat kalau kedua stream itu diberikan ke satu mesin saja.

Kalkulator

Bekerja mundur. Sebutkan berapa item yang Anda perkirakan dan berapa error yang bisa Anda terima, lalu ini memberi Anda struktur yang harus dibangun dan berapa biayanya dalam memory.