Learned FBF: Learning-Based Functional Bloom Filter for Key-Value Storage
- 주제(키워드) deep learning , functional Bloom filter , Key-value storage , search failure
- 등재 SCIE, SCOPUS
- 발행기관 IEEE Computer Society
- 발행년도 2022
- 총서유형 Journal
- URI http://www.dcollection.net/handler/ewha/000000193319
- 본문언어 영어
- Published As https://doi.org/10.1109/TC.2021.3112079
초록/요약
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. © 1968-2012 IEEE.
more