Search

As a challenging attempt to replace a traditional data structure with a learned model, this paper proposes a learned functional Bloom filter (L-FBF) for a key–value storage. The learned model in the proposed L-FBF learns the characteristics and the distribution of given data and classifies each input. It is shown through theoretical analysis that the L-FBF provides a lower search failure rate than a single FBF in the same memory size, while providing the same semantic guarantees. For model training, character-level neural networks are used with pretrained embeddings. In experiments, four types of different character-level neural networks are trained: a single gated recurrent unit (GRU), two GRUs, a single long short-term memory (LSTM), and a single one-dimensional convolutional neural network (1D-CNN). Experimental results prove the validity of theoretical results, and show that the L-FBF reduces the search failures by 82.8% to 83.9% when compared with a single FBF under the same amount of memory used. [ABSTRACT FROM AUTHOR]

Key–value data structures have been extensively used in various applications. When a large amount of data needs to be compactly stored in a fixed memory size, a functional Bloom filter is a space-efficient key–value structure. In this letter, we propose a 2-stage functional Bloom filter structure composed of a primary functional Bloom filter and a secondary functional Bloom filter to resolve the indeterminables produced from the primary functional Bloom filter. We analytically present the memory ratio allocated for each of the two Bloom filters to achieve the lowest search failure rate. The analytical result is validated through experiments, thereby demonstrating that the optimal performance is realized when the secondary functional Bloom filter uses 3% of the total memory. [ABSTRACT FROM AUTHOR]

A counting Bloom filter (CBF) is commonly used in many applications for the membership queries of dynamic data since the CBF can provide delete operations. A CBF uses an array of $c$ -bit counters. The $c$ should be large enough to avoid overflows. In this letter, we propose an alternative to CBF, named ternary Bloom filter (TBF) for performance improvement. The proposed TBF allocates the minimum number of bits to each counter and includes more number of counters instead to reduce false positive probability. We present a mathematical analysis and experimental results for a set of performance measures. When the TBF consumes the same amount of memory as the CBF, the TBF provides much lower false positive rates than the CBF. [ABSTRACT FROM PUBLISHER]