디지털 라이브러리[ 검색결과 ]
전통적 탐색을 넘어서: SIMD 최적화 기반 Learned Index 오차 보정 탐색
http://doi.org/10.5626/JOK.2025.52.5.363
기계 학습 기반의 Learned Index는 전통적 인덱스 기법의 한계를 극복하기 위해 등장했다. 본 논문에서는 읽기 전용 RMI와 수정 가능한 ALEX의 탐색 성능을 분석하고, 오차 보정 과정에서 발생하는 오버헤드를 줄이기 위한 SIMD 기반 최적화 기법을 제안한다. Learned Index는 키의 분포를 학습해 예측과 오차 보정의 두 단계로 탐색을 수행하는데, 오차 보정이 전체 탐색 시간의 최대 80%를 차지할 수 있음이 확인되었다. RMI에서는 오차가 클 때 탐색 범위를 빠르게 줄이는 SIMD Branchless Binary Search, 작을 때 모델 예측 기반의 SIMD Linear Search가 효과적이었다. 반면, ALEX는 일정한 오차 범위를 유지하는 특성으로 인해 단순한 SIMD Linear Search가 가장 효율적이었다. 이를 통해 데이터셋의 오차 범위, 인덱스 크기 및 밀도에 따라 적절한 탐색 알고리즘을 선택하는 것이 성능 최적화에 중요함을 제시한다.
격자 탐색을 통한 확장 학습 블룸 필터의 거짓 양성 비율 개선
http://doi.org/10.5626/JOK.2022.49.1.78
블룸 필터는 집합을 표현하는 자료구조로 데이터의 포함 여부에 대해서 반환하는 역할을 수행한다. 단, 공간을 적게 사용하는 대가로 거짓 양성을 반환하는 경우가 존재한다. 학습 블룸 필터는 기존의 블룸 필터에 추가적으로 기계학습 모델을 전처리 과정에 사용하여 거짓 양성 비율을 개선하는 방법이다. 즉, 학습 블룸 필터는 기계학습 모델로 일부의 데이터를 저장하고, 모델이 저장하지 못하는 데이터는 보조 필터에 저장한다. 보조 필터는 블룸 필터를 그대로 사용하는 방법도 존재하지만, 본 논문에서의 보조 필터는 블룸 필터와 학습 해시 함수를 같이 사용하는 학습 블룸 필터에 대해서 살펴보고 이를 확장 학습 블룸 필터라고 부른다. 학습 해시 함수는 전처리 과정에서 사용하던 기계학습 모델의 출력값을 해시 함수로 사용하는 방법이다. 본 논문에서는 격자 탐색을 통해서 확장 학습 블룸 필터의 거짓 양성 비율을 개선하는 방법을 제안한다. 이는 학습 해시 함수의 비율을 나타내는 초매게변수의 값을 늘려나가며 가장 낮은 거짓 양성 비율을 가지는 확장 학습 블룸 필터를 탐색하는 방법이다. 결과적으로, 100,000개 이상의 데이터를 저장해야하는 실험 환경에서는 격자 탐색을 통해서 선택된 확장 학습 블룸 필터가 기존의 학습 블룸 필터 보다 20% 개선된 거짓 양성 비율을 가질 수 있음을 실험적으로 보인다. 추가적으로, 학습 해시 함수에 사용되는 인공신경망 모델의 출력값이 32비트 부동소수점인 경우에 거짓 음성 오류 문제가 발생할 수 있음을 보이고, 이를 64비트 부동소수점으로 변경하면 해결됨을 보인다. 마지막으로, 10,000개의 데이터를 질의하는 실험 환경에서 인공신경망 모델의 구조를 조정하여 20KB의 공간을 절약하고 동일한 거짓 양성 비율을 갖는 확장 학습 블룸 필터를 만들 수 있음을 보인다. 단, 20KB의 공간을 절약하는 대가로 질의 시간이 2% 늘어난 것을 실험적으로 보인다.
