In keyword search over data graphs, an answer is a nonredundant subtree that contains the keywords of the query. Ranking of answers should take into account both their textual relevance and the signi cance of their semantic structure. A novel method for answers priors is developed and used in conjunction with query-dependent features. Since the space of all possible answers is huge, e ciency is also a major problem. A new algorithm that drastically cuts down the search space is presented. It generates candidate answers by rst selecting top-n roots and top-n nodes for each query keyword. The selection is by means of a novel concept of virtual documents with weighted term frequencies. Markov random eld models are used for ranking the virtual documents and then the generated answers. The proposed approach outperforms existing systems on a standard evaluation framework.
Data graphs are a convenient, exible way of representing knowledge bases. They can be constructed from a variety of formats (e.g., XML, RDB and RDF). Their semistructured nature makes it possible to create them incrementally, distributively and heterogeneously. Since they do not have a rigid schema, it is essential to support keyword search over them (rather than querying in some formal language, such as XQuery or SPARQL). Yet, it could be possible to get succinct answers that have some semantic structure. In particular, their answers can show semantic connections between distinct units (e.g., Web pages), which is impossible This work was supported by the Israel Science Foundation (Grant No. 1632/12). in ordinary keyword search, where a result is always a single unit (e.g., document).
The nodes of a data graph represent entities and relationships, while the connections among them are introduced as edges. Free text can be associated with nodes and edges. In keyword search over data graphs, answer are non-redundant subtrees that contain all the keywords of the query.
Keyword search over data graphs has been investigated extensively in recent years (cf. [5]). It involves two main challenges: e ectiveness and e ciency. The rst one means that we have to develop e ective methods for ranking of answers (i.e., subtrees) that take into account the structure (e.g., the importance of entities and the strength of relationships among them) as well as the relevance of the keywords of the query. The second challenge is to generate candidate (i.e., potentially relevant) answers e ciently. This is not an easy problem, because there could be a huge number of subtrees that contain all the keywords of the query.
A common approach begins by assigning weights to the nodes and edges of the data graph. Then, the search for answers starts from nodes containing keywords of the query. The weights are intended to focus the search on paths that lead to roots of the most relevant answers. However, those weights are assigned based on local considerations (e.g., the text of a node) and, hence, their e ectiveness is limited for the following reason. Nodes belonging to relevant answers are those that have, in their vicinity, other nodes with keywords of the query. To solve this problem, we introduce virtual documents (VDs) that contain a node and its vicinity. We rank VDs by applying (similarly to [1,20]) a Markov random eld (MRF) model that combines query-dependent and independent features. In particular, we adapt positional language models [18] by using distances based on static weights that re ect the structure of the data graph. Also, we use node priors as a query-independent feature.
We apply the ranking of VDs to the process of selecting the top-n keyword nodes (i.e., nodes containing keywords of the query) and the top-n roots. Only after selecting both keyword nodes and roots, do we construct paths that connect them, thereby yielding answers. By rst selecting roots and not just keyword nodes, we realize a higher degree of both e ectiveness and e ciency. It should be noted that several papers [10, 21] use notions of virtual documents that are also returned as answers. In contrast, we apply VDs just as a rst step in the construction of answers.
For the nal ranking of the generated answers, we use once again an MRF model for combining query-dependent and independent features. Unlike previous work, our queryindependent feature is not ad hoc, but based on a rigorous computation of answer priors.
We have evaluated our system on the framework of [5] that consists of three datasets: IMDB, Wikipedia and Mondial, as well as fty queries for each one. On all three datasets, our method outperforms the state-of-the-art systems. Our experiment include automatic learning of the parameters of the MRF models.
We also show that our approach o ers an excellent way of improving the e ciency with just a minor impact on the effectiveness (i.e., quality of answers). It is done by decreasing n (i.e., the number of selected roots and keyword nodes).
In summary, our main contributions are the following. 1. By developing virtual documents and using them for rst selecting the top-n keyword nodes and also the top-n roots, we have an algorithm for generating answers that is both highly e cient and e ective. 2. We formally compute answer priors and use them as a query-independent feature in the nal ranking. Our experiments show that they make a highly signi cant contribution to the e ectiveness of our system. In the area of keyword search over data graphs, this is the rst time that query-independent features are based on a rigorous formalism, rather than ad hoc intuition. 3. We describe an e cient implementation using inverted indexes. We have done extensive experiments showing that our system is highly e ective and e cient.
The rest of the paper is organized as follows. In Section 2, we discuss related work. Section 3 reviews basic concepts. Section 4 develops the virtual documents and their features. Section 5 presents the algorithm that uses the selected roots and keyword nodes for generating answers. Section 6 develops the features of answers. Section 7 describes the implementation and the experiments that verify the e ectiveness and e ciency of our approach. We conclude in Section 8.
We discuss systems for keyword search over data graphs along the dimensions of e ciency (i.e., how to generate answers) and e ectiveness (i.e., how to rank answers). The common approach to generate answers e ciently [2, 12, 19] uses backward iterators that start from keyword nodes until they meet at a root node. In [13] they improved [2] by adding forward iterators that can go back from the detected roots, to keyword nodes. Still, they have to start from keyword nodes. In [8], they present a method for keyword search over RDF graphs that starts with triples that match each keyword. Then they produce answers by joining the triples through their subjects and objects. In our work we use virtual documents to start simultaneously from roots and keyword nodes, thus we further reduce the search space.
Other papers have also used virtual documents in keyword search over data graphs. In [10, 21], they create a virtual document from a node and its vicinity, and search it for the keywords. In [4], they do entity search over RDF data and their virtual documents contain a node, but only with its literal neighbors. All of these systems return virtual documents or their roots as answers, whereas we use them just as a rst step to generate answers (i.e., subtrees).
For an e ective ranking of answers (cf. [7]), systems use features that consider both relevance to the keywords of the query and to the structure of answers. In [3] they use pseudo-feedback to apply relevance models to tuples and use them for ranking of answers. The works of [12, 17, 19] resemble our work in that they concatenate the text in the nodes of answers and use IR methods combined with queryindependent features for ranking. We also apply IR features on the concatenated text, but di erent from those works, we present a probabilistic feature that considers the prior of an answer, and we use a well established theory of MRF for combining it with the IR features.
In [16] they builds priors to paths in graphs for the application of recommendation of conferences, papers to cite, or experts for a new paper that one writes. In comparison, we assign di erent priors to each answer (i.e., subtree) while they assign priors for paths, and their priors are xed for all paths of the same type.
In [15], they learn per-term weights for each eld; in our case, it gave inferior results. So, we use a term-independent weight for each eld as in [11, 14].
Data graphs can be created from any format (XML, RDF, RDB, etc.). Figure 1 shows a tiny portion of the IMDB data graph. In this paper, we experiment with data graphs that are obtained from relational databases as follows. Each tuple t becomes a node vt that has the relation name as its type. A tuple t can be either an entity or a relationship. In the former case, vt is an entity node and is shown as a rectangle in Figure 1. In the latter case, vt is a relationship node and is shown as a diamond. The attribute-value pairs of vt are those of the tuple t, excluding foreign keys. That is, a foreign key is represented in the data graph by a directed edge (shown in Figure 1 as a solid arrow). An opposite edge (shown as a dashed arrow) is added in the reverse direction in order not to miss relevant answers.
In Figure 1, the diamond of a relationship node shows the type (e.g., cast). The top line of a rectangle shows the entity's name (e.g., goldfinger) followed by its type (e.g., movie). The other attribute-value pairs are listed below the top line.
The value of an attribute could be free text. For the name of an entity node, we choose the value of an appropriate attribute, such as title, etc. We shall refer to that attribute generically as name. The value of name is a short string that serves as a not-necessarily-unique identi er; for example, it could be the title of a movie or the name of a person. Relationship nodes typically do not have the attribute name. 3.2
In [9,11,14], they showed that combining elds yields better results when searching XML, the Web or at documents. Similarly, we group the attributes of a node into two semantic elds (that could overlap). The content eld consists of the names and values of all the attributes. The title eld comprises only the value of the attribute name. In Figure 1, for example, the title eld of node 2 is: goldfinger, and the content eld is: title goldfinger type movie releasedate 1964 genre action adventure producedin uk plot bond is back and his next mission ...
The content and title elds (of a node) contain textual information that we use to assign IR scores. We distinguish between these two elds in order to control the relative importance of an occurrence (of a query keyword) in the title compared with an occurrence only in the content eld. 3.3
A query Q = (q1; :::; qm) on a data graph is a set of keywords. Each qi should match a term in the content of some node(s); that is, we use the AND semantics as usually done in keyword search over data graphs (supporting the OR semantics is left for future work).
Answers are subtrees of the data graph, rather than subgraphs, because a tree is easier to understand quickly and is typically an indivisible unit of information. Formally, an answer to Q is a non-redundant subtree a of the data graph, such that a contains all the keywords of Q. Containment means that each keyword appears in some node(s). Nonredundancy requires an answer not to have a proper subtree that also contains all the keywords of the query.
As an example, consider the data graph of Figure 1 and the query \sean connery eming" for nding movies that are related to those names. A possible answer comprises ve nodes: goldfinger (of type movie), ian fleming and james bond (both of type person), and the two connecting nodes of type cast. Note that non-redundancy does not imply minimality, and a query could have numerous answers. 3.4
Markov random eld (MRF) models make it possible to combine query-dependent and independent features. We apply the sequential dependency model of [1, 20] and use unigrams and unordered bigrams as query-dependent features. Our query-independent feature is the prior of either a node or an answer. The score with respect to a query Q = (q1; :::; qm) is given by score(Q; x) = X
T fT (qi; x) + T^fT^(qi; x) qi2Q
X +
fqi;qi+1g2Q + LfL(x);
U fU (qi; qi+1; x) + U^ fU^ (qi; qi+1; x)
(
We actually use two variants of Equation (
T After the algorithm generates n answers, they are re-ranked using the potential functions fT , fT^, fU , fUa^ and fLa that are a a a de ned in Section 6. 4. 4.1
We consider a data graph G = (V; E), where V and E are the sets of nodes and edges, respectively. In [19], each node v 2 V is deemed a document. We take a di erent approach and view a small vicinity of a node (including the node itself) as a virtual document. Intuitive motivation is that often keywords of a query are spread over several nodes that are close to one another.
Formally, the virtual document (abbr. VD) of a node v, denoted by v?, consists of all nodes u, such that the following holds. There is a path p in the data graph G from v to some entity node x (where x could be u), such that p includes u and has at most entity nodes, excluding v itself. The parameter is called the diameter of the VD. As a running example, we use Figure 1 with = 1. The VD of node 6 consists of nodes 2, 3, 4 and 6 (node 3 is not counted in , because it is a relationship). The VD of node 2 comprises nodes 1, 2, 3, 4, 5, and 6. Note that v? is de ned as a set of nodes. However, v? can also be viewed as the subgraph of G induced by its nodes (i.e., the subgraph comprising the nodes of v? and the edges between them).
A node consists of two elds: content and title. We denote by vf the text in the eld f of node v. In particular, vcnt and vttl are ordinary documents consisting of the text in the content and title elds, respectively, of v. Similarly, vf? denotes the eld f of the VD v?, that is, the concatenation of the text in eld f of all the nodes comprising v?. (However, the weighted term frequencies de ned later are applied to v?.) Recall that V is the set of nodes of the data graph. We use Vf to denote the collection that comprises all the vf . 4.2
In the VD v? of a node v, occurrences of terms closer to v are more important. Distances among nodes are determined by minimal-weight paths. We assign static weights (which are query independent) to nodes and edges as follows.
For an entity node u, the importance is proportional to the number of its neighbors. Thus, the static weight of u, denoted by wns(u), is de ned as wns(u) =
1
ln(e + Deg(u))
;
(
Next, we consider relationship nodes and edges. Two entity nodes are directly related if they are connected by either a single edge or a pair of edges that pass through a relationship node. In this paper, we do not consider types of nodes and edges when determining static weights. In addition, the degree of a relationship node is usually 2 or 3. Therefore, we apply the rule that the static weight of a direct relationship is always 1. In this way, we give some preference to smaller answers (i.e., with fewer nodes). To conform to the above rule, the static weight wns(u) of a relationship node u is 1. The static weight of an edge e, denoted by wes(e), is 1 if e connects two entity nodes; otherwise e connects an entity with a relationship node and wes(e) = 0.
A path p from node v to node u is written as pv!u. The static weight of pv!u, denoted by ws(pv!u), is the sum of static weights of all the edges and nodes of p; that is, ws(pv!u) = X wes(e) + X wns(x);
e2p x2p where the rst sum is over all edges e of p and the second| over all nodes x of p. Note that if the path consists of only node v, its weight is wns(v). 4.3
Next, we de ne the weighted terms frequencies of unigrams and unordered bigrams in a VD v?. Given a node u of v?, the relative static weight of u in v?, denoted by ws(v?; u), is the minimum weight over all paths from v to u in v?; that is, ws(v?; u) = pv!u is in v? ws(pv!u):
min Note that all the nodes and edges of pv!u are in v?. For example, in Figure 1, the relative static weight of node 4 in the VD of node 2 is ws(2?; 4) = 0:64 + 1 + 0:76 = 2:4.
Let t be either a unigram or an unordered bigram. To
de ne the frequency of t in v?, we adapt the method used in
positional language models [18]. That is, the weight of t in a
node u of v? is inversely proportional to ws(v?; u) ws(v?; v),
which is the weighted distance of u from v in the VD v?. In
particular, a kernel serves as a discounting factor. We use a
Gaussian kernel, because it was shown to be the best [18].
Formally, the weighted term frequency of t in eld f of v?,
denoted by wtf (t; vf?), is
(
X e
u2v?
(ws(v?;u) ws(v?;v))2
2 2
tf (t; uf );
(
Note that the sum in Equations (
Consider a query Q = (q1; :::; qm). We now de ne
potential functions for unigrams, unordered bigrams and nodes.
In Section 5, we use Equation (
fTn^ (qi; v) = ln (1
where Tn and Tn^ are smoothing parameters for the content and title elds, respectively, and Vcnt and Vttl are the collections comprising the content and title elds, respectively, of all the nodes of the data graph. We use Dirichlet smoothing for Tn and Tn^, as described in Section 7.3.
We use the maximum likelihood estimate. Hence, in each
one of Equations (
P (qijvx?) = Pt2vx? wtf (t; vx?) ;
wtf (qi; vx?)
where we use weighted term frequencies (de ned by
Equation (
In each of Equations (
P (qijVx) = P u2V Pu2V tf (qi; ux)
Pt2ux tf (t; ux) : where x is either cnt or ttl .
Unordered bigrams. For an unordered bigram fqi; qi+1g
of Q (similarly to unigrams), we use the following two
potential functions for the content and title elds.
(
Here, Un and Un^ are the smoothing parameters for
unordered bigrams. Similarly to unigrams, we use Dirichlet
smoothing for these parameters. As earlier, the
probabilities in Equations (
Query independent. We use one query-independent potential function that is given by the node prior. In particular, we assume that the probability of a node v is proportional to its degree in the graph. Hence, fLn (v) = ln P
Deg(v) u2V Deg(u) :
Overall, there are ve potential functions and, thus, we have to learn ve parameters (i.e., Tn , Tn^, nU , nU^ and nL). In the next section, we use the ve functions twice: once for selecting roots and a second time for choosing keyword nodes. The learning is done separately for each one of these two cases, as described in Section 7.3.
In this section, we rank nodes according to score(Q; v)
of Equation (
We begin by selecting roots and keyword nodes. The former will be roots of answers. The latter will appear in answers as nodes containing keywords of the given query Q = (q1; : : : ; qm). We do it as follows. First, we consider all nodes v of G, such that v? contains every qi. We rank them according to score(Q; v) and select the top-n. These are the selected roots. Second, we consider the set U of all nodes v, such that v is in r? where r is a selected root. Let Ui be the subset of U that comprises all nodes v, such that v contains the keyword qi of Q. For each keyword qi 2 Q, we rank the nodes of Ui according to score(Q; v) and choose the top-n. These are the selected keyword nodes (for qi). Let S be the set consisting of all the selected roots and keyword nodes.
We will construct answers from minimal-weight paths that connect the selected roots and keyword nodes. We want the weight of a path from a root r to a keyword node v to re ect also the scores of its endpoints (i.e., score(Q; r) and score(Q; v)), rather than just the static weights of Section 4.2. Hence, we convert scores into dynamic weights. When converting, we invert the scores, because lower weights are better (whereas it is the opposite for scores). The conversion produces dynamic weights in the interval [0; 1], to make them commensurate with the static weights. Formally, the dynamic weight of a node v 2 S, denoted by wnd(v), is wnd(v) = 1 max score(Q; u) u2S score(Q; v) Since score(Q; v) is negative (i.e., obtained by applying logarithm to probabilities), wnd(v) is in the interval [0; 1]. Note that wnd(v) = 0 if node v has the highest score in S.
The static weight of a path pr!v is given by Equation (
X
x2p^x2=fr;vg
wns(x):
(
Let r be a selected root. The set Uri consists of all the keyword nodes that were selected for qi and are in r?. Observe that every combination of m minimal-weight paths, such that each one is from r to a keyword node of Uri (1 i m), yields an answer to Q = (q1; : : : ; qm).1 For each root r and keyword qi, we generate these paths and keep them in a separate sorted list.
To generate answers, a priority queue A stores for each selected root r, the next best answer (with r as the root) that has not yet been added to the output (or discarded if it is not valid). Answers are removed from A by increasing height. Note that the height of a tree is the maximum combined weight over all the paths from the root to some leaf.
An answer a is valid if it satis es the following conditions. First, a is non-redundant, that is, a does not have a proper subtree that also contains all the keywords of the query. If a is redundant, we convert it to a non-redundant answer by re1Formally, such a combination may not create a tree. However, it can be easily modi ed to form a tree. cursively removing the root r, thereby decreasing its height. Second, a is not a duplicate of another answer that is already in the output. Duplicates are removed based on an undirected semantics (to conform to the evaluation framework of Section 7). Third, a does not have a relationship node with fewer than two adjacent entity nodes. 6.
We view an answer a as a document by concatenating the
instances of each eld over all the nodes of a. Thus, acnt
and attl are ordinary documents obtained by concatenating
the content and title elds, respectively, of all the nodes
of a. Similarly to nodes, we de ne potential functions for
unigrams, unordered bigrams and query-independent answer
priors. These functions are used for scoring answers with
respect to Q by means of Equation (
Unigrams. Analogously to Equations (
fTa (qi; a) = ln (1
fTa^(qi; a) = ln (1 aT^)P (qijattl ) + aT^P (qijVttl ) Recall that Vcnt and Vttl are the collections comprising the content and title elds, respectively, of all the nodes of the data graph.
Unordered bigrams. Similarly to Equations (
As in Section 4.4, we use the maximum likelihood estimate for the probabilities in the above equations. Since acnt and attl are ordinary documents, we employ the usual term frequencies, rather than the weighted ones. We use Dirichlet smoothing for Ta , aT^, Ua and Ua^ (see Section 7.3). Query independent. We use one query-independent potential function fLa that is derived from an answer prior as follows. Let ar be an answer. The subscript of ar means that node r is the root. To derive the prior P (ar), we consider the skeleton sr that is obtained by deleting the content of ar. Namely, sr has the same nodes and edges as ar, but without attribute-value pairs.
To obtain the probability P (ar), we assume that ar is generated in two steps. First, the skeleton sr is generated with probability P (sr). Second, sr is instantiated to ar with probability P (arjsr); this is also done in two steps. First, the root of sr is instantiated to a speci c node of the data graph G. Second, the following is repeated. After instantiating a node v of sr to some node v0 of G, we select a neighbor of v0 for each child of v.
The prior of an answer ar is P (ar) = P (arjsr)P (sr). For
simplicity, we assume that P (sr) is the same for all
skeletons, so P (ar) = P (arjsr). To compute P (arjsr), we make
another simplifying assumption, namely, the probability of
choosing a speci c node u of ar depends only on its parent,
denoted by par (u). In particular, the probability of
choosing the root r of ar depends only on the data graph G. And
as in the derivation of Equation (
P (r) = Pv2V Deg(v) For a node u 6= r of ar, the probability of choosing u is proportional to its degree when compared with all the adjacent nodes of its parent. Hence,
P (ujpar (u)) = Pv2N (par(u)) Deg(v) ; Deg(u) where N (par (u)) consists of all the neighbors of par (u). Therefore, the probability of ar is
P (ar) = P (r)
P (ujpar (u)):
Y u2a;u6=r Note that the product of the conditional probabilities is over all nodes u of a, except the root. Since an answer a is an undirected subtree, we can pick any one of its nodes as the root; hence, we de ne fLa(a) = ln
max r is a node of a
! P (ar) :
We use the evaluation framework of [5] that was specifically developed for testing the e ectiveness of systems for keyword search over data graphs. The framework consists of three datasets: IMDB, Wikipedia and Mondial.
The datasets are given as relations. Each tuple of those relations has a unique id and may have some foreign keys pointing to other tuples. IMDB and Wikipedia contain six relations each, and Mondial contains twenty four relations. IMDB has 1.6M tuples, Wikipedia has 206K tuples and Mondial|only 17K tuples. IMDB and Wikipedia contain relatively large chunks of text, while Mondial has only short strings, such as names of countries and cities, etc. The Mondial data graph has on average a large number of edges per node, compared with the other two datasets.
For each dataset, the evaluation framework of [5] has fty queries and their qrels (i.e., query relevance judgments). The average number of keywords per query is 2:91, when excluding ve queries of IMDB that consist of very long quotations from movies. The average number of answers per query is 4:49 and the largest number of tuples in an answer is 5. 7.2
We translated each dataset into a data graph, as explained
in Section 3.1. Each data graph is indexed into three data
structures. First, the graph index comprises the nodes and
edges, and is kept in a Berkeley DB.2 It is used for
traversing the data graph and for storing query-independent
information that is needed for computing the potential
functions. The stored information includes, for example, the
?
static weights and for each node v, the lengths of vcnt and
vt?tl ; the latter two are used in Equation (
Mondial Wikipedia
IMDB
The second data structure, called the node index, is an Apache Lucene3 inverted index. It handles each node as a separate document consisting of the title and content elds, after applying stemming and stop-word removal.4 We use the Lucene Field class to implement those two elds. We keep two instances of the inverted node index, one for unigrams and another for unordered bigrams. The node index also stores the full text of each node, because it is needed for building the virtual index that is described next.
The third data structure, called the virtual index, is a
Lucene inverted index for the VDs (virtual documents) (one
per node). Similarly to the node index, it has title and
content elds, and two instances (for unigrams and unordered
bigrams). The posting list of t keeps, as a Lucene payload,
the weighted term frequency of t (see Equation (
Table 1 gives the sizes of the indexes for each dataset.5 For IMDB, the graph index is relatively big, due to the large number of entities and relationships in that dataset. The node index and virtual index for = 1 have similar sizes. This is due to the fact that the node index also stores the full text of the title and content elds (rather than just the inverted lists). The virtual index for = 2 is larger by two orders of magnitude than the one for = 1.
The selection of roots and keyword nodes in Section 5 is
e ciently implemented as follows. Let Q = (q1; : : : ; qm) be
the given query. In Lucene, we run Q as a boolean
conjunctive query on the virtual index and nd all nodes v, such
that the VD v? contains all the qi. We rank those nodes
by score(Q; v) of Equation (
We use Equation (
We generated three labeled les|for roots, keyword nodes and answers|with positive and negative examples for each query as follows. The qrels in the benchmark [5] contain only 3https://lucene.apache.org/ 4We used stop words from http://www.textfixer.com/ resources/common-english-words.txt, added some negation words, such as can't and won't, and removed stop words that could be names of people, such as Will. 5The sizes of the node and virtual indexes are shown for unigrams. The unordered-bigram indexes are between two to eight times larger than those of the unigrams. 6http://sourceforge.net/p/lemur/wiki/RankLib/ the correct answers that are labeled with 1. For each node v of those answers, if v can be a root (i.e., its VD contains all the query keywords) or a keyword node, then it is added to the corresponding le with the label 1. To add negative examples, we ran our system with equal weights of 0:2 for all of the ve parameters (when scoring roots, keyword nodes and answers). We used the default values of n = 1; 000 and k = 1; 000. Among the top-k answers obtained in this way, we chose those that are not in the qrels and labeled them with 0. Each node that can be a root or a keyword node of an answer that is not in the qrels was also labeled with 0 and added to the corresponding le, provided that it had not previously been labeled with 1.
Our experiments use cross validation. Namely, we learn the parameters on two datasets and use them on the third one. We report the results for each dataset with those learned parameters. The les with both 0 and 1 labels are just for training. The MAP is measured on the third dataset by using the original qrels of the evaluation framework.
We use Dirichlet smoothing with the parameter +jxj ,
where jxj is the length of x. For Tn , Tn^, Un and ? Un^ in
Equations (
For the parameters Ta , Ta^, aU and aU^ in Equations (
The diameter of VDs is = 1 (see Section 4.1). Unless otherwise speci ed, when selecting the top-n roots and keyword nodes for each qi (see Section 5), we use n = 1; 000. 7.4
We compare our approach with the top systems, namely, BANKS [2], Bidirectional [13] and CD [6], among those tested in [5], as well as with GraphLM [19]. In [7], they extended the binary relevance set of [5] to include answers with marginal relevance. However, they have not made that extended framework available, so we cannot use it. Similarly to [5, 19], we use the default k = 1; 000 when producing the top-k answers for each query. 7.5
We compare our approach, called MRF-KS, with the stateof-the-art systems using the evaluation framework of [5].7
Figure 2 shows that MRF-KS outperforms the other systems on each of the three datasets.8 The second best is GraphLM. On Wikipedia, MRF-KS achieves a MAP of 0:76 compared with 0:63 for GraphLM (an improvement of 20%). On IMDB, MRF-KS has a MAP of 0:76 compared with 0:68 for GraphLM (an improvement of 11:3%). And on Mon7For all the systems, the MAP on IMDB is based on the updated qrels that appear in http://www.cs.virginia.edu/ ~jmc7tp/resources.php#search. 8We show only the top performing state-of-the-art systems. dial, MRF-KS has a MAP of 0:89 compared with 0:83 for GraphLM (an improvement of 7:6%).
The advantage of MRF-KS over the second best system GraphLM is statistically signi cant on all three datasets, as measured in a one-tailed t-test (p-value < 0:05). We exclude the work of [3] from this comparison due to the following. Some essential details (e.g., the algorithm for generating answers in ranked order) are missing from their paper, which has made it impossible for us to reproduce their results. Moreover, they declined our request to get their code or, at least, the AP (average precision) they obtained for each individual query of the evaluation framework of [5]; hence, verifying their results is problematic. In any case, they reported that for Mondial, Wikipedia and IMDB, they got a MAP of 0:9, 0:78 and 0:79, respectively. Our results are almost the same: 0:89, 0:76 and 0:76, respectively.
MRF-KS noTitle
Mondial Wikipedia IMDB
MRF-KS( = 2) noWTF( = 2) noAnswerPriors onlyAnserPriors noBigram
We now show the e ect of various components of our system by measuring the MAP yielded by di erent con gurations, as shown in Figure 3. Unless otherwise speci ed, VDs have the default diameter of = 1. To magnify the e ect of the di erent con gurations, we select a relatively small number (n = 100) of roots and keyword nodes. For each con guration, we relearned the relevant parameters on two datasets and then measured the MAP on the third one, as explained in Section 7.3.
The rst two columns show that increasing the diameter of VDs from 1 to 2 slightly lowers the MAP. The third column (labeled with noWTF) is when the diameter is 2 and ordinary term frequencies (instead of the weighted ones) are used. In this case, the MAP drops on all three datasets and the larger e ect is on Wikipedia (from 0:74 to 0:66).
The rest of the columns show an ablation test that disables one feature at a time. The column noBigram is when disabling the unordered bigrams in the content and title elds (setting U ; U^ = 0) for roots, keyword nodes and answers. The column noTitle denotes the e ect of disabling the title eld for unigrams and unordered bigrams (setting ^ ; U^ = 0) for roots, keyword nodes and answers. The colT umn noAnswerPriors is when using all features except the answer priors (setting L = 0). The last column onlyAnswerPriors shows the MAP when using only answer priors for ranking the answers (setting T ; U ; T^ ; U^ = 0 for answers and keeping all features for roots and keyword nodes).
We can see that the most dominant feature is the answer priors. When disabled, the MAP drops sharply on all three datasets. For example, on Wikipedia it drops from 0:75 to 0:6 and on IMDB|from 0:76 to 0:56. The contribution of the answer priors is statistically signi cant. The title eld has the second largest e ect on IMDB and Wikipedia. The unordered bigrams have a moderate e ect on Mondial and Wikipedia, but a larger one on IMDB.
In this section, we show that our method o ers a useful trade-o between e ectiveness and e ciency that can be easily tuned, thereby substantially improving the running time while only slightly lowering the MAP. This ability is hardly found in any other system. Figure 4 gives the average running time per query and the MAP for di erent values of n (i.e., the number of selected roots and keyword nodes). The results are for k = 100 rather than the default k = 1; 000, thereby making the results more signi cant.
Figure 4 shows that the running time drops at a much faster rate than the MAP, as n gets smaller. On the three datasets, even for the small value of n = 50, the MAP is almost the same as for n = 1; 000. Hence, the parameter n enables us to substantially increase the e ciency without sacri cing e ectiveness.
n=10 Mondial-MAP n=50
n=100 Wikipedia-MAP
We presented a novel approach, couched in probability theory, to nding the top-k answers in keyword search over data graphs. It is based on new ideas and concepts. First, we showed how to estimate the prior of an answer (i.e., subtree) and showed its contribution to the nal ranking of answers. Second, we de ned virtual documents with weighted term frequencies and showed their e ectiveness in selecting the most promising roots and keyword nodes of candidate an0:8 P0:6 A M0:4 0:2 3 2 1 0 ) c e s ( e m i T swers. Third, we presented an e cient algorithm for generating and ranking answers. The ranking of nodes (i.e., roots and keyword nodes) and answers is based on a combination of query-dependent and independent features.
We compared our approach with other systems on the evaluation framework of [5] that consists of three datasets: IMDB, Wikipedia and Mondial. In terms of MAP, our approach has a statistically signi cant advantage over other tested systems on each of these datasets. For example, on Wikipedia, we achieved an improvement of 20% compared with the best state-of-the-art system.
We performed an extensive analysis of the contribution of the various components. The most signi cant feature is the answer priors. We further showed that that the MAP remains almost the same even when selecting a small number of keyword nodes and roots, thereby reducing the search space and increasing the e ciency. 9.
The authors thank Oren Kurland for helpful comments.