In the Semantic Web, the types of resources on the Web and the semantic relationships between resources are defined in an ontology. By using those information, the accuracy and the efficiency of the Web search can be improved. In this dissertation, we focus on the effective semantic search using the ontology.
The goal of the semantic search is to retrieve $\It{top-k}$ resources which are the most relevant to query keywords through semantic relationships in the ontology. To do this, we first propose an effective ranking method for the semantic search. We first devise a measure to determine the weight of the semantic relationship. Based on this measure, we devise a novel relevance scoring function to be used for ranking resources. The novel relevance scoring function considers the number of meaningful semantic relationship paths connecting the resource with keywords, the coverage of keywords related to the resource, and the distinguishable power of keywords related to the resource. Moreover, in order to improve the efficiency of the search, we prune the unnecessary search space using thresholds based on the length and the weight of the semantic relationship path.
For a huge number of resources, it is impractical to compute the relevance scores for all the resources and extract the most relevant $\It{k}$ resources which have the highest relevance scores in a reasonable time. Therefore, we propose an efficient $\It{top-k}$ query processing technique based on a more accurate score estimation. In order to efficiently and accurately estimate the upper bound score of a resource, we devise a bloom filter embedded-index structure called the index filter built on a partitioned input list. Then, we adapt TA-style $\It{top-k}$ query processing algorithms by employing the index filter, so that non-answer candidates are pruned as rapidly as possible. Consequently, the performance of $\It{top-k}$ query processing is considerably improved while preserving the correctness of the top-k answer. Furthermore, we devise a novel non-uniform partitioning method for input lists in order to more accurately estimate upper bound scores.
Additionally, in order to retrieve the relevant resources distributed in multiple ontologies, we propose an efficient distributed ontology query processing method. We first suggest extended models of the distributed ontology query and the semantic mapping among multiple ontologies to support query processing in more general environments. Our distributed ontology query processing approach logically integrates multiple ontologies through the query rewriting based on the semantic mapping. As a result, we can effectively extract an integrated answer of a distributed ontology query over multiple ontologies. Also, we present several query optimization techniques considering the characteristics of the multiple distributed ontology environment.
Finally, through the experimental evaluation, we observe the accuracy and the efficiency of the our semantic search techniques including the relevance scoring function, the technique to reduce the search space, the adapted TA-$\It{style top-k }$ query processing algorithms using the index filter, the novel non-uniform partitioning method for input lists, and the distributed ontology query processing techniques.
시맨틱 웹에서 웹 리소스의 타입과 리소스들간의 시맨틱 연관관계는 온톨로지 상에 정의되며, 이와같은 온톨로지 정보를 활용하여 검색의 정확도와 효율성을 향상시킬 수 있다. 본 학위논문에서는 온톨로지를 활용한 효과적인 시맨틱 검색 기법을 소개한다.
시맨틱 검색의 목적은 온톨로지 상에서 시맨틱 연관 관계를 통해 질의 키워드들과 밀접한 관련을 맺고 있는 상위 k개의 리소스를 찾는 것이다. 이를 위해, 본 논문에서는 시맨틱 검색을 위한 효과적인 랭킹 기법을 제안한다. 우선 시맨틱 연관 관계의 가중치를 결정하는 기법을 제시하고, 질의에 대한 리소스의 관련 정도를 결정하는데 사용될 연관도 산정 함수 (relevance scoring function) 를 소개한다. 제안하는 연관도 산정 함수는 대상 리소스와 질의 키워드들사이에 존재하는 의미있는 시맨틱 연관 관계의 수, 리소스와 연관된 질의 키워드의 수, 리소스와 연관된 질의 키워드의 중요도를 반영한다. 또한, 검색의 효율성을 향상시키기 위해 시맨틱 연관 관계의 길이 및 가중치 기반 임계값 (threshold) 을 이용한 검색 범위 축소 기법을 제안한다.
검색 대상이 되는 리소스가 매우 많은 경우, 적당한 시간내에 질의와 관련된 모든 후보 리소스들의 연관도를 산정하고, 그 중에서 연관도 (relevance score) 가 가장 높은 상위 k개 의 리소스를 추출하는 것은 현실적으로 불가능하다. 따라서, 본 논문에서는 보다 정확한 연관도 예측을 통한 효율적인 $\It{top-k}$ 질의 처리 기법을 제안한다. 우선 검색 대상에 대한 연관도를 정확하고 효율적으로 예측하기 위해, 분할된 입력 리소스 리스트에 구축되며 bloom filter를 내장하는 인덱스 구조인 index filter를 소개한다. 또한, 고안된 index filter을 활용 할 수 있도록 TA 기반 $\It{top-k}$질의 처리 알고리즘들을 수정한다. 수정된 알고리즘들은 top-k 질의 처리시 최종 질의 결과에 포함되지 못하는 리소스들을 효과적으로 보다 빨리 제거하여 정확한 $\It{top-k}$ 결과를 제공함과 동시에 $\It{top-k}$ 질의 처리 시간을 크게 감소시킨다. 더불어, 보다 정밀하게 연관도를 예측하기 위한 불균등 입력 리스트 분할 기법을 제안한다.
추가적으로, 본 논문에서는 여러 온톨로지에 분산되어 있는 리소스들을 검색하기 위한 효율적인 분산 온톨로지 질의 처리 기법을 제안한다. 우선, 일반적인 분산 온톨로지 환경에서의 질의 처리를 지원하기 위해, 확장된 온톨로지 질의 모델 및 시맨틱 매핑 모델을 제안한다. 본 논문에서 제안하는 분산 온톨로지 질의 처리 기법은 시맨틱 매핑에 기반한 질의 재생성 (query rewriting) 을 통해 여러 분산된 온톨로지를 논리적으로 통합함으로써 여러 온톨로지에 대한 질의를 효과적으로 처리한다. 또한, 다중 분산 온톨로지 환경의 특성을 고려한 질의 처리 최적화 기법을 소개한다.
마지막으로, 본 논문에서 제안하는 연관도 산정 함수, 검색 범위 축소 기법, index filter를 활용한 TA 기반 $\It{top-k}$ 질의 처리 기법, 비균등 입력 리스트 분할 기법, 분산 온톨로지 질의 처리 기법의 정확성과 효율성에 대한 실험 검증 결과를 보인다.
