Research Area
| NP-hard 그래프 문제들을 대규모 그래프에서 풀 수 있는 세계 최고 성능의 알고리즘들을 개발한다. 대표적인 NP-hard 그래프 문제로는 Subgraph isomorphism이 있다. Subgraph isomorphism은 데이터 그래프에서 쿼리 그래프와 동형(isomorphic)인 부분 그래프(subgraph)를 찾는 문제이다. - 대용량의 그래프 데이터에 대해서 subgraph isomorphism 문제를 푸는 세계 최고 성능의 알고리즘을 개발함 (Efficient subgraph matching: Harmonizing dynamic programming, adaptive matching order, and failing set together, SIGMOD 2019)
- 대용량의 그래프 데이터에 대해서 subgraph query processing 문제를 푸는 세계 최고 성능의 알고리즘을 개발함 (Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching, SIGMOD 2021)
|
| 정보를 표현하는 가장 간단하고 자연스러운 방법은 문자열(string)을 이용하는 것이다. 문자로 표현된 데이터를 정렬(sorting), 압축(compression) 및 검색(search)하는 문자열 알고리즘과 full-text index 등 문자열 자료구조에 대한 연구가 활발히 진행되고 있다. - Linear-time longest-common-prefix computation in suffix arrays and its applications, Annual Symposium on Combinatorial Pattern Matching, 2001, Google 인용지수 652
- 1000개 이상의 Human DNA를 효율적으로 저장하고 빠른 검색을 지원하는 자료구조를 제시함 (FM-index of alignment with gaps, Theoretical Computer Science 2018)
|
| 질량분석(mass spectrometry)은 단백질을 분해한 펩타이드를 질량분석기에 돌려서 나온 질량스펙트럼(mass spectrum) 데이터를 연구/분석하는 학문이다. 질량스펙트럼을 분석하여 단백질에 어떤 펩타이드가 존재하는지 확인할 수 있고, 질병 샘플과 정상 샘플 사이에 펩타이드의 양이 어떻게 변화하였는지 정량분석을 통해 알 수 있다. - 기존의 THRASH알고리즘보다 빠르고 정확한 질량스펙트럼에서의 펩타이드 단동위질량 결정알고리즘을 개발함. (Analytical Chemistry, 2008)
De novo 시퀀스 어셈블리 (De novo sequence assembly)는 레퍼런스 시퀀스 (reference sequence) 없이 주어진 DNA 시퀀스 조각들로부터 하나의 DNA 시퀀스를 재조립하는 작업이다. De novo 시퀀스 어셈블리 작업은 Overlap, Layout, Consensus 단계로 진행되는데 overlap 단계가 가장 많은 시간을 차지한다. 컴퓨터 이론 분야에서는 이 overlap 단계를 All-Pairs Suffix-Prefix 문제로 정의하고 많은 연구가 진행되어왔다. - All-pairs suffix-prefix 문제를 푸는 세계 최고 성능의 알고리즘을 개발함 (Algorithm engineering for all-pairs suffix-prefix matching, International Symposium on Experimental Algorithms, 2017)
|
| 인터넷 상에서 통신을 할 때, 기밀성 (비밀 유지), 무결성 (데이터 변조 방지), 인증 (통신상대 확인), 그리고 부인방지를 위해서 암호는 필수불가결한 요소이다. - High‐speed parallel implementations of the rainbow method based on perfect tables in a heterogeneous system, Software: Practice and Experience, 2015
- Fast batch modular exponentiation with common-multiplicand multiplication, Information Processing Letters, 2018
- Finding Highly Similar Regions of Genomic Sequences Through Homomorphic Encryption, Journal of Computational Biology, 2024
|
| 금융 분야에서 발생하는 여러가지 문제를 해결하는 알고리즘을 개발하고 실제 데이터에 대하여 성능을 실험한다. - CNN 모델을 활용한 미국 주식시장에서의 가치투자 분석, KCC 2021
|
Acheivements
Publication | - 컴퓨터이론 분야의 권위 있는 국제학술지 SIAM Journal on Computing, SIAM Journal on Discrete Mathematics, Theoretical Computer Science, Algorithmica, Journal of Parallel and Distributed Computing, Information and Computation 등에 다수의 논문 게재.
- 융합연구를 통해 SIGMOD, PVLDB, Analytical Chemistry, IEEE Transactions on Software Engineering, IEEE Transactions on Information Forensics and Security, Philosophical Transactions of the Royal Society A, Journal of Proteome Research 등에 다수의 논문 게재.
|
Collaboration | - 외국의 석학들과 공동 연구를 통해 다수의 논문 발표
- Algorithm 분야: Z. Galil, M. Crochemore, A. Apostolico, C.S. Iliopoulos, A. Amir, G.M. Landau, R. Giancarlo, M. Farach, G.H. Chen, O. Berkman, W.F. Smyth, W. Rytter, L. Gasieniec, R. Cole, S. Muthukrishnan, R. Hariharan, H. Arimura, S. Arikawa, R. Clifford, P. Eades, T. Tokuyama, T. Lecroq 등
- Cryptography 분야: M. Yung, M.K. Franklin 등
- 다른 분야와 융합연구를 통해 다수의 논문 발표
- 컴퓨터공학 내 다른 분야: 컴퓨터구조 및 시스템 (S.L. Min, Y. Cho 등), Database (W.S. Han, X. Lin 등), Network (Y. Choi, K. Nahrstedt 등), 회로 설계 (S. Ha 등)
- 다른 학문 분야: 수학 (J.H. Cheon), 화학 (S.W. Lee), 물리 (H. Jeong), 생명과학 (K.H. Cho, G. Jung, C. Lee 등), 의학 (J.S. Seo)
|
Development | - 웹 검색엔진 wispon을 개발하였고, 3억개의 웹문서를 crawl하여 2007년 10월부터 2009년 8월까지 일반에게 검색 서비스를 제공하였음. 최종적으로 외국기업 SAP에 매각하였고, 현재까지 SAP에서 consulting 수행 중.
- 질량분석(mass spectrometry) 분야에서 peptide의 질량을 빠르고 정확하게 찾아내는 프로그램 RAPID를 개발하였고, 이는 국내특허 및 미국특허 등록되었음. RAPID는 미국 Pacific Northwest National Laboratory, University of Illinois at Urbana-Champaign, 독일 Max Planck Institute 등에서 사용되고 있음.
|
