News

  • Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching – SIGMOD 2021에 논문 게재
    박근수 교수 연구진의 부분그래프 쿼리 프로세싱 (subgraph query processing) 및 부분그래프 매칭 (subgraph matching) 알고리즘에 관한 최신 연구 논문이 SIGMOD 2021에 게재되었다. SIGMOD는 데이터베이스와 빅데이터 분야에서 세계 최고로 인정받고 있는 학회이다. 본 논문은 소셜 네트워크 등에서 특정한 패턴을 찾아내는 알고리즘을 제시한 것으로서 현재까지 알려진 알고리즘 중에서 가장 빠른 성능을 보인다. 논문에서 제안한 알고리즘은 benchmark그래프들에서 이전 […]
  • Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming – VLDB 2021에 논문 게재
    박근수 교수 연구진이 세계 최고 성능의 continuous subgraph matching 알고리즘 기술을 개발하였다. Continuous subgraph matching 문제는 데이터 그래프가 변화할 때 마다 쿼리 그래프와 동형이면서 새로 생기거나 삭제되는 데이터 그래프의 부분 그래프를 찾아내는 알고리즘으로 사이버 보안, 사기 탐지, 소셜 네트워크 서비스 등에서 이용된다. 논문에서 제안한 알고리즘은 benchmark 그래프 데이터에서 이전 최신 알고리즘보다 수백 배 빠르게 문제를 […]
  • Fast algorithms for single and multiple pattern Cartesian tree matching – Theoretical Computer Science에 논문 게재
    본 논문에서는 generalized matching 문제 중 하나인 Cartesian tree matching 문제를 빠르게 해결하는 알고리즘을 제시하였다. 주어진 pattern과 text를 0과 1로 이루어진 binary 문자열로 바꿔 기존의 string matching을 사용하여 matching이 일어날 수 있는 위치를 찾는 binary filtration과 각 위치가 답이 되는 지 효율적으로 확인할 수 있는 verification technique을 통해 기존 알고리즘보다 평균 38배의 성능향상을 달성할 수 […]
  • 박근수 교수 연구진, 그래프 동형 문제에 대한 세계 최고 성능 알고리즘 기술 개발
    박근수 교수 연구진이 세계 최고 성능의 그래프 동형(Graph Isomorphism) 알고리즘 기술을 개발하였다. 그래프 동형 문제는 두 개의 그래프가 동형인지 판별하는 문제로 소셜 네트워크 서비스, 생물정보학, 화학정보학 등 다양한 응용 분야에서 그래프 분석을 위해 다루고 있는 핵심 문제이다. Garey & Johnson은 1979년에 NP-complete에 속하는지 혹은 P에 속하는지 알려지지 않은 12개의 미해결 문제를 소개하였는데, 그중에서 그래프 동형 […]
  • Finding patterns and periods in Cartesian tree matching – Theoretical Computer Science에 논문 게재
    본 논문은 Cartesian tree를 이용한 generalized matching 문제를 제시하였으며, 이는 기존에 있던 order-preserving matching 등의 다른 generalized matching 문제로는 찾기 어려운 종류의 패턴을 찾는 새로운 가능성을 제시하였다. Cartesian tree matching과 그에 연관된 다양한 문제들을 효율적으로 해결하는 방법을 제시하였다는 점에서, 본 논문을 확장하여 다양한 연구를 수행할 수 있는 기반을 마련하였다. 또한 본 논문은 Cartesian tree matching […]
  • 박근수 교수 연구진, 빅데이터 그래프 검색 기술 개발
    박근수 교수 연구진이 개발한 슈퍼그래프 검색 기술은 화합물 등의 그래프 데이터를 인덱싱하고 특정한 패턴에 포함되는 그래프들을 찾아내는 알고리즘을 제시한 것으로서, 현재까지 알려진 알고리즘 중에서 가장 빠른 성능을 보인다. 논문에서 제안한 알고리즘은 benchmark 그래프들을 이전 최신 알고리즘들보다 최대 수십 배 빠르게 인덱싱하며 최대 수천 배 빠르게 패턴에 포함되는 그래프들을 찾아낸다. 또한 크기가 큰 패턴에서도 대량의 그래프 […]
  • Fast String Matching for DNA Sequences – Theoretical Computer Science에 논문 게재
    본 논문에서는 문자열 매칭 문제에서 최고 성능을 보이는 알고리즘을 제시하였다. 평균 shift 길이가 최대로 되도록 하는 pattern scan order를 사용한 MAS 알고리즘은 BM-family 알고리즘 중 scan speed와 실행 시간 측면에서 가장 좋았으며 MAS 알고리즘을 확장한 TMAS, QMAS 알고리즘은 state-of-the-art의 성능을 달성하였다. https://www.sciencedirect.com/science/article/pii/S0304397519305821 이 기술은 과학기술정보통신부 재원으로 정보통신기획평가원의 지원을 받아 SW컴퓨팅산업원천기술개발사업 SW스타랩 과제로 개발한 연구성과 결과물이다.
  • 서울대 컴퓨터공학부 박근수 교수 연구진, SIGMOD 2019에 논문 게재
    박근수 교수 연구진의 부분그래프 매칭 (subgraph matching) 알고리즘에 관한 최신 연구 논문이 SIGMOD 2019에 게재되었다. SIGMOD는 데이터베이스와 빅데이터 분야에서 세계 최고로 인정받고 있는 학회이다. 본 논문은 소셜 네트워크 등에서 특정한 패턴을 찾아내는 알고리즘을 제시한 것으로서 현재까지 알려진 알고리즘 중에서 가장 빠른 성능을 보인다. 논문에서 제안한 알고리즘은 benchmark 그래프들에서 이전 최고 성능 알고리즘보다 최대 10,000배 빠르게 […]