디지털 라이브러리[ 검색결과 ]
노드 사상 정보를 이용한 효과적인 그래프 편집 거리 학습 모델
http://doi.org/10.5626/JOK.2025.52.1.88
그래프 편집 거리(GED, Graph Edit Distance)는 그래프 사이의 유사도를 정량화하기 위한 가장 대표적인 방법이다. 그러나 정확한 GED 계산은 NP-Hard 문제로 많은 계산 비용을 필요로 한다. 따라서 최근 GED 근삿값을 예측하는 많은 딥러닝 모델들이 제안되었다. 하지만 기존 모델들은 상대 그래프와의 연관 관계를 부분적으로 고려함에 따라 근삿값의 오차가 크고, 노드 매칭 정보를 고려하지 않아 예측한 근삿값에 대한 설명력이 부족한 문제가 있다. 본 논문에서는 두 그래프의 노드 레벨 임베딩을 통해 사상 행렬을 학습하여 GED 근삿값의 설명력을 제공하며 학습 과정에서의 정보 손실을 최소화 하여 보다 정확한 GED를 예측하는 모델을 제안한다. 실험을 통해 제안한 모델이 기존 모델들보다 더 정확하게 GED를 예측하는 것을 보인다.
OLTP 워크로드에서 쓰기-웜 페이지에 대한 고찰
http://doi.org/10.5626/JOK.2023.50.11.1002
버퍼 교체 정책의 중요한 목적 중 하나는 버퍼 풀에 자주 접근되는 데이터를 캐싱하여 디스크 I/O를 최소화하는 것이다. 그러나, 버퍼 풀에 참조 빈도가 높은 페이지들이 효과적으로 저장됨에도 불구하고, 적은 양의 페이지들에 의해 과도하게 많은 디스크 I/O가 발생할 수 있다. 이는 버퍼 풀에서 페이지가 축출될 때, 상대적으로 참조 빈도가 높은 쓰기-웜 페이지(Write-Warm Page)가 쫓겨나 해당 페이지에 대한 버퍼 풀 반입과 반출 과정이 반복되기 때문이다. 본 논문에서는 이러한 현상을 "웜 페이지 스레싱((Write-)Warm Page Thrashing)"이라고 정의하며, 디스크로 플러시 되는 페이지 중 10%에 해당하는 페이지들이 약 41%의 디스크 쓰기를 발생시키는 쓰기-웜 페이지의 존재를 확인하였다. 특히, 이는 읽기 대비 쓰기가 느린 플래시 저장장치에서 성능에 악영향을 미칠 수 있기 때문에, 이를 검출하고, 스레싱을 방지하는 새로운 버퍼 관리 정책을 필요로 한다.
미시간 스타일 심층 학습 분류기 시스템 기반 적응적 데이터베이스 침입 탐지
http://doi.org/10.5626/JOK.2023.50.10.891
역할 기반 접근 제어(RBAC) 환경에서 데이터베이스 침입 탐지는 쿼리 트랜잭션에 대한 역할 분류기를 설계하고, 예측된 역할이 실제 수행된 역할과 다를 때 침입으로 판단함으로써 실현될 수 있다. 최근의 쿼리-역할 분류기 설계 방법들은 딥러닝 모델을 활용하였지만, 변화하는 패턴에 대해 높은 정확도와 불완전한 적응성을 동시에 달성하는 것이 어려웠다. 이러한 문제를 해결하기 위해, 본 연구에서는 미시간 스타일 심층 학습 분류기 시스템(MDLCS)을 제안한다. 이 방법은 입력 공간을 패턴별로 분할하고 최적의 분류기를 할당하는 분할-정복 전략을 적용하며, 미시간 스타일 학습 분류기 시스템의 진화 연산 원리와 딥러닝 분류기를 결합하여 실시간으로 변화하는 패턴에 적응하고 탐지 성능을 향상시킨다. 제안된 MDLCS 방법은 이상 징후 탐지, 서명 기반 탐지, 행동 기반 탐지 등 기존 침입 탐지 방법들과 비교하여 강한 적응성과 견고함을 제공한다. MDLCS는 TPC-E 스키마를 따르는 상업 데이터베이스에서 평가되었고, 순차적으로 새로운 패턴이 발생하는 실제 환경 조건에서 기존 방법 대비 26.81%p 개선된 탐지 성능을 달성하였다.
OANet: 데이터베이스 성능 예측을 위한 주의관심 메커니즘 기반 Ortho-Attention Net
http://doi.org/10.5626/JOK.2022.49.11.1026
데이터베이스에는 수정할 수 있는 다양한 매개변수들이 있는데, 이를 Knob이라 한다. Knob들의 설정에 따라 데이터베이스의 성능이 상이하기 때문에 데이터베이스의 Knob을 튜닝 하는 것이 중요하다. 이 때 Knob 설정에 따른 데이터베이스 성능을 신뢰할 수 있고 신속하게 예측할 수 있는 모델이 필요하다. 하지만 Knob 설정이 같더라도 벤치마크를 수행하는 워크로드가 다른 경우 그 결과가 다를 수 있다. 따라서 본 논문에서는 주의관심 메커니즘을 기반으로 한 OANet을 제안함으로써 Knob뿐만 아니라 워크로드와 Knob 간의 연관성도 고려할 수 있도록 하였다. 그리고 제안한 모델의 성능을 확인하기 위해 기존에 사용하던 기계학습 기법들과 데이터베이스의 성능 예측 결과를 비교하였고 가장 높은 결과를 보임으로써 모델의 우수성을 검증하였다.
멀티테넌트 환경에서 SSD 내부 채널 간섭 완화를 위한 데이터베이스 튜닝 기법
http://doi.org/10.5626/JOK.2022.49.5.388
멀티테넌트 환경에서 다수의 테넌트들은 단일 SSD를 저장장치로 공유한다. IO의 특성이 상이한 멀티테넌트는 SSD 내부 채널 수준의 간섭이 발생한다. 본 논문에서는 SSD 내부 채널 수준의 병렬성을 충분히 활용하기 위한 두 가지 튜닝 기법인 페이지 크기 정렬 기법과 Readahead 크기 증가 기법을 제안하고, 도커 컨테이너 기반 환경에서 Linkbench와 TPC-H를 동시 수행하여 트랜잭션 처리량 및 응답(수행)시간 성능을 평가한다. 성능평가 결과, 페이지 크기 정렬 기법은 SSD 내부에서 불필요한 데이터 패딩/분할 작업의 오버헤드를 줄이고, IO 요청의 불필요한 채널점유를 방지하기 때문에 내부 간섭을 완화시켜, Linkbench와 TPC-H 모두 성능이 향상되었다. 하지만, Readahead 크기 증가 기법은 순차 읽기 요청의 SSD 내부 채널 점유율을 높여, Linkbench의 비교적 작은 크기의 임의 IO 요청에 의한 간섭을 줄이기 때문에, TPC-H의 성능만 향상되었다.
공간 키워드 유사도 기반의 부분적 집단 공간 키워드 질의처리 기법
http://doi.org/10.5626/JOK.2021.48.10.1142
집단적 공간 키워드 질의(collective spatial keyword query)는 질의 위치와 가까우면서 제시된 키워드 집합을 모두 포함하는 관심지점(point of interest; POI)들을 반환한다. 하지만 고정된 수의 질의 키워드를 고려하므로 사용자의 부분 키워드 집합에 대한 선호도를 충분히 반영할 수 없다. 따라서 POI 마다 선호도에 맞는 키워드를 유동적으로 고려하는 새로운 질의인 부분적 집단 공간 키워드 질의(partial collective spatial keyword query)를 제안한다. 이 질의는 조합 최적화 문제이므로 POI의 수가 늘어남에 따라 수행 시간이 급격하게 증가한다. 따라서 이러한 문제를 해결하기 위해 전체적인 탐색 공간을 줄이는 키워드 기반 탐색 기법을 제안한다. 또한 키워드의 부분집합을 계산하는 시간을 줄이기 위해 선형 탐색에 기반한 단말노드 가지치기 기법과 근사 알고리즘 기법 및 임계값에 기반한 가지치기 기법들을 제안한다.
클라우드 컴퓨팅 환경에서 개인정보를 보호하는 FP-Growth 기반 연관 규칙 마이닝 알고리즘
http://doi.org/10.5626/JOK.2020.47.8.707
최근 클라우드 컴퓨팅 기술의 발전과 함께, 데이터베이스 소유자는 자신의 데이터베이스를 클라우드 서버에 아웃소싱하여 낮은 비용으로 전문적인 데이터 관리를 제공받을 수 있다. 그러나 원본 데이터베이스를 클라우드 서버에 아웃소싱하는 것은 데이터베이스에 있는 금융, 의료와 같은 민감 정보가 노출될 수 있다. 본 논문에서는 클라우드 컴퓨팅 환경에서 개인 정보를 보호하는 FP-Growth 기반 연관 규칙 마이닝 알고리즘을 제안한다. 제안하는 알고리즘은 민감 정보를 보호하기 위해 암호문 상에서 특정 연산을 지원하는 동형 암호 체계를 사용하여 원본 데이터와 사용자의 질의를 암호화한다. 암호문 상에서의 효율적인 질의 처리를 제공하기 위해, 원본 데이터의 노출 없이 암호문을 비교하는 비교 연산 프로토콜을 제안한다. 성능평가를 통해 제안하는 알고리즘이 기존 기법에 비해 약 68～123%의 성능 향상을 보인다.
PSL-DB: 비휘발성 메모리 환경에서 스킵리스트를 이용한 LSM-Tree 최적화
http://doi.org/10.5626/JOK.2020.47.7.635
Intel의 Optane DC Persistent Memory가 출시되면서 DRAM보다 높은 용량을 제공하며, SSD와 HDD보다 높은 성능을 보여주는 비휘발성 메모리가 차세대 스토리지로 각광받고 있다. 본 논문에서는 스킵리스트를 사용하여 비휘발성 메모리가 스토리지로 사용되는 환경에 최적화한 Key-Value 데이터베이스인 Persistent SkipList DataBase (PSL-DB)를 제안한다. PSL-DB는 비휘발성 메모리의 바이트 단위 접근이 가능한 점을 이용하여 기존 LevelDB의 블록 단위 접근을 위한 SSTable 구조 대신, 바이트 단위 쓰기가 가능한 스킵리스트를 활용한다. 그 결과 PSL-DB는 같은 데이터를 중복해서 여러 번 쓰는 쓰기 증폭 문제를 발생시키지 않으며, 읽기 성능을 위해 쓰기 성능을 고의로 제한하지 않아 성능을 크게 향상시킬 수 있다. Intel Optane DC Persistent Memory를 활용한 실험에서 PSL-DB는 같은 Optane DC PM을 사용하는 기존 LevelDB보다 읽기와 쓰기 명령모두 높은 초당 연산량을 보여주었다.
도로 교통망 환경에서 G-트리 구조를 이용한 단일 그룹 콜렉티브 여행 질의 처리
http://doi.org/10.5626/JOK.2020.47.5.513
본 연구에서는, 위치 기반의 승차 공유 서비스에서 전체 여행비용을 최소화 하는 단일 그룹 콜렉티브 여행 질의 처리를 다루려고 한다. 단일 그룹 콜렉티브 여행 질의는 여러 명의 사용자들이 특정 지점에 모여서 하나의 운송 수단을 이용하여 도착 지점으로 이동을 할 때, 이 때 소요되는 전체 비용을 최소화 하는 지점을 찾는 것이 목표이다. 콜렉티브 여행 질의와 관련된 연구들이 많이 진행이 되었지만 특정 상황에서만 효과적인 성능을 보인다는 문제점을 가지고 있다. 따라서 우리는 단일 그룹 콜렉티브 여행질의의 기초 해결 방안을 소개하고 해당 방안보다 더 나은 성능을 보이는 G-트리 기반의 효과적인 가지치기 기법을 제시한다. 추가로, 기존에 연구되었던 방법들의 한계를 밝히고, 제시하는 기법이 기존 연구들이 갖는 한계에 영향을 받지 않고 최적 결과를 구할 수 있음을 실험을 통해 보인다.
LSM-tree 기반 Key-value 데이터베이스의 재귀적 컴팩션 기법
http://doi.org/10.5626/JOK.2019.46.9.946
LSM-tree 기반 Key-value 데이터베이스는 데이터 쓰기 연산의 성능에 최적화 된 구조를 가지며, 일반적으로 컴팩션 연산을 통해 LSM-tree의 형태를 유지하며 데이터를 관리한다. 컴팩션 연산은 저장 장치에 기록된 데이터를 메모리로 읽어들여 정렬한 뒤 결과 데이터를 저장 장치로 다시 쓰는 작업을 반복하며, 이러한 동작 패턴은 몇 가지의 문제점을 발생시킨다. 본 논문에서는 이러한 컴팩션 연산이 유발하는 성능 손실 및 쓰기 증폭 현상에 대하여 분석하고, 이를 개선하기 위한 재귀적 컴팩션 기법을 제안한다. 재귀적 컴팩션 기법은 멀티스레드를 활용하여 동시에 여러 컴팩션을 수행하며 읽기 요청 및 가비지 컬렉션을 적절히 수행하여 컴팩션이 유발하는 문제를 완화시킨다. 위 기법을 LSM-tree based Key-value 데이터베이스 중 하나인 Google의 LevelDB에 적용한 뒤 이에 대한 실험 결과를 분석한다.
