Learned indexes utilize machine learning models to predict the position of a data record for a given lookup key. On read-intensive tasks, it has been shown that learned index structures are more efficient than traditional tree-like structures (e.g., B-Trees) in terms of lookup time and memory consumption. However, existing learned indexes require the tuning of parameters for the index to achieve the best performance. Though parameter tuning can significantly affect lookup time and memory consumption, it often requires too much time and effort to find the optimal parameters for the given environment. In this paper, we propose the Log-Concave Density Estimation (LCDE) index that uses nonparametric density estimation in the process of index construction. LCDE learns the distribution of data under a constrained memory budget, without requiring manual parameter tuning. Through intensive experiments on various workloads, we show that LCDE outperforms other existing methods in most cases in terms of query throughput and space consumption.
학습된 색인은 머신 러닝 모델을 활용해 탐색 키에 대해 데이터 레코드의 위치를 예측한다. 읽기 중심의 작업에서 학습된 색인은 B-트리와 같은 전통적인 트리 구조의 색인과 비교하여 탐색 시간과 메모리 소비 측면에서 효율적임이 보여진 바 있다. 그러나 기존의 학습된 색인은 최적의 성능을 얻기 위해 색인의 파라미터를 알맞게 설정할 필요가 있다. 학습된 색인의 파라미터 설정은 색인의 탐색 시간과 메모리 소비에 큰 영향을 주는 요소이므로, 특정 환경에 대한 최적의 파라미터를 찾기 위해 색인 구축 시 많은 시간이 소요된다. 본 논문에서 제안하는 학습된 색인인 LCDE는 색인의 구성 과정에서 사용자의 파라미터 설정 과정 없이 비모수 밀도 추정을 활용하여 주어진 메모리 예산 내에서 데이터의 분포를 학습한다. 다양한 워크로드에 대한 실험 결과를 통해 LCDE가 기존의 방법들에 비해 탐색 속도와 색인 크기 면에서 뛰어남을 보인다.
