Recently, SPARQL became the standard language for querying RDF data on the Web. Like other formal query languages, it applies a Boolean-match semantics, i.e. results adhere strictly to the query. Thus, queries formulated for one dataset can not easily be reused for querying other datasets. If another target dataset is to be queried, the queries need to be rewritten using the vocabulary of the target dataset, while preserving the captured information need. This is a tedious manual task, which requires the knowledge of the target vocabulary and often relies on computational expensive techniques, such as mapping, data consolidation or reasoning methods. Given the scale as well as the dynamics of Web datasets, even automatic rewriting is often infeasible. In this paper, we elaborate on a novel approach, which allows to reuse existing SPARQL queries adhering to one dataset to search for entities in other dataset, which are neither linked nor otherwise integrated beforehand. We use the results returned by the given seed query, to construct an entity relevance model (ERM), which captures the content and the structure of relevant results. Candidate entities from the target dataset are obtained using existing keyword search techniques and subsequently ranked according to their similarity to the ERM. During this ranking task, we compute mappings between the structure of the ERM and of the candidates onthe- y. The e ectiveness of this approach is shown in experiments using large-scale datasets and compared to a keyword search baseline.
Publishing structured data on the Web according to the Linked Data
principles has been advocated by the Linked Data movement and the Semantic Web
community and recently also receives an increasing support from companies
like Yahoo!, Google, and Facebook, and also from governmental institutions.
The amount of Linked Data on the Web increases rapidly and is now in the
order of several billion RDF triples. In order to query these structured data
e ectively, SPARQL an expressive, formal query language has been developed,
which became the standard as recommended by the W3C in 2008 [
In this paper, we elaborate on a novel approach, which allows to search for entities in a target dataset immediately without any prior integration using a star-shaped SPARQL query adhering to the vocabulary of another dataset. This approach combines the exibility of unstructured information retrieval solutions with nature of database-style querying by incorporating the structure of the underlying data. The idea is to start with a structured seed query speci ed for one particular data source. Based on the content as well as the structure of results obtained from this data source, we construct an Entity Relevance Model (ERM) that can be seen as an abstract representation of relevant results. Instead of relying on mappings for rewriting the structured seed query, we simply treat the seed query as a keyword query and submit it against other data sources to obtain additional results. Then, we create mappings between the structure of candidate results and the structure of the ERM during runtime, which are used for the subsequent matching and ranking. Candidates matching more closely to the content as well as the structure captured by the ERM are ranked higher. This way, we can use unstructured keywords for querying, but at the same time, incorporate structure information into matching and ranking that are part of the search process.
We investigate the e ectiveness of our approach in experiments using DBpedia as the source dataset and an RDF representation of IMdb as target dataset. Our approach is not limited to these datasets, but general enough to be applied to any datasets. However, the scenario involving DBpedia illustrates also an important use case, because DBpedia as the nucleus of the Web of data is probably the best known dataset and many users already have SPARQL queries or know how to create such queries for DBpedia. In addition many applications are build on top of DBpedia, which will also bene t, if the underlying retrieval incorporates entities from other datasets on-the- y.
Contributions. The contributions of this work can be summarized as
follows: (1) We propose a novel approach for searching Web data sources that
does not rely on upfront data integration, but uses an Entity Relevance Model
(ERM) for searching as well as for computing mappings on-the- y in line with
the pay-as-you-go data integration [
Outline. Section 2 de nes the research problem and gives an overview and brie y sketches our new approach. This approach of relevance based on-the- y mappings is presented in detail in Section 3. Evaluation results are presented in Section 4. Section 5 discussed the related work before we conclude in Section 6. 2
In this section we de ne the setting of the addressed problem, present existing solutions, and brie y sketch the framework we propose to deal with this problem. 2.1
Data on the Web The problem we address is situated in a Web data scenario. Therefore, the kind of Web data that is of most interest is RDF data. For reasons of simplicity and generality, we employ a generic graph-based data model that omits speci c RDF features such as blank nodes. In this model, entity nodes are RDF resources, literal nodes correspond to RDF literals, attributes are RDF properties, and edges stand for RDF triples.
Data Graph. The data graph is a directed and labeled graph G = (N; E). The set of nodes N is a disjoint union of entities NE and literals NL, i.e. N = NE ] NL. Edges E can be conceived as a disjoint union E = EE ] EL of edges representing connections between entities, i.e. a(e1; e2) 2 EE , i e1; e2 2 NE , and connections between entities and literals, i.e. a(e1; v) 2 EL, i e1 2 NE and v 2 NL. Given this graph structure, we de ne the set of edges including the targeted nodes A(e) = fa(e; ) 2 Eg as the description of the entity e 2 NE , and each member a(e; ) 2 A(e) is called an attribute of e. Thus, we in fact neglect the distinction between EE and EL and simply refer to all edges as attributes. The set of distinct attribute labels of an entity e, i.e. A0(e) = faja 2 A(e)g, is called the model of e. 2.2
Research Problem
Given this model of Web data, structured queries can be speci ed to search over
such datasets. The most commonly used language for querying RDF data on
the Web is SPARQL [
One particular form of BGP with high importance are so-called entity queries.
Essentially, they are star-shaped queries with the node in the center of the star
representing the entity (entities) to be retrieved. Figure 3 provides several
examples. According to a recent Web query logs study performed by Yahoo!
researchers, this type of queries is most common on the Web [
Problem. The problem is nding relevant entities in a set of target datasets Dt given a source dataset Ds and an entity query qs adhering to the vocabulary of Ds. Clearly, if there are no syntactical di erences at the level of schema and data as discussed above, then qs can directly be used to retrieve information from Dt. However, given Web data are heterogeneous in that sense, the following two strategies can be applied.
Baseline KW. The rst and most widespread solution to this end is to use keyword search over so called `bag-of-words' representations of entities. That is, the description of an entity is simply a set of terms. A query is also a set of terms, which is then matched against the at term-based representation of data. This unstructured approach bridges di erences at the level of schemas and data simply by ignoring the ne-grained semantics and structure available in the entity descriptions, as illustrated in Fig. 1. Clearly, this approach is simple but also exible in the sense that the same keyword query speci ed for Ds can also be used for Dt because results from Dt can be obtained when there are matches at the level of terms.
director rainer werner fassbinder released 1982 type film (2)
Our approach. In this paper, we present a framework to address this problem of searching for entities in Web data using on-the- y mappings computed in a pay-as-you-go fashion based on entity relevance models (ERM). This framework is instantiated involving the following three steps. (1) First, we compute an ERM from the results returned from the source dataset Ds using qs. (2) Second, we present a light-weight on-the- y integration technique, which maps the structure of result candidates of the target datasets Dt to the structure of the ERM. (3) Finally, the result candidates are ranked according to their similarity to the ERM using the mappings computing during runtime. (1) 3
In this section, we present how the entity relevance model is constructed and discuss how this model can be exploited for ranking and relevance-based on-they data integration. 3.1
Entity Relevance Model
We aim to build a model that captures the structure and content of entities
relevant to the information need, which is expressed in the seed entity query qs.
This proposed model is called the Entity Relevance Model (ERM). The model
is based on the notion of structured relevance model that has been proposed
before [
The ERM is a composite model that consists of several, atomic language
models[
ERM ajs (w) =
P e2Rs P e2Rs
Pv2ajs n(w; v)
P v2ajs jvj where n(w; v) denotes the number of occurrences of word w in the content value v of attribute ajs and jvj the length of v. Note that the outer sum goes over the entities e 2 Rs returned by qs and the inner sum goes over all values v of attributes with labels ajs. Thus, entity descriptions, which do not have the attribute j ajs, do not contribute to ERM as (w). In order to capture the importance of the atomic attribute-speci c models, we de ne the probability of occurrence P (ajs) for every ERM ajs (w)) as P (ajs) = n(ajs; e1:::m)=m, where the numerator denotes s the number of entities having attributes with label ajs and m = jRsj is the total number of entity results. In summary, an ERM has n elds, each corresponds to an attribute with a speci c label, has a corresponding language model, which has a probability of occurrence. An example for an ERM constructed from two entities is illustrated in Fig. 2. (2) ERM as P (as) w : ERMas (w) label 1 world:0.2, on:0.2, wires:0.2, : : : starring 0.5 klaus:0.25, lowitsch:0.25, barbara:: : : director 1 rainer:0.33, werner:0.33, fassbinder:0.33 released 1 1973:0.5, 1982:0.5 language 0.5 english:1
type 1 lm:1 (3) et
at w : etat (w) i:title e:0.33, t:0.33, 1994:0.33 i:actors coyote:0.5, peter:0.5 i:directors spielberg:0.33, steven:0.33, i:0.33 i:producer spielberg:0.33, steven:0.33, i:0.33
type movie:1 We tackle the problem of searching over heterogeneous data in a way similar to entity consolidation. That is, given the results es 2 Rs from the source dataset obtained for the seed query, we aim to nd out which entities in the target datasets are similar to Rs. We use the ERM as the model of those relevant results. In particular, we estimate which entities et of Dt are relevant for the query qs by measuring their similarity to the ERM and rank them by decreasing similarity. First, we capture the values of atk of each entity et using a language k model etat (w). Similar to the ERM, this model is de ned based on the number of word occurrences as follows:
k etat (w) =
Pv2atk n(w; v)
P v2atk jvj (2) As before, the sum goes over all values of attributes with label atk, n(w; v) denotes that number of occurrences of w in v, and jvj denotes the length of v. Fig. 2 (3) illustrates an example.
The similarity of a candidate entity et from the target dataset Dt to the ERM is calculated as the sum of the weighted similarities between the language model of eld ajs and the language model of atk, which is calculated by their cross entropy H:
Sim(ERM; et) = X j k j P (ajs) H(ERM as jjetat ) as j as
In particular, we apply this similarity calculation only when we know which eld ajs of ERM should be matched against which attribute atk of et. We address this problem in the next section and show how the ERM can be exploited to create on-the- y schema mappings, i.e. mappings between an attribute atk and a eld ajs of ERM . Equation 3 applies to corresponding pairs of attribute and eld. If there is no mapping between ajs and atk, then we use a \maximum distance". j This distance is computed as the cross entropy between ERM as and a language j model that contains all words in the vocabulary expect the ones of ERM as .
The similarity for each eld ajs is weighted by the occurrence probability of this eld, P (ajs), and the parameter ajs . This parameter gives us the exibility to boost the importance of attributes that occur in the query qs as follows: as j = 1 b if ajs 2= qs if ajs 2 qs; b > 1
For constructing the language models of the ERM and of the candidate entities, a maximum likelihood estimation has been used, which is proportional to the count of the words in an attribute value. However, such an estimation assigns zero probabilities to those words not occurring in the attribute value.
k In order to address this issue, etat (w) is smoothed using a collection-wide model cs(w), which captures the probability of w occurring in the entire dataset Ds. This smoothing is controlled by the Jelinek-Mercer parameter . As a result, the entropy H is calculated over the vocabulary V of eld ajs as: (3) (4) j k H(ERM as jjetat ) =
X w2Vajs
ERM ajs (w) log(
k etat (w) + (1 ) cs(w) ) (5) 3.3
On The Fly Integration Using ERM
We want to determine which attribute of an entity needs to be compared to a
given eld of the ERM constructed for Ds. The ERM is not only used for search,
but also exploited for this alignment task. The details for computing mappings
between entity attributes etat1:::r and ERM elds ERM as1:::n are presented in
Algorithm (1).The rational of the algorithm is that a eld ajs is aligned to an
attribute atk when the cross entropy H(ERM ajs jjetatk ) between their language
models is low, i.e. a mapping is established, if H is lower than a threshold t
(normalized based on the highest cross entropy, line 12).That is, entropy is used
as a similarity measure and the features used to compare attributes are based on
their entire contents represented using language models. The algorithm iterates
over n r comparisons in worst case for an ERM with n elds and an entity
with r = jA0(et)j attribute labels. Note that this on-the- y algorithm operates
only on entities that are requested as part of the search process, i.e. n and
r are rather small, compared to full- edge upfront integration that takes the
entire schema into account, see Table 1 and Table 3. Especially, this computation
comes for free: searching also requires the same computation (Equation 3) and
thus the entropy values computed here are kept and subsequently reused for that.
Moreover, for a faster performance, ERM elds having an occurrence probability
of P (ajs) < c can be pruned, because of their negligible in uence. In addition,
existing mappings can be used to reduce the number of comparisons even further.
Algorithm 1 On the y Alignment
In this section, we report on the experiments conducted using an
implementation of the proposed approach. We performed the experiments with the following
parameter setting: = 10, c = 0:8, t = 0:75 and follow the Cran eld [
Note that this ground truth is conservative in the sense that it considers only matches that can be obtained through query rewriting based on same-as mappings. However, some possibly relevant entities may either be represented di erently (using attributes that cannot be aligned via same-as mappings) or do not contain information for some of the query predicates. Hence, this ground truth de nes a lower bound on the actual performance.
We created two query sets, each containing 23 BGP entity queries of
different complexities, ranging from 2 to 4 triple patterns and yielded a varying
number of relevant entities (see Table 2). The structured queries represent
realworld information needs, e.g. retrieve \all movies directed by Steven Spielberg",
\all movies available in English and also in Hebrew", or \all movies directed
by Rainer Werner Fassbinder, which were released in 1982". The last query is
illustrated in Fig. 3.
We compare the performance of our ERM approach against Semplore [
The robustness of the retrieval performance of ERM can be observed in Fig. 4(b), which shows the interpolated precision across the recall levels. We can observe that ERM considerably outperforms the KW baseline across the recall-levels. 5
We have discussed related work throughout the paper. Basically, there are two
existing lines of approaches, one that is based on keyword search and the other
one is structured query rewriting. Our approach represent a novel
combination which combines the exibility of keyword search with the power of query
rewriting. Just like keyword search, it does not rely on precomputed mappings.
However, it is able to exploit the ne-grained structure of query and results,
which is the primary advantage of structured query rewriting. In addition, it
can leverage existing mappings created by tools like [
More precisely, there exist similar keyword search retrieval models that also
take the structure of the underlying data into account. In fact, the model
underlying our approach originates from the concept of language models [
Beside the query rewriting [
The proposed mapping technique is in principle similar to existing
techniques, e.g. [
We have proposed a novel approach for searching Web datasets using one single structured seed query that adheres to the vocabulary of just one of the dataset. It is based on using an entity relevance model computed from the seed query, which captures the structure and content of relevant results. This model is used both for matching and ranking relevant results, as well as for performing data integration on-the- y. This approach combines the exibility of keyword search in the sense that no upfront integration is required, with the power of structured query rewriting techniques that comes from the use of the ned-grained structure of query and results. The experiments showed that our approach outperform a common keyword search baseline.
We demonstrated our approach between one source and one target dataset. However, there is no inherent limitation to the number of target datasets. So theoretically, one query can be used `to bind them all'.
This work was supported by the German Federal Ministry of Education and Research (BMBF) under the iGreen project (grant 01IA08005K).