FeCBF: A Novel Sub-Optimal Cascaded Bloom Filter Structure Based on Feature Extraction

Abstract

This work presents the Feature extraction Cascaded Bloom Filter (FeCBF), a novel probabilistic data structure formed by cascading multiple Bloom filters in an optimum sequence. The FeCBF’s distinctive design of alternating positive and negative filter layers effectively suppresses False Positive/Negative Rates (FPR/FNR), enabling exact filtering with reasonable resource cost. Compared to other state-of-the-art designs on the same experimental dataset, FeCBF demonstrates significant memory space savings of 45% to 76% while maintaining the best FPR in its class. The proposed model also includes a closed-form expression for determining the sub-optimal FeCBF configuration based on desired filter performance metrics, offering the potential for automatic design flow. The FeCBF architecture, designed for hardware implementation, holds promise for many applications. It can be readily deployed as an accelerator in various computing problems, including massive content filtering, network traffic filtering, and online malware/virus detection.

Keywords

• Bloom filter
• feature extraction
• pattern matching
• big-data filter
• probabilistic filter
• hardware acceleration