Keyword search is receiving a lot of attention not only in Web contexts but also in the database area. It is an easy way to allow inexperienced user to query systems without the need of knowing any specific language or how data is structured. As a matter of fact, the amount of data available, in the Web as well as in other systems, is constantly increasing. And, with the improvements and the simplification of the technology, the amount of people accessing such information is growing too. Providing simple, yet effective tools that allow inexperienced users to quickly discover desired information is a big challenge in modern times. The prevalent approaches build on dedicated indexing techniques as well as search algorithms aiming at finding substructures that connect the data elements matching the keywords. In this paper, we introduce a novel keyword search paradigm for graph-structured data, focusing in particular on the RDF data model. While related techniques search the best answer trees, we propose a novel algorithm for the exploration and computation of all matching subgraphs.
Keyword-based search approaches have the huge benefit that users can ignore both the language and the structure of the data they are going to query. A keyword based search engine returns a list of candidate pages, documents or set of data that match keywords provided in input. Then a user has to dedicate her time and efforts navigating each result returned from the engine in order to discover the desired information, i.e. the answer she is looking for. Figure 1 illustrates the actual scenario of the Web. In a simple scenario the user’s desired answer is contained in a single document or set of data. In a slightly more complex scenario such an answer may not be confined to a single document: it may reside on a logical connection between concepts in different documents. A user has to explore the returned results in order to discover the connection, and then the data, she is looking for. In general, the user has to face two issues: the number of results to explore and the distance between the results containing the concepts holding the desired connection. The first issue can be mitigated by submitting a more selective query. However, it’s unlikely the case that not expert users are able to submit a complex query with an high selectivity. The second issue is rather hard to address.
Therefore, attention around searching and query processing of graph-structured
data continue to increase as the Web, XML documents and even relational
database can be represented as a graph. In particular many efforts focus on
RDF data querying, given the great momentum of Semantic Web in which Web
pages carry information that can be read and understood by machines in a
systematic way. Current approaches rely on a combination of IR and tree/graph
exploration techniques whose goal is to rank results according to a relevance
criterion. Keyword search on tree-structured data counts a good number of
approaches already [
In this paper, we propose a novel approach to keyword search in the graphstructure data in an RDF representation. The approach aims to provide effective answers in an efficient way. The main contribution of this paper relies in how connections between identified parts of the structure containing keywords of interest are combined together. We assume here that annotations in the graph are generated out of a specific ontology domain. That means that data are instances of concepts belonging to a knowledge base schema. Therefore, the idea is to aggregate the parts of the data structures containing keywords in clusters, according to their schemas, i.e. temporarily ignoring instance values. If two instances come from a common schema then they share a template. Then the parts in each cluster, and the clusters too, are ranked according to a function, taking into account both structural and contextual features. Finally parts from the several clusters are composed, when possible, starting with the most relevant one in the most relevant cluster. As a result, most relevant solutions emerge early in the process because the approach tries to compose the best candidates from each cluster first. Moreover, the clustering technique allows avoiding the combination (exploration) of overlapping solutions.
The paper is organized as follows: Section 2 introduces the preliminaries of the problem and the data structures used. Section 3 describes the query processing in details. Finally Section 4 presents the related works, and Section 5 sketches conclusions and future works. 2
Problem Definition. Formally, the problem we are trying to solve may be
defined as follows. Similar to [
For instance W1-Works-CIV is an informative path ptk. We use the notation posptk (ri) (posptk (pj)) to indicate the position of the resource ri(pj) into the vector ptk. For example posptk (W 1) returns 1. We compute the informative paths from root nodes because they allow to reach any node in the graph. In case a root node is not present, a fictitious one can be added. Having the information to navigate from the roots to nodes matching keywords is at the basis of our approach to solutions discovery. Then we call template the schema associated to an informative path.
Definition 2 (Template) Given an informative path pt, we associate a template t to pt replacing each ri ∈ pt with the wild card # For instance the template associated to ptk is #-Works-#. Then we introduce two basic notions as follows. Definition 3 (Subsumption) Given two informative paths pt1 and pt2, we say that pt1 is subsumed by pt2, denoted by pt1 C pt2, if ∀ri, pj ∈ pt1 then ∃rm, pn ∈ pt2 such that ri = rm and pj = pn, and pospt1 (ri) = pospt2 (rm) and pospt1 (pj) = pospt2 (pn) Definition 4 (Graft) Given two informative paths pt1 and pt2, there is a graft between pt1 and pt2, denoted by pt1 ↔ pt2, if ∃ri ∈ pt1(pt2) such that ri ∈ pt2(pt1) An Architecture of Reference. A flexible architecture of the system was design, as shown in Figure 3. It serves as a logical view of how the system looks like. This is a typical use scenario of the system: 1. The RDF Parser takes as input a collection of RDF Documents and parses them into triples. Here we use the Jena framework (http://jena.sourceforge. net/); 2. The Indexer builds an index on top of the triple collections to achieve structural information useful for the query process. Here the indexing is supported by Lucene (http://lucene.apache.org/) and WordNet (http:// wordnet.princeton.edu) to allow query expansion; 3. A user performs a query through a GUI helper, handling events and the query itself; 4. The parsed query is given to the Searcher for processing; 5. The Searcher processes the query over the Indexed Resource Base and returns the search result to the caller. It communicates with the Indexer to extract the instances matching input keywords, group them into clusters and compose elements from clusters into the final solutions (i.e. subgraph structures). Each structure (i.e. instance, cluster and solution) are ordered by a ranking function. Here we adopt the exhaustivity of the result as scoring function that is the number of matched keywords with respect to the number of submitted keywords. Although a ranking function is a relevant aspect in the framework, in this paper we focus on the composition of the solutions. The approach is composed of two main phases: an off-line one where documents of interest are indexed in order to have immediate access to nodes (steps 1 and 2), and an on-line one where the query evaluation takes place (steps 3 to 5). In the next section we illustrate the query processing. 3
The approach is composed of two main phases: the off-line indexing where documents of interest are indexed in order to have immediate access to nodes, and the keyword processing (on-the-fly) where the query evaluation takes place. Off-line indexing During this phase, an index structure is built and incrementally updated while documents of interest are loaded or modified. Here the indexing is supported by Lucene (http://lucene.apache.org/) with WordNet (http://wordnet.princeton.edu) for query expansion. With the indexing the information in the graph is augmented by: identifying root nodes in the graph and storing in each node the paths to reach such node from the roots. Each path is computed by implementing the breadth-first search (BFS) algorithm. Although this process could be expensive, let us remark that: (i) it is an incremental process, so its cost dramatically reduces once the system is loaded, and (ii) the index drastically speeds up the on-the-fly query evaluation. We don’t have to navigate the graph at runtime and we have immediate access to the path root-matching node that is the basis for our clustering and combining techniques. Keywords processing. Given a keyword the index structure allows immediate access to the node with such a keyword. Lucene index returns all the informative paths from roots to the nodes matching one of the specified keywords. So we result a list of informative paths ordered by the length. Referring to our example we obtain the following list: c) [RM3-Composition-Bag-rdf:li-DIA-type-Department] d) [RM3-Composition-Bag-rdf:li-AI-type-Department] e) [RM3-Composition-Bag-rdf:li-MEC-type-Department] f) [LaSap-Composition-Bag-rdf:li-CIV-type-Department] z) [LaSap-Composition-Bag-rdf:li-CIV] g) [W1-Works-CIV-type-Department] a) [RM3-type-University] b) [LaSap-type-University] y) [W1-Works-CIV] For instance y) is subsumed by g) and there is a graft between them in nodes W 1 and CIV . Now the goal is to “extract” the schema behind the paths so that we can cluster paths according to the discovered schema(s). A cluster is represented by a template t. So it is a set of informative paths that share the same template t. Such templates are the attempt of identifying and giving values to a structure in the information graph that is not explicitly provided with the query. Such a structure is a recurrent pattern in an anonymous path that we refer to as schema. Therefore given the list of informative paths P T , the set of clusters CL is computed in the following way while P T is not empty, we extract pt from P T .
• if ∃CLi ∈ CL such that we can associate the representative template t of CLi to pt, then ∗ if @pt0 ∈ CLi such that pt C pt0 then insert pt into CLi. We order the elements of CLi with respect to the exhaustivity. • else a new cluster CLj with the representative template associated to pt is built and we insert pt into CLj , CLj into CL.
In this process we need to order both paths and clusters with respect to a scoring
function. So we define the rank of an element (path or cluster) with respect to
the query Q = k1, k2, . . . , kn as
R(e, Q) = Pk∈Q weight(k, Q) · weight(k, e) ; weight(k, e) = wweeiigghhttcsttxr((kk,,ee))
where weight(k, Q) is the weight associated with each keyword k with respect to
the query Q and where weight(k, e) is the weight associated with each keyword
k and e where is a path, when ranking paths, or a cluster, when ranking clusters.
We assume all the keywords in the input query have the same weight, i.e. from
the user point of view all the keywords have the same relevance. The weight
weight(k, e) is the ratio between the contextual and the structural weights of
k when considering e. When ranking paths the structural weight represents a
measure of the proximity of k with the other keywords whereas the contextual
weight represents the relevance of k with respect to the other keywords, according
to the following:
weightstr(k, pt) = Pki∈pt,ki6=k dpt(k,ki) ; weightctx(k, pt) = (11+−lsn)+(1s+· lanv(gt(fd)l)) · (1 + ln( dfN+1 ))
dl dl
In the first formula, pt is a path, dpt(k, ki) is the distance between two keywords
and dl is the number of terms in the path pt. In the second formula, tf is the
number of times the keyword k occurs in the path pt, df is the number of paths
where k occurs, N is the number of path containings at least one of the input
keywords; dl has the same meaning as in the first formula and avg(dl) is the
mean of all the dl; finally, s is a constant, usually 0.2 [
Ppt∈CL weightstr (k,pt) ; weightctx(k, CL) = |CL|
Ppt∈CL weightctx(k,pt) |CL| In the following the resulting ordered clusters set computed respect to the reference example.
CL3: [#-Works-#-type-#] { (g) } CL2: [#-Composition-#-rdf:li-#-type-#] { (f) , (c,d,e) } CL1: [#-type-#] { (a,b) } The final step is combining the paths from different clusters. A solution is a set of informative paths that present a graft in pairs. So computing a solution an informative path pt can be included into a solution S if ∃pt0 ∈ S such that pt and pt0 present a graft. Paths in clusters are combined, when possible, starting from the most relevant path in the most relevant cluster: we combine the best candidate paths of each cluster to compose a single solution. Including an informative path into a solution, we delete it from the starting cluster. Therefore the solutions generation ends when the set CL is empty. Because of the ranking on both the clusters and the paths in each cluster, solutions will come out from the process starting with the most relevant one, then descending to the least relevant. This allows for optimizations like: cutting the answering process if relevance decrease under a specific threshold, or returning the user with an initial set of answers she can start exploring while elaboration of remaining ones is still undergoing. More important, the clustering and the combining techniques guarantee the combination of paths only for instance data belonging to different schemas, thus avoiding overlapping. Overlapping is undesired and time consuming. At the end we result the following solutions (also depicted in Figure 4) over the reference example: S1: { (g) , (f) } and S2: { (c,d,e) , (a,b) }.
There is a broad literature on information search. Natural language interfaces to
database systems have been investigated in several works. Approaches
addressing relational database systems are: BANKS [
We presented a full-text search index for ontology triples that provides matching capabilities based on semantic and morphological expansion of terms used for indexing the triple. Given a set of text matches, we propose a method to construct the set of answer paths by a template based clustering technique. In this paper the paths retrieved by the system are ordered with respect to a trivial measurement, that is the exhaustivity. Hence, it could potentially lead to information overload. Semantic association ranking metrics could be used to present only paths most relevant to users context. Future works concern a sophisticated ranking function, and using it a set of experimental results over (very) large datasets. DBpedia, Yago are recent efforts to generate semantic metadata by extracting structured information form the Web (Wikipedia). A keyword or natural language search interface to such knowledge bases would prove immensely useful as the end user need not be aware of the structure of the information. It will be worthwhile to build a search interface that accepts queries in natural language.