Digital Library[ Search Result ]
Improving False Positive Rate of Extended Learned Bloom Filters Using Grid Search
http://doi.org/10.5626/JOK.2022.49.1.78
Bloom filter is a data structure that represents a set and returns whether data is included or not. However, there are cases in which false positives are returned at the cost of using less space. The learned bloom filter is a variation of the bloom filter, that uses a machine learning model in the pre-processing process to improve the false-positive rate. The learned bloom filter stores some data in the machine learning model, and the leftover data is stored in the auxiliary filter. An auxiliary filter can be implemented by using a bloom filter only, but in this paper, we use the bloom filter and the learned hash function, and this is called an extended learned bloom filter. The learned hash function uses the output value of the machine learning model as a hash function. In this paper, we propose a method that improves the false positive rate of the extended learned bloom filter through grid search. This method explores the extended learned bloom filter with the lowest false positive rate, by increasing the hyperparameter that represents the ratio of the learned hash function. As a result, we experimentally show that the extended learned bloom filter selected through grid search, can have a 20% improvement in false-positive rate compared to the learned bloom filter, in the experiment that needs more than 100,000 data to store. In addition, we also show that the false negative error may occur in the learned hash function by the use of 32-bit floating points in the neural network model. This can be solved by changing the floating points to 64-bit. Finally, we show that in an experiment where we query 10,000 data, we can adjust the structure of the neural network model to save 20KB of space and create an extended learned bloom filter with the same false-positive rate. However, the query time is increased by 2% at the cost of saving 20KB of space.
A Packet Classification Algorithm Using Bloom Filter Pre-Searching on Area-based Quad-Trie
As a representative area-decomposed algorithm, an area-based quad-trie (AQT) has an issue of search performance. The search procedure must continue to follow the path to its end, due to the possibility of the higher priority-matching rule, even though a matching rule is encountered in a node. A leaf-pushing AQT improves the search performance of the AQT by making a single rule node exist in each search path. This paper proposes a new algorithm to further improve the search performance of the leaf-pushing AQT. The proposed algorithm implements a leaf-pushing AQT using a hash table and an on-chip Bloom filter. In the proposed algorithm, by sequentially querying the Bloom filter, the level of the rule node in the leaf-pushing AQT is identified first. After this procedure, the rule database, which is usually stored in an off-chip memory, is accessed. Simulation results show that packet classification can be performed through a single hash table access using a reasonable sized Bloom filter. The proposed algorithm is compared with existing algorithms in terms of the memory requirement and the search performance.
Search
Journal of KIISE
- ISSN : 2383-630X(Print)
- ISSN : 2383-6296(Electronic)
- KCI Accredited Journal
Editorial Office
- Tel. +82-2-588-9240
- Fax. +82-2-521-1352
- E-mail. chwoo@kiise.or.kr