분산 환경에서 학습된 색인을 활용한 효율적인 고차원 색인 기법 :

이현병

추천

검색

자료유형: 학위논문

저자정보: 이현병 (충북대학교 )

지도교수: 유재수

발행연도: 2023

저작권: 충북대학교 논문은 저작권에 의해 보호받습니다.

이용수5

이 논문의 연구 히스토리 (5)

2024

스파크 환경에서 학습된 색인 및 VA 파일을 이용한 고차원 데이터 색인 기법

이현병 , 송상호 , 김상혁 외 6명 한국콘텐츠학회논문지 2024.04 학술저널

2023

스파크에서 내용 기반 이미지 검색을 위한 VA-File 기반의 고차원 데이터 색인 기법

이현병 , 송상호 , 김상혁 외 5명 한국정보과학회 학술발표논문집 2023.06 학술대회자료

스파크에서 벡터 근사를 활용한 효율적인 고차원 데이터 색인 기법

이현병 , 송상호 , 최도진 외 6명 한국콘텐츠학회논문지 2023.06 학술저널

스파크에서 고차원 데이터 처리를 위한 학습된 색인 기법

이현병 , 김상혁 , 성우제 외 5명 한국콘텐츠학회 종합학술대회 논문집 2023.05 학술대회자료

분산 환경에서 학습된 색인을 활용한 효율적인 고차원 색인 기법

이현병 정보통신공학과 2023.01 학위논문

이 논문의 후속연구가 궁금하신가요?
연관 학술논문 또는 학술발표를 통해 보다 발전된 연구결과를 확인하실 수 있습니다.
이 논문의 연구 히스토리 확인하기

초록· 키워드

오류제보하기

최근 현대 사회는 다양한 원천으로부터 복잡하고 다양한 형태의 데이터를 생성하고 있다. 특히 고차원 데이터의 생성으로 데이터 분석은 더욱 복잡해지고 차원의 저주(Curse of dimensionality) 문제에 직면한다. 고차원 데이터의 차원의 저주 문제는 컴퓨터 과학 분야에서 오랫동안 해결 중인 문제 중 하나이다. 이 문제의 특징 중 하나는 차원의 수가 너무 많기 때문에 각 차원 간의 관계를 이해하고 분석하는 것이 어렵다는 것이다. 데이터 구조와 알고리즘은 데이터 저장 및 처리의 효율성을 결정하는 주요 요소다. 특히, 색인 구조는 데이터베이스에서 빠른 탐색을 위한 핵심 개념이다.
과거의 고차원 데이터는 이미지로부터 추출한 특징 데이터로 적게는 수십 차원에서 많게는 수백 차원을 가진 데이터로 이를 표현할 수 있었다. 그러나 최근 기계학습 기반의 특징 데이터를 생성하는 연구가 진행되면서 이는 1,000차원 이상의 특징 데이터로도 이를 상세히 표현하기 어렵다. 이러한 데이터를 활용하기 위해서는 일반적으로 K-최근접 이웃 질의(K-Nearest Neighbor, KNN)나 일정 범위에 대한 질의를 수행하는 범위 질의(Range Query) 혹은 정답으로 가장 많이 등장하는 K개의 항목 탐색하는 Top-K 질의 등을 효과적으로 수행할 수 있어야 한다. 또한, 고차원 데이터 집합에서 정확한 질의 처리가 어렵기 때문에 일부의 정확도 손실을 감안하고 더 빠른 속도로 근사한 정답을 찾는 ANN(Approximate Nearest Neighbor) 또한 고려가 필요하다.
학습된 색인(Learned Index)은 기계학습 모델을 활용하여 색인을 구성하는 새로운 접근 방법이다. 학습된 색인은 전통적인 B-tree, 해싱 등과 같은 색인 구조들을 기계학습 모델로 대체하는 아이디어를 기반으로 한다. 여기서 핵심은 기계학습 모델이 특정 입력에 대한 출력을 예측할 수 있음을 이용하는 것이다. 그러나 학습된 색인 또한 복잡한 데이터에 대하여 탐색을 수행하기는 차원의 저주 등의 문제로 인하여 효과적인 탐색이 어렵다.
본 논문은 분산 환경에서 학습된 색인을 활용한 효율적인 고차원 색인 기법인 HILNDR(efficient High dimensional Indexing schemes using LearNed index in Distributed enviRonments)를 제안한다. 제안하는 기법은 벡터 근사화 기반 방법인 VA-File과 학습된 색인을 활용한다. VA-File은 고차원 벡터 데이터에 대한 근사 정보를 저장하는 간단하면서도 효과적인 색인 구조 중 하나이다. 기존 학습된 색인의 한계점인 고차원 데이터나 대용량 데이터에 이를 활용하기 어려운 점을 극복하기 위하여 VA-File을 활용하여 분산 처리 환경인 아파치 스파크(Apache Spark)를 활용하여 제안하는 기법을 구현했다. 이를 위해 전체 데이터 집합을 파티셔닝하고 각 파티션별로 학습된 색인을 구축하고 이를 활용하여 질의 처리를 수행한다.
제안하는 기법의 우수성을 보이기 위해, KD-Tree, iDistance와 같은 트리 기반의 기법과 LSH, FAISS 등 고차원 데이터에 자주 사용되는 색인 기법과 다양한 성능평가를 수행한다. 실험 결과, 제안하는 기법이 K-NN 질의 처리를 수행했을 때 질의 수행 속도 측면에서 기존 기법보다 최대 6배 이상 빠른 성능을 보였다. 또한 정확도 역시 기존 근사 탐색 기법보다 약 33% 뛰어난 성능을 보였다.

Recently, modern society is generating complex and diverse types of data from various sources. In particular, with the generation of high-dimensional data, they become more complex in data analysis and face the problem of curses of dimensions. The problem of the dimension curses of high-dimensional data is one of the long-standing problems in computer science. One of the characteristics of this problem is that the number of dimensions is so large that it is difficult to understand and analyze the relationship between each dimension. Data structures and algorithms are the main factors that determine the efficiency of data storage and processing. In particular, index structure is a key concept for fast search in databases.
In the past, high-dimensional data could be expressed as feature data extracted from images, with at least tens of dimensions to as many as hundreds of dimensions. However, with recent research on generating machine learning-based feature data, it is difficult to express it in detail even with feature data of more than 1,000 dimensions. In order to utilize such data, it is necessary to effectively perform K-Nearest Neighbor (KNN), Range Query that performs queries on a certain range, or Top-K queries that search for K items that appear the most as correct answers. In addition, since accurate query processing on high-dimensional datasets is difficult, Approximate Nearest Neighbor (ANN) that takes into account some loss of accuracy and finds approximate answers at a faster rate also needs to be considered.
Learned Index is a new approach to constructing indexes using machine learning models. The learned index is based on the idea of replacing index structures such as traditional B-tree and Hashing with machine learning models. The key here is to use that the machine learning model can predict the output for a specific input. However, the learned index is also difficult to search effectively due to problems such as dimension curses to perform searches on complex data.
In this dissertation, we propose an efficient high-dimensional indexing scheme using learned indexes, called HILNDR(efficient High dimensional Indexing schemes using LearNed index in Distributed enviRonments) in distributed environments. The proposed scheme utilizes VA-File, a vector approximation-based method, and a learned index. VA-File is one of the simple and effective index structures that stores approximate information for high-dimensional vector data. To overcome the difficulty of using it for high-dimensional data or large-capacity data, which is a limitation of existing learned indexes, VA-File is used to implement the proposed scheme based on Apache Spark, a distributed processing environment.
It is shown through various performance evaluations that the proposed scheme outperforms the existing tree-based schemes such as KD-Tree and iDistance, and the indexing schemes frequently used for high-dimensional data such as LSH and FAISS. As a result of the experiment, when the proposed scheme performs K-NN query processing, it achieves up to 6 times faster performance improvements than the existing schemes. In addition, the proposed scheme achieves about 33% better accuracy than the existing approximate search schemes.

#고차원 색인 #분산 환경 #학습된 색인

Ⅰ. 서 론 1
1.1 연구 필요성 1
1.2 연구 목적 및 특징 7
1.3 연구의 구성 9
II. 관련연구 10
2.1 질의 정의 10
2.2 차원의 저주 및 차원 축소 방법 14
2.3 고차원 색인 기법 17
2.4 학습된 색인 기법 22
2.5 아파치 스파크 25
III. 제안하는 고차원 색인 기법 28
3.1 연구 동기 29
3.2 전체 구조 및 처리 절차 30
3.3 전처리 과정 35
3.4 VA-File 색인 구축 과정 41
3.5 학습된 색인 구축 과정 53
3.6 질의 처리 과정 56
IV. 성능평가 62
4.1 성능평가 환경 62
4.2 VA-File 구성 파라미터에 대한 정확도 보존 성능 66
4.3 색인 구축 소요 시간 및 색인 크기 71
4.4 학습된 색인 탐색 성능 결과 73
4.5 전체 데이터 탐색 결과 75
4.6 성능평가 결과 91
V. 결 론 92
참고문헌 94

최근 본 자료

전체보기

구분	그룹	데이터 항목
AI 학습용 데이터	원문	원문 PDF 파일
AI 학습용 데이터	원문 + 메타 (기본/상세)	원문 PDF 파일 및 서지정보 CSV
대량 구매용 데이터	B2B 구독 방식	특정 자료 한정으로 원문 접근 권한 부여
대량 구매용 데이터	URL 전달 방식	바로 PDF 뷰어를 열람할 수 있는 URL 제공

구분	그룹	데이터 항목
AI 학습용 데이터	기본 메타	발행기관명, 간행물명, 권호명, 권(vol), 호(issue), 통권, 발행연도, 발행월, 논문명, 저자명, 시작페이지, 종료페이지, 전체페이지, 상세페이지URL
상세 메타 데이터	발행기관 메타	발행기관 이명, 영문명, 창립연도, 홈페이지URL, 발행기관 소개
	간행물 메타	부제목, 간행물 유형, ISSN, ISBN, 최초발행연도, 폐간연도, 간행빈도, 발행주기, 등재사항, 이용수, 피인용수, 권호수, 논문수, 표지이미지
	논문 메타	작성 언어, 부제목, 대등제목, 목차, 키워드, 초록, 이미지, 참고문헌, 이용수, 피인용수, 논문활용도, DBpia통합주제분류, KDC분류, DDC분류, 한국연구재단분류, UCI, DOI
	저자 메타	소속기관, 소속부서, 직급, 연구분야, 연구키워드, 이용수, 피인용수, 저자 논문활용도

구분	그룹	데이터 항목
※ 결합형/맞춤형 메타 데이터는 신청 내용에 따라 다양하게 제공 가능
이용순위 정보	주제분야별 많이 이용된 논문	“인문학”에서 많이 이용된 논문 TOP100
	이용기관별 많이 이용된 논문	“중고등학교”에서 많이 이용된 논문 TOP100
	세부기관별 많이 이용된 논문	“서울대학교”에서 많이 이용된 논문 TOP100
	키워드별 많이 이용된 논문	“Chat GPT”에서 많이 이용된 논문 TOP100
키워드 정보	많이 이용된 키워드	특정기간/분야/저널 내 많이 이용된 키워드
	많이 발행된 키워드	특정기간/분야/저널 내 많이 발행된 키워드
	많이 검색된 키워드	특정기간/분야/저널 내 많이 검색된 키워드
	연구 트렌드 키워드	특정 키워드 연관 연구동향 분석 데이터 키워드

논문 기본 정보

이 논문의 연구 히스토리 (5)

초록· 키워드

목차

최근 본 자료

댓글(0)