資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學阻塞布隆過濾器
- 我們首先選擇一個記憶體塊。
- 然後我們選擇每個塊內的區域性布隆過濾器。
- 這可能會導致記憶體塊之間不平衡。
- 這種過濾器效率很高，但假陽性率 (FPR) 較差。
- 首先，阻塞布隆過濾器的假陽性率 (FPR) 應該與相同大小的標準布隆過濾器相同。
- 阻塞布隆過濾器由一系列塊 b 組成，這些塊 b 比標準布隆過濾器 (布隆過濾器塊) 小得多，每個塊都適合一個快取行。
- 阻塞布隆過濾器方案與分割槽方案不同，在分割槽方案中，每個位元都插入到不同的塊中。
阻塞布隆過濾器可以透過以下方式實現：
位模式 (pat)
在本主題中，我們討論瞭如何透過實現預計算位模式來實現阻塞布隆過濾器。與其透過評估 k 個雜湊函式來設定 k 個位元，不如使用單個雜湊函式從一個包含寬度為 B 的隨機 k 位模式的表中選擇一個預計算模式。在許多情況下，此表將適合快取。使用此解決方案，只需要一個小的（就位元而言）雜湊值，並且可以使用少量 SIMD（單指令多資料）指令來實現該操作。在傳輸布隆過濾器時，無需在資料中顯式包含該表，而是可以透過實現種子值來重建該表。
位模式方法的主要缺點是，當兩個元素被雜湊到相同的模式時，它們可能會導致表衝突。這會導致 FPR 增加。
多路複用模式
為了進一步改進這個想法，我們可以透過將 x 個模式進行按位或運算來從單個表中獲得更多種類的模式，這些模式的平均設定位數為 k/x。
多塊
另一種有助於提高 FPR 的變體稱為多塊。我們允許查詢操作訪問 X 個布隆過濾器塊，分別在每個塊中設定或測試 k/X 個位元。（當 k 不能被 X 整除時，我們在前 k mod X 個塊中設定一個額外的位元。）多塊的效能優於將塊大小簡單地增加到 XB（B-每個塊大小），因為這樣可以引入更多變化。如果我們將設定的位分佈在幾個塊中，則每個塊中 1 位的預期數量保持不變。但是，在訪問元素時，每個參與塊中只考慮 k/X 個位元。
更新於：2020年1月3日
747 次瀏覽
廣告