대규모 그래프 데이터에 대한 키워드 검색에서 다양한 결과를 구하는 효율적인 방법 = Efficient Method for Finding Diverse Results in Keyword Search on Large Graph Data

국문 초록 (Abstract)

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

다국어 초록 (Multilingual Abstract)

Recently, as graph-structured data is exploited in various fields such as Knowledge Graph, social networks, and biomedicine, needs for a keyword search method have been increasing to find relevant and diverse results on a large-scale graph data. In this paper, we propose an effective method which can find a set of answer sub-trees that are relevant to the query as well as diverse satisfying a given similarity constraint. We provide a search algorithm that selects result trees with high query relevance and low similarity with other ones based on the ratio of query relevance to similarity and calculating the average similarity by weighting the query relevance of other trees. We also present an enhanced algorithm that recalculates the relevance-similarity ratio in the process of selecting result trees. We show by experiments that the proposed algorithm can efficiently find diverse results with query relevance of over 90% of the optimal solution and the execution time is improved by over 86% compared to the existing algorithm. It is expected that the our method can increase user’s satisfaction by providing diverse and relevant results much more efficiently than the existing method.

참고문헌 (Reference)

1 박창섭, "콘텐트 노드의 유사성 제어를 통한 그래프구조 데이터 검색의 다양성 향상" 20 (20): 18-30, 2020

2 A. Dass, "Trading off popularity for diversity in the results sets of keyword queries on linked data" 151-170, 2017

3 W. Le, "Scalable keyword search on large RDF data" 26 (26): 2774-2788, 2014

4 J. Yang, "Keyword search on large graphs : a survey" 6 : 142-162, 2021

5 K. Golenberg, "Keyword proximity search in complex data graphs" 927-940, 2008

6 B. Ding, "Finding top-k min-cost connected trees in databases" 836-845, 2007

7 C. Liu, "Finding smallest k-Compact tree set for keyword queries on graphs using map-reduce" 19 (19): 499-518, 2016

8 C. S. Park, "Efficient keyword search on graph data for finding diverse and relevant answers" 19 (19): 19-41, 2023

9 M. Kargar, "Efficient duplication free and minimal keyword search in graphs" 26 (26): 1657-1669, 2014

10 C. S. Park, "Effective keyword search on graph data using limited root redundancy of answer trees" 14 (14): 299-316, 2018

11 M. Zhong, "Coverage-oriented diversification of keyword search results on graphs" 166-183, 2018

12 H. He, "BLINKS : ranked keyword searches on graphs" 305-316, 2007