- Trước tiên, chúng tôi chọn một khối bộ nhớ.
- Sau đó, chúng tôi chọn Bộ lọc Bloom cục bộ trong mỗi khối.
- Nó có thể gây mất cân bằng giữa các khối bộ nhớ
- Bộ lọc này hiệu quả, nhưng tỷ lệ dương tính giả (FPR) kém.
- Lúc đầu, các bộ lọc Bloom bị chặn phải có cùng FPR (Tỷ lệ Tích cực Sai) như các bộ lọc Bloom tiêu chuẩn có cùng kích thước.
- Bộ lọc Bloom bị chặn bao gồm một chuỗi khối b tương đối ít hơn các bộ lọc Bloom tiêu chuẩn (khối bộ lọc Bloom), mỗi khối phù hợp với một dòng bộ nhớ cache.
- Lược đồ bộ lọc Blocked Bloom khác với các lược đồ phân vùng, trong đó mỗi bit được chèn vào một khối khác nhau.
Bộ lọc Nở hoa bị chặn được triển khai theo những cách sau -
Mẫu Bit (pat)
Trong chủ đề này, chúng ta thảo luận để triển khai các bộ lọc Bloom bị chặn triển khai các mẫu bit được tính toán trước. Thay vì đặt k bit thông qua việc đánh giá k hàm băm, một hàm băm đơn chọn một mẫu tính toán trước từ bảng mẫu k-bit ngẫu nhiên có độ rộng B. Trong nhiều trường hợp, bảng này sẽ phù hợp với bộ nhớ cache. Với giải pháp này, chỉ cần một giá trị băm nhỏ (tính theo bit) và hoạt động có thể được thực hiện bằng cách sử dụng một vài lệnh SIMD (Đa dữ liệu hướng dẫn đơn). Tại thời điểm chuyển bộ lọc Bloom, bảng không cần phải được đưa vào dữ liệu một cách rõ ràng, nhưng có thể được tạo lại bằng cách thực hiện giá trị gốc.
Nhược điểm chính của phương pháp mẫu bit là hai phần tử có thể gây ra xung đột bảng khi chúng được băm thành cùng một mẫu. Điều này làm tăng FPR.
Các mẫu ghép kênh
Để tinh chỉnh ý tưởng này một lần nữa, chúng tôi có thể đạt được nhiều mẫu hơn từ một bảng đơn lẻ bằng các mẫu x theo chiều dọc hoặc theo chiều với số lượng bit đặt trung bình là k / x.
Đa khối
Một biến thể khác giúp cải thiện FPR, được gọi là đa chặn. Chúng tôi cho phép thao tác truy vấn truy cập các khối bộ lọc X Bloom, thiết lập hoặc kiểm tra k / X bit tương ứng trong mỗi khối. (Khi k không chia hết cho X, chúng tôi đặt thêm một bit trong k mod X. khối đầu tiên.) Đa chặn hoạt động tốt hơn so với việc chỉ tăng kích thước khối lên XB (B-kích thước mỗi khối), vì điều này có nhiều sự đa dạng hơn. đường. Nếu chúng ta chia các bit đã đặt cho một số khối, số lượng mong đợi 1 bit trên mỗi khối sẽ không đổi. Tuy nhiên, chỉ k / X bit được xem xét trong mỗi khối tham gia, khi truy cập một phần tử.