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 Construction of Two-Dimensional Suffix Trees, 2011, Algorithmica, SCI
    Two-Dimensional suffix-tree를 O(n) 시간에 구성.
  • 한글에 대한 편집 거리 문제, 2010, 정보과학회 논문지
    한글 문자열에 대한 편집거리에 대한 정의와 알고리즘
Data Structures
Ds intro.png

  • 간결한 자료 구조 (Succinct data structures) : 빠른 처리 속도를 가지면서 최적에 가까운 크기의 공간에 자료를 저장함으로서 현대 사회에서 정보량의 빠른 증가에 대처할 수 있는 자료 구조를 디자인 한다.
  • 외부 메모리를 위한 자료 구조 : 자료의 크기 문제로 인해 주기억장치에 이들을 다 저장할 수 없는 경우 이 자료들은 자기디스크나 광디스크, 플래시 메모리와 같은 보조 저장 장치에 저장되어야 하며 이들은 주 기억 장치들에 비해 속도가 매우 느리다. 이와 같은 보조 기억 장치들을 위한 자료 구조를 디자인 하는 것이 새로운 연구 분야로 떠오르고 있다.

 

 

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

  • 악의적인 공격에도 견딜 수 있는 안전한 시스템 디자인
    임계암호시스템 (Threshold Cryptosystem) 에 대한 “공평함”의 개념을 정의함과 동시에 다양한 스킴을 제안함 (Int. J. Applied Cryptography, 2010)
  • 빠른 암호 알고리즘 디자인 및 구현
    NTRU 암호시스템의 암호화와 복호화의 속도 향상 (ACNS, 2007)

 

Bioinformatics
Bio intro.png질량분석(mass spectrometry)은 단백질을 분해한 펩타이드를 질량분석기에 돌려서 나온 질량스펙트럼(mass spectrum) 데이터를 연구/분석하는 학문이다. 질량스펙트럼을 분석하여 단백질에 어떤 펩타이드가 존재하는지 확인할 수 있고, 질병 샘플과 정상 샘플 사이에 펩타이드의 양이 어떻게 변화하였는지 정량분석을 통해 알 수 있다.

  • 질량스펙트럼에서의 펩타이드 단동위질량 결정알고리즘 개발
    기존의 THRASH알고리즘보다 빠르고 정확. (Analytical Chemistry, 2008)
  • duplex & triplex mTRAQ 실험에서의 정량분석 알고리즘
    기존의 XPRESS알고리즘보다 정확. (JPR, 2010; APBC, 2011)

 

Search Engines
width=250검색엔진은 인터넷을 대상으로 웹페이지, 문서, 이미지 등의 다양한 정보를 수집하여 검색해주는 시스템이다. 검색엔진의 크롤러(crawler)는 웹의 링크를 따라가며 정보를 수집하는 프로그램이며, 인덱서(indexer)는 수집된 정보의 단어 목록을 만드는 프로그램이다. 그 외 사용자 인터페이스와 쿼리 서버 등으로 구성되어 있다.

  • 실제 웹 검색엔진인 위스폰을 개발하여 일반에게 서비스를 제공함
  • 효율적인 웹 크롤링 알고리즘 개발
  • 웹 페이지의 중요도에 따른 랭킹 알고리즘 연구
  • 효율적인 “Soft Error”를 감지하는 알고리즘 개발

 

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