디지털 라이브러리[ 검색결과 ]
다각적 Top-k 부분 그래프 질의를 위한 효율적인 알고리즘
http://doi.org/10.5626/JOK.2024.51.2.103
부분 그래프 매칭은 그래프 분석에서 핵심적이고 중요한 문제로서 데이터 그래프에서 쿼리 그래프의 모든 임베딩을 찾는 문제이다. 그러나 이전에 제시된 알고리즘에서 출력한 결과들은 서로 간의 겹치는 부분이 많아 흥미로운 결과를 놓치는 경우가 많다. 이를 위해 다각적 top-k 부분 그래프 매칭 문제가 제시되었다. 다각적 top-k 부분 그래프 매칭 문제는 쿼리 그래프의 임베딩들 중 커버리지가 가장 높게 되는 k개의 임베딩을 찾는 문제이다. 본 논문에서는 해당 문제에 대한 알고리즘을 제시하고 기존 알고리즘과 비교하여 다각적인 top-k 결과를 효율적으로 찾는다는 것을 입증하였다.
부분 그래프 매칭 문제를 위한 새로운 동적 매칭 순서와 성능 비교
http://doi.org/10.5626/JOK.2022.49.1.1
최근 다양한 분야에서 그래프 분석이 사용되고 있다. 그래프 분석에서 가장 핵심적인 문제 중 하나는 부분 그래프 매칭(subgraph matching) 문제이다. 부분 그래프 매칭 문제는 데이터 그래프와 쿼리그래프가 주어졌을 때 데이터 그래프에서 쿼리 그래프의 모든 임베딩(embedding)을 찾는 문제이다. 그동안 이 문제를 해결하는 백트래킹 기반의 많은 알고리즘이 연구되어왔다. 본 논문에서는 이 문제를 해결하는 최신 알고리즘인 DAF에서 제안한 동적 매칭 순서의 문제점을 분석하고 이를 개선한 동적 매칭 순서를 소개한다. 또한, 제안한 매칭 순서를 실제 데이터 그래프를 가지고 실험을 진행하여 가지치기 기법을 사용하지 않았거나 가지치기 기법을 사용하더라도 수행 시간이 매우 짧지 않으면 이전 매칭 순서들보다 효과적임을 입증하였다.
이분 매칭 기반의 가지치기를 활용한 부분 그래프 동형 알고리즘 성능 향상
http://doi.org/10.5626/JOK.2021.48.9.973
대형 그래프에 대한 분석은 최근 다양한 분야에서 점차 중요해지고 있다. 그래프 분석에서 가장 핵심적인 문제 중 하나로 부분 그래프 동형(subgraph isomorphism) 문제가 있다. 부분 그래프 동형 문제란 데이터 그래프와 쿼리 그래프가 주어졌을 때, 데이터 그래프에서 쿼리 그래프의 임베딩이 존재하는지 확인하는 문제이다. 부분 그래프 동형 문제를 해결하는 많은 알고리즘이 제시되어왔지만 여전히 특정 입력에서는 답을 찾기 위해 알고리즘이 동작하는 시간이 긴 경우가 있어서 실제 문제에 적용이 어려운 경우가 있다. 본 논문에서는 실행 시간을 획기적으로 줄일 수 있는 이분 매칭 알고리즘을 활용한 가지치기 기법을 소개하고 실제 그래프 데이터상에서 실험을 진행하여 제시한 기법이 문제를 효율적으로 해결하는 데 도움이 되는 방법임을 입증했다.
De novo 시퀀스 어셈블리의 overlap 단계의 최근 연구 실험 분석
http://doi.org/10.5626/JOK.2018.45.3.200
여러 DNA 리드 시퀀스가 주어졌을 때, de novo 시퀀스 어셈블리는 레퍼런스 시퀀스 없이 하나의 시퀀스를 재조립한다. 재조립을 위해 de novo 시퀀스 어셈블리는 리드 사이의 모든 겹침을 계산하는 overlap 단계가 필요하다. Overlap 단계는 전체 연산 중 비용이 가장 많이 들기 때문에 어셈블리의 계산성능을 좌우한다. 여러 분야에서 overlap 단계를 위한 연구가 많이 발표되고 있는데, 그 중 가장 최신의 세 연구 결과는 Readjoiner, SOF, Lim-Park 알고리즘이다. 최근 염기 분석기술의 큰 발전으로 DNA 리드 데이터 셋을 기존보다 저비용으로 대량 생산하는 것이 가능해져 DNA 리드 데이터 셋을 생성하는 여러 플랫폼들이 개발되었다. 각 플랫폼마다 생성하는 데이터 셋의 통계적 특성이 다르기 때문에 overlap 단계의 성능 평가 시 다양한 통계적 특성의 데이터 셋이 반영되어야 한다. 본 논문은 여러 통계적 특성을 가진 DNA 리드 데이터 셋을 이용하여 위의 세 알고리즘의 성능을 비교 분석한다.
X-means 클러스터링을 이용한 악성 트래픽 탐지 방법
한명지, 임지혁, 최준용, 김현준, 서정주, 유철, 김성렬, 박근수
악성 트래픽은 디도스 공격, 봇넷 통신 등의 인터넷 망을 교란시키거나 특정 네트워크, 서버, 혹은 호스트에 피해를 끼칠 의도를 가지고 발생시키는 트래픽을 지칭한다. 이와 같은 악성 트래픽은 인터넷이 발생한 이래 꾸준히 양과 질에서 진화하고 있고 이에 대한 대응 연구도 계속되고 있다. 이 논문에서는 악성 트래픽을 기존 X-means 클러스터링 알고리즘을 적용하여 효과적으로 탐지하는 방법을 제시하였다. 특히 악성 트래픽의 통계적 특징을 분석하고 클러스터링을 위한 메트릭을 정의하는 방법을 체계적으로 제시하였다. 또한 두 개의 공개된 트래픽 데이터에 대한 실험을 통해 실효성을 검증하였다.
