Discovering expansion entities for keyword-based entity search in linked data

Abstract

There is an inherent rift between the characteristics of Web of documents and the Web of data – the latter is enriched with semantic properties that are not present in the former. This creates a formidable challenge for entity search in the era of Linked Data, requiring a new method that leverages on such features. Query expansion, used in keyword-based search, improves search quality by enhancing a query with terms. Existing query-expansion methods, statistical- and lexical-based approaches, are inadequate for linked data in two ways: (a) term-to-term co-occurrence, used in the statistical-based approach, cannot find satisfactory expansions in internal corpus (SPO triples) or external corpus (Web of documents); and (b) lexical incomparability between ontologies (or thesauri) as reference knowledge and linked data renders tenuous the possibility of creating lexically sound expanded queries. The study introduces a framework to expand keyword queries with expansion entities for keyword-based entity search in linked data. The framework offers two structures, star-shaped and multi-shaped RDF graphs (documents), to model the entities in linked data for indexing and search, and an algorithm called PFC for expansion entities by which to expand a given query. PFC obtains expansion entities by measuring a global importance (PageRank and entity–document Frequency) and a local importance (Centrality) of the candidates extracted from the returned RDF documents of the entity search. Our experiments illustrate that PFC improves search results by approximately 7%. This study also includes suggestions on how to glean important link types for extracting candidate expansion entities, as well as identifying properties of these entities by which to expand the query.

Keywords

Keyword-based entity search linked data query expansion

1. Introduction

With the development of the Semantic Web, Linked Data has become popular for connecting distributed datasets across the Web. During the past few years, the size of Linked Data has increased gradually, reaching 28.5 billion triples in 2010 [1]. An entity described by multiple triples is identifiable using a de-referenceable URL. For example, the entity ‘Michael Jackson’ is identified by the URL ‘Dbpedia:Michael_Jackson’, which is an RDF document with the triples about the entity ‘Dbpedia:Michael_Jackson’. All of the entities with a unique URL related to the entity ‘Dbpedia:Michael_Jackson’ are contained in the RDF document. Linked Data supplies users with comprehensive knowledge, but also raises a need to search entities in Linked Data. Entity search aims to find entities based on a query. Keyword-based entity searches address indexing scalability and query formalization, which are the main limitations of SPARQL endpoints [2], and are considered a better solution for entity search [3, 4]. Several entity search engines, such as Swoogle [5], Sindice [6] and Falcon [7], have adapted Information Retrieval (IR) techniques to provide solutions for keyword-based entity search. Keyword queries are typically very short [8], which makes an entity search engine hardly capture query contexts. Furthermore, users often resort to folksonomies described by various terminologies used in Linked Data, effectively creating a problem called ‘vocabulary problem’ [9]. Therefore, query expansion is studied to improve keyword-based entity search in Linked Data with expanded queries [10].

Query expansion [11] adds new terms to a query in an attempt to provide better contextualization and to help search engines to retrieve relevant documents [9]. Automatic query expansion techniques leverage various data sources to find new features related to queries. The techniques can in general be classified into two categories: lexical- and statistical-based approaches [12]. The inability to acquire suitable entities from RDF documents to expand the query is due to several reasons. In the lexical approaches, the use of thesauri or ontologies may be insufficient to cover the topics in a linked dataset. Furthermore, thesauri and ontologies differ in their structures of concepts from those in the linked data. The statistical approaches compute co-occurrences of a query in different documents or windows to help find related concepts [9]. For Linked Data, co-occurrences should not be regarded as a valuable measurement for finding suitable expansion entities. Most entities appear only once in the processed RDF documents in the entity search engines [13, 14], so this flat structure of the documents limits co-occurrence computations in Linked Data and decreases the importance of highly co-occurring entities. Concepts found by the statistical approaches with external corpora, such as Web pages, can be used to expand queries for improving entity search [10]. However, concepts explored with Web pages sometimes have too much noise, which limits their contributions for improving entity search in Linked Data.

To improve entity search in Linked Data, we aimed to discover expansion entities from an internal corpus (a linked dataset). Three tasks are involved in the study to achieve our goal: (a) how to find expansion entities by which to expand a query; (b) which links in RDF documents play an important role in extracting effective expansion entities; and (c) how to model expanded queries with expansion entities. To achieve the first task, we have extended the work in Zong et al. [15], which explores related entities or links in order to help new linked data suppliers to find new alignments. We propose a framework to help existing keyword-based entity search engines, such as Sindice [16], to improve search by expanding queries with expansion entities (the expansion entities denote entities used to expand a query). The framework provides two graph structures, star-shaped and multi-shaped indices, to model the entities in linked data for indexing, and an expansion entity discovering and ranking algorithm called PFC. The PFC discovers candidate expansion entities based on the returned RDF documents from an entity search, and sorts the candidates with a global importance measure, adapted from PageRank and entity–document frequency in the global graph, and a local importance measure, adapted from graph centrality in the local graph. Several parameters are adjusted to determine an acceptable level of query shifting [17]. With the experiments based on a linked dataset, Billion Triple Challenge 2009, we demonstrate that the PFC performs better than the lexical-based method with a knowledge base (WordNet), the statistical-based methods with the internal (the searched linked dataset) and the external corpus (Web of documents). From our experience while solving the second and the third tasks, we gained two insights based on the experiments:

Some link types (defined by DBpedia, Foaf, Sioc) are more important than others in extracting candidate expansion entities.

A URL or name of an entity is more suitable for expanding a query than other properties.

The rest of the paper is organized as follows: Section 2 shows the related works; Section 3 presents our query expansion framework; Section 4 details the entity ranking functions on the PFC; Section 5 describes the experiments in which our approach has achieved satisfactory results in both efficiency and effectiveness, when compared with other classic query expansion approaches; in Sections 6 and 7, we discuss the link types for candidate expansion entity extraction and identification of properties for modelling expanded queries; Section 8 discusses limitations of our study; and some conclusions and future work are presented in Section 9.

2. Related works

Since as early as the 1960s [18], automatic query expansion has been used to improve search results. Early research developed a range of seminal techniques, which have subsequently been improved and extended upon in various ways, such as vector feedback, term-term clustering and comparative analysis of term distributions [9]. On the other hand, a number of early experiments using small-scale collections produced inconclusive results that gained in recall but were often offset by a corresponding loss in precision, with respect to the retrieval effectiveness of such techniques [9]. The approaches can generally be classified into two categories: statistical and lexical approaches [9, 12].

In the lexical approaches, some studies use ontologies or thesauri to leverage global language properties to expand query terms. WordNet, known as a domain-independent ontology, is one of the most frequently used ontologies in language-specific approaches [19]. Synonyms, hypernyms and hyponyms are extracted to expand queries [20]. However, WordNet, used in query expansion, poses challenges, such as lack of proper nouns and/or collocations, or of an exact match between a query and concepts. To overcome the weaknesses, glossaries are used to expand queries instead of synonyms, hypernyms and hyponyms [21]. In addition, different types of information in WordNet are combined to give a better expansion [22 –24]. Other resources such as Wikipedia [25 –27] and Open Directory Project [28 –30] are used as thesauri for query expansion. These external corpora used as knowledge bases or thesauri can improve effectiveness in text retrieval, such as Web of documents. However, little improvement can be achieved from using an external knowledge base or thesaurus if its domain differs from the domain of the data searched. In our experiment, WordNet was such an example in which the external data did not contribute to search improvement.

A domain-specific ontology is used to expand queries with concepts in the same domain as that of the data, which narrows down the search space [19]. For example, Fu et al. [31] build an expansion based on a domain and a geographical ontology for queries. In the biomedical domain, Jain et al. [32] integrate domain ontologies and automatic semantic relationship learning approaches to create semantic query expansions for EMR retrieval systems. Similarly, Álvarez et al. [33] use a medical ontology, MeSH, to expand queries with medical terms for improving performance of a Multi-modal Information Retrieval System. However, finding an appropriate ontology for data under search is a challenge.

In the statistical approaches, studies exist that explore query-related terms by computing co-occurrences using a term–document matrix dynamically generated by relevance feedbacks [9]. Relevance feedback approaches are also adapted to link entities in a knowledge base [34]. However, different from unstructured data, most co-occurring entities only appear once in an RDF document that describes an entity. Using co-occurrences hardly finds expansion entities with this flat structure. The query-specific approach based on co-occurrences extracts unsuitable entities and damages the search in our experiment in Section 5.3. External corpora can also be used to find expansion concepts instead of using an internal corpus based on statistical approaches. Diaz and Metzler [35] extract concepts from an external corpus based on a language model to improve ad-hoc retrieval on text data. Similar to Diaz and Metzler [35], external corpora, such as the Web of documents, are used to extract expansion concepts based on the Vector Space Model (VSM) and a language model to improve entity search in linked data [10]. However, an external corpus often contains too much noise and is not contributive to expanding queries. In our experiment, the PFC can find better expansion entities than those found by the methods used in Halpin and Lavrenko [10] based on the Web of documents. Other approaches, such as Semantic Associations [36], Semantic Relatedness [37] and constraints and logics [38], are used to expand queries for Linked Data: semantic associations between entities are used to calculate a related entity using a ranking strategy based on various aspects such as subsumption weight, path length weight, context weight and trust weight [36]. Semantic relatedness of an entity is calculated by maximizing paths from the entity with a spreading activation algorithm, and the most related entities are used for expanding queries [37]. Queries are expanded based on constraints and logics to form unfolding queries, which are mapped into relationships in the source to form folded queries [38]. Different from those approaches using either a global corpus or local feedback, the PFC takes global and local importance measures into consideration and can flexibly adjust effects of the global corpus and local feedbacks by changing parameters.

3. Framework

We propose a framework in which expansion entities are discovered to expand a given keyword query. The framework comprises four main parts: data pre-processing, PageRank computation, entity indexing and search, and expansion entity discovery and ranking. Figure 1 shows an architectural view of the framework. In data pre-processing (stage 1 in Figure 1), the whole linked dataset is partitioned into RDF documents, each of which models an entity in the data. Three strategies are used to model each entity: star-shaped, multi-shaped and context-shaped. The partitioned RDF documents will be indexed and searched with a given query by Siren (stage 3). The returned RDF documents from Siren will be used as an input to the PFC that discovers expansion entities (stage 4) in the three steps. First, candidate expansion entities are extracted from the returned documents. Second, candidates are sorted by a global importance, which is based on the PageRank scores computed in stage 2 and entity–document frequency pre-computed when indexing, and a local importance based on centrality. Finally, the top N candidates will be returned as the expansion entities. This section describes in detail each stage in the framework.

Figure 1.

Framework of our query expansion method for keyword-based entity search.

3.1. Data pre-processing

In this paper, we will use an example to explain the processes of our method with the data in Figure 2(a). In a linked dataset, an RDF document that contains several triples (subject, predicate and object) is published with N-triple format (http://www.w3.org/2001/sw/RDFCore/ntriples/). An RDF document can also be published with N-quads format (http://sw.deri.org/2008/07/n-quads/) that contains quads (subject, predicate, object and context). In a triple or a quad, the values of the subject and the predicate are entities identified by de-referenceable URLs. The object value can be either an entity or a text (please note that, the term ‘entity’ used in this paper refers to the URL of the entity). For example, there are 10 triples in Figure 2(a). In the first triple, the subject is the entity ‘Dbpedia:Michael_jackson’, and the predicate and object are the entities ‘Dbpeida-owl:artist of’ and ‘Dbpedia:King_of_Pop(album)’. The value of an object can also be a text, such as the object of the third triple in Figure 2(a). An RDF document can be represented as an RDF graph [39]. For example, in Figure 2(a), 10 triples in an RDF document present an RDF graph that contains seven nodes and 10 directed links. The nodes are entities in the document, and the links are the relationships between them. In Figure 2, the first triple can generate a directed link named ‘Dbpedia-owl:artist of’ from the node named ‘Dbpedia:Michael_jackson’ to the node named ‘Dbpedia:king_of_Pop(album)’ (please note that, the concepts of RDF document and RDF graph are considered as the same, and are used interchangeably in this paper). An entity in linked data is described by a set of predicates and objects. Therefore, in keyword-based entity search engines, an entity is modelled with an RDF document that contains the triples or quads about the entity [13, 14]. If an RDF document contains the query, the document will be returned as the search result. In the data pre-processing stage, keyword-based entity search engines partition the whole linked data into RDF documents, each of which contains the triples about an entity. There are three ways to model the entities into the RDF graphs (documents): star-shaped, multi-shaped and context-shaped graphs.

Figure 2.

An example of an RDF data and the RDF graph of this data.

Definition 1: A star-shaped graph is a graph structure that describes an entity by its subject.

For example, the dataset in Figure 2(a) can generate three RDF graphs for ‘Dbpedia:michael_jackson’, ‘Dbpedia:king_of_Pop(album)’ and ‘Dbpedia:Barry_White’, as in Figure 3. The RDF graph for ‘Dbpedia:michael_jackson’ is obtained by extracting all the triples with the subject: ‘Dbpedia:michael_jackson’.

Figure 3.

Star-shaped graphs obtained from Figure 2(a).

Definition 2: A multi-shaped graph is a graph structure that describes an entity by its subject or object.

For example, the dataset in Figure 2(a) can generate eight multi-shaped RDF graphs for all of the entities in Figure 4. The multi-shaped RDF graph for ‘Dbpedia:michael_jackson’ contains six triples for the entity ‘Dbpedia:michael_jackson’. In contrast to the star-shaped graph in Figure 3, the four triples refer to the same subject ‘Dbpedia:michael_jackson’, and the two triples refer to the entity ‘Dbpedia:michael_jackson’ as the object.

Figure 4.

Multi-shaped graphs obtained from Figure 2(a).

Definition 3: A context-shaped graph is a graph structure that contains all the triples in the same context.

For example, a context-shaped graph generated from Figure 2(a) contains all of the triples in the same provenance (context) ‘Dbpedia’ defined by the authors, and the graph will look like the RDF graph in Figure 2(b). A data supplier may define contexts for partitioning the whole dataset into different groups for diverse purposes. For example in BTC 2009, the entities ‘Dblp:Feitelson03’ and ‘Dblp: FenstermacherG02’ have the same context ‘swetodblp:swetodblp_march_2007_part_22.rdf’, since their provenance is ‘swetodblp:swetodblp_march_2007_part_22.rdf’. The entity ‘Dblp:EvjeF06’ and the entity ‘ Dblp:FengK05’ have the same context ‘ DBlp:jscic’, which is the journal where the two entities (articles) are published. Therefore, an entity can be in different context graphs. For example, the entity ‘Dblp:ColeZ04a’ can be contained in two context graphs: ‘Dblp: jscic’ and ‘DBlp: ColeZ04a’. We will discuss the context of the RDF documents in Section 5.3 in detail.

3.2. Keyword-based entity indexing and search

The inverted index has been widely used in information retrieval (IR), and there has been much interest from the semantic community in using the inverted index for searching RDF documents [14]. Generally, IR uses either the VSM or probabilistic models to index and search Web pages [14]. In the conventional VSM, RDF documents are represented as vectors of terms. A term weight indicating the importance of the term in the vector is computed by the Term Frequency–Inverse Document Frequency (TF-IDF). Some approaches have adapted the TF-IDF for calculating term weights in RDF documents: Siren uses the Term Frequency–Inverse Source Frequency (TF-ISF) and indexes RDF data based on a node-indexing scheme [16].

We adapted the node-indexing of Siren to index the RDF documents generated (stage 3 in Figure 1). The subject of an RDF document generated in Section 3.1 is not its identifier. For example, the subject ‘Dbpedia:michael_jackson’ is not the identifier of the RDF document 2 in Figure 4. Therefore, we have changed the TF-ISF for a star-shaped graph into the Term Frequency–Inverse RDF document Frequency (TF-IRF) to accommodate the multi-shaped and context-shaped graphs. The TF-IRF weighting scheme assigns to a term $t$ a weight in an RDF document $r$ using the following formula:

t f . i r f (t, r) = t f_{t, r} \times i r f_{t}

(1)

where $t f_{t, r}$ is the term frequency of the term $t$ in the RDF document $r$ , and

t f_{t, r} = \frac{# t i n R D F d o c u m e n t r}{# t e r m s i n R D F d o c u m e n t r} \cdot i r f_{t}

is the inverse RDF document frequency, and

ir f_{t} = \log \frac{# RDF documents}{# RDF documents contained t}

A query is converted into a vector that is used to compute the similarities between the vectors of RDF documents based on TF-IRF. Given a Boolean query $q$ , the ranking score of an RDF document $r$ is inherited from the equations in Delbru et al. [16] as follows:

score (q, r) = \sum_{p_{i} \in P} score (q, p_{i}) \times spread (q, r)

(2)

where $p_{i}$ is a predicate that exists in a predicate set $P$ in the RDF document $r$ . $spread (q, r)$ is a normalization factor that prefers the RDF document matched terms in one object. $spread (q, r)$ is calculated as:

spread (q, r) = \frac{(| q | - | O |) + 1}{| q |}

(3)

where $| q |$ is the number of the terms in the query, and $| O |$ is the number of the objects matching at least one term in the query. For example, searching the RDF documents in Figure 3 with the query ‘Michael Jackson’, $spread (q, r)$ of the predicate ‘Dbpedia-owl:abstract’ in the star-shaped RDF document 1 of the entity ‘Dbpedia:michael_jackson’ is

\frac{(2 - 1) + 1}{2} = 1

$score (q, p_{i})$ in equation (2) is a ranking score based on the predicate $p_{i}$ , and is calculated as:

score (q, p_{i}) = \sum_{o_{j} \in O_{i}} score (q, o_{j})

(4)

where $o_{j}$ is an object in the object set $O_{i}$ for the predicate $p_{i}$ and $score (q, o_{j})$ . is calculated as:

score (q, o_{j}) = \sum_{t \in q} t f_{t, o_{j}} . irf (t, r)

(5)

where $t f_{o_{j}}$ is the term frequency $t$ in $o_{j}$ . Different graphs may obtain different scores for the same entity. For example, with the same query $q$ ‘Michael Jackson’, the star-shaped document $r$ of ‘Dbpedia:michael_jackson’ in Figure 3 has only one triple containing the query, that is, the value of the predicate $p_{1}$ ‘Dbpedia-owl:abstract’. Therefore, $score (q, r) = score (q, p_{1}) \times spread (q, r)$ , where $spread (q, r) = 1$ , which we already obtained in the example of equation (3). The query is constituted of two terms that are ‘Michael’ and ‘Jackson’, hence $score (q, r) = 2 \times \frac{1}{4} \times \log \frac{3}{1} = 0.239$ . Similarly, the scores of the multi-shaped document of ‘Dbpedia:michael_jackson’ is $score (q, o) = 2 \times \frac{1}{6} \times \log \frac{8}{1} = 0.301$ in Figure 4 and the context-shaped graph of ‘Dbpedia’ $score (q, o) = 2 \times \frac{1}{10} \times \log \frac{1}{1} = 0.0$ in Figure 2(b).

3.3. PFC for discovering and ranking of expansion entities

Entities are connected by links in Linked Data. To find expansion entities for a query, we developed an algorithm (PFC) that discovers expansion entities based on the returned RDF documents with a query in Siren and two importance measures (stage 4 in Figure 1). First, the top K RDF documents will be obtained by Siren with the given keyword query (line 1 in Algorithm 1). Second, all the entities in each RDF document will be extracted (lines 2 and 3). There is a special entity called the anchor entity that contains any term of the query in its URL (line 4). In the ongoing example, three RDF documents containing the query ‘Michael Jackson’ will be found in Figure 3, and the entity ‘DBpedia:michael_jackson’ is considered as the anchor entity. Given an anchor entity, we assume that an entity is potentially important if there is a link that connects it with the anchor entity. Hence, our efforts are directed towards discovering candidate expansion entities that have links to anchor entities. Third, for each returned document, the entities connected to an anchor entity are collected as candidate expansion entities (lines 5 and 6). The candidates are sorted by the two importance measures (line 7). Finally, the top N candidates are returned as expansion entities.

Algorithm 1.

The process for discovering important entities

Input: keyword query

q

, Index, top

K

documents, top

N

Output: List

I_{e}

D_{Top} \leftarrow

Get top

K

documents based on index using a query

q

;

2. for all

d \in D_{Top}

E_{n} \leftarrow

All entities inside the document

d

;

A_{m} \leftarrow

anchor entities in

d

;

5. for all

e \in E_{n}

6. if

e

links to any of the anchor entities of

A_{m}

then

7. Compute importance of

e

;

I_{e} \leftarrow e

;

I_{e} \leftarrow

sort

I_{e}

by importance;

10. return top

N

I_{e}

;

There are two importance measures attached to an entity: global and local [8]. The global importance measure for an entity denotes the amount of authority that the entity obtains from authority teleporting in PageRank, and the number of documents containing the entity in the global graph (i.e. the whole corpus). The local importance measure is the centrality inside a local graph formed by the returned top K RDF documents (graphs).

4. Expansion entity ranking algorithm in the PFC

Entity-ranking approaches consider the importance of entities in the global graph, and several variations of PageRank have been implemented for different ranking purposes. The scalability problems in these variations [40] will easily render their approaches infeasible when they process big datasets such as linked data. We adapted the original global PageRank for computing entity importance, since it cost the least amount of computation, compared with other variations [41 –45]. In addition, the document frequency of an entity is considered to be another global importance measure in the PFC. In contrast to global impornce measures, local importance measures are considered closer to queries [8]. The centrality value of an entity in a local graph is another importance measure in the PFC. In this study, we compute the importance of an entity using the global (global PageRank score and entity–document frequency) and local (centrality) importance measures, as shown in the equation as follows:

score (e_{i}) = α PR (e_{i}) + β Cen (e_{i}) + γ Freq (e_{i})

(6)

where $α$ , $β$ and $γ$ are used to control the influence of each measure in the equation, and $α + β + γ = 1$ .

4.1. Global importance

Given an RDF dataset, the subjects, predicates and objects are used to compute the global importance of the entities in the data. Two measures are used to evaluate the global importance of an entity, PageRank score and entity–document frequency.

To compute the PageRank score, a directed graph is constructed. First, the entities in subjects or objects will be used to form a set of nodes $E = {e_{1}, e_{2}, \dots, e_{m}}$ for the graph, where $e_{i}$ is an entity in the data. The texts in objects will be ignored to compute the PageRank. Second, all the predicates in the triples are equally used to form directed links between the entities in subjects and objects. For example, triple ‘<Dbpedia:Michael_jackson><Dbpedia-owl:artist of>< Dbpedia:king_of_Pop(album)>’ can create a directed edge from node ‘Dbpedia:Michael_jackson’ to node ‘Dbpedia:king_of_Pop(album)’. PageRank [46] utilizes the Random Surfer Model to calculate the importance of each entity. A surfer starts from a random entity $e_{i}$ of $E$ , and at each step, it either follows a link with a probability of $d$ or jumps to a random entity with the probability of $1 - d$ . The PageRank value of each entity is the probability $PR (e_{i})$ that the surfer stays in $e_{i}$ , which can represent the importance of the entity $e_{i}$ . PageRank computes the importance of the entity $e_{i}$ as follows:

PR (e_{i}) = \frac{1 - d}{m} + d \sum_{e_{j} \in in (e_{i})} \frac{PR (e_{j})}{| out (e_{j}) |}

(7)

where $in (e_{i})$ is a set of inbound entities of $e_{i}$ , $| out (e_{j}) |$ is the number of outbound links of $e_{j}$ , and $m$ is the total number of entities.

The whole dataset is partitioned into RDF documents and indexed in an index $I$ introduced in Section 3.1. Therefore, an entity–document frequency of the entity $e_{i}$ is calculated as follows:

Fre q_{I} (e_{i}) = \frac{# documents contained e_{i}}{# documents}

(8)

where $# documents contained e_{i}$ is the number of RDF documents that contain the entity $e_{i}$ in the index $I$ . In practice, because of the size of linked data, the index $I = {I_{1}, I_{2}, \dots, I_{x}}$ is a set of indices. In order to distributed compute the entity–document frequency, we obtain this measure as follows:

Freq (e_{i}) = \sum_{I_{j} \in I} Fre q_{I_{j}} (e_{i})

(9)

4.2. Local importance

Given a set of graph-structured RDF documents $Doc = {do c_{1}, do c_{2}, \dots, do c_{k}}$ that contains a set of entities $E_{loc} = {e_{1,} e_{2}, \dots, e_{p}}$ and a set of links $L_{loc} = {l_{1,} l_{2}, \dots, l_{q}}$ , $E_{loc}$ and $L_{loc}$ constitute a local graph $G_{loc} = {E_{loc}, L_{loc}}$ , and are used to compute the centrality of each entity $e_{i}$ connected to anchor entities of $A = {a_{1}, a_{2}, \dots, a_{x}}$ in $G_{loc}$ , where $a_{x}$ is an anchor entity. The degree centrality is the number of links connected to an entity, and is used as the entity centrality, for the reason that it takes a shorter time to calculate a degree centrality than closeness or between centrality [47].

A standardized centrality is defined as follows:

Ce n_{G} (e_{i}) = \frac{\deg (e_{i})}{(# nodes in G) - 1}

(10)

where $\deg (e_{i})$ is the degree of $e_{i}$ in a graph $G$ . In real computations, the local graph $G_{loc}$ is big. In practice, we measure the local importance through distributed computations as follows:

Cen (e_{i}) = \sum_{do c_{j} \in Doc} w_{j} Ce n_{do c_{j}} (e_{i}) .

(11)

where $w_{j}$ is the Siren ranking score of the RDF document $do c_{j}$ , and $Ce n_{do c_{j}} (e_{i})$ is the standardized centrality of entity $e_{i}$ in $do c_{j}$ .

Figure 5 shows an example of discovering the expansion entities for a query ‘Michael Jackson’ with the star-shaped graphs in Figure 3. Three RDF graphs (documents) are found by the query. The entity ‘Dbpedia:michael_jackson’ that contains the query in its URL is considered as an anchor entity (shaped with the box). All other entities connected with the anchor entity ‘Dbpedia:michael_jackson’ are considered as the candidate expansion entities (shaped with the ellipses in solid line). All of the entities in the three RDF graphs form a local graph to compute the local importance of the candidate expansion entities. The ranking list of the candidates is sorted by the sum of the global importance values and the local importance value. The top N candidate entities are finally returned as the expansion entities for the query.

Figure 5.

An example of entity ranking.

5. Experiment and evaluation

5.1. Preparation

In evaluating our semantic query expansion approach, we used the Billion Triple Challenge 2009 (BTC 2009) (http://challenge.semanticweb.org/) as the dataset. For PageRank computation and RDF document indexing, a Hadoop (http://hadoop.apache.org/) cluster was used, which has one master and two slaves, based on a 12-core computing unit with a 300 Gb hard disk and 3 Gb RAM in a cloud environment. For local searches, an Intel I-5 CPU with 4 Gb RAM and a 1 Tb hard disk on a Windows XP system was used. The BTC 2009 was partitioned into star-shaped, multi-shaped, and context-shaped graphs for indexing. The context-shaped index, using the provenances or subjects supplied by BTC 2009, puts all the triples from the same origin or subject into one document. It should be noted that the context graphs are not universally applicable as the star- and multi-shaped indices, since not all linked datasets are published with the N-quads format. Table 1 shows our dataset and indices.

Table 1.

Statistics of datasets and index sizes

Data	Size
BTC2009 original (compressed)	17.46 Gb
Star-shaped index (compressed)	26.4 Gb
Context-shaped index (compressed)	27.3 Gb
Multi-shaped index (compressed)	54.6 Gb

5.2. Gold standard and query expansion approaches in comparison

The query expansion approaches in these experiments were evaluated based on the Yahoo! Semantic Challenge Test Data Sets (http://semsearch.yahoo.com/datasets.php). We chose Query Set #1 for entity search. Query Set #1 contains 50 queries (http://semsearch.yahoo.com/ﬁnal-entities-2011.txt) and the assessment file are downloaded from the Yahoo! Web scope (http://webscope.sandbox.yahoo.com/). We compared the PFC with four other approaches: the lexical-based approach (LS) that uses WordNet as a thesaurus, the query-specific statistical approach (QS) that uses co-occurrences based on an internal data [12], and the statistical approaches based on Web of documents: Okapi-inquery and the LM-tf [10]. The approaches are implemented as follows.

Language-specific (LS): Given a query, relevant concepts or terms are discovered by WordNet to expand into the query [21]. The Java API for WordNet Searching (JAWS) (http://lyle.smu.edu/tspell/jaws/index.html) is used. Hyponyms and hypernyms are extracted and sorted by the WordNet Similarity (http://code.google.com/p/ws4j/). An original query is expanded with the top N concepts (hyponyms and hypernyms).

Query-specific (QS): We adapted entity-entity co-occurrences [12], called query-specific (QS), for discovering expansion entities. We used Latent Semantic Indexing (LSI) [48] for building the entity–document matrix based on Pseudo-Relevance feedbacks [12]. Using the Java Matrix Package (JAMA) (http://math.nist.gov/javanumerics/jama/), entity–entity co-occurrences based on Singular Value Decomposition (SVD) [49] are calculated. The top N entities for each query based on the co-occurrence matrix are extracted as the expansion entities. In our experiment, we used the top 100 (QS_100) and 1000 (QS_1000) documents separately to get entity co-occurrence matrices.

Okapi-inquery and the LM-tf: The concepts used to expand a query are generated from Web of documents [10]. We implemented two methods that performed best in Halpin and Lavrenko [10]. We obtained the top K Web pages from a Web search engine, Bing (http://www.bing.com/toolbox/bingsearchapi), for each query. The top K Web pages can be represented by the VSM and a language model. With the VSM, most-related terms, in the top X Pseudo-relevant documents obtained by the Okapi method [50], are gained by sorting similarity values with a given query with the inquery function [51]. We call this method Okapi-inquery, and set the parameters as $K = 10$ ., $X = 5$ , $k_{1} = 2$ . and $b = 0.75$ . With the language model, the most-related terms, in the top X pseudo-relevant documents obtained by the cross entropy, are gained by sorting similarity values with a given query in the concatenated relevance model. We call this method LM-tf, and set the parameters as $K = 10$ , $X = 5$ and $ϵ = 0.2$ .

Our baseline results are gleaned from Siren using the original queries. The recall in IR increases as the number of query term increases. This makes the measure unsuitable for evaluating a query expansion method; hence, we evaluated the effectiveness by two kinds of precision (prevision at N and R-precision). We also evaluated running times and effectiveness using a different number of expansion entities.

5.3. Results

We ran the 50 queries with the six methods. The PFC read the Siren index and PageRank index from caches instead of reading from hard disks as shown in Figure 1. In order to fairly compare all the methods, we put the indices of the returned RDF documents from Siren and ontologies into caches. For the QS, we read the same Siren indices from the caches as the PFC does. For the LS, we installed a local database for WordNet, and cached all the concepts (hyponyms and hypernyms) used as candidate expansion concepts. Please note that we did not put the HTML documents used in Okapi-inquery and the LM-tf into caches, since the documents were obtained based on the search results of Bing dynamically. Figure 6 shows the details on the average running times of the 50 queries. The execution times of the LS (with the average of 76.14 ms) are much shorter than those of the PFC (248.46 ms), QS_100 (720.91 ms), QS_1000 (49163.2 ms), Okapi-inquery (24840.58 ms) ahe LM-tf (248455 ms). The PFC is quicker than the QS_100, and they are both much faster than the QS_1000. Okapi-inquery runs as fast as the LM-tf, and both are roughly twice as fast as QS_1000. The LS only requires a visit of the local WordNet database, which takes a very short time. The PFC considers three ranking scores for each candidate expansion entity: PageRank score, entity–document frequency and centrality. PageRank scores and entity–document frequencies are obtained from the PageRank index and the main RDF documents index, which are both pre-computed offline. The most on-the-fly time spent by the PFC is constructing a local graph based on returned RDF documents. A centrality computation in the local graph, generated with the search results of Siren for each query, needs comparably more time than reading of PageRank scores and entity–document frequencies from the indices, but requires less time than computations of the SVD used in the QS (100 and 1000) methods. The QS obtains expansions based on Pseudo-Relevance feedbacks, and the more documents are used, the more time is spent on the computation of the SVD. The PFC has an advantage that the online computations of the PFC are much lighter than those of the QS. Okapi-inquery and the LM-tf generate expansion concepts based on the VSM and the language model, which also need small computations on-the-fly. However, different from the other four methods, these two methods obtain expansions based on the results from a Web search engine, and need to send HTTP requests to obtain HTML documents on-the-fly. Therefore, as we mentioned, the efficiencies of Okapi-inquery and the LM-tf can be hardly improved using cashes since it is not practical to pre-cache the indices of the contents of the HTML documents returned from a Web search engine.

Figure 6.

Running times of the six approaches for 50 queries.

We evaluated our approach using Terrier (http://terrier.org/). We followed the Terrier precision evaluation (http://terrier.org/docs/v3.5/evaluation.html), which checks the precision at N- and R-precision. We ran the 50 queries on the five query expansion approaches and the baseline approach with the three types of indices. For each query on an expansion method, we used the top one to five expansions to expand the original query. We compare the best search results of the expansion methods in Table 2.

Table 2.

The precisions at N- and R-precisions of all the algorithms for the three indices

Graph types		PFC	Okapi-inquery	LM-tf	LS	QS_1000	QS_100	Baseline
Multi-shaped	P@5	0.1957	0.2043	0.2	0.1522	0.1304	0.1652	0.1826
	P@10	0.1674	0.1435	0.1587	0.1196	0.1087	0.1348	0.1435
	P@20	0.1109	0.113	0.1163	0.0946	0.1	0.0957	0.112
	Average	0.2405	0.1734	0.2016	0.1216	0.1496	0.153	0.1736
Star-shaped	P@5	0.1913	0.1739	0.1913	0.1391	0.113	0.1565	0.187
	P@10	0.1348	0.1326	0.1348	0.1022	0.1043	0.113	0.134
	P@20	0.1011	0.087	0.0902	0.0674	0.0891	0.0848	0.0957
	Average	0.1155	0.1147	0.1036	0.0615	0.0572	0.0857	0.1071
Context-shaped	P@5	0.1913	0.1783	0.1739	0.1261	0.1217	0.1435	0.1609
	P@10	0.1348	0.1391	0.1326	0.0978	0.1043	0.113	0.1348
	P@20	0.0946	0.0946	0.0924	0.0663	0.0793	0.0848	0.0935
	Average	0.1663	0.1507	0.1522	0.0984	0.0839	0.1302	0.1439
Multi-shaped	P@0.1	0.5074	0.4315	0.4715	0.3302	0.2805	0.3577	0.4206
	P@0.2	0.3261	0.2911	0.306	0.2254	0.2442	0.2722	0.3182
	P@0.5	0.1698	0.1399	0.1384	0.093	0.1288	0.1459	0.153
	RP	0.1488	0.1542	0.1514	0.1195	0.1522	0.1286	0.1507
Star-shaped	P@0.1	0.4697	0.3715	0.4278	0.2974	0.2589	0.3374	0.4127
	P@0.2	0.2577	0.2255	0.1943	0.1246	0.1501	0.1951	0.2521
	P@0.5	0.0929	0.0714	0.0551	0.0387	0.0396	0.0622	0.0722
	RP	0.1118	0.1402	0.1323	0.0884	0.0885	0.1149	0.1073
Context-shaped	P@0.1	0.4032	0.4297	0.4325	0.268	0.2402	0.3078	0.4016
	P@0.2	0.2699	0.2729	0.261	0.1811	0.1503	0.2133	0.2629
	P@0.5	0.1233	0.1317	0.1131	0.0897	0.0704	0.1348	0.093
	RP	0.1507	0.15	0.1406	0.1052	0.084	0.1217	0.138

As Table 2 shows, the PFC ( $α = 0.6, β = 0.4, γ = 0.0$ ) receives the best query results from the three index structures. The experiments show that the PFC improves precision by 6.6, 0.8 and 2.2% from the baseline using the multi-shaped, star-shaped and context-shaped structures, respectively. Okapi-inquery (0.0, 0.8 and 0.7%) and the LM-tf (2.8, −0.4 and 0.8%) show a slight precision improvement. The LS (−4.8, −4.0 and −4.6%), QS_100 (−2.4, −5.0 and −6.0%) and QS_1000 (−2.0, −2.1 and −1.4%) search results reduce the search performance.

Table 3 shows one example of the expansions for the #9 query ‘ashley wagner’ in which the PFC is compared with the others. The original query ‘ashley wagner’ obtains one relevant entity ‘Dbpedia:Ashley_Wagner’ from the multi-shaped graph. With the expansion entity ‘Sioc:types#WikiArticle’, the PFC obtains one more relevant entity ‘wikipedia:Ashley_Wagner’. The LS provides the concepts related in WordNet, but not the terms related in the query in the BTC 2009. For example, ‘ashley wagner’ used in the #9 query is an American figure skater, and the concepts, such as ‘music’ used to expand the query in the LS, are not related to ‘ashley wagner’. Expanding the original query with non-related concepts will lead to non-relevant entities. In this example, expanded query ‘ashley wagner music’ returns no relevant entity. Since entities of the BTC 2009 are mostly extracted from the Web, using the Web as an external corpus performs better than WordNet in our experiments. For example, the #4 query ‘New England Coffee’ obtains zero relevant entity in entity search. With the query expanded with the concepts (‘page’ and ‘menu’) extracted from the Web, Okapi-inquery and the LM-tf obtain one relevant entity, ‘Dbpedia:The_21’s_Coffee_bar’. Using the Web of documents is heavily relied on for the results of Web search engines. The results of a Web search frequently change, which means that, for each query, concepts obtained by Okapi-inquery and the LM-tf for expanding queries vary greatly with Web search results. Therefore, the performances of these two methods are not as stable as the other methods. For example, the top 1 expansion concept of Okapi-inquery for the #1 query ‘08 Toyota tundra’ changes from ‘toyota’ to ‘cars’ in 4 weeks, from 18 August 2014 to 23 September 2014, in our experiment. The QS cannot find good expansions for the queries. Unlike the Web of documents, Linked Data contains a candidate entity occurring only once in a returned RDF graph, which decreases the importance of highly co-occurring entities inside the document and does not reflect the correlation between the candidate and the query. For example, ‘Wikipedia: User:Ashley_Pomeroy’ and ‘Dbpedia:Robert_Wagner’ obtained by the QS are two names that are not related to ‘ashley wagner’. The QS_100 achieves comparatively better results than the QS_1000, which demonstrates that the more entities are used to compute co-occurrences, the worse the expansion entities that are obtained.

Table 3.

The expansions of different approaches for the #9 query ‘ashley wagner’ in multi-shaped graph

Rank	PFC	Okapi-inquery	LM-tf	LS	QS_100	QS_1000
1	Sioc:types#WikiArticle	ashley	ashley	Music	Wikipedia:User:Ashley_Pomeroy	Dbpedia:Robert_Wagner
2	Dbpedia:Richard_Wagner	wagner	wagner	Wager	Wikipedia:Ashley_Hammond	Dbpedia:Honus_Wagner
3	Foaf:Person	free	site	tto Wager	Dbpedia:Wagner_(surname)	Wikipedia:Ashley_Pomeroy
4	Dbpedia:Ashley_Wagner	date	world	Richard Wagner	Sioc:Ashley_Hammond	Dbpedia:Ashley_Fisher
5	Dbpedia:Ashley_Tisdale	world	fs	Wilhelm Richard Wager	Dbpedia:Ashley_(name)	Dbpedia:Anthony_Ashley-Cooper,_1st_Earl_of_Shaftesbury

We also observe that the multi-shaped index is the best structure for entity search (baseline) and query expansion (PFC), compared with the others. Both baseline and the PFC achieve better precision with the multi-shaped index, as shown in Figure 7. This can be explained by the content of the structures: the multi-shaped graph contains both inbound and outbound entities, which causes a higher inverse RDF document frequency and a lower term frequency than the other two structures. For example, with the query ‘Michael Jackson’ to search the RDF documents in Figure 5, the $score (q, o)$ for the star-shaped RDF document ‘Dbpedia:michael_jackson’ is $2 \times \frac{1}{4} \times \log \frac{3}{1} = 0.239$ , but the $score (q, o)$ for the multi-shaped RDF document ‘Dbpedia:michael_jackson’ is $2 \times \frac{1}{6} \times \log \frac{8}{1} = 0.301$ . The multi-shaped graph obtains better results with the same ranking function than the star-shaped graph. For example, the multi-shaped graph obtains three relevant entities (Dbpedia:Madrid, Dbpedia:Madrid_Metro, and Dbpedia:Real_Madrid_C.F.) for the query ‘MADRID’ in the top five returned entities, but the star-shaped graph only obtains one relevant entity (Dbpedia:Madrid). The context-based structure, which puts all entities under the same context into an RDF document, increases the probability of finding relevant documents. The context-based graph has a higher chance of finding relevant documents; however, there can be cases in which relevant RDF documents can be returned with irrelevant names. For example, when searching the context-based graphs with the #1 query ‘08 Toyota tundra’, only four relevant documents, ‘Dbpedia:Toyota_Tundra’, ‘Dbpedia: List_of_Toyota_vehicles’, ‘Dbpedia: Toyota_Tundra_200’ and ‘Opencyc:ToyotaTundraCar’, are returned. The RDF document about the relevant HTML page ‘http://richmond.craigslist.org/pts/1100468361.html’ is returned with an irrelevant name ‘http://richmond.craigslist.org/pts/index.rss’. Therefore, even when the RDF document about the ‘http://richmond.craigslist.org/pts/1100468361.html’ is found by the search, it is still considered as irrelevant because it is named after an irrelevant entity name ‘http://richmond.craigslist.org/pts/index.rss’ instead of a relevant entity name ‘http://richmond.craigslist.org/pts/1100468361.html’. We observed that HTML pages and videos are unlikely to be found with context-shaped graphs for this reason. For query expansion, we learned that diverse performances of different graphs are caused by two reasons. The first is that the more candidate entities are used, the higher chance is of finding good expansion entities. For example, with the query ‘08 Toyota tundra’, the multi-shaped graph obtained 13313 candidate expansion entities, the context-shaped graph 9340 entities, and the star-shaped graph 3297 entities. The entity ‘Opencys:ToyotaTundraCar’ that can improve search can only be obtained by the multi- and context-shaped graphs. The second is that inbound entities are as important as outbound entities. Outbound entities lead to the entities that share the same expansion entities with the anchor entities, which could potentially cause a search shift into irrelevant entities. However, inbound entities either lead in the multi-shaped graphs towards the entities that share the same expansion entities with the anchor entities, or the search stops. For example, in the multi-shaped graph, the query expanded with the inbound entity ‘Dbpedia:Lexus_LS’ returns the relevant entity ‘Dbpedia_Toyota_Tundra’, and the same query expanded with another inbound entity ‘Opencys:ToyotaTundraCar’ returns the same inbound entity that is relevant to the query.

Figure 7.

Average precisions of the PFC for the three different indexing structures.

We also evaluated the query outcomes by the number of expansion entities. As shown in Table 4, the improvement in search decreases as the number of expansion entities used increases. The best results are obtained when queries are expanded only with the top one candidate expansion entity. We consider that this phenomenon is caused by a search drift: the larger the number of entities used to expand a query, the higher the possibility is that the search will drift to other topics. This differs from what commonly would be expected, that the more query words the user enters, the more likely it is that the search system will be able to determine the user’s intention. The automatic query expansion tends to improve precision by restricting the number of expansions for the effect of a search drift.

Table 4.

Precisions of the different number of expansions in different index structures

Number of expansions	Multi-shaped	Star-shaped	Context-shaped
1	0.2405	0.1155	0.1663
2	0.2209	0.1021	0.1547
3	0.2239	0.0967	0.1508
4	0.2000	0.0892	0.1471
5	0.1702	0.0843	0.1376

5.4. Parameters of importance measures

We tested various combinations of PageRank scores, centrality and entity–document frequency parameters in the PFC using the multi-shaped index. Precisions of expanded queries are indicated by the node sizes in Figure 8, with bigger nodes denoting higher precisions. We learned that the centrality and PageRank play relatively important roles in achieving improvements in semantic query expansion.

Figure 8.

Distribution of average precisions in the different parameter combinations.

PageRank plays the most important role in increasing precision. We find that, for the high precisions shown in Figure 9 (a dimensionally reduced version of Figure 8), $γ$ in equation (6) does not contribute, resulting in $α + β = 1$ , where $α \geq 0.5$ .

Figure 9.

The precision distribution based on PageRank and centrality after filtering unsatisfactory experimental results.

6. Important links for extracting the entities to expand the query

In Linked Data, link types (predicates or properties) provide varying effects on ranking algorithms. Analysis of effects imposed by link types will help users form valuable intuitions about them, and in turn, help personalize entity discovery by tracing a few important link types. We analysed the significance of each link type on global importance values and local importance value. We counted the frequency of each link type when it generated an expansion entity that belongs to one of the top N best expansion entities for each query by using one single importance value – PageRank, centrality or entity–document frequency.

Table 5 shows the top 10 most important link types for expanding the 50 queries, where N = 20. As Table 5 shows, expansion entities from ‘Dbpedia:wikiPageUsesTemplate’ with entity–document frequency as the importance measure achieve the best results in 41 queries. Expansion entities from ‘Foaf:page’ with centrality and PageRank as importance measures achieve the best results in 40 (centrality) and 39 (PageRank) queries. In general, the most important predicates are almost the same and are from DBpedia.

Table 5.

Top 10 most important link types for expansion using precision

Entity–document frequency		Centrality		PageRank
Entity	Frequency	Entity	Frequency	Entity	Frequency
Dbpedia:property/wikiPageUsesTemplate	41	Foaf:page	40	Foaf:page	39
Foaf:page	38	Dbpedia:property/wikiPageUsesTemplate	37	Dbpedia:property/wikiPageUsesTemplate	34
Dbpedia: property/location	29	Dbpedia: property/location	29	Dbpedia:property/birthPlace	32
Dbpedia:property/redirect	29	Dbpedia:property/birthPlace	28	Dbpedia:property/redirect	30
Dbpedia:property/birthPlace	28	Dbpedia:property/redirect	28	Dbpedia: property/location	27
Dbpedia:ontology /birthplace	17	Dbpedia:ontology /birthplace	16	Dbpedia:ontology /birthplace	16
Sioc:links_to	14	Sioc:links_to	14	Sioc:links_to	15
Dbpedia:ontology/type	14	Dbpedia:ontology/type	14	Dbpedia:ontology/type	14
Dbpedia:ontology/occupation	13	Dbpedia:property/settlementType	11	Dbpedia:property/settlementType	13
Dbpedia:property/settlementType	11	Dbpedia:property/cityServed	11	Dbpedia:property/hometown	10

7. Identifying the best properties for modelling the expanded query

An entity is indistinct, thus needs to be identified by its URL or represented by values of properties such as ‘Rdf:type’ and ‘Rdf:label’. Given expansion entities, an issue arises of how to model an expanded query with the expansion entities [52]. Searches with a query expanded with different values of predicates can perform differently. For example, category-based expanded queries outperform term-based expanded queries for probability-based entity search in the INEX Entity Ranking track 2007 and 2008 [52]. Entities in Linked Data have a more complex structure than entities in INEX Entity Ranking track (http://www.inex.otago.ac.nz/tracks/entity-ranking/guidelines.asp). In this section, we discuss which property achieves better precision for expansion. We have modelled six types of expanded query with the most frequently used properties of the top 1 candidate expansion entities found by the PFC, which are query+URL, query+‘RDF:type’, query+‘name’, query+‘Owl:SameAs’, query+‘RDF:label’ and query+‘subject’. We compared the six different types of expanded queries with the parameter values $α = 0.6, β = 0.4, γ = 0.0$ in the PFC for the 50 queries using the multi-shaped index.

Figure 10 shows the search improvement attributed to the six different properties. The URLs provide the highest precision for the 50 queries, and are proved to be the best property to expand the query in our study. Entity names and ‘Rdf:Label’ also show satisfactorily positive improvement, with a slight drawback of adding more terms than necessary, compared with the URL. Our results show that ‘Rdf:type’ and ‘subject’ are not suitable for expanding the query.

Figure 10.

The improvements attributed to the six different properties in query expansion.

8. Discussion

There are several limitations in this study that need to be further studied:

Function of anchor entities – as the results of Section 5.3 show, the more candidate expansion entities are used, the better are the results that can be achieved by the PFC. However, more candidate entities require more importance measures. In the PFC, anchor entities are used to restrict the scope of candidate expansion entities. A good anchor entity should be capable of covering the best candidate expansion entities in a small scope of importance measuring. We defined an anchor entity as an entity containing any term of a query in its URL. It is possible that an anchor entity defined in the PFC explores bad candidate expansion entities for a query. For example, in the query #9 ‘ashley wagner’, the anchor entity ‘Dbpedia:Ashley_Tisdale’, an American actress, relates to entities that are not good for expanding ‘ashley wagner’, who is an American figure skater. A more advanced judgement of anchor entities can be achieved by checking properties that have semantic meanings of an entity, such as ‘Rdf:label’ and ‘RDF:type’. However, this raises three questions to be answered: (a) how to utilize properties to judge anchor entities with quantitative measures; (b) how to obtain all properties of entities in the returned RDF documents in a scalable time; and (c) whether the efficiency is improved with a new judgement method of anchor entities. Our future work aims improve the efficiency of the PFC with better anchor entities by answering these questions.

Role of the entity–document frequency – for the BTC 2009, the PFC shows high precision using the importance parameters with high weights for PageRank and centrality. However, the frequency computed with distributed computations is not normalized, which could potentially imbalance the three measures. Therefore, the importance of using entity–document frequency can be underestimated by the PFC, since the entity–document frequency is considered an important factor for discovering entities [53 –55]. A normalized entity–document frequency could improve the search as we considered. Moreover, IDF [55], and residual IDF (RIDF) [54] can help increase the weight proportions in global importance to achieve better precision, which this study leaves as another potential improvement for the future.

Combinations of parameters for the importance measures – query shifting [17] is a difficult issue in the field of query expansion and semantic query expansion is no exception. We use different combinations of PageRank value, centrality, and entity–document frequency within our algorithm to determine the best parameters, and we are currently considering how to use a heuristic algorithm to help automatically obtain the best combination. In our future work, we will explore paths such as personalized query expansion by tracing more important link types, discussed in Section 6. We will also focus on improving search results with the help of user profiles and historical search records.

9. Conclusions

In this study, we introduced a framework that presents efficient and effective ways to discover expansion entities in Linked Data by formalizing an expanded query for keyword-based entity search. Instead of computing co-occurrences or using ontology, we trace links in local graphs to find candidate expansion entities and rank them by global and local importance measures.

The PFC explores candidate expansion entities from local graphs, which are more related to the query, instead of global corpus or ontologies. In addition, the global and local importance measures are better for ranking entities than insufficiently computing co-occurrences with the flat data structure used by keyword-based entity search engines. Our experiment demonstrates that the PFC performs better on precision than existing query expansion methods. Two important issues inherent in Linked Data are also addressed: (a) roles of link types in discovering expansions are presented; and (b) application of URL or entity name as expansions is also discussed.

Footnotes

Funding

This work was supported by the Industrial Strategic Technology Development Program (10044494, WiseKB: Big data based self-evolving knowledge base and reasoning platform) funded by the Ministry of Science, ICT & Future Planning (MSIP, Korea), and in part by Professor Overseas Research Support Enterprise of LG Yonam Cultural Foundation.

References

Parundekar

Ambite

Knoblock

(eds). Aligning unions of concepts in ontologies of geospatial linked data. In: Proceedings of the terra cognita 2011 workshop in conjunction with the 10th international semantic web conference, Bonn, Germany, 2011.

Prud’Hommeaux

andSeaborne

. SPARQL query language for RDF. W3C Recommendation 2008; 15.

Bron

Balog

de Rijke

. Example based entity search in the web of data. In: Advances in information retrieval. Berlin: Springer, 2013, pp. 392–403.

Blanco

Mika

Vigna

. Effective and efficient entity search in RDF data. In: The Semantic Web – ISWC 2011. Berlin: Springer, 2011, pp. 83–97.

Ding

Finin

Joshi

Pan

Cost

Peng

. (eds). Swoogle: A semantic web search and metadata engine. In: Proceedings of the 13th ACM conference on information and knowledge management, 2004.

Oren

Delbru

Catasta

Cyganiak

Stenzhorn

Tummarello

. Sindice. com: A document-oriented lookup index for open linked data. International Journal of Metadata, Semantics and Ontologies. 2008;3(1):37–52.

Cheng

. Falcon-S: An ontology-based approach to searching objects and images in the Soccer domain. Supplemental Proceedings of ISWC, 2006.

Croft

(eds). Query expansion using local and global document analysis. In: Proceedings of the 19th annual international ACM SIGIR conference on research and development in information retrieval,. New York: ACM, 1006.

Carpineto

Romano

. A survey of automatic query expansion in information retrieval. ACM Computing Surveys (CSUR) 2012; 44(1): 1.

10.

Halpin

Lavrenko

. Relevance feedback between hypertext and Semantic Web search: Frameworks and evaluation. Web Semantics 2011; 9(4): 474–489.

11.

Stenmark

. Query expansion using an intranet-based semantic net. In: Proceedings of IRIS-26, 2003.

12.

Natsev

Haubold

Tešić

Xie

Yan

(eds). Semantic concept-based query expansion and re-ranking for multimedia retrieval. In: Proceedings of the 15th international conference on multimedia. New York: ACM, 2007.

13.

Delbru

Campinas

Tummarello

. Searching web data: An entity retrieval and high-performance indexing model. Web Semantics: Science, Services and Agents on the World Wide Web 2012; 10: 33–58.

14.

Blanco

Halpin

Herzig

Mika

Pound

Thompson

. (eds). Entity search evaluation over structured web data. In: Proceedings of the 1st international workshop on entity-oriented search workshop (SIGIR 2011). New York: ACM, 2011.

15.

Zong

Yang

Namgoong

Kim

H-G

. Discovering and ranking new links for linked data supplier. In: The Semantic Web. Berlin: Springer, 2012, pp. 358–365.

16.

Delbru

Rakhmawati

Tummarello

(eds). Sindice at SemSearch 2010. In: Proceedings of the 19th international World Wide Web conference, Raleigh, NC, 2010.

17.

Jones

Rey

Madani

Greiner

(eds). Generating query substitutions. In: Proceedings of the 15th international conference on World Wide Web. ACM: New York, 2006.

18.

Maron

Kuhns

. On relevance, probabilistic indexing and information retrieval. Journal of the ACM 1960; 7(3): 216–244.

19.

Bhogal

MacFarlane

Smith

. A review of ontology based query expansion. Information Processing and Management 2007; 43(4): 866–886.

20.

Voorhees

(ed.). Query expansion using lexical-semantic relations. In: SIGIR’94. Berlin: Springer, 1994.

21.

Navigli

Velardi

(eds). An analysis of ontology-based query expansion strategies. In: Proceedings of the 14th European conference on machine learning, workshop on adaptive text extraction and mining, Cavtat-Dubrovnik, Croatia, 2003.

22.

Gong

Cheang

(eds). Multi-term web query expansion using WordNet. In: Database and expert systems applications. Berlin: Springer, 2006.

23.

Liu

Meng

(eds). An effective approach to document retrieval via utilizing WordNet and recognizing phrases. In: Proceedings of the 27th annual international ACM SIGIR conference on research and development in information retrieval. New York: ACM, 2004.

24.

Song

I-Y

Allen

. Integration of association rules and ontologies for semantic query expansion. Data & Knowledge Engineering 2007; 63(1): 63–75.

25.

Hsu

C-C

Y-T

Chen

Y-W

S-H

. Query expansion via link analysis of wikipedia for clir. In: Proceedings of NTCIR-7, 2008.

26.

Luk

WPR

KSE

Chung

FLK

(eds). Improving weak ad-hoc queries using wikipedia asexternal corpus. In: Proceedings of the 30th annual international ACM SIGIR conference on research and development in information retrieval. New York: ACM, 2007.

27.

Jones

Wang

(eds). Query dependent pseudo-relevance feedback based on wikipedia. In: Proceedings of the 32nd international ACM SIGIR conference on research and development in information retrieval. New York: ACM, 2009.

28.

Bai

Nie

J-Y

Cao

Bouchard

(eds). Using query contexts in information retrieval. In: Proceedings of the 30th annual international ACM SIGIR conference on research and development in information retrieval. New York: ACM, 2007.

29.

Shen

Sun

J-T

Yang

Chen

(eds). Building bridges for web query classification. In: Proceedings of the 29th annual international ACM SIGIR conference on research and development in information retrieval. New York: ACM, 2006.

30.

Wang

Davison

(eds). Explorations in tag suggestion and query expansion. In: Proceedings of the 2008 ACM workshop on Search in social media. New York: ACM, 2008.

31.

Jones

Abdelmoty

. Ontology-based spatial query expansion in information retrieval. In: On the move to meaningful internet systems 2005: CoopIS, DOA, and ODBASE. Berlin: Springer, 2005, pp. 1466–1482.

32.

Jain

Thao

Zhao

. Enhancing electronic medical record retrieval through semantic query expansion. Information Systems and e-Business Management 2012; 10(2): 165–181.

33.

Álvarez

Labra

Calmeau

Marín

. Query expansion methods and performance evaluation for reusing linking open data of the European public procurement notices. In: Advances in artificial intelligence. Berlin: Springer, 2011, pp. 494–503.

34.

Gottipati

Jiang

(eds). Linking entities to a knowledge base with query expansion. In: Proceedings of the conference on empirical methods in natural language processing. Association for Computational Linguistics, 2011.

35.

Diaz

Metzler

. Improving the estimation of relevance models using large external corpora. In: Proceedings of the 29th annual international ACM SIGIR conference on research and development in information retrieval, Seattle, WA. New York: ACM, 2006, pp. 154–161.

36.

Aleman-Meza

Halaschek-Wiener

Arpinar

Sheth

(eds). Context-Aware Semantic Association Ranking. In: SWDB. Citeseer, 2003.

37.

Freitas

Oliveira

O’Riain

Curry

Da Silva

JCP

. Querying linked data using semantic relatedness: A vocabulary independent approach. In: Natural language processing and information systems. Berlin: Springer, 2011, pp. 40–51.

38.

Poggi

Lembo

Calvanese

De Giacomo

Lenzerini

Rosati

. Linking data to ontologies. Journal on Data Semantics 2008; X: 133–173.

39.

Klyne

Carroll

. Resource description framework RDF: Concepts and abstract syntax, 2004.

40.

Bahmani

Chakrabarti

Xin

(eds). Fast personalized pagerank on mapreduce. In: Proceedings of the 2011 ACM SIGMOD international conference on management of data. New York: ACM, 2011.

41.

Balmin

Hristidis

Papakonstantinou

(eds). Objectrank: Authority-based keyword search in databases. In: Proceedings of the thirtieth international conference on very large data bases, Vol. 30. VLDB Endowment, 2004.

42.

Ding

Pan

Finin

Joshi

Peng

Kolari

. Finding and ranking knowledge on the semantic web. In: The semantic web – ISWC 2005. Berlin: Springer, 2005, pp. 156–170.

43.

Toupikov

Umbrich

Delbru

Hausenblas

Tummarello

. DING! Dataset ranking using formal descriptions, 2009.

44.

Hogan

Harth

Decker

. Reconrank: A scalable ranking method for semantic web data with context, 2006.

45.

Franz

Schultz

Sizov

Staab

. Triplerank: Ranking semantic web data by tensor decomposition. In: The Semantic Web – ISWC 2009. Berlin: Springer, 2009, pp. 213–228.

46.

Page

Brin

Motwani

Winograd

. The PageRank citation ranking: Bringing order to the web, 1999.

47.

Brandes

. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology 2001; 25(2): 163–177.

48.

Hull

(ed.). Improving text retrieval for the routing problem using latent semantic indexing. In: SIGIR’94. Berlin: Springer, 1994.

49.

Wall

Rechtsteiner

Rocha

. Singular value decomposition and principal component analysis. A practical approach to microarray data analysis, 2003, pp. 91–109.

50.

Robertson

Walker

Jones

Hancock-Beaulieu

Gatford

. Okapi at TREC-3. NIST Special Publication, 1995, p. 109.

51.

Allan

Connell

Croft

Feng

F-F

Fisher

. Inquery and trec-9. DTIC document, 2000.

52.

Balog

Bron

Rijke

. Query modeling for entity search based on terms, categories, and examples. ACM Transactions on Information Systems 2011; 29(4): 1–31.

53.

Bunescu

Pasca

(eds). Using encyclopedic knowledge for named entity disambiguation. EACL, 2006.

54.

Rennie

Jaakkola

(eds). Using term informativeness for named entity detection. In: Proceedings of the 28th annual international ACM SIGIR conference on research and development in information retrieval. New York: ACM, 2005.

55.

Zhang

(eds). New event detection based on indexing-tree and named entity. In: Proceedings of the 30th annual international ACM SIGIR conference on research and development in information retrieval. New York: ACM, 2007.