이론적 보장을 갖춘 파티션 학습 블룸 필터의 고속 구성

블룸 필터는 근사 멤버십 질의에 널리 사용되는 고전적인 자료구조입니다. 학습 블룸 필터는 기계 학습을 활용하여 메모리 효율성을 개선하며, 파티션 학습 블룸 필터(PLBF)는 가장 메모리 효율적인 변형 중 하나로 꼽힙니다. 그러나 PLBF는 구성 비용이 높다는 단점이 있으며, 그 시간 복잡도는 N과 k가 하이퍼파라미터일 때 O(N^3k)에 달합니다. 본 논문에서는 이러한 높은 구성 비용 문제를 해결하기 위해 fast PLBF, fast PLBF++, fast PLBF#의 세 가지 방법을 제안합니다. 이 방법들은 구성 복잡도를 각각 O(N^2k), O(Nk log N), O(Nk log k)로 크게 줄입니다. fast PLBF는 원본 PLBF의 구조와 메모리 효율성을 그대로 유지합니다. fast PLBF++와 fast PLBF#는 구조가 다를 수 있지만, 이상적인 데이터 분포에서는 PLBF와 동등함을 이론적으로 증명합니다. 또한, 비이상적인 시나리오를 위해 이상적인 분포로부터의 편차를 측정하는 인스턴스별 지표를 도입하고, 이를 사용하여 PLBF와 fast PLBF++ 간의 메모리 효율성 차이를 한정합니다. 실제 데이터셋을 이용한 실험 결과, 기본 설정(N=1000, k=5)에서 fast PLBF, fast PLBF++, fast PLBF#는 기존 PLBF보다 구성 속도가 각각 최대 58.7배, 74.5배, 75.7배 빨랐습니다. 더 정확한 PLBF 구성이 가능한 더 큰 k 값(k=50)을 사용한 실험에서는 속도 향상이 각각 235배, 865배, 871배에 달했습니다. fast PLBF는 PLBF와 동일한 자료구조를 유지하며, fast PLBF++와 fast PLBF#는 거의 동일한 메모리 효율성을 달성합니다. 이 연구는 학습 블룸 필터의 실용성을 크게 향상시킬 것입니다.