Tottering 현상을 방지하는 개선된 Random Walk 그래프 탐색 기법에 대한 연구
A Study on the Advanced Random Walk Graph Search Technique to Prevent Tottering Phenomena
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
그래프 편집 거리는 데이터 정보 손실이 적으며, 유연성이 높아 그래프 구조 유사도 검사 시 널리 사용된다. 그러나 그래프 편집 거리는 NP-Hard 문제에 속하므로 그래프의 노드 혹은 엣지가 많은 복잡한 그래프에대해 효율성이 크게 저하된다. 이와 같은 문제를 해결하기 위해 다양한 휴리스틱 알고리즘을 연구됐고, 그 중Random Walk 기법은 구현이 쉽고, 높은 유연성으로 인해 널리 사용되고 있다. 그러나 Random Walk 기법은중복 방문 현상인 Tottering 현상이 발생해 효율성이 저하된다. 이를 해결하고자 다양한 연구가 수행되었으나해당 방식들 또한 Tottering 현상이 최소 1회 이상 발생하는 한계점이 존재한다. 본 논문에선 이러한 문제를해결하기 위해 Tottering 현상이 발생하기 전 Tottering 검사를 수행하는 개선된 k-Walk 그래프 탐색 기법을제안한다. 본 제안방식은 Tottering 현상이 발생하기 이전에 Tottering 현상을 탐지함으로써 Tottering 현상발생을 원천적으로 차단할 수 있다. 이를 그래프 구조 기반 소스코드 유사도 검사에 활용 시 보다 효율적인유사도 검사가 가능하다.
Abstract
The graph edit distance algorithm is widely used for structural similarity detection due to its flexibility and minimal information loss, but its computational inefficiency on large, complex graphs—stemming from its NP-Hard nature—has led to the development of various heuristic, including the Random Walk approach, which, despite its advantages, suffers from the Tottering phenomenon that degrades efficiency; although prior methods attempt to address this, they fail to eliminate Tottering entirely, prompting this paper's proposal of a novel Random Walk technique that proactively detects and prevents Tottering before it occurs. This enables more efficient similarity checks when applied to graph structure based source code similarity detection.