Adopting keyword query interface to semantic search on RDF data can help users keep away from learning the SPARQL query syntax and understanding the complex and fast evolving data schema. The existing approaches are divided into two categories: instance-based approaches and schema-based approaches. The instance-based approaches relying on the original RDF graph can generate precise answers but take a long processing time. In contrast, the schema-based approaches relying on the reduced summary graph require much less processing time but cannot always generate correct answers. In this paper, we propose a novel approach based on a hybrid graph which can achieve signi cant improvements on processing time with a limited accuracy drop compared with instance-based approaches, and meanwhile, can achieve promising accuracy gains at an a ordable time cost compared with schema-based approaches.
Introduction
On the way to Semantic Web, Resource Description Framework (RDF) is a
language for representing information about resources in the World Wide Web.
The ever growing semantic data in RDF format provides fertile soil for semantic
search, and formal query languages (e.g. SPARQL) are adopted by most current
semantic search systems[
In XML and database communities, bridging the gap between keyword queries
and formal queries has been widely studied. However, there exists a limited
amount of work on how to answer keyword queries on semantic data in RDF
format. As an early attempt to build a semantic search system, SemSearch [
In this paper, we propose a novel e ective and e cient keyword query interpretation approach based on a hybrid graph carefully constructed from the original RDF graph. A hybrid graph is much smaller than the original RDF graph, and meanwhile it can preserve as much connectivity information as possible. In this way, we construct the hybrid graph under the guidance of a graph score which re ects the best tradeo between e ectiveness and e ciency of keyword query interpretation. 2
The Hybrid Graph based Approach
The construction of hybrid graph is an iterative process which extracts and re nes a quali ed subgraph from the original RDF graph by means of a graph score. The graph score is used to de ne the overall interpretation performance, which plays an important role from the starting point to the ending point of each interaction in the whole construction process. More precisely, the graph score is the linear combination of the size of the hybrid graph and the amount of the connectivity information contained in the graph. The work ow of a hybrid graph construction is illustrated in Figure 2(a) which takes the original RDF graph as input. A construction unit (CU) is employed to carry out the re nement on the given RDF graph to generate a quali ed hybrid subgraph. The CUs are additionally used several times for further re nement on the remaining unquali ed RDF subgraphs. Finally, several quali ed hybrid subgraphs are returned, and combined together to form an overall hybrid graph.
… … CU
… …
We compare our approach with instance-based approches and schema-based counterparts on three di erent datasets (i.e., semanticweb.org, DBpedia, DBLP) in terms of processing time and interpretation accuracy. Table 1 lists The statistics of the three data sets. We manually construct 42 scenarios (17 from semanticweb.org, 10 from DBpedia, and 5 from DBLP) for the comparison.
Data set ]Category ]Instance ]Relation ]Inst.degree ]Rel.kind ]Rel/kind semanticweb.org 5:06 102 7:483 103 1:628 104
DBLP 1:0 101 1:640 106 3:176 106 DBpedia 2:694 105 2:520 106 6:868 106 0.20 0.00
1.00 0.88 0.53
1.00 0.93 0.40 0.33 SemanticWeb DBLP Data set
27 26 SemanticWeb
973 803 13 DBLP Data set