격자 탐색을 통한 확장 학습 블룸 필터의 거짓 양성 비율 개선

Abstract

블룸 필터는 집합을 표현하는 자료구조로 데이터의 포함 여부에 대해서 반환하는 역할을 수행한다. 단, 공간을 적게 사용하는 대가로 거짓 양성을 반환하는 경우가 존재한다. 학습 블룸 필터는 기존의 블룸 필터에 추가적으로 기계학습 모델을 전처리 과정에 사용하여 거짓 양성 비율을 개선하는 방법이다. 즉, 학습 블룸 필터는 기계학습 모델로 일부의 데이터를 저장하고, 모델이 저장하지 못하는 데이터는 보조 필터에 저장한다. 보조 필터는 블룸 필터를 그대로 사용하는 방법도 존재하지만, 본 논문에서의 보조 필터는 블룸 필터와 학습 해시 함수를 같이 사용하는 학습 블룸 필터에 대해서 살펴보고 이를 확장 학습 블룸 필터라고 부른다. 학습 해시 함수는 전처리 과정에서 사용하던 기계학습 모델의 출력값을 해시 함수로 사용하는 방법이다. 본 논문에서는 격자 탐색을 통해서 확장 학습 블룸 필터의 거짓 양성 비율을 개선하는 방법을 제안한다. 이는 학습 해시 함수의 비율을 나타내는 초매게변수의 값을 늘려나가며 가장 낮은 거짓 양성 비율을 가지는 확장 학습 블룸 필터를 탐색하는 방법이다. 결과적으로, 100,000개 이상의 데이터를 저장해야하는 실험 환경에서는 격자 탐색을 통해서 선택된 확장 학습 블룸 필터가 기존의 학습 블룸 필터보다 20% 개선된 거짓 양성 비율을 가질 수 있음을 실험적으로 보인다. 추가적으로, 학습 해시 함수에 사용되는 인공신경망 모델의 출력값이 32비트 부동소수점인 경우에 거짓 음성 오류 문제가 발생할 수 있음을 보이고, 이를 64비트 부동소수점으로 변경하면 해결됨을 보인다. 마지막으로, 10,000개의 데이터를 질의하는 실험 환경에서 인공신경망 모델의 구조를 조정하여 20KB의 공간을 절약하고 동일한 거짓 양성 비율을 갖는 확장 학습 블룸 필터를 만들 수 있음을 보인다. 단, 20KB의 공간을 절약하는 대가로 질의 시간이 2% 늘어난 것을 실험적으로 보인다.