디지털 라이브러리[ 검색결과 ]
전통적 탐색을 넘어서: 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.2025.52.4.331
본 논문은 h-index, g-index, i10-index와 같은 기존의 학문적 성과 평가 지수들이 최신 연구 성과를 충분히 반영하지 못한다는 한계를 보완하기 위해, 연구자의 최근 성과와 연구 영향력을 함께 반영한 새로운 연구자 추천 지수를 제안한다. 제안하는 지수는 최신성과 연구 영향력이라는 두 가지 요소로 구성된다. 이 지수는 연구자가 발표한 논문의 최신성에 가중치를 부여하여 현재 연구 동향에 발맞춘 학문적 성과를 평가할 수 있도록 설계된다. 또한, 사용자가 원하는 평가 목적에 따라 최신성과 연구 영향력의 가중치를 조정할 수 있어, 맞춤형 연구자 추천이 가능하다. 실험을 통해 제안한 지수와 기존 지수 간의 상관 관계를 분석한 결과, 제안한 지수는 최신 연구 성과가 많은 연구자들을 더 효과적으로 식별하며, 기존 지수와 일정 부분 연관성을 유지하면서도 최신성을 반영해 서로 다른 특징을 보여준다. 구체적으로, 최신성의 가중치를 높일 경우 최근 성과가 우수한 연구자들이 더 높은 순위를 차지한다. 반면, 연구 영향력의 가중치를 높일 경우, 기존 지수와 강한 상관관계를 보이며 안정적인 평가 결과를 제공한다.
MemTable의 부분 비우기를 사용한 LSM 트리의 성능 개선
http://doi.org/10.5626/JOK.2023.50.1.87
NoSQL의 종류 중 하나인 키-값 저장소에서는 색인 자료 구조로 로그 기반 병합 트리(이하 LSM 트리)가 널리 사용된다. LSM 트리는 대체로 빠른 쓰기 성능을 보이나, 쓰기 증폭과 쓰기 멈춤 문제로 인해 최대한의 성능을 내는 것이 쉽지 않다. 본 논문에서는 최근 데이터 센터의 주 메모리의 크기가 증가하는 추세인 점을 고려하여, 기존 LSM 트리의 메모리 자료 구조인 MemTable의 크기를 확장하여 설계한 Extended MemTable을 소개한다. Extended MemTable은 키-값을 삽입할 때, 키 값의 범위에 따른 구획을 이용하여 컴팩션 연산이 효율적으로 작동할 수 있도록 비우기(Flush) 연산을 수행한다. 실험 결과 본 논문의 디자인은 쓰기 처리량을 기존 RocksDB에 비해 최대 2배, 읽기 처리량은 기존 RocksDB 대비 최대 4배 개선하였으며, 쓰기 증폭 현상은 최대 3.7배 줄어들어 쓰기 증폭과 쓰기 멈춤 문제를 크게 개선하였음을 확인할 수 있다.
격자 탐색을 통한 확장 학습 블룸 필터의 거짓 양성 비율 개선
http://doi.org/10.5626/JOK.2022.49.1.78
블룸 필터는 집합을 표현하는 자료구조로 데이터의 포함 여부에 대해서 반환하는 역할을 수행한다. 단, 공간을 적게 사용하는 대가로 거짓 양성을 반환하는 경우가 존재한다. 학습 블룸 필터는 기존의 블룸 필터에 추가적으로 기계학습 모델을 전처리 과정에 사용하여 거짓 양성 비율을 개선하는 방법이다. 즉, 학습 블룸 필터는 기계학습 모델로 일부의 데이터를 저장하고, 모델이 저장하지 못하는 데이터는 보조 필터에 저장한다. 보조 필터는 블룸 필터를 그대로 사용하는 방법도 존재하지만, 본 논문에서의 보조 필터는 블룸 필터와 학습 해시 함수를 같이 사용하는 학습 블룸 필터에 대해서 살펴보고 이를 확장 학습 블룸 필터라고 부른다. 학습 해시 함수는 전처리 과정에서 사용하던 기계학습 모델의 출력값을 해시 함수로 사용하는 방법이다. 본 논문에서는 격자 탐색을 통해서 확장 학습 블룸 필터의 거짓 양성 비율을 개선하는 방법을 제안한다. 이는 학습 해시 함수의 비율을 나타내는 초매게변수의 값을 늘려나가며 가장 낮은 거짓 양성 비율을 가지는 확장 학습 블룸 필터를 탐색하는 방법이다. 결과적으로, 100,000개 이상의 데이터를 저장해야하는 실험 환경에서는 격자 탐색을 통해서 선택된 확장 학습 블룸 필터가 기존의 학습 블룸 필터 보다 20% 개선된 거짓 양성 비율을 가질 수 있음을 실험적으로 보인다. 추가적으로, 학습 해시 함수에 사용되는 인공신경망 모델의 출력값이 32비트 부동소수점인 경우에 거짓 음성 오류 문제가 발생할 수 있음을 보이고, 이를 64비트 부동소수점으로 변경하면 해결됨을 보인다. 마지막으로, 10,000개의 데이터를 질의하는 실험 환경에서 인공신경망 모델의 구조를 조정하여 20KB의 공간을 절약하고 동일한 거짓 양성 비율을 갖는 확장 학습 블룸 필터를 만들 수 있음을 보인다. 단, 20KB의 공간을 절약하는 대가로 질의 시간이 2% 늘어난 것을 실험적으로 보인다.
Opt Tree: Optane DCPM 내부 버퍼를 활용한 쓰기 최적화 트리
http://doi.org/10.5626/JOK.2021.48.7.742
최근 상용화된 비휘발성 메모리인 Intel사의 Optane DC Persistent Memory는 캐시 라인 단위 또는 워드 단위의 메모리 접근 명령을 256바이트 단위로 처리하는 내부 버퍼가 존재한다. 본 논문에서는 Optane DCPM의 내부 버퍼를 활용하는 인덱스인 Opt Tree를 제안한다. Opt Tree는 트리의 노드를 256 바이트 단위의 여러 작은 블록으로 나누어 노드 내의 데이터들을 분할 저장하며, 노드 접근 시에는 2개의 블록만을 접근하는 삽입 및 탐색 알고리즘을 가진다. Opt Tree는 Optane DCPM의 내부 버퍼에 친화적인 디자인과 알고리즘을 바탕으로 기존의 비휘발성 메모리를 위한 인덱스들보다 더 나은 삽입 성능을 보여준다.
방대한 시공간 IoT 센서 데이터의 효율적인 검색을 위한 트라이 기반 색인 방법
추하원, 서영균, 이용, 박민우, 장래영, 이상환, 송사광
http://doi.org/10.5626/JOK.2020.47.12.1199
통신 기술과 컴퓨팅 능력의 발전으로 인해 사물인터넷 센서가 여러 분야에 보편화되면서 대량의 시공간 사물 데이터가 끊임없이 생성되고 있다. 고차원적인 추가 분석을 위해, 그러한 거대한 시공간 사물 데이터를 저장 시스템에 수집하는 것은 고도화된 저장 기술 덕분에 그리 어렵지 않게 되었다. 그럼에도 불구하고, 사물데이터의 거대한 양과 복잡한 시공간성으로 인해 질의된 사물 데이터를 신속히 찾아내는 것은 여전히 도전적인 문제로 여겨져 왔다. 본 논문은 이러한 문제점을 해결하기 위해 시공간성을 가진 대용량 사물 데이터에 대해 효율적인 검색을 지원하는 색인 방법인 ST-Trie를 제안한다. ST-Trie의 핵심 아이디어는 시공간 지역성을 고려하여 3차원 시공간 정보를 1차원 데이터로 부호화한 다음, 이를 논리적인 트라이(Trie) 구조로 조직하는 것이다. 제안된 방법인 ST-Trie에 대한 실제 사물인터넷 센서로부터 얻은 데이터 셋들을 이용한 실험 결과, ST-Trie가 질의 응답 시간에 관하여 비교된 복합 색인보다 최대 92배 더 높은 성능을 보였다. 특히, 우리는 ST-Trie가 주어진 시간 범위가 커질수록 더 확장성 있는 검색을 수행하였음을 확인하였다.
스파크 환경에서 내용 기반 이미지 검색을 위한 효율적인 분산 인-메모리 고차원 색인 기법
최도진, 박송희, 김연동, 위지원, 이현병, 임종태, 복경수, 유재수
http://doi.org/10.5626/JOK.2020.47.1.95
영상에서 범죄 행위 모니터링 및 추적을 위해서 이미지 내에 포함된 객체를 검색하는 내용 기반 검색이 활용되고 있다. 본 논문에서는 내용 기반 이미지 검색을 위해 이미지 또는 객체에서 추출한 대용량 특징 벡터를 이용한 유사도 검색을 지원하는 분산 인-메모리 기반 고차원 색인 기법을 제안한다. 대용량 분산 처리를 위해 빅데이터 플랫폼인 스파크를 활용하고 효율적인 분산 질의 처리 할당을 위해 마스터/슬레이브 모델을 활용한다. 마스터에서는 데이터 및 질의 분배를 수행하고 슬레이브에서는 데이터를 색인한다. 더불어 기존 분산 고차원 색인 기법에서 k-최근접 질의 처리의 성능 문제를 해결하기 위해서 밀집도 및 탐색 비용을 고려한 k-최근접 질의 최적화 기법을 제안한다. 제안하는 기법의 우수성 및 타당성을 입증하기 위해 다양한 성능 평가를 수행한다.
하이퍼그래프 데이터베이스에서 구조 인덱스를 활용한 효율적인 동형 서브그래프 검색
http://doi.org/10.5626/JOK.2019.46.7.697
그래프는 실세계의 객체 간 관계를 모델링 할 수 있으며, 관계들을 분석하는 데 사용된다. 하이퍼그래프는 그래프의 일반화된 모델로서 하나의 하이퍼에지가 2개 이상의 객체가 참여하는 관계를 나타낼 수 있다. 본 논문에서는 데이터 하이퍼그래프에서 질의 그래프와 동형인 서브그래프를 검색하는 효율적인 방법을 제안한다. 동형 서브그래프 검색의 높은 계산 비용을 줄이기 위해 기존 연구들에서는 각 질의 노드 에 대해 정답이 될 수 있는 후보군을 선택하고, 후보들의 조합으로 이루어진 서브그래프와 질의 그래프의 동형성을 검증하여 정답을 반환한다. 본 연구에서는 검색 성능을 높이기 위해, 질의 그래프를 여러 개의 서브그래프로 분해하여 제안하는 구조 인덱스로 각 서브그래프의 후보를 찾고, 제안하는 검색 알고리즘으로 서브그래프 동형성을 검증한다. 실제 데이터셋을 이용한 실험에서 제안 연구는 기존 연구 대비 검색 응답 속도 측면에서 최소 10배의 성능 향상을 얻었다.
IoT 환경에서의 시공간 조인의 효율적 처리 기법
http://doi.org/10.5626/JOK.2019.46.1.86
시공간 조인은 서로 다른 릴레이션의 데이터 중 서로 동일한 시간과 동일한 위치 값을 가지는 데이터를 결합하는 연산이다. 특히 최근 IoT의 보급과 함께 서로 다른 사물들이 과거에 발생시킨 데이터 중 동일한 시간에 동일한 위치에서 발생된 데이터를 검색하기 위해 시공간 조인의 필요성이 증가하고 있다. 본 논문에서는 둘 이상의 사물들이 발생시킨 데이터를 효율적으로 시공간 조인하는 기법을 제안한다. 제안 방법은 평면과 시간으로 이루어진 3차원 시공간을 작은 부분 공간들로 나누고, 각 부분 공간 별로 그 내부에 데이터가 존재하는 사물들을 기록한다. 사물들 간 시공간 조인이 요청되면, 제안 방법은 해당 사물들의 데이터가 서로 가까이 존재하는 공간들을 탐색한다. 그 후 탐색된 공간 내에 존재하는 데이터만을 가져와서 조인을 수행한다. 따라서 제안 방법은 서로 조인 가능성이 있는 데이터만을 접근하므로 수행비용이 크게 감소한다. 실제 사물 데이터로 성능을 측정한 결과 제안 방법은 기존 시공간 조인 방법에 비해 수행 시간을 크게 단축함을 확인하였다.
모바일 앱 스피드 인덱스 측정 도구 설계 및 구현
http://doi.org/10.5626/JOK.2018.45.11.1135
모바일 앱의 속도는 사용자 경험에 큰 영향을 미치기 때문에 개발자들은 사용자의 만족도를 높이기 위하여 앱의 속도를 고려한다. 하지만 안드로이드 개발 도구가 제공하는 앱 속도 측정 방법은 다운로드 컨텐츠의 렌더링 시간을 측정하지 못 하기 때문에 사용자가 실제로 느끼는 속도를 알려주지 못 한다. 본 연구는 웹의 성능 지표인 스피드 인덱스를 모바일 앱에 적용하여 모바일 앱의 속도를 측정하는 방법을 제안한다. 모바일 앱 스피드 인덱스 계산을 위하여 무작위 사용자 이벤트 생성기와 속도 측정기를 개발하였으며 이미지 유사도 비교를 통하여 렌더링 완료를 파악하였다. Google Play Store 인기 차트 1093개의 앱을 대상으로 스피드 인덱스를 계산하여 8%의 느린 앱을 발견하였다.
