[이근배 교수] Multi-Level Attention Aggregation for Language-Agnostic Speaker Replication

[연구의 필요성] 기본 음성합성 모델들이 생성하는 음성의 품질이 매우 자연스러워져서, 원하는 사람의 목소리로 음성을 합성하는 다중 화자 TTS 연구가 증가하고 있습니다. 그러나, 기존의 다중 화자 TTS는 특정 언어 내에서만 음성 합성이 가능하기 때문에, 학습 데이터와 다른 언어로 말하는 화자의 목소리를 따라하지 못하는 한계가 있습니다. 따라서, 본 연구에서는 이러한 unseen 언어로 말하는 화자에게도 해당 화자의 목소리로 음성 합성이 가능하도록 하는 방법을 탐색하였습니다. [포스텍이 가진 고유의 기술] 화자의 목소리는 pitch와 timbre 같은 다양한 특징으로 구성되어 있습니다. 이에 따라 기존의 다중 화자 TTS 연구는 이러한 정보를 학습하거나 사전 훈련된 화자 확인 모델을 사용하여 input reference audio에서 화자의 목소리 정보를 직접 추출하는 방법을 채택했습니다. 본 논문은 이러한 모든 방법을 사용하면서도, 다양한 정보를 어떻게 융합해야 언어와 무관하게 화자의 음성을 복제할 수 있는지를 탐구했습니다. 구체적으로는 사전 훈련된 화자 확인 모델을 통해 추출된 reference audio representation을 yin algorithm으로 추출한 pitch관련 representation과 cross attention을 진행하였습니다. 이후, 화자의 전역 timbre 정보를 컨볼루션 블록을 통해 추출하고 이를 이전 aggregation 단계의 아웃풋과 다시 cross attention을 통해 결합합니다. Generalizability를 향상시키기 위해 representation splitting을 진행하였고, 최종적으로 생성된 화자 표현을 기준 TTS 프레임워크에 condition으로 적용했습니다. [연구의 의미] 본 연구에서는 말하는 언어와 관계없이 화자의 목소리를 추출할 수 있는 새로운 task를 제안하였으며이를 위해 다양한 화자의 목소리 정보를 추출하고 융합하는 최적의 절차를 탐색하였습니다. 실험 결과, 정보 융합을 위한 2단계 절차를 거칠 때 언어와 상관없이 화자의 목소리를 대체적으로 잘 모방할 수 있는 것을 확인할 수 있었습니다. [연구결과의 진행 상태 및 향후 계획] 처음으로 제시한 테스크인만큼, 성능을 더 높일 수 있는 방법을 탐색할 계획입니다. [성과와 관련된 실적] Yejin Jeon, Gary Geunbae Lee, EACL 2024 Accepted [성과와 관련된 이미지]

[유환조 교수] Noisy Label Detection by Discriminative Dynamics with Label Corruption

[연구의 필요성] 딥러닝 모델을 효과적으로 학습하기 위해서는 정확한 라벨을 가진 대규모 데이터셋을 확보하는 것이 매우 중요하다. 그러나 현실에서는 사용되는 데이터의 라벨이 오염되는 경우가 많은데, 이는 딥러닝 모델의 성능에 부정적인 영향을 미친다. 따라서, 오염된 라벨을 가진 샘플을 식별하고 수정함으로써, 원본 데이터 세트의 품질을 향상시키거나, 오염된 라벨에 강건한 모델을 개발하는것은 매우 중요하다. [포스텍이 가진 고유의 기술] 본 연구에서는 오염된 라벨 감지를 위해 라벨을 인위적으로 손상시킨 데이터를 추가 후, 정확한 라벨을 가진 샘플과 오염된 라벨을 가진 샘플의 학습 다이나믹스 차이를 학습하는 새로운 프레임워크를 제시한다. 구체적으로, 제시하는 모델은 학습 다이나믹스의의 잠재적 표현을 클러스터링하여 오염된 라벨을 식별한다. 이를 위해 먼저 원본 샘플들과 인위적으로 손상된 샘플의 학습 다이나믹스을 생성한다. 이후 다이나믹스 인코더를 사용해 훈련 궤적 내에서 판별 패턴을 인코딩하는 역학 표현을 계산하고 분류한다. [연구의 의미] 본 연구는 지도학습 기반의 딥러닝 모델 개발을 위해 필수적인 정확한 데이터를 확보하는 데 도움을 준다. 또한, 이 연구를 통해 데이터셋에 포함된 오염된 샘플을 식별하고 개선할 수 있다. [연구결과의 진행 상태 및 향후 계획] 본 연구는 컴퓨터 비전 분야 최우수 국제학술대회인 The IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2024) 에 발표될 예정이다. 추후 본 연구 결과를 그래프 도메인에 접목시켜, 분자 그래프와 관련된 응용 분야에서의 활용 가능성을 탐구할 것이다. [성과와 관련된 실적] SY Kim, SK Kang, SK Chae, SH Jang, D Lee, H Yu, ” Learning Discriminative Dynamics with Label Corruption for Noisy Label Detection” The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2024. [성과와 관련된 이미지]

[이근배 교수] Denoising Table-Text Retrieval for Open-Domain Question Answering

[연구의 필요성] 오픈 도메인 질의 응답은 일반적으로 유저의 질의와 관계 있는 문서들을 검색하고 이 문서에 기반하여 응답을 생성하는 작업으로 이뤄진다. 이는 유저의 질의에 대한 응답을 직접적으로 제공할 수 있다는 점에서 관련성 있는 검색 결과만을 제공하는 기존의 검색 엔진에 비해 효과적이다. 최근에는 검색된 문서에서 텍스트 뿐만 아니라 테이블 정보까지 동시에 고려하여 응답을 생성하는 연구(Table-Text ODQA)가 활발히 이뤄지고 있다. 그러나 기존의 연구들은 Retriever 의 학습 과정이 데이터셋에 포함된 false-positive instance로 인해 noisy했고, 테이블 단위의 정보를 처리하지 못했다. 이에 본 연구는 기존의 연구들의 문제점을 완화한 Retriever를 개발하였다. [포스텍이 가진 고유의 기술] False positive detection: Retriever는 테이블의 행과 관련된 문서가 결합된 fused block을 검색 단위로 한다. 그러나 데이터셋에는 fused block 단위의 label이 되어 있지 않기에 이전 연구에서는 정답이 포함된 fused block을 positive instance로 취급하였다. 이는 정답이 테이블에서 빈번하게 등장하는 entity인 경우 false-positive training instance의 문제가 발생하게 된다. 이를 완화하기 위해 질의와 fused block간의 관련성을 수치화 하는 false-positive detection model을 훈련시켜 데이터셋을 denoising하였다. Rank-Aware Table Encoding (RATE): Fused block의 정보는 Table의 행 단위에 국한되어 있기에 질의가 테이블 단위의 비교를 요구하는 경우에는 검색기가 이를 처리할 수 없다. 이에 테이블 내에 속하는 값들의 순위 정보를 Rank-aware column encoder를 통해 ranking representation으로 변환하고 Retriever를 학습시킬 때 이러한 정보를 추가적으로 제공하였다. [연구의 의미] 본 연구에서는 기존의 Retriever 모델들이 간과하고 있던 한계점을 지적하였으며, 이를 개선하여 fused-block 단위의 검색 성능에서 state-of-the-art (SOTA)를 달성하였다. 또한, 질의응답 성능에서도 기존 연구보다 향상된 성능을 보였다. [연구결과의 진행 상태 및 향후 계획] 본 연구는 자연어처리 분야 우수 국제학술대회인 LREC-COLING 2024에 소개될 예정이다. 향후 순위 정보 뿐만 아니라 다양한 테이블 단위의 정보를 처리할 수 있는 Retriever를 개발하는 것을 목표로 하고 있다. [성과와 관련된 실적] Deokhyung Kang, Baikjin Jung, Yunsu Kim, and Gary Geunbae Lee, “Denoising Table—Text Retrieval for Open-Domain Question Answering”, LREC-COLING 2024 (accepted) [성과와 관련된 이미지] [이미지 1(대표 이미지) ] An overview of the encoding process for a fused block b with RATE [이미지 2] An example of a question and related table requires table-level reasoning

[최승문 교수] 비형식 학습 환경에서 물리적 전시물과 햅틱 전시물의 비교 연구

[연구의 필요성] 물리적 경험은 학습자의 지각과 학습 개념과 직접 연결함으로써 추상적인 개념 이해를 돕는 특별한 교육적 이점을 지닌다. 햅틱 피드백을 이용한 가상 전시물은 실제 물리적 전시물보다 낮은 비용으로 이러한 학습 효과와 콘텐츠 확장 기회를 제공할 수 있으나, 햅틱 전시물이 비형식 학습 환경에서 제공하는 교육적 가치와 가능성을 조사한 연구는 거의 없다. [포스텍이 가진 고유의 기술] 본 연구는 큰 시각 디스플레이에 붙일 수 있는 2-자유도 케이블 구동 햅틱 장치를 개발하고 물리적 전시물을 밀접하게 모방하는 가상 지레 시뮬레이션을 구현했다. 개발한 햅틱 전시물을 과학 박물관에서 제공하는 전통적인 물리적 전시물과 직접 비교하여 햅틱 전시물의 학습 원리와 확장된 콘텐츠의 효과를 정성적으로 평가했다. [연구의 의미] 지역 과학 박물관에서 수행된 사용자 연구는 어린이 방문객들이 햅틱 인터페이스에 대해 지니고 있는 일반적인 생소함에도 불구하 가상 전시물을 잘 받아들이고 높은 수준의 참여 행동을 보인다는 결과를 얻었다. 또한, 가상 전시물과 물리적 전시물은 서로 다른 학습 원리를 기반으로 하며, 이를 통해 가상 전시물을 개선하고 물리적 전시물을 보완할 수 있는 아이디어를 도출했다. 이는 다양한 학습 환경에서 햅틱 시스템의 활용 가능성을 시사하고 효과적인 햅틱 전시물의 추가적인 탐구를 촉진한다. [연구결과의 진행 상태 및 향후 계획] 본 연구에서는 비형식 학습 환경에서 어린이 방문객을 대상으로 2-자유도 햅틱 인터페이스를 활용한 가상 전시물의 효용성을 평가하였다. 보다 다양한 환경과 사용자를 대상으로 효용성을 조사해볼 필요가 있으며, 실질적인 적용을 위해 햅틱 인터페이스의 안전성을 개선하면 좋을 것이다. [성과와 관련된 실적] 국제 저널 논문: Lee, D., Nam, D., Yoon, J., Yoon, D., Jeong, S., Kim, K., & Choi, S. (2024). A Comparative Study of Physical and Haptic Exhibits in an Informal Learning Environment. IEEE Transactions on Haptics. [성과와 관련된 이미지] 그림 1. 왼쪽: 지역 과학 박물관에 설치되어 있는 전통적인 물리적 전시물. 오른쪽: 2-자유도 햅틱 인터페이스를 활용한 가상 전시물. 그림 2. 물리적 전시물과 가상 전시물의 학습 경험 비교. 가상 전시물이 확장된 컨텐츠로 인해 더 높은 사용 시간과 몰입 수준이 높은 사용 행동을 보임.

[한욱신 교수] 델타 질의 컴파일 프레임워크를 이용한 동적 서브그래프 매칭 방법 심층 분석

[연구의 필요성] 동적 서브그래프 매칭은 데이터 그래프가 업데이트될 때, 주어진 질의 그래프와 새롭게 매치되거나 더 이상 매치되지 않는 서브그래프를 찾는 문제이다. 동적 서브그래프 매칭은 사기 탐지를 비롯한 다양한 실생활 응용 분야에서 활용된다. 동적 서브그래프 매칭을 수행하는 다양한 방법이 개발됨에 따라, 각 방법을 공정하게 비교하고 장단점을 분석할 필요가 있다. 그러나 기존에 수행된 연구들은 동일한 방법들을 서로 다르게 구현하는 등 공정한 비교를 하지 못했고, 성능 차이를 만드는 핵심 요인 또한 분석하지 않았다. 최근에는 기존 방법들을 하나의 프레임워크 상에 구현하여 성능을 비교하고 분석하려는 시도가 있었지만, 기존 방법들을 틀리게 혹은 비효율적으로 구현하여 잘못된 실험 결과를 얻었으며, 방법별로 공통된 부분을 통합하지 않고 각각 별도로 구현하여 성능 차이에 대한 원인을 정확히 분석하지 못하였다. 따라서,동적 서브그래프 매칭 방법들을 공정하고 심도있게 비교할 수 있는 새로운 프레임워크의 개발이 필요하다. [포스텍이 가진 고유의 기술] 본 기술은 동적 서브그래프 매칭 문제를 관계형 데이터베이스의 점진적 뷰 유지(IVM)에서의 델타 질의라는 공통된 관점으로 보고, 각 동적 서브그래프 매칭 방법들을 델타 질의 플랜으로 표현 및 수행하는 프레임워크를 제안함으로써 앞서 언급한 문제들을 해결하였다. 먼저, 모든 방법에서 동일한 물리적 연산자에 대해 통일된 구현을 사용하여 기존 방법들을 공정하게 비교하였다. 또한, 기존 방법들에서 사용하는 다양한 기술들을 플랜 일부만 수정함으로써 쉽게 통합하거나 제거할 수 있게 되었고, 이를 통해 각 기술이 성능에 미치는 영향을 상세히 분석했다. 추가적으로, 본 기술은 질의 플랜 컴파일레이션과 같은 관계형 데이터베이스의 기술을 활용하여 기존 방법들의 성능을 더욱 개선하였다. [연구의 의미] 본 연구는 기존에 수행된 연구들에서 보인 실험 결과 및 분석이 잘못되었음을 밝혔으며, 기존 방법들을 우리 프레임워크를 사용하여 공평하게 다시 비교하였고, 방법들 간의 성능 차이를 내는 요인을 논리적, 물리적 플랜의 관점에서 자세히 분석하였다. 특히, 가장 최신에 나온 방법보다 성능이 낮다고 알려진 기존 방법들도, 제안한 프레임워크 상에서 올바르게 구현한다면 최신 방법보다 최대 48.6배 높은 성능을 보인다는 사실을 밝혔다. [연구결과의 진행 상태 및 향후 계획] 본 연구는 데이터베이스 시스템 분야 최고 학술대회인 ACM SIGMOD 2024에 발표될 예정이다. 향후 본 연구를 확장하여 동적 서브그래프 매칭 방법들에 대한 비용 기반의 최적화기를 개발하고자 한다. [성과와 관련된 실적] Lee, Y., Kim, K., Lee, W., and Han, W.-S., “In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework,” In 50th Int’l Conf. on Management of Data, ACM SIGMOD, Chile, June 2024. (Corresponding author) [성과와 관련된 이미지] (그림 1) 기존 방법인 TurboFlux를 질의 플랜으로 표현한 예시 (그림 2) 기존 방법인 SymBi를 질의 플랜으로 표현한 예시

[안성수 교수] Efficient credit assignments in training GFlowNets

[연구의 필요성] Generative Flow Network (GFlowNet)은 주어진 특성을 만족하는 다양한 후보를 생성하는 방법론이며, 신약 및 신소재 개발 또는 조합 최적화 문제와 같은 문제에서 광범위하게 적용되고 있다. GFlowNet의 생성 과정은 다양한 action을 선택하며 점진적으로 샘플을 생성하는 것이며, 이 때 action의 선택 확률은 생성된 타겟의 특성을 기반으로 훈련된다. 하지만, 생성되는 타겟은 여러 action에 관련되어 있으며, 최종적으로 관측되는 특성 기반의 훈련은 각 action이 어떤 기여를 하는지 인지하기 어렵다는 credit assignment 문제가 존재한다. 이에 본 연구는 보다 개선된 credit assignment를 수행할 수 있는 GFlowNet의 훈련 방법을 제안한다. [포스텍이 가진 고유의 기술] 본 연구는 Learning Energy Decomposition for Partial Inference in GFlowNets (LED-GFN)이라는 이름의 에너지 분해 기반의 GFlowNet 학습 방법을 제안한다. 핵심 아이디어는 최종 상태 특성 (에너지)를 각 action에 따른 상태 전이와 관련된 학습 가능한 potential의 합으로 분해하여 로컬 크레딧으로 사용하는 것이다. 특히, 각 potential이 최종 상태와의 상관 관계를 잘 반영할 수 있도록 하는 정규화 방법을 적용하여 훈련한다. 이러한 potential은 중간 action이 최종 특성에 어떻게 영향을 미치는지에 대한 훈련 신호로서 credit assignment를 개선한다. [연구의 의미] 본 연구에서 제시하는 방법론은 효율적인 부분 추론 기반의 GFlowNet 훈련 방법을 새롭게 제시하였다. 이는 기존의 GFlowNet 훈련 방법과 비교하여, 분자 생성 및 조합 최적화 등 다양한 benchmark에서 질 좋은 샘플들의 생성을 더욱 촉진 시킬 수 있음을 보였다. [연구결과의 진행 상태 및 향후 계획] 본 연구는 인공지능 분야 최우수 국제 학술 대회인 International Conference on Learning Representations (ICLR 2024)에서 oral presentation award를 수상하였다 (제출 논문 중 상위 1.16%). 향후 계획은, GFlowNet의 훈련 과정에서 credit assignment을 어렵게하는 다른 요인을 발견 및 개선하는 것이 목표로 한다. [성과와 관련된 실적] Jang, H., Kim, M., and Ahn, S. Learning energy decompo- sitions for partial inference of GFlowNets. International Conference on Learning Representations (ICLR), 2024. [성과와 관련된 이미지]

[김동우/안성수 교수] New representations for graph generation

[연구의 필요성] 최근 중요성이 대두되고 있는 신약 개발, 신소재 개발 등에 생성 모델을 적용하기 위해서는 그래프 생성 모델의 개발이 필수적이다. 기존의 그래프 생성 모델 연구들은 그래프에 맞는 형태의 모델 아키텍처를 개발하는 것에 집중해왔고, 그래프의 representation으로 인접 행렬만을 사용해왔다. 하지만 생성 모델은 representation의 분포를 학습해야 하기 때문에, 더 간단하고 모델이 학습하기에 좋은 representation의 개발은 생성 모델의 성능에 직접적으로 영향을 미친다. 이에 본 연구는 새로운 그래프 representation을 제시하여 학습 데이터의 특징을 잘 학습하여 그래프를 생성할 수 있는 생성 모델을 개발하였다. [포스텍이 가진 고유의 기술] Graph generation with K2-trees (HGGT): 기존에 그래프 압축(compression) 분야에서 사용되던 K2-tree를 생성 모델에 적용하여 이를 autoregressive하게 생성하는 그래프 생성 모델을 개발하였다. K2-tree는 인접행렬을 서브행렬로 나누어 모든 성분이 0인 서브행렬을 하나의 성분 0으로 매핑하여 효율적으로 그래프를 표현할 뿐만 아니라, 서브행렬 간의 hierarchy를 표현하는 것이 가능하다. 본 연구에서는 이러한 K2-tree의 특성을 반영하는 시퀀스 형태의 representation을 제시하여 양질의 그래프를 더 빠르게 생성하는 생성 모델을 제시하였다. A simple and scalable representation for graph generation (GEEL): 그래프 bandwidth를 활용한 엣지 리스트를 그래프의 새로운 representation으로 제시하여 이를 autoregressive하게 생성하는 그래프 생성 모델을 개발하였다. 이를 통해 인접 행렬 기반의 representation보다는 생성 단계의 수를 줄여 더 빠른 생성이 가능하고, 기존의 엣지 리스트 기반 representation보다는 토큰의 종류를 줄여 더 적은 메모리만을 활용해도 생성이 가능하도록 하여 더 scalable한 그래프 생성 모델을 제시하였다. [연구의 의미] 본 연구에서 제시하는 생성모델은 기존 그래프 생성 모델들보다 더 신속한 생성 속도를 가지지만 더 높은 질의 그래프를 생성하여 state-of-the-art (SOTA) 성능을 보였다. 뿐만 아니라, 중요성에 비해 비교적 선행 연구가 부족했던 생성 모델을 위한 representation의 선택에 집중하여 이의 중요성을 환기하였다. [연구결과의 진행 상태 및 향후 계획] 본 연구는 인공지능 분야 최우수 국제학술대회인 International Conference on Learning Representations (ICLR 2024)에서 포스터로 발표되었다.이 연구는 이산화된 특성(discrete feature)을 가지는 분자 그래프만을 대상으로 했는데, 향후 3D 위치 등 연속된 특성을 가지는 그래프에 대해서 연구를 확장할 예정이다. [성과와 관련된 실적] Yunhui Jang, Dongwoo Kim, Sungsoo Ahn, “Graph generation with K2-trees”, ICLR 2024 Yunhui Jang, Seul Lee, Sungsoo Ahn, “A simple and scalable representation for graph generation”, ICLR 2024 [성과와 관련된 이미지]

[한욱신 교수] 데이터베이스 질의 최적화를 위한 머신러닝 기반 질의 결과 개수 예측 방법

[연구의 필요성] 데이터베이스 질의 최적화는 사용자가 요청한 데이터베이스 질의를 사용자에 맡기지 않고 데이터베이스가 알아서 최적화를 진행해 수행하는 것으로, 질의를 수행할 수 있는 수많은 플랜(plan) 중 가장 빠를 것으로 예상되는 플랜을 선택한다. 이를 위해 각 플랜의 예상 시간을 미리 예측해야 하는데, 가장 빠른 것과 느린 것의 차이가 만 배 이상 나오기도 하므로, 매우 느린 플랜을 선택하지 않기 위해 정확한 예측이 필수적이다. 예상 시간을 예측할 때 가장 중요한 요인 중 하나는 질의 수행 결과의 크기 혹은 개수(cardinality)이므로, 이를 정확하게 예측하는 것이 매우 중요하며, 더 나아가 질의의 최종 결과 개수 뿐만 아니라 플랜이 생성하는 서브질의(subquery)들의 결과 개수들을 전부 예측해야 한다. 최근 머신러닝의 발전으로 데이터 분포를 학습해 예측에 사용하는 등, 예측의 정확도는 크게 향상되어 보다 빠른 플랜을 선택할 수 있게 되었으나, 예측 속도는 이전보다 크게 느려져, 결국 최적화와 수행에 걸리는 전체 시간(end-to-end execution time)은 크게 나아지지 않았다. 가장 최신의 연구 또한, 예측 속도를 높이기 위해 동적 프로그래밍(dynamicprogramming) 기법을 사용했는데, 예를 들어 테이블 A, B를 포함하는 서브질의 q1의 예측 결과 개수를, 테이블 A, B, C를 포함하는 서브질의 q2의 결과 개수를 예측할 때 재사용한다. 이때 문제는, q1의 테이블들의 데이터 분포와 q1에 없던 테이블 C의 데이터 분포가 독립적(independent)임을, 즉 서로 연관이 없음을 가정하는데, 이 비현실적인 가정 때문에 예측 정확도가 크게 낮아지기도 했다. 따라서, 예측 속도와 정확도를 둘 다 높일 수 있는 방법이 필요하였다. [포스텍이 가진 고유의 기술] 본 기술은 머신러닝과 동적 프로그래밍을 사용하면서도, 언급한 데이터 분포의 독립성을 가정하지 않고 정확하게 예측하는 방법을 제안한다. 먼저 머신러닝 모델 중 비지도학습 기반 자기회귀모델(autoregressive model)을 사용하여 질의에 포함된 각 테이블의 분포를 예측한다. 그 뒤 샘플링(sampling)에 기반하여 이 분포들을 독립성 가정 없이 합쳐, 여러 테이블을 포함하는 서브질의의 결과 개수를 정확하게 예측한다. 마지막으로 다차원 분포 합침(multi-dimensional statistics merging)은 샘플링과 동적 프로그래밍 기법을 융합하여 수천에서 수만 개의 서브질의에 대해 효율적으로 예측한다. [연구의 의미] 본 연구는 정확한 결과 개수 예측으로 데이터베이스 질의 최적화에 적용시 최적(optimal)에 가까운 플랜들을 선택하였고, 빠른 예측 속도로 최적화 시간을 효율적으로 유지하여, 이전 최신 연구보다 최대 300배 가까이 질의 수행 시간을 단축시켰다. [연구결과의 진행 상태 및 향후 계획] 본 연구는 데이터베이스 시스템 분야 최고 학술대회인 ACM SIGMOD 2024에 발표될 예정이다. 향후 더 크고 복잡한 질의에 대해서도 높은 예측 정확도와 빠른 예측 속도를 지원하는 방법을 개발하고자 한다. [성과와 관련된 실적] Kim, K. Lee, S., Kim, I., Han, W.-S. “ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation.” Proceedings of the ACM on Management of Data 2.1 (2024), pp. 45:1–45:27. (Corresponding author) [성과와 관련된 이미지]

[한욱신 교수] 데이터베이스 재생 시스템을 위한 고속 의존성 그래프 생성 방법 개발

[연구의 필요성] 데이터베이스 재생 시스템은 프로덕션 환경에서 데이터베이스 워크로드를 수집하고 테스트 환경에서 재생해, 소프트웨어 및 하드웨어 변경에 따른 성능 변화와 버그를 프로덕션 시스템에 영향 없이 검사한다. 데이터베이스 재생 시스템은 워크로드 내 각 요청(request)의 재생이 수집 시와 동일한 결과를 내도록 보장하기 위해 의존성 그래프(dependency graph)를 생성하는데, 이 그래프는 각 요청을 정점으로, 의존성이 있는 두 요청 간의 선후 관계를 간선으로 나타낸다. 그러나 기존의 방법은 각 요청마다 다른 요청들을 탐색하여 간선들을 생성하는데, 최악의 경우 워크로드 내 요청 수의 제곱에 비례하는 시간을 소모하여, 워크로드 수집에서 재생으로 이어지는 전체 과정에서 병목을 유발한다. 또한, 이렇게 생성되는 간선의 대다수는 중복 간선(redundant edge; 제거하더라도 다른 경로에 의해 선후 관계가 지켜지는 간선)이기 때문에, 워크로드 재생 전 이들을 제거하는 값비싼 전이적 축소(transitive reduction) 과정의 비용을 증가시킨다. 따라서 시간에 따라 변화하는 워크로드를 지속적으로 수집하고 신속하게 재생하여 테스트하기 위해서는, 중복 간선이 적은 간결한 의존성 그래프를 효율적으로 생성할 필요가 있다. [포스텍이 가진 고유의 기술] 본 기술은 단일 스캔과 메모이제이션(memoization)을 활용하여 간선을 생성하는 데 필요한 최소한의 정보만 메모 자료구조에 유지하고 이로부터 간결한 의존성 그래프를 효율적으로 생성한다. 먼저, 중복된 간선의 대부분을 차지하는 두 가지 중복 유형을 정의하고 분석하여, 이러한 중복을 갖지 않는 간선을 생성하는 데 필요한 최소한의 정보만을 메모 자료구조에 유지한다. 또한, 각 요청마다 다른 요청을 탐색하는 대신 단일 스캔으로 메모 자료구조로부터 간선을 생성하는 효율적인 알고리즘을 제안하여, 요청 수에 비례하는 시간 안에 간결한 의존성 그래프를 생성한다. [연구의 의미] 본 연구는 데이터베이스 재생 시스템의 의존성 그래프 생성 과정을 최대 100배 이상 가속하여, 수집에서 재생으로 이어지는 전체 과정에서의 병목을 제거하고 신속한 재생 결과 확인이 가능하도록 하였다. [연구결과의 진행 상태 및 향후 계획] 본 연구는 데이터베이스 시스템 분야 최고 학술대회인 ACM SIGMOD 2024에 발표될 예정이다. 향후 데이터베이스 재생 단계에서의 동시성 향상 방법을 연구하여, 초당 백만 단위의 트랜잭션을 초고속으로 처리하는 현대 학술용 데이터베이스 시스템에서도 데이터베이스 재생을 지원하고자 한다. [성과와 관련된 실적] 1. Lee, W., Ha, J., Han, W.-S., Park, C., Park, M., Han, J., and Lee, J. “DoppelGanger++: Towards Fast Dependency Graph Generation for Database Replay.” Proceedings of the ACM on Management of Data 2.1 (2024), pp. 67:1–67:26. (Corresponding author) [성과와 관련된 이미지]