DEIM Forum 2017 C6-3

Entity Search by Leveraging Attributive Terms in Sentential Queries
over RDF Data
Wiradee IMRATTANATRAI† , Makoto P. KATO† , and Katsumi TANAKA†† Graduate School of Informatics, Kyoto University36-1 Yoshida-Honmachi, Sakyo-ku, Kyoto, 606-8501 Japan
E-mail: †{wiradee,kato,tanaka}@dl.kuis.kyoto-u.ac.jp
Abstract This paper proposes methods of finding relevant entities from RDF data for a given sentential query(e.g. “Cars 3”, “Toy Story 4”, or “The Incredibles 2” for the query “upcoming animated films pixar”) by leveraging
diﬀerent types of modifiers in the query through identifying corresponding properties (e.g. released and studio’s
industry for the modifiers “upcoming” and “animated”, respectively). While a major search engine like Google
provides a function that shows a list of entities with respects to users’ queries on their search result page, theentities are neither presented for a large fraction of users’ queries, nor in the order that users expect. To enhancethe eﬃciency of this function, we propose a method of finding entities based on the similarity between a query andentity type names together with the frequency of entities in search results returned in response to the query. We
also propose a method of identifying a property corresponding to each modifier in a query based on the frequency
of property values containing the modifier and co-occurrence of the modifier and property names. Moreover, theproposed method utilizes the diﬀerence in property value distributions of entities in the search results for a querywith and without the modifier. The experimental results showed that our proposed methods could predict relevant
entities based on relevant entity types for more queries than the existing function and achieved the best performancefor identifying relevant properties when all of the criteria were combined.
Key words RDF, entity search, knowledge base

1. Introduction
Users often search using entity type names as a query in a
Web search according to our survey which was performed byrandomly sampling 100,000 queries from a query log. The
result shows that approximately 36% of queries contained
entity type names (the details are reported in Section 4.).
Entity type names usually refer to a collection of entities.
For example, the entity type name “Retail stores in America” refers to the entities “Walmart”, “Costco”, and “TheHome Depot”. This moderate fraction of queries suggeststhat many users want to find entity type related informationthat includes a list of entities from Web search results. To
satisfy this information need, major search engines such as
Google have started to provide a function that presents a listof entities at the top of the search engine result page for agiven search query. Thus, providing entities in response tousers’ search queries becomes important as users can immediately find entity information without browsing among thesearch results.
However, since search queries are as varied as users’ need,
it is crucial for this kind of function to handle a wide variety of search queries such as “highest profitable companies
japan”, “upcoming american mystery movies” and “recent

query = latest american comedy movies
producedIn
movie x

<producedBy>company c<location>

U.S.

Figure 1: Example of multiple predicates as a property.

fantasy novels”. Furthermore, queries sometimes containmodifiers such as “highest profitable”, “upcoming”, and “recent” that modify other components in the queries like entity
type names. These modifiers are useful to narrow down thelist of entities, yet the existing function does not select orsort entities by taking into account such modifiers. Accordingly, it is necessary to interpret modifiers in queries and sortentities in the order of their relevance to the modifiers.
To overcome these limitations, we propose methods thatutilize RDF (Resource Description Framework) data from alarge-scale knowledge base (e.g. DBpedia（注 1）) for 1) finding
a set of entities for a larger fraction of Web search queries
and 2) identifying properties that are relevant to the modifier terms in the query for entity ranking. The structureof RDF data is a collection of triples where each triple con-

（注 1）：http://wiki.dbpedia.org/

sists of a subject, a predicate, and an object. Predicateswithin triples denote the relationship between pairs of subjects and objects. A set of such RDF triples can be viewed
as a graph in which predicates are edge labels connecting
subjects with objects. By utilizing the RDF data, we caneasily capture the relationship among subjects and objects.
For example, the subject “Japanese bands” and the object“Nintendo” are associated by the predicate <is a subject of>that represents the relationship between “Japanese bands”
as the entity type and “Nintendo” as the entity. Likewise, thesubject “Nintendo” as the entity is connected by the predicates <founder>, <numEmployees> and <revenue>. These
predicates represent the diﬀerent essences and link the subject “Nintendo” as the entity with diﬀerent objects. By using
these kinds of relationship, we can identify which entities areassociated with entity types and which properties relevant tomodifiers with respect to a given query. For example, given
the query “highest profitable companies japan”, we find a setof companies in Japan based on their entity types along withthe property corresponding to the term “highest profitable”,
which is the property revenue derived from the predicate<revenue> that describes the amount of money earned by
the companies. In addition, the corresponding properties canconsist of one or more predicates. For example, the predicates (<producedBy>, <location>) as the property producedIn for the modifier “american” in the query “latest
american comedy movies” as shown in Figure 1.
Our proposed method for finding a set of entities is basedon the similarity between a query and entity type names
as well as the document frequency of entities in the search
results returned in response to the query. We identify a relevant property for a given modifier based on three criteria: 1)
the frequency of property values including the modifier, 2)
the co-occurrence of the modifier and property names, and3) the diﬀerence in property value distributions of entities inthe search results for a query with and without the modifier.
In the experiments, we used 40 queries to evaluate theeﬀectiveness of our proposed methods. The experimental
results showed that our methods could predict relevant entities for more queries than the existing function provided by amajor search engine, and achieved the best performance for
identifying relevant properties when all criteria were combined. The contributions of this paper are:
• We introduced two fundamental tasks: entity set retrieval and property identification for entity ranking.
• We proposed methods for the two tasks, which utilize
the RDF data with some statistics that can be computed by
performing a Web search.
• We conducted two experiments to evaluate the performance of the methods and demonstrated the eﬀectivenessover the existing system.
The rest of the paper is organized as follows. Section 2.
surveys related work on finding relevant entities and properties. Section 3. introduces our proposed methods, andSection 4. presents experimental results. Finally, Section 5.
concludes the paper by outlining future work.

2. Related Work
This section introduces some related works to the problemof finding relevant entities and properties. One of the mostrelated works is entity ranking, which has been addressed insome tracks in INEX and TREC [2], [4], [5], [7]. The INEX
entity ranking track is comprised of two tasks: entity ranking and entity list completion tasks. The entity ranking task
expects systems to return relevant Wikipedia articles (or entities) in response to a given query where there is assumptionthat all entities have the corresponding pages in Wikipedia.
There are some proposed approaches for this task. Kaptein
et al. proposed methods to rank Wikipedia entities by estimating relevant Wikipedia categories for a given query, andrank entities based on the query likelihood model with estimated categories [11]. Demartini et al. expanded queries forthe entity ranking task in many diﬀerent ways such as using hierarchical relationship in the ontology and synonyms,
and extracting named entities from the queries [6]. Balog etal. proposed a probabilistic framework for the entity ranking
task, which can model not only keyword queries, but also
the other input such as categories in which relevant entities
should belong to and examples of relevant entities [1].
The entity track in TREC 2010 introduced another task
called related entity finding. This task is related to the entity
ranking tracks in INEX although it is diﬀerent in many ways:
the main input is an entity name or a homepage of an entityand output is a list of homepages of entities. There are also
some works that proposed methods for this task. For example, Bron et al. proposed methods to reduce problems inranking by using four components including co-occurrence,
type filtering, context modeling, and homepage finding [3].
Moreover, there are some related works about finding andranking a set of RDF subgraphs by considering relevant predicates (or properties) based on keyword queries [9], [12]. The
basic idea of the keyword search over graph-structured datais to match keywords with the elements in the graph, and torank a set of related subgraphs containing the matching elements using the predicates. If the keyword often appears in
relation to the predicates, its subgraphs would rank higher.
Therefore, the top ranked subgraphs contains the related elements (or entities).
Similar to the keyword search problem, the question answering over RDF graph is also considered as one of related
works [13], [15]. These works attempted to find answers (orentities) based on questions (or queries). The authors ofthese works also consider the modifier in the questions inwhich they finds the corresponding properties for the modifier terms. Zou et al. proposed methods to find relevant predicates or predicate paths (or properties) using supporting entity pairs for the relation phase (or modifier). For example,
the relation phase “play in” has the supporting pairs such as
Julia Roberts with Runaway Bride, while Unger et al. proposed methods that use of the pattern library extracted by
the BOA framework [10] besides string matching for finding
relevant properties.

More study related to the problem of finding properties
corresponding to modifiers was authored by Zhang et al. [14].
In this work, relevant properties (of facets) were estimatedfor a given query in order to provide better snippets for structured documents. While a machine learning approach was
employed for finding relevant properties, most of the features
were textual similarity that often used for learning to rank
for Web search (e.g. TF-IDF or BM25).
The problem of finding relevant entities is almost the sameas the entity ranking tasks, keyword search and question answering over RDF except for types of queries in which weare interested in. The query type that we target includes themodifiers that are not necessarily included in the Wikipedia
articles or the elements in the RDF graphs (e.g. “latest” or“most profitable”). Moreover, we use not only textual similarity based on a knowledge base, but also Web search engine results for finding relevant entities. This means that we
make use of both structured and unstructured information
for finding relevant entities.
The existing approaches for finding relevant properties andsequences of properties such as the textual similarity are
not suitable for modifiers that represent numerical attributes(e.g. “oldest”, “newest”, and “latest” ), for which we propose
methods based on the co-occurrence of terms on the Web andproperty value distributions of entities.

q: upcoming animated movies pixar

sim(q, t1) sim(q, t2)t3t4

sim(q, t3)

sim(q, t4)tn..

sim(q, tn)

t4

is a subject of

e

e

Tq

t3

t2

t1

is a subject of

e

top-k
searchresultsdf(e, Rq)esim(q, t)c(q, t)c(q, e)

t

t

wet

t4

t3

E*q

wte
e

e

e

e

e

e

df(e, Rq)(a) Entity set retrieval

TASK 2

m2

m1
q: upcoming

e
P *

Eq

animatedmoviespixar

directore

3. Methodology
In this section, we propose two fundamental tasks andmethods for these tasks. The first task is entity set retrieval
where given a query, we need to find a set of relevant entities.
The second task is property identification, i.e. identifying themost appropriate properties for modifier terms in a query.
3. 1 Problem Definition
Before going through each method, we formally define ourproblem in this subsection. Our problem is to return aranked list of entities for a given query q ∈ Q. We are specifically interested in queries Q that contain entity type names
and modifiers. A modifier is an attributive term that describes a typical feature of entities. Examples of modifiers are“oldest”, “american”, “comedy”, and “private”. Examplesof queries Q are “ancient temples” ([modifier] [type]), “latest
comedy movies” ([modifier] [modifier] [type]), and “universities new york” ([type] [modifier] [modifier]), where [modifier]and [type] in parentheses indicate that the term in the queryis a modifier and entity type name, respectively.
As was mentioned earlier, we build on RDF data from aknowledge base that indicate a relationship between entities
E and entity types T and properties P . Entities of the entity
type t ∈ T are denoted by Et , entity types to which entitye ∈ E belongs are denoted by Te , and a set of propertiesof entity e ∈ E are denoted by Pe . This set of properties
consists of kth -distant properties which are the edge labelsof the k-edge far from entity e ∈ E in the RDF graph wherek ∈ [1, K]. In our work, the problem is addressed throughtwo tasks: 1) finding a set of entities Eq∗ ⊂ E for query q andq

TASK 1eeeestudioreleasedgross
starring

birthPlacestudioindustry

1st-distant 2nd-distantproperty property(b) Relevant property identification

Figure 2: Overview of Two Fundamental Tasks∪2) finding a set of relevant properties Pq∗ ⊂ PEq∗ = e∈E ∗ Peq
for query q, where Eq∗ should belong to entity types relevantto the entity type names in query q, and Pq∗ should correspond to the modifiers in query q. Having obtained Eq∗ andPq∗ , we get a ranked list of entities by ranking Eq∗ based on
properties Pq∗ .
In the following subsections, we describe methods for eachof the two tasks for finding a set of candidate entities anda set of relevant properties. The overview of both tasks is
illustrated in 2a and 2b.
3. 2 Finding Set of Candidate Entities
Since we assume that a given query contains entity type
names, entity types and their entities should be relevant if
the name of the entity types is similar to the query. Here, we
use the Okapi BM25 to measure their similarity. In addition,
relevant entities may frequently appear in Web search resultsreturned in response to the query as some Web pages list up
entities that belong to a certain entity type.
3. 2. 1 BM25 Score between Query and Entity TypeWe measure the similarity between query q ∈ Q and entity
type t ∈ T using the Okapi BM25 as sim(q, t). We regard
entity types whose sim(q, t) is θ% (0.8 in our experiments) of
the maximum score or larger as a set of entity types denotedas Tq :
Tq = { t | sim(q, t) >(sim(q, t′ )) }(1)
= θ max′t ∈T∪
The set of candidate entities is Eq = t∈Tq Et .
In some cases, even though the BM25 score is high, theresultant entity types Tq can still be irrelevant to the query.
For example, given the query “suspension bridges in manhattan”, Tq includes “Suspension bridges”, “Bridges in Manhattan”, “Suspension bridges in Japan”, “Suspension bridges in
the United States”, and “Suspension bridges in Hungary”,
of which two are irrelevant to the query. To deal with thisproblem, we utilize the Web document frequency of entities.
3. 2. 2 Document Frequency of Entities in Web Search
To exclude irrelevant entities from Tq , we utilize the Web
search results for query q. We issue the original search queryq to a Web search engine and collect the top S search results
Rq (S was set to 20 in our experiments). For each candidate entity e ∈ Eq , we count the number of search resultsthat include the entity name in their content. More formally, the search result frequency is defined as df(e, Rq ) =| { r | r ∈ Rq ∧ e ∈ Er } | where Er is the set of entities whosename is included in the content of search result r. Entities
that have a high document frequency can be regarded as relevant to query q because they appear many times in the Web
search results for q.
3. 2. 3 Co-HITS Algorithm using BM25 Score and Document Frequency
Given the BM25 scores of entity types and document frequency of entities, we utilize the Co-HITS algorithm [8] tocombine these two criteria based on two assumptions: 1)
Entity types are likely to be relevant if they contain relevant
entities. 2) Entities are likely to be relevant if they belong torelevant entity types. As entities that have a high document
frequency are likely to be relevant to query q, we can inferthat entity types including such entities are also relevant. Ina similar way, we can further infer that entities included in
relevant entity types are also relevant. The Co-HITS algorithm can be used to make these inferences and enables us
to find more relevant entities and entity types that would be
missed when using methods described above.
The Co-HITS algorithm can be described with the following equations:∑c(q, t) = (1 − λT ) sim(q, t) + λT
wet c(q, e),
(2)
e∈Eq

c(q, e) = (1 − λE ) df(e, Rq ) + λE∑

wte c(q, t),

(3)

t∈Tq

where c(q, t) and c(q, e) are the Co-HITS scores for entity
types and entities, wet is the edge weight from entity e toentity type t, wte is the edge weight from t to e, and λT and
λE are the parameters that control the eﬀect of the BM25
score and document frequency on the Co-HITS score. Theedge weights indicate an is-a relationship between the entity types and entities and are defined as wet = 1/|Te | andwte = 1/|Et | if entity e belongs to entity type t; otherwise,
the edge weights are zero. Entities with the highest Co-HITSscores are used as Eq∗ and are later ranked by properties identified in the second task.
The Co-HITS score reflects our two assumptions. It becomes higher for entity type t if the Co-HITS scores for entities of t (the rightmost term in Equation 2) become higher,
while it becomes higher for entity e if the Co-HITS scores forentity types of e (the rightmost term in Equation 3) become
higher.
By using the example query “suspension bridges in manhattan”, the top 5 entity types in terms of Co-HITS score are“Suspension bridges”, “Bridges”, “Suspension bridges in the
United States”, “Bridges in Manhattan”, and “Bridges in
New York City”. This shows that the more relevant entity
types can be ranked higher by combining the BM25 scoreand document frequency.
3. 3 Finding Set of Relevant Properties
For this second task, we firstly identify the terms to bemodifiers in a given search query. These modifiers are used
to find corresponding properties based on the three methods: 1) counting the frequency of property values including
the modifier, 2) measuring the co-occurrence of the modifier and property names, and 3) measuring the diﬀerence inproperty value distributions of entities in search results for aquery with and without the modifier.
3. 3. 1 Identifying Query Terms to be Modifiers
Since we have found relevant entity types, we assume thatthe modifiers are terms that are not used for indicating therelevant entity types, i.e. ones that do not contribute to theBM25 scores of the relevant entity types. Specifically, foreach term w in query q, we sum up all the BM25 scores ofthe entity types in Tq that contain term w in their entity
type names. Then, we select term w as a modifier only if thesum of the BM25 scores for term w is relatively low. The
set of modifiers in query q is denoted by Mq and obtained asfollows:
{
Mq =

w

∑

<

t∈Tq ∧w∈n(t) sim(q, t) = ϕ

∑

w′ ∈q

∑

t∈Tq ∧w′ ∈n(t) sim(q, t)

}
,

(4)

where n(t) represents a set of terms in the name of entity
type t, and ϕ is a parameter that we set to 0.2 in our experiments. The left term in the inequality is the sum of BM25
scores for term w, while the right term is that for all theterms in the query.
For each modifier m ∈ Mq , we attempt to find a corre∪
sponding property from properties PEq∗ (= e∈E ∗ Pe ) thatq
can appropriately describe the modifier.
3. 3. 2 Counting Frequency of Property Values
The first method to find relevant properties is to countthe frequency of property values for each property p that
contain modifier term m. Some kinds of modifiers indicate a

P(v)

p1

P(v)

p2
q-m

q-m

q-m

q

q
v

p3

P(v)

q
v

v

Figure 3: Distributions of q and q−m for each property (pj )where x-axis (v) represents the property value of pj , and yaxis (P (v)) represents probability density of property value
v. In these examples, largest distribution diﬀerence can beseen with property p2 , which is possibly relevant to modifierm.
certain type of entities (e.g. “zen” is a property value of relevant property <denomination> and “new york” is includedin the property values of the relevant property <address>)and often specifies the property values of relevant properties. The frequency of property values including modifier mis computed as follows:
freq(q, m, p) = | { e | e ∈ Eq∗ ∧ m ∈ p(e) } |,(5)

modifiers excluded from the query. Figure 3 shows some examples of pairs of property value distributions. We estimatethat property p2 is relevant to modifier m since the distributions for the original search query (q) and original search
query without modifier term m (q−m ) are significantly different.
The property value distribution of property p for query q
can be estimated as follows:
Ppq (v) = ∑| { e | e ∈ ERq ∧ p(e) = v } |,| { e | e ∈ ERq ∧ p(e) = v ′ } |where v is a property value (v ∈ Vp ; Vp is the set of all
possible property values for property p), and ERq is a set ofentities included in the search results for query q (formally∪defined as ERq = r∈Rq Er ).
Letting q−m be query q with modifier m excluded (i.e. q −{m} if q is represented as a set of terms), the diﬀerence between property value distributions for queries q and q−m ismeasured by Kullback-Leibler divergence as follows:q

where p(e) represents the property value of property p for
entity e, which is represented as a set of terms in this case.
This method can only be applied to modifiers that appear
as a part of property values. Some modifiers such as “latest”,“oldest”, and “recent” cannot be directly found in their relevant property by only looking at the property value. Thus,
we need to use the second and third methods for these kindsof modifiers.
3. 3. 3 Measuring the Co-occurrence on the Web
The second method is to measure the co-occurrence ofmodifiers and property names on the Web. When people describe the characteristic of entities by modifiers (e.g. “old”,“large”, and “highest profitable”), they are likely to show
their property values as evidence that prove the statement isreliable (e.g. “foundation date”, “area size”, and “income”,
respectively). Thus, a high co-occurrence between a modifier and a property name indicates that the modifier specifies
a certain property value of the property. We compute howfrequently modifier m co-occurs with property p as follows:co(m, p) =| Dm ∩ Dn(p) |,| Dm |(6)

where Dm is the set of web pages containing term m, andn(p) is the name of property p.
3. 3. 4 Measuring KL Divergence between Property
Value Distributions
The third method is to measure the diﬀerence in property
value distributions of entities in search results for a querywith and without the modifier. We expect that Web searchengines can return search results containing some entities
whose property values are relevant to modifiers when theoriginal query is used as a Web search query, but they cannot
do this when modifiers are excluded from the query. Basedon this assumption, we can measure the change in property
value distributions of each property for these cases and estimate that properties that cause big changes are relevant to(7)v ′ ∈Vpdiﬀ(q, m, p) = D(Ppq ∥ Pp −m ) =∑Ppq (v)qv∈Vp log Pp (v) P q−m (v) .

(8)p

3. 3. 5 Combination of Three Criteria for Identifying Relevant Properties
Lastly, after applying all three methods to every property p
for each modifier m ∈ Mq , we need to find most appropriate
property by linearly combining these methods:f (q, m, p) = α1 freq(q, m, p) + α2 co(m, p) + α3 diﬀ(q, m, p),(9)where parameter α1 should be higher than the other parameters α2 and α3 according to our preliminary experiments.
Thus, we opted to use α1 = 0.8, α2 = 0.1, and α3 = 0.1 inour experiments described in the next section.
We selected the property with the highest f (q, m, p) for
each modifier m ∈ Mq and finally obtained a set of properties Pq∗ = { argmaxp∈PE∗ λe,p f (q, m, p) | m ∈ Mq } whereq1λe,p = d(e,p). d(e, p) denotes the distance of property p fromentity e ∈ E since the nearer the property is to the entity,
the more relevance it can be for the modifier.

4. Experiments
In this section, we explain our survey on the entity type
names in queries, introduce evaluation methodology for our
proposed methods, and show and discuss our experimental
results.
In the experiments, we used RDF data from DBpedia as
knowledge base to evaluate our methods. We obtained aset of entity types, entities, properties and property values
from DBpedia, which contains structured information derived from Wikipedia. We extracted pairs of an entity andan entity type by using the predicate <is a subject of> as theproperty, where the subjects and objects are treated as entity
types and entities, respectively. For extracting properties
and property values, we retrieved all triples whose the subjects are the entities, and treated the predicates as the property names and the objects as the property values. After theTable 1: Precision, Recall and F-score for entity types for 25 combinations of λE and λT .
(a) Precision

λT
λE
0.00
0.25
0.50
0.75
1.00

(b) Recall

0.00

0.25

0.50

0.75

1.00

0.659
0.517
0.517
0.517
0.517

0.553
0.554
0.543
0.540
0.504

0.554
0.560
0.549
0.547
0.499

0.552
0.554
0.562
0.552
0.493

0.569
0.571
0.571
0.550
0.494

λT
λE
0.00
0.25
0.50
0.75
1.00

0.00

0.25

0.50

0.75

0.260
0.198
0.198
0.198
0.198

0.443
0.448
0.429
0.438
0.413

0.445
0.452
0.442
0.446
0.406

0.441 0.456
0.446 0.457
0.449 0.453
0.446 0.438
0.398 0.371

Table 2: Examples of top five entity types obtained by bestparameter values for λE (0.25) and λT (1.00) with the CoHITS algorithm.
Query

Entity Types

Films directed by John Lasseter
Films featuring anthropomorphic characters
upcoming animated films pixar Films directed by Rob Zombie
Films directed by Andrew Stanton
2000s science fiction films

newest video games 2016

Upcoming video games scheduled for 2016PlayStation 4 games
Video games set in 2016
Video games featuring female protagonists
Dinosaurs in video games

Business in Europe
Education in Budapest
private business schools europe Europe Business Schools
Business schools in Germany
Universities and colleges in Cyprus

large companion dog breeds(c) F-score

Dog breeds
Dog breeds originating in Germany
Companion dogs
Spaniels
Sighthounds

extraction, we got 974,417 entity types including 4,811,226
entities and 60,252 properties from all the entities in total.
4. 1 Survey on Entity Type Names in Queries
To find out that how many search queries issued by users
contain an entity type name, we randomly picked 100,000
queries from an AOL query log and found queries containing entity type names from DBpedia. We used the BM25
score to measure the similarity between queries and entity
type names and selected queries with high scores using thesame criterion as that used in finding relevant entity types.
Queries were considered as ones including an entity typename only if they were retrieved by BM25 and satisfied thecriteria shown below:()|q ∩ n(t)| >|n(t)| >∃t ∈ T
β
∧
β
(10)
2 ,
= 1
|q|
|q| =
where q represents the set of terms in the query, n(t) is a setof terms in the name of entity type t, and β1 and β2 were set
to 0.65 and 0.5, respectively. These two criteria guaranteedthat 65% or more terms in the queries were terms in an entity type name, and the number of terms in the queries was
double or less than that in the entity type name. For example, “retail stores america” and “taylor swift songs” werecounted because of entity types “Retail stores in America”

1.00

λT
λE
0.00
0.25
0.50
0.75
1.00

0.00

0.25

0.50

0.75

1.00

0.325
0.254
0.254
0.254
0.254

0.449
0.453
0.439
0.442
0.413

0.451
0.457
0.449
0.448
0.408

0.448 0.463
0.451 0.465
0.458 0.464
0.450 0.446
0.400 0.391

and “Songs written by Taylor Swift”, whereas “walmart” and“taylor swift” were not. As a result, we found that approximately 36% of the search queries contain entity type names,
and conclude that our methods can be applied to a moderate
fraction of Web queries.
4. 2 Evaluation Methodology
We separately evaluated resultant entities and properties
for measuring the performance of our proposed methods indetail. In the experiments, we used 40 search queries that
contain modifiers and an entity type name (examples of thequeries can be found in Table 2).
4. 2. 1 Evaluation of Entities
To evaluate the performance of the proposed methods forfinding candidate entities, for simplicity, we opted to evaluate entity types rather than entities since the relevance of
retrieved entity types usually indicates that of entities in our
problem setting.
For each query, we evaluated 10 entity types with the highest Co-HITS scores (c(q, t)) for 25 possible combinationsof the two parameters involved in the Co-HITS algorithm,
where λT and λI were set to 0.00, 0.25, 0.50, 0.75, and 1.00.
Parameter λT controls the eﬀect of the BM25 score of entity
types, while parameter λI controls the eﬀect of document
frequency of entities on the Co-HITS score.
As a result, we obtained 25 sets of entity types for eachquery, and pooled the results for evaluation. The relevanceassessment was carried out by three assessors including twoof the authors. An entity type was considered relevant if at
least one of its entities was relevant for a given query. Theinter-rater agreement was measured by Fleiss’ Kappa andwas considered to be moderate at 0.601. We used majority
voting to decide the relevance of each entity type.
We computed the precision, recall, and F-measure basedon the relevance given by three assessors. Moreover, we compared our methods with the existing function provided by
Google. We computed the percentage of queries for which
the top ranked entity type was relevant for our methods andpercentage of queries for which Google’s function can present
a list of entities. Note that these results are not perfectlycomparable due to the diﬀerence in the metrics, but they
can still show the coverage of queries achieved by our methods and Google’s function.
4. 2. 2 Evaluation of Properties
This part of the evaluation was designed for evaluating theperformance of the three methods for finding properties rele-vant to modifiers in queries. In this part, we initially set K to
1 for finding a set of properties of entities with the same set of
queries as that used in the evaluation of entities. We detected
49 modifiers from 40 queries by the method explained in Section 3. 3, and evaluated the top five properties for each modifier using the following methods: Method I: Counting thefrequency of property values (Equation 5), Method II: Measuring the co-occurrence on the Web (Equation 6), Method
III: Measuring KL divergence (Equation 8), and Method IV:
Combination of Methods I, II, and III (Equation 9). No
baseline method was used due to lack of existing methods.
The relevance of each property was assessed by the sameassessors as those involved in the evaluation of entities. They
were required to judge a property as relevant only if a given
modifier seemed to specify a certain type of entity by property values of the property in a sequence. The inter-rater
agreement was measured by Fleiss’ Kappa and was considered to be substantial at 0.745. Majority voting was used todecide the relevance of each property.
We compared the results by Mean Reciprocal Rank
∑M 11
(MRR), which is defined as follows: MRR = M
i=1 ri ,where M is the number of modifiers in our experiment(i.e. 49), and ri denotes the rank of the first relevant property
for the i-th modifier. The MRR is often used for evaluating
ranked lists where only the first relevant result matters andis suitable for this evaluation since we expect only a relevant
property can be used for each modifier.
4. 3 Experimental Results for Entities
Table 1a and 1b show the precision and recall of the resultant entity types for 25 combinations of parameter λE
and λT , respectively. We noticed that the highest precision(0.659) was achieved when λE = 0.00 and λT = 0.00. Although the highest precision was achieved when λT = 0.00,
the lowest recalls were obtained (0.198) with the same setting. Since λT = 0.00 indicates that the Co-HITS score wasdetermined solely by the BM25 score, this result suggeststhat only the BM25 score can achieve high precision but low
recall.
We achieved high performance for both of the precisionand recall with 0.00 <= λE <= 0.50 and λT = 1.00. Amongthese parameter values, the highest recall was achieved when
λE = 0.25 and λT = 1.00. Moreover, we obtained the highest F-measure for λE = 0.25 and λT = 1.00 as shown in
Table 1c. Table 2 shows examples of entity types obtainedby the best parameter values. This result suggests that weshould not rely much on the similarity, but we should give ahigh weight to the document frequency in the Co-HITS algorithm. Note, however, that this does not mean the BM25
score is not necessarily used in our method as the BM25 scoreis still required to retrieve entities used in the Co-HITS algorithm. We could get more irrelevant entities if we directly
found entity names from Web search results without knowing the candidate entities by the entity types, since irrelevant
but common entity names may appear in the search results(e.g. “I” (a song title) or “IT” (a film title)).
We also compared our method with Google’s function. To

Table 3: MRR for results of identifying relevant properties.
Method I Method II Method III Method IV
MRR

0.326

0.223

0.194

0.426

Table 4: Examples of properties ranked at top by eachmethod for identifying relevant properties.
Method Modifier

Properties

Example of property values

kyotoitalianaddress
foodType

Fushimi-ku, Kyoto
Italian cuisineII

ancient
recentlatestfoundedtimeyear

1049-11-22
1200.01999

III

ancient
large
oldestfoundedfemaleheightestablished1049-11-22
75.0
mid 10th century

ancientkyoto
oldestrecentfoundedaddress
establishedtime1049-11-22
Fushimi-ku, Kyoto
mid 10th century
1200.0I

IV

this end, we computed the percentage of queries whose top
ranked entity type was relevant with the best combinationof parameters (λT = 1.00 and λE = 0.25) and percentageof queries for which Google’s function can present a list ofentities. We founded that our methods (57.5%) performed
approximately twice as well as Google’s (25.0%). Again, notethat diﬀerent metrics were used for ours and Google’s, andthis comparison could be an over- or under-estimation of theperformance of our method.
4. 4 Experimental Results for Properties
Table 3 shows the MRR achieved by each method for identifying relevant properties and indicates that combining allof the three methods (Method IV) could achieve the best
performance.
To drill down the results in Table 3, Figure 4 illustrates theperformance in terms of the RR achieved for each modifier,where the x-axis represents the modifiers, and the height ofeach portion of the stacked bars represent the MRR achievedby each method. Note that the total height of the stacked
bars does not represent the overall performance: it simply
means the average performance of all the methods. It can beseen that the diﬀerent methods could identify relevant properties for diﬀerent types of modifiers. For some modifiers,
relevant properties could be found at high ranks by Method
I, while Methods II and III could not rank them near the top(e.g. 10th and 20th modifiers from the left). On the other
hand, if relevant properties could be ranked high by Methods II or III, Method I could not rank them near the top
in some cases (e.g. 14th and 16th modifiers from the left).
These observations suggest that the combination of the threemethods (Method IV) could identify relevant properties mostaccurately by complementing each other.
Table 4 shows examples of relevant properties found at the
top by each method. It suggests that if the modifier specifies a categorical value such as “kyoto”, “zen”, and “italian”,
their properties can be successfully found by Method I. If the

3.5
3
2.5
2
1.5
1
0.5
0
1

2

3

4

5

6

7

8

9

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
Method I

Method II

Method III

Method IV

Figure 4: Reciprocal Rank (RR) of four methods for identifying relevant properties.

modifier specifies a certain range of numerical values or acertain order by numerical properties (e.g. “latest”, “recent”
and “oldest”), their properties can be identified by either
Method II or Method III. These results are also consistent
with our observation in Figure 4 that diﬀerent methods could
identify relevant properties for diﬀerent modifiers, and theysuggest that Method IV achieved the best performance because the three diﬀerent methods complemented each other.

5. Conclusions
This paper proposes methods of finding relevant entities fora given sentential query by leveraging diﬀerent types of modifiers in the query using RDF data. We proposed a method offinding entities based on the similarity between a query andentity type names together with the frequency of entities insearch results returned in response to the query. We also
proposed a method of identifying a property corresponding
to each modifier in a query using the methods 1) counting
the frequency of property values including the modifier, 2)
measuring the co-occurrence of the modifier and property
names, and 3) measuring the diﬀerence in property value
distributions of entities in search results for a query withand without the modifier. Experimental results showed thatour proposed methods could predict relevant entity types
for more queries than the existing function and achieved thebest performance for identifying relevant properties when allof the criteria were combined.
Our implementation mainly focused on finding the relevant entities and properties for a given sentential query withattributive terms. In addition, for our future works, we aim
to find other property identification methods that can handle
the properties which are derived from multiple predicates in
the RDF data. After that, we are going to apply those relevant properties as for ranking the resultant relevant entities.
To actually rank the entities, it may also requires various
kinds of methods.
Acknowledgement This work was supported in part by
Grants-in-Aid for Scientific Research (Nos. 15H01718, and26700009) from MEXT of Japan and Yahoo Japan Corporation.

References[1] K. Balog, M. Bron, and M. De Rijke. Query modeling for entity search based on terms, categories, and examples. ACM
TOIS, 29(4):22:1–22:31, 2011.
[2] K. Balog, P. Serdyukov, and A. P. d. Vries. Overview of the
TREC 2010 entity track. In TREC, 2010.
[3] M. Bron, K. Balog, and M. De Rijke. Ranking related entities: components and analyses. In CIKM, pages 1079–1088,
2010.
[4] A. P. De Vries, A.-M. Vercoustre, J. A. Thom, N. Craswell,and M. Lalmas. Overview of the INEX 2007 entity ranking
track. In INEX, pages 245–251, 2007.
[5] G. Demartini, A. P. de Vries, T. Iofciu, and J. Zhu.
Overview of the INEX 2008 entity ranking track. In INEX,
pages 243–252, 2008.
[6] G. Demartini, C. S. Firan, T. Iofciu, R. Krestel, and W. Nejdl. Why finding entities in Wikipedia is diﬃcult, sometimes. Information Retrieval, 13(5):534–567, 2010.
[7] G. Demartini, T. Iofciu, and A. P. De Vries. Overview of the
INEX 2009 entity ranking track. In INEX, pages 254–264,
2009.
[8] H. Deng, M. R. Lyu, and I. King. A generalized Co-HITS
algorithm and its application to bipartite graphs. In KDD,
pages 239–248, 2009.
[9] S. Elbassuoni and R. Blanco. Keyword search over rdf
graphs. In Proceedings of the 20th ACM international conference on Information and knowledge management, pages
237–242. ACM, 2011.
[10] D. Gerber and A.-C. N. Ngomo. Bootstrapping the linked
data web. In 1st Workshop on Web Scale Knowledge Extraction@ ISWC, volume 2011, 2011.
[11] R. Kaptein, P. Serdyukov, A. De Vries, and J. Kamps. Entity ranking using Wikipedia as a pivot. In CIKM, pages
69–78, 2010.
[12] T. Tran, H. Wang, S. Rudolph, and P. Cimiano. Top-k exploration of query candidates for eﬃcient keyword searchon graph-shaped (rdf) data. In Data Engineering, 2009.
ICDE’09. IEEE 25th International Conference on, pages
405–416. IEEE, 2009.
[13] C. Unger, L. Bühmann, J. Lehmann, A.-C. Ngonga Ngomo,
D. Gerber, and P. Cimiano. Template-based question answering over rdf data. In Proceedings of the 21st international conference on World Wide Web, pages 639–648.
ACM, 2012.
[14] L. Zhang, Y. Zhang, and Y. Chen. Summarizing highly
structured documents for eﬀective search interaction. In
SIGIR, pages 145–154, 2012.
[15] L. Zou, R. Huang, H. Wang, J. X. Yu, W. He, and D. Zhao.
Natural language question answering over rdf: a graph data
driven approach. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data,
pages 313–324. ACM, 2014.