확장 학습 블룸 필터의 효율적인 구현

Abstract

기존의 자료구조는 데이터의 분포와 무관하게 일정한 성능을 가지는 것을 목표로 하고 있다. 하지만 데이터의 분포를 사용한다면 성능을 개선할 수 있다는 연구가 학습 인덱스라는 이름으로 진행되고 있다. 본 연구에서는 학습 인덱스의 종류 중 하나인 학습 블룸 필터를 확장하고 구현하는데 초점을 둔다. 이를 확장 학습 블룸 필터라고 부르며, 이는 기존의 학습 블룸 필터의 구조에 학습 해시 함수를 추가한 자료구조이다. 해당 자료구조는 하이퍼파라미터 ɑ를 통해서 학습 해시 함수와 보조 필터의 비율을 조정할 수 있으며, 기존의 학습 블룸 필터에 비해서 거짓 양성 비율을 개선시킬 수 있음을 실험을 통해 보인다. 추가적으로 확장 학습 블룸 필터를 구현하는 도중에 발생했던 모델의 정밀도 문제를 소개하고, 이를 64비트 부동소수점으로 해결할 수 있음을 보인다. 그 외에도 모델 조정을 통해서 확장 학습 블룸 필터의 성능이 개선될 수 있음을 보이고, 학습 해시 함수가 성능 개선에 기여하는 방법을 이해하고자 한다.

Existing data structures aim to have constant performance regardless of data distribution. However, a study is being conducted under the name of learned index, that the performance can be improved by the use of data distribution. In this study, we focus on extending and implementing learned bloom filter, which is one of the types of learned index. This is called as an extended learned bloom filter, and it is a data structure which adds a learned hash function into the structure of learned bloom filter. Experiments show that false positive rate can be improved through changing the ratio of learned hash function and the auxiliary filter using the hyperparameter ɑ. Additionally, we introduce the model precision problem that occurred during the implementation of the extended learned bloom filter, which can be solved by using 64-bit floating point. In addition, we show that the performance of the extended learned bloom filter can be improved by tuning the model, and we try to understand how the learned hash function contributes to performance improvement.