콘텐트 노드의 유사성 제어를 통한 그래프 구조 데이터 검색의 다양성 향상

국문 초록 (Abstract)

최근 소셜 네트워크, 시맨틱 웹 등 여러 분야에서 그래프 구조 데이터가 널리 사용됨에 따라 대량의 그래프데이터에 대한 효과적이고 효율적인 검색 방법의 필요성이 커지고 있다. 기존 키워드 기반 검색 방법들은 대부분 주어진 질의에 대한 연관도만을 고려하여 결과를 구한다. 그러나 이런 방법은 질의 연관도는 높지만 콘텐트 노드들을 공유하는 유사한 결과들이 함께 선택될 가능성이 높다. 이런 문제점을 개선하기 위해 본 논문에서는 키워드 질의에 대한 답 트리에 포함된 콘텐트 노드들의 유사성을 제어하여 콘텐트 노드가 다양한 답 트리들을 구하는 top-k 검색 방법을 제안한다. 다양한 답 트리 집합의 기준을 정의하고, 다양한 top-k 결과 집합을 구하기 위한 두 가지 방법으로 점진적 나열 알고리즘과 A* 탐색 기법을 이용한 휴리스틱 탐색 알고리즘을 설계한다. 또 휴리스틱 탐색의 성능을 높이기 위한 개선 방법을 제시한다. 실 데이터를 이용한 성능 실험 결과를 통해, 본 논문에서 제안한 휴리스틱 탐색 방법이 질의 연관성뿐만 아니라 콘텐트 노드들의 상이도가 높은 다양한 답 트리들을 효율적으로 구할 수 있음을 보인다.

다국어 초록 (Multilingual Abstract)

Recently, as graph-structured data is widely used in various fields such as social networks and semantic Webs, needs for an effective and efficient search on a large amount of graph data have been increasing. Previous keyword-based search methods often find results by considering only the relevance to a given query. However, they are likely to produce semantically similar results by selecting answers which have high query relevance but share the same content nodes. To improve the diversity of search results, we propose a top-k search method that finds a set of subtrees which are not only relevant but also diverse in terms of the content nodes by controlling their similarity. We define a criterion for a set of diverse answer trees and design two kinds of diversified top-k search algorithms which are based on incremental enumeration and A* heuristic search, respectively. We also suggest an improvement on the A* search algorithm to enhance its performance. We show by experiments using real data sets that the proposed heuristic search method can find relevant answers with diverse content nodes efficiently.

목차 (Table of Contents)

• 요약
• Abstract
• I. 서론
• II. 관련 연구
• III. 다양화된 Top-k 검색
• IV. 질의 처리 방법
• V. 성능 평가
• VI. 결론
• 참고문헌

참고문헌 (Reference)

1 박창섭, "그래프 데이터에 대한 비 - 중복적 키워드 검색 방법" 한국콘텐츠학회 16 (16): 205-214, 2016

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 "SPARQL Query Language for RDF"

5 C. S. Park, "Reducing redundancy in keyword query processing on graph databases" 34 (34): 551-574, 2018

6 L. Qin, "Querying communities in relational databases" 724-735, 2009

7 M. Kargar, "Keyword search in graphs : finding r-cliques" 4 : 681-692, 2011

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

9 C. N. Ziegler, "Improving recommendation lists through topic diversification" 22-32, 2005

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

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

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

13 A. Angel, "Efficient diversity-aware search" 781-792, 2011

14 G. Capannini, "Efficient diversification of web search results" 4 : 451-459, 2011

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

16 D. Rafiei, "Diversifying web search results" 781-790,

17 "Cypher Query Language"

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

19 V. Kacholia, "Bidirectional expansion for keyword search on graph databases" 505-516, 2005

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