Efficient Method for Finding Diverse Results in Keyword Search on Large Graph Data

최근 지식 그래프, 사회 연결망, 생물의학 등 여러 응용 분야에서 그래프 구조를 갖는 데이터가 활용됨에 따라 대규모 그래프 데이터에 대한 키워드 질의에 대해 효과적이고 다양한 결과를 검색할 수 있는 방법의 필요성이 증가하고 있다. 본 논문에서는 질의 연관성이 높고 주어진 유사도 제약을 만족하는 다양한 답 트리 집합을 효율적으로 찾을 수 있는 방법을 제안한다. 답 트리의 질의 연관도와 유사도의 비율을 이용해서 결과 트리들을 선택하는 방법과, 다른 트리들의 연관도를 가중 평균해서 유사도를 계산하는 방법을 통해 질의 연관성이 높으면서 서로 유사도가 낮은 결과들의 집합을 구하는 알고리즘을 제시한다. 또 각 반복 단계에서 연관도-유사도 비율을 현 상태에 적합하게 재계산함으로써 질의 연관도가 더 높은 결과 집합을 구할 수 있는 개선된 방법을 제안한다. 실제 그래프 데이터를 이용한 성능 실험을 통해 제안한 방법이 질의 연관도가 최적 해 대비 90% 이상인 효과적인 검색 결과를 생성하고, 검색 실행 시간은 기존 방법보다 86% 이상 향상됨을 보인다. 제안한 방법은 기존 방법보다 훨씬 효율적으로 다양하고 연관도 높은 결과를 제공함으로써 사용자의 검색 만족도를 높일 수 있을 것으로 기대된다.