• >
  • 스타랩과제
  • >    컴퓨터이론 및 응용 연구실
컴퓨터이론 및 응용 연구실
NP-hard 그래프 문제를 위한 실용적인 알고리즘 프레임워크
서울대학교 / 총괄 책임자 : 박근수 / http://theory.snu.ac.kr
과제 소개
본 연구는 NP-hard 그래프 문제들을 대규모 그래프에서 풀 수 있는 세계 최고 성능의 알고리즘들을 개발하고, 이를 기반으로 NP-hard 그래프 문제들에 특화된 공개 SW 프레임워크를 개발한다. 주요 성능지표인 알고리즘 수행시간에 있어서 현존 최고 성능의 알고리즘 대비 개선율 100% 이상을 달성한다. 이를 통해 국제 산업계와 학계를 선도하는 기술을 확보하고, NP-hard 그래프 문제에 대한 연구 및 응용 SW 개발의 오픈 생태계를 구축한다.
인사말
컴퓨터이론은 컴퓨터공학의 기초학문으로서 효율적인 알고리즘 개발, NP-complete 개념, 현대 암호학 이론 등으로 컴퓨터공학 발전에 근본적인 기여를 하여 왔다. Turing Award를 받은 다수의 컴퓨터이론 학자들이 이러한 사실을 잘 보여주고 있다. 본 연구실은 컴퓨터이론 및 응용에 대해 연구하는 곳으로 구체적으로 스트링 알고리즘, 암호학, bioinformatics, 그래프 알고리즘, 금융공학 등에 대해 연구하고 있다.
연락처
전화 : 02-880-1828
메일주소 : kpark@theory.snu.ac.kr
찾아오는길
주소: 151-742 서울특별시 관악구 관악로 1 서울대학교 301동 414호, 452-1호
교통편
- 서울대입구역 3번출구-> 5511,5513 버스 -> 제2공학관
- 낙성대역 4번출구 -> 관악 02 버스 -> 제2공학관
총괄책임자
서울대학교 / 총괄책임자 : 박근수 / http://theory.snu.ac.kr
박근수 교수는 서울대학교 컴퓨터공학부에 재직 중 이며, 컴퓨터 이론 및 응용 연구실을 이끌고 있다. 주요 연구 분야는 컴퓨터 이론 및 알고리즘, 생물정보학, 암호학 등 이며, SW스타랩을 통해 subgraph isomorphism 같은 NP-hard 그래프 문제를 위한 실용적인 알고리즘을 개발하고 있다. 박근수 교수는 미국 Columbia 대학교에서 컴퓨터 이론으로 박사학위를 받았고, 영국 런던대학교 King’s College 조교수를 역임하였다. 또한, 호주 Curtin 대학교 방문연구원, 프랑스 Marne-la-Vallee 대학교 방문교수를 역임하였다. STOC, FOCS, SODA, SIAM Journal on Computing, Algorithmica 등 컴퓨터 이론 분야의 top-tier 학술대회 및 저널에 논문을 발표하였고, 금융감독원, 경찰청, 서울지검 등에 자문을 수행하였다.
구성원
성명 직위 연구담당분야 이메일
류철 석박사통합과정 오픈 생태계 구성 rcheol@theory.snu.ac.kr
김현준 석박사통합과정 그래프 알고리즘연구 hjkim@theory.snu.ac.kr
구건모 석박사통합과정 소프트웨어 및 툴 개발 gmgu@theory.snu.ac.kr
민승환 석박사통합과정 그래프 알고리즘연구 shmin@theory.snu.ac.kr
이선호 석박사통합과정 그래프 알고리즘연구 shlee2@theory.snu.ac.kr
Magsarjav Bataa 박사과정 오픈 생태계 구성 magsarjav@theory.snu.ac.kr
홍선기 석사과정 그래프 알고리즘 연구 sghong@theory.snu.ac.kr
송시우 석박사통합과정 소프트웨어 및 툴 개발 swsong@theory.snu.ac.kr
김현우 석사과정 소프트웨어 및 툴 개발 hwkim@theory.snu.ac.kr
박성관 석사과정 오픈 생태계 구성 sgpark@theory.snu.ac.kr
최윤영 석박사통합과정 소프트웨어 및 툴 개발 yychoi@theory.snu.ac.kr
남예현 학사과정 소프트웨어 및 툴 개발 lameinthebox@snu.ac.kr
박범수 학사과정 그래프 알고리즘 연구 zigui_@naver.com
연구목표
NP-hard 그래프 문제들을 대규모 그래프에서 풀 수 있는 세계 최고 성능의 알고리즘들을 개발하고, 이를 기반으로 NP-hard 그래프 문제들에 특화된 공개 SW 프레임워크를 개발한다. 주요 성능지표인 알고리즘 수행시간에 있어서 현존 최고 성능의 알고리즘 대비 개선율 100% 이상을 달성한다. 이를 통해 국제 산업계와 학계를 선도하는 기술을 확보하고, NP-hard 그래프 문제에 대한 연구 및 응용 SW 개발의 오픈 생태계를 구축한다.
연구내용
본 과제에서 개발하는 “NP-hard 그래프 문제를 위한 알고리즘 프레임워크”는 자료구조/툴, 그래프 알고리즘, 응용 SW의 세 층으로 구성된다.
(1) 대규모 그래프 처리를 위한 자료구조 및 그래프 생성/변환/분석 툴을 개발하고
(2) 중요 NP-hard 그래프 문제들(subgraph isomorphism, supergraph search, graph homomorphism, diversified top-k subgraph querying, graph similarity search)에 대하여 세계 최고 성능의 알고리즘을 개발하고
(3) 이를 기반으로 소셜 네트워크 분석 SW, protein-protein interaction 네트워크 분석 SW, RDF 쿼리 처리 SW, 화합물 검색 SW를 개발한다.
개발된 소스코드 및 라이브러리를 순차적으로 공개하여 NP-hard 그래프 문제를 위한 오픈 생태계를 형성한다.
연구성과
구분 논문 수 비고
국제 최상위 학술대회 1 국제 최상위 학술대회 SIGMOD 1편 (Efficient Subgraph Matching, 2019)
국외학술대회 1 CPM 2019 1편
국내학술지 1 Journal of Computing Science and Engineering 1편
협력성과
해외 연구진들과 상호 방문하여 공동연구를 진행하고 활발한 교류를 통하여 의미 있는 연구결과를 발표한다.
- 이스라엘: Amihood Amir, Gad M. Landau 두 교수님과 Cartesian tree matching and indexing에 관한 공동연구를 진행하여 연구결과를 국외학술대회(CPM 2019)에 논문으로 출판하였다.
- 프랑스: Thierry Lecroq 교수님과 fast string matching for DNA sequences에 관한 공동연구를 진행하여 연구결과를 SCI급 국제학술지(Theoretical Computer Science)에 제출하였다.
졸업생 취업현황
사업년도 이름 학위 취업 기관명
2018 이정문 석사 수아랩
2018 안용주 석사 삼성전자
개발성과
SW 등록 1건 (그래프 통계 분석 툴
공개SW기술
Efficient Subgraph Matching: 부분 그래프 동형 문제(subgraph matching, subgraph isomorphism)는 소셜 네트워크 분석, 단백질-단백질 상호작용 분석, 자원기술프레임워크 쿼리 처리, 화합물 검색 등 빅데이터 분석을 위해 풀어야 하는 문제이다. 본 연구진은 부분 그래프 동형 문제를 해결하는 전세계적으로 가장 빠른 알고리즘 DAF를 개발하고, 연구한 내용을 논문으로 작성하여 Computer Science 분야 국제 최상위 학술대회인 SIGMOD에 출판하였다.
공개SW내용 및 커뮤니티 사이트
번호 저장소 이름 설명 저장소 주소
1 Graph Analysis Tool 그래프 통계 분석 툴 https://github.com/SNUCSE-CTA/graph-analysis-tool
2 Fast APSP A fast algorithm for the all-pairs suffix-prefix problem https://github.com/SNUCSE-CTA/FastAPSP
23 Improved scan order Improved Pattern-Scan-Order Algorithms for String Matching http://theory.snu.ac.kr/?p=1218
4 MOPM Fast Multiple Order-Preserving Matching Algorithms http://theory.snu.ac.kr/?p=1264
공개 SW 현황
Algorithm Engineering for All-Pairs Suffix-Prefix Matching
All-pairs suffix-prefix matching은 DNA sequence assembly에서 가장 시간이 많이 소요되는 부분에 대한 문제이다. 이 연구에서는 all-pairs suffix-prefix matching을 기존에 존재하는 알고리즘들보다 현실적으로 빠르게 푸는 알고리즘을 개발하여 오픈소스로 공개하였다.
Improved Pattern-Scan-Order Algorithms for String Matching
이 연구에서는 패턴 스캔 순서를 이용하여 string matching 문제를 빠르게 풀 수 있는 알고리즘들을 개발하여 오픈소스로 공개하였다.
Fast Multiple Order-Preserving Matching Algorithms
텍스트 T와 패턴 P가 주어졌을 때 order-preserving problem은 T에 있는 substring 중에 P와 상대적 순서가 같은 것을 모두 찾는 문제이다. 이 연구에서는 패턴이 여러 개 주어지는 경우인 multiple order-preserving matching problem을 빠르게 푸는 알고리즘들을 개발하고 오픈소스로 공개하였다.
과제 연구 홍보 사이트
Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together, SIGMOD 2019