Semantic Web was proposed by Tim Berners Lee as an alternative to current Web. Keyword search ap-proaches for complex data such as relational database, XML, and graph data, have been spotlighted to stand for complex query languages. A keyword search approach in Semantic Web is defined as semantic search. Providing as results semantically relevant objects as well as objects containing the given query terms, semantic search is different from current document search and proposed to overcome the limitations of current document search. Observing the literatures of semantic search, it is composed of three phases: keyword matching, semantic expansion, and resource mapping. Keyword matching is a phase to collect an initial set for the following phases, retrieving the objects directly related to the keyword terms entered by users. Semantic expansion is a phase distinguishing semantic search from current document search, adding the semantically related objects to the initial set constructed in keyword matching phase. In resource mapping phase, the actual resources are returned to the user based on the result set of semantic expansion.
Relevance measuring methods, one approach of IR techniques, which scores relevance values between keyword terms and objects, are used to be exploited in keyword matching of semantic search. There are two main approaches to exploit IR techniques in keyword matching. The first approach is to merge all the texts linked to an object, searches through the merged texts, and returns the linked object. Though the approach is simple to exploit IR techniques in keyword matching, it returns unwanted results or ranks less relevant objects highly ignoring the semantics between texts and the linked object. The second previous approach for keyword matching searches texts independently without merging process, and returns the linked objects. Although the method preserves the semantics between a text and the linked object, the result does not include or ranks lowly the true objects even if other unmatched keyword terms are matched to other text which is linked to the same object. The two methods used previously have such limitations modeling relationships between texts and objects as one-to-one to exploit IR techniques directly. We propose a new keyword matching and define a relevance scoring function to support the method to be suitable to ontology. in order to evaluate the proposed keyword matching method, we conduct experiments with three public data sets, implemented the two previous keyword matching methods to compare with our approach in precision and recall. We suggest three hybrid methods to improve object oriented keyword matching, and showed the validity comparing ranked result sets with true set.
In the literatures of semantic search, many approaches are suggested enhancing semantic expansion process, and such existing semantic expansions are performed at the time the given query is processed. For efficient query process, we propose a full inverted index combining the two relevance functions, a relevance scoring function for keyword matching and a semantic relevance function for semantic expansion. Instead of using inverted index only for keyword matching, we include semantically relevant objects in the inverted index. Since the measures defined for keyword matching and for semantic expansion are different, a combined relevance function should be defined. We modeled a generalized combining mechanism to be able to use any other semantic expansion methods. Using the combined relevance function value as a measure, full inverted index are constructed for keyword matched and semantic expanded objects. Due to the inverted index structure, IR techniques are applicable to the constructed index such as top-k query processing. The cost of query processing is formalized based on the number of random disk accesses.
Since postings of the full inverted index include semantically relevant objects as well as objects con-taining the given keyword terms, lots of disk space to store the whole index are required for the proposed in-dex structure. There were many approaches to compress index encoding term dictionary and postings into short sequences of bits. We focused on the data stored in postings. Postings in index for ontology imply URI to reference the corresponding object in ontology data set. According to simple measurement for inverted index on ontology, we observed that over 66% of the size of index is used to store URIs. This shows that com-pressing URI methods help to reduce the size of inverted index for ontology. We propose a dictionary-based URI compression method utilizing prefix tree representations of URIs and Huffman coding. For index com-pression, criteria are defined as compression ratio and decompression speed. Measuring probability infor-mation in keyword matching phase, Huffman coding is suitable to exploit to URI compression. We imple-mented character-based Huffman coding, prefix-based Huffman coding to compare compression ratio and decompression time with our approach. The empirical results show that proposed dictionary-based method compresses URIs with high compression ratio and low decompression time.
Tim Berners Lee는 현재 웹을 보완하는 형태로 새로운 웹 표준인 시맨틱 웹(Semantic Web)을 제안하였다. 관계형 데이터베이스, XML, 그래프 데이터와 같이 복잡한 형태의 데이터에 대한 질의의 대안으로 키워드 검색이 주목 받고 있다. 특히, SQL와 같이 질의어 문법의 복잡성과 스키마에 대한 추가 정보의 필요성 등으로 인해 일반 사용자들에게 어려운 질의 방법으로 널리 알려졌다. 시맨틱 웹 환경에서의 키워드 검색인 시맨틱 검색(semantic search)은 질의어를 직접 포함하는 객체뿐만 아니라 간접적으로 연관도가 높은 객체들을 함께 검색해줌으로써 기존의 문서 검색 기법들이 가지는 한계를 극복하고자 한다. 현 시맨틱 검색 기법들을 살펴보면, 시맨틱 기법은 다음과 같이 세 단계로 구성된다. 바로 키워드 매칭(keyword matching), 시맨틱 확장(semantic expansion), 자원 대응(resource mapping)이 그 세 단계이다. 키워드 매칭은 질의어와 직접적으로 연관된 객체를 추출하여 시맨틱 검색의 다음 단계를 위한 초기 집합을 구성하는 단계이다. 시맨틱 확장은 시맨틱 검색이 기존의 문서 검색과 차별성을 가지는 단계로서, 키워드 매칭으로 구해진 초기 집합에 간접적으로 연관도가 높은 객체들을 포함시킴으로써 결과 집합을 확장하는 단계이다. 이와 같이 검색된 객체들은 자원 대응 단계를 통해 서비스, 데이터베이스 또는 문서 등과 같은 실제 자원으로 변환되어 사용자에게 검색 결과로 제공된다.
정보 검색(information retrieval) 분야에서 사용되는 기법 중 연관도 측정 기법들은 시맨틱 검색의 키워드 매칭에서 질의어와 객체 간의 연관도를 정의하는 부분에서 활용될 수 있다. 정보 검색 기법을 키워드 매칭에 활용한 기존의 키워드 매칭 기법에는 크게 두 가지 방법이 있다. 첫 번째 방법은 한 객체에 연결되어 있는 문자열들을 하나의 문자열로 병합하고 이에 대한 검색을 수행한 다음 연결된 객체를 반환하는 방법이다. 여러 개로 연결되어 있던 문자열들을 하나로 병합하였기 때문에 이에 대한 정보 검색 기법을 적용하기는 매우 용이해질 수 있으나, 온톨로지에 기술되어 있던 문자열과 객체 간의 의미 관계가 무시됨에 따라 키워드 매칭 결과에 사용자가 원하지 않는 객체를 포함하거나 연관도가 낮은 객체가 상위에 정렬되어 반환될 수 있는 문제점을 가진다. 또 다른 키워드 매칭 기법은 병합 과정 없이 각 문자열들을 독립적으로 검색한 다음 이와 연결된 객체들을 결과로 반환하는 방법이다. 비록 문자열과 객체 간의 의미 관계를 유지하고는 있지만, 만일 입력된 질의어가 각기 다른 문자열에 매칭되었을 경우 같은 객체에 연결되어 있을지라도 부분적으로만 매칭된 결과로 반환된다. 이와 같이 한계를 가지는 키워드 매칭 기법을 기존에 활용한 이유는 정보 검색 기법을 손쉽게 적용할 수 있도록 문자열과 객체의 관계를 1:1 대응 관계로 변환함에 따라 의미 정보가 손실되었기 때문이다. 본 연구에서는 앞선 두 방법의 단점을 보완하고 장점을 합친 새로운 키워드 매칭 기법을 제안하고, 제안된 매칭 기법을 지원하는 연관도 함수를 정의한다. 제안된 키워드 매칭 기법의 효용성을 평가하기 위해, 널리 사용되는 세 개의 데이터 집합에 대한 비교 실험을 수행하였다. 비교 대상으로는 앞선 두 방법을 선택하였고, 비교 값으로는 정확도(precision)와 재현율(recall)을 선정하여 측정하였다.
시맨틱 검색 분야에서 시맨틱 확장에 초점을 둔 연구들이 많이 등장하였고, 대부분의 기법들이 질의가 처리되는 시간에 수행됨에 따라 질의 처리 속도를 낮추고 있다. 효율적인 질의 처리를 위해 본 연구에서는 키워드 매칭에서의 연관도 함수와 시맨틱 확장에서의 연관도 함수를 하나의 연관도 함수로 결합하여 구축되는 전체 역방향 인덱스를 정의한다. 역방향 인덱스를 키워드 매칭에만 사용하는 대신에 시맨틱 확장된 결과로 검색된 객체들도 역방향 인덱스에 포함시키는 방법이다. 이 때, 키워드 매칭에서 정의된 연관도 함수와 시맨틱 확장을 위해 정의된 연관도 함수가 다르게 정의되어 있기 때문에 이를 결합하여 하나의 연관도 함수를 정의하는 과정이 필요하다. 본 연구에서는 기존에 연구된 다양한 시맨틱 확장들 모두 활용될 수 있도록 일반화된 결합 방법론을 제안한다. 이와 같이 결합된 하나의 연관도 함수 값들을 바탕으로 키워드 매칭과 시맨틱 확장 두 단계를 위한 전체 역방향 인덱스가 구축된다. 중요한 점은, 제안된 역방향 인덱스가 top-k 질의 처리와 같은 기존의 정보 검색 기법들을 그대로 적용할 수 있는 역방향 인덱스 형태를 가진다는 점이다. 질의 처리를 위한 비용은 무작위 디스크 접근 횟수를 정형화함으로써 평가하였다.
전체 역방향 인덱스의 포스팅(posting)들이 질의어를 포함한 객체들뿐만 아니라 간접적인 연관도가 있는 객체들도 인덱싱해줌에 따라, 제안된 인덱스 구조를 저장하기 위한 디스크 용량이 매우 커지게 된다. 인덱스의 용어들이나 포스팅 자체를 보다 짧은 값으로 대체함으로써 이니덱스를 압축하는 많은 방법들이 제안되어 왔다. 본 연구에서는 포스팅 내에 저장된 데이터에 초점을 두었다. 온톨로지에 대한 역방향 인덱스의 포스팅에는 온톨로지의 객체를 참조하기 위해 항상 URI를 저장해야만 한다. 간단한 측정 실험을 통해 온톨로지에 대한 역방향 인덱스 내에서 URI가 차지하는 용량이 66%를 넘는다는 것을 확인하였다. 이와 같이 큰 부분을 차지하고 있는 URI를 압축할 수 있다면 인덱스의 전체 용량도 크게 줄일 수 있게 된다. 본 연구에서는 URI들간에 공유되는 어두들을 바탕으로 어두 트리(prefix tree)를 생성하고 이를 Huffman coding하는 사전 기반 URI 압축 기법을 제안한다. 인덱스 압축의 경우에는 압축률과 압축 해제 속도가 중요한 평가 기준이 된다. 다시 말하면, 인덱스를 생성할 때 공유되는 어두들의 빈도를 측정하는 비용은 크게 중요하지 않게 되는 것이다. 따라서 본 연구에서는 Huffman coding을 기본 압축 기법으로 선택하였다. 비교 실험을 위해 글자 기반 Huffman coding과 어두 기반 Huffman coding도 함께 구현하여 압축률과 압축 해제 시간을 측정하였다. 실험 결과는 본 연구에서 제안하는 사전 기반 방식의 Huffman coding이 URI 압축에 높은 성능을 보여줌을 말해준다.
