Computer Theory and Application Laboratory

Research

Achievements

Publication
  • 컴퓨터이론 분야의 권위 있는 국제학술지 SIAM Journal on Computing, SIAM Journal on Discrete Mathematics, Theoretical Computer Science, Algorithmica, Journal of Parallel and Distributed Computing, Information and Computation 등에 다수의 논문 게재.
  • 융합연구를 통해 저명 학술지 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 (S.K. Cha 등), 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)

 

Developement
  • 웹 검색엔진 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 등에서 사용되고 있음.

 

Research Area

String Algorithms
String intro 2.png정보를 표현하는 가장 간단하고 자연스러운 방법은 문자열(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 인용지수 491
  • 한글에 대한 편집 거리 문제, 정보과학회 논문지, 2010
    한글 문자열에 대한 편집거리에 대한 정의와 알고리즘

 

Cryptography
Crypto intro.png인터넷 상에서 통신을 할 때, 기밀성 (비밀 유지), 무결성 (데이터 변조 방지), 인증 (통신상대 확인), 그리고 부인방지를 위해서 암호는 필수불가결한 요소이다.

  • 악의적인 공격에도 견딜 수 있는 안전한 시스템 디자인
    임계암호시스템 (Threshold Cryptosystem) 에 대한 “공평함”의 개념을 정의함과 동시에 다양한 스킴을 제안함 (Int. J. Applied Cryptography, 2010)
  • High‐speed parallel implementations of the rainbow method based on perfect tables in a heterogeneous system, Software: Practice and Experience, 2015

 

Bioinformatics
Bio intro.png질량분석(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 문제로 정의하고 많은 연구가 진행되어왔다.

  • Algorithm Engineering for All-Pairs Suffix-Prefix Matching, International Symposium on Experimental Algorithms, 2017
    All-pairs suffix-prefix 문제를 빠르게 해결하는 알고리즘 개발

 

Graph Algorithms
대용량의 그래프 데이터에 대해서 subgraph isomorphism 문제를 푸는 알고리즘을 개발한다.

 

Financial Engineering
금융 분야에서 발생하는 여러가지 문제를 해결하는 알고리즘을 개발하고 실제 데이터에 대하여 알고리즘의 성능을 실험한다.