FLEX : 공유 노드 구조를 활용한 유연한 학습 기반 인덱스
Breaking the Tree: Flexible Learned Indexing with Shared-Node Topology
- 주제(키워드) Learned Index , Routing Flexibiltiy , Error Correction
- 주제(DDC) 355
- 발행기관 아주대학교 일반대학원
- 지도교수 김상훈
- 발행년도 2025
- 학위수여년월 2025. 8
- 학위명 석사
- 학과 및 전공 일반대학원 국방디지털융합학과
- 실제URI http://www.dcollection.net/handler/ajou/000000034894
- 본문언어 한국어
- 저작권 아주대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
기존 인덱스 구조는 데이터 분포를 추정하지 않기 때문에, 데이터가 대규모이거나 분포가 왜 곡된 환경에서는 탐색 효율성과 확장성 측면에서 한계를 드러낸다. 이를 극복하기 위해 제안된 학습 기반 인덱스(Learned Index)는 데이터 키 분포를 기계학습 모델로 학습하여 키의 위치를 예측하는 방식으로, 탐색 성능과 메모리 효율성을 동시에 개선할 수 있는 가능성을 제시한다. 그러나 Learned Index는 정적인 데이터셋을 기반으로 학습되기 때문에, 동적 워크로드에서 빈 번한 모델 재학습이 요구되며 이는 높은 오버헤드를 초래한다. 이러한 한계를 극복하기 위해 제안된 ALEX는 gapped array 구조와 부분적 재학습을 통해 동적 환경에 적응하는 구조를 제공하지만 트리 구조 내 모델 예측의 한계와 경직된 모델 계층 구조로 인해 예측 오류가 연쇄적으로 전파되는 서브 트리 lock-in 문제를 안고 있다. 본 논문 에서는 이러한 구조적 한계를 극복하기 위해, 하나의 노드를 복수의 상위 모델이 공유할 수 있 도록 설계된 DAG 기반의 유연한 인덱스 구조인 FLEX를 제안한다. FLEX는 탐색 경로의 다 양성을 확보하여 예측 오류 시 복원 능력을 제공하고, 삽입 시 불필요한 구조 변경을 억제함으 로써 확장성을 강화한다. 다양한 데이터셋을 통한 실험 결과, FLEX는 ALEX 대비 탐색 성능을 최대 40% 개선하고, 전체 모델 수를 약 10% 줄이면서도 데이터 및 내부 노드 분할 빈도를 안정적으로 감소시킴을 보였다. 본 연구는 학습 기반 인덱스 구조의 정확도, 유연성, 확장성 간의 균형을 달성할 수 있 는 새로운 방향성을 제시한다.
more초록/요약
Traditional indexing structures do not account for the distribution of data, which limits their scalability and lookup efficiency in large-scale or highly skewed datasets. To address this limitation, learned index structures have been proposed. These approaches use machine learning models to approximate the key distribution and predict key positions, offering the potential to improve both search performance and memory efficiency. However, because they are trained on static datasets, learned indexes often require frequent model retraining under dynamic workloads, leading to significant overhead. ALEX mitigates this issue by introducing a gapped array structure and partial model retraining to handle insertions and deletions. Nonetheless, its strict tree-based model hierarchy propagates prediction errors, resulting in the subtree lock-in problem, where mispredictions at higher levels lock the search path into incorrect subtrees. To address this structural limitation, we propose FLEX, a DAG-based indexing architecture that allows a single data node to be shared among multiple parent models. FLEX enhances search flexibility by enabling alternative paths for recovery and suppresses unnecessary structural updates during insertions, thereby improving scalability. Experimental results on various datasets demonstrate that FLEX achieves up to 40%improvement in lookup performance and approximately 10% reduction in model count compared to ALEX, while also reducing the frequency of data and internal node splits. This study presents a novel direction for learned index structures by achieving a more balanced trade-off among accuracy, flexibility, and scalability in dynamic environments.
more목차
제 1 장 서론 1
제 2 장 관련 연구 3
제 1 절 기계학습 기반 인덱스 3
제 2 절 관련 연구 동향 5
제 3 장 연구 목적 7
제 4 장 시스템 구현 11
제 1 절 RMI 구현 11
제 2 절 FLEX 동작 방식 14
1. 탐색 14
2. 삽입 17
3. 수정 및 삭제 19
제 5 장 성능 평가 21
제 1 절 실험 환경 21
제 2 절 RMI 구조 분석 23
제 3 절 탐색 성능 분석 24
제 4 절 확장성 분석 27
제 6 장 결론 29
참고문헌 30
Abstract 32
