TY - JOUR
T1 - Learned FBF
T2 - Learning-Based Functional Bloom Filter for Key-Value Storage
AU - Byun, Hayoung
AU - Lim, Hyesook
N1 - Publisher Copyright:
© 1968-2012 IEEE.
PY - 2022/8/1
Y1 - 2022/8/1
N2 - 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.
AB - 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.
KW - Key-value storage
KW - deep learning
KW - functional Bloom filter
KW - search failure
UR - http://www.scopus.com/inward/record.url?scp=85115137735&partnerID=8YFLogxK
U2 - 10.1109/TC.2021.3112079
DO - 10.1109/TC.2021.3112079
M3 - Article
AN - SCOPUS:85115137735
SN - 0018-9340
VL - 71
SP - 1928
EP - 1938
JO - IEEE Transactions on Computers
JF - IEEE Transactions on Computers
IS - 8
ER -