Providing accurate approaches for keyword search or question answering to access the data available on the Linked Data Web is of central importance to ensure that it can be used by non-experts. In many cases, these approaches return a large number of results that need to be provided in the right order so as to be of relevance to the user. Achieving the goal of improving the access to the Linked Data Web thus demands the provision of ranking approaches that allow sorting potentially large number of results appropriately. While such functions have been designed in previous works, they have not been evaluated exhaustively. This work addresses this research gap by proposing a formal framework designed towards comparing and evaluating di erent ranking functions for RDF data. The framework allows combining these rankings by means of an extension of the Spearman's footrule estimation of the upper bound of this function. We supply a benchmark with a total of 60 manually annotated entity ranks by users from USA and India recruited over Amazon Mechanical Turk. Moreover, we evaluated nine entity ranking functions over the proposed benchmark.
A large number of applications rely on ranking methods for querying, browsing,
linking and presenting RDF data. Examples of such applications are Search
Engines [
The rest of the paper is structured as follows. The related work is discussed in Section 2. Thereafter, we introduce a variation of the Spearman's footrule for evaluating heterogeneous ranks in Section 3. The evaluation, results and performance of di erent ranks for entities are presented respectively in Section 4, Section 5. Finally, we conclude with our plans for future work in Section 6. 2
During the last years, ranking algorithms have started to become more personalized. This means that instead of using only the data structures themselves, approaches have begun to use third-party information, i.e. information that cannot be found in the data itself. For instance, search engines use the previous query terms to rank potential results. Another valuable third-party information can be the users' previously visited web sites and their frequency. That information can help enhance the rank of the query results. Thus, ranks can be divided into two categories: dynamic and static.
Static ranks are those that can be derived from a particular data structure
or information and do not change. That is the case of Page-Rank [
Dynamic ranks change according to a given third-party information.
Examples of such ranks are CHR, DFF, CNN and COMB introduced by Cheng et
al. [
Rank Similarity Functions
Ranks are sequence of similar elements, sorted in a particular order. The
problem of measuring ranking similarities can be focused on nding how distant
or close two ranks are from each other by comparing the order of their
elements. In order to nd how similar two ranks are from each other, there are two
approaches: Spearman's Footrule [
Ranking Ranking methods have been studied for a long time as they are useful for measuring the relevance of a certain feature. Ranking methods can be dynamic or static. Ranking algorithms for RDF data are usually designed for three main features: (1) entities (objects or individuals), (2) properties and (3) classes.
Ranking for entities is the most common type of ranking available. For instance, a query \persons" can return thousands of entities if applied to the DBpedia knowledge base, but not all the information can be useful. In this way, entity ranks can help search engines sort the resulting set according to its relevance.
Page-Rank [
Despite that, entities can have a large number of properties, but a big portion
of them might not be interesting to users. To deal with this problem of so-called
as entity summarization, approaches implementing di erent types and levels of
abstractions were introduced. RELIN [
Dataset Statistics Another type of measure that can be used for ranking is the dataset statistics. Some of the dataset statistics are, for example, the number of instances of a certain resource. Another set of information can be the number of references, predicates or outgoing links. These statistics are speci cally useful for ranking entities.
However, as the Semantic Web usually deals with real world entities, some
approaches have introduced rankings using statistics coming from external sources [
Currently there are many available search engines that are able to crawl big portions of the Web as Google, Yahoo and Bing. Beside that, they can nd related content to a give query. By crawling a large volume of the Web, the search engines can also became a big source of information that can help when ranking resources. One source of information can be, for instance, the number of available Web documents with a particular term or sentence. Another source of information can be the query log. For instance, Google Trends 10 is a public web platform containing the historical search index of a particular term in Google Knowledge Graph topics, Search interest, trending YouTube videos, and Google News articles. The Google Trends index is based on how often a particular term is searched in relation to the total search-volume across various regions of the world, and in various languages. The Google Trends index can be used to either rank entities, properties, and their correlation. 3
As discussed before, Spearman's Footrule is a distance measure function designed to measure similarities among homogeneous rankings. Here in, we propose a new rank similarity function measure based on Spearman's Footrule for measuring similarity among heterogeneous rankings. That is, rankings that have di erent set of resources.
According to Spearman's Footrule, the similarity between two ranks is measured by a summation of the di erence among the positions of the element e in the two ranks r and r . The Spearman's Footrule is formally de ned by the function SF (r ; r ) = Pjir=1j;f =r (i) j r 1(f ) r 1(f )j.
However, to measure how similar a rank is from each other, it is necessary to compute the maximal distance between the two ranks. The maximal distance between two ranks in Spearman's Footrule can be obtained by induction in a very trivial process and will not be discussed here. However, the maximal distance between two ranks is given by the function sfmax that receives a rank size and computes the maximal distance. Herein, we de ne the length of a list as a natural extance of a rank is given by SFmax (jrj) = The intuition behind the extension. Let A and B be two rankings, and, let C = A=B and D = B=A. The idea behind our extended rank similarity function is to devise a function that is the upper bound of any possible ranking that (1) conforms to A and B and (2) contains all elements of A [ B. The Spearman's Footrule is very powerful for measuring homogeneous ranks. However, imagine a scenario where there are two ranks A = fa; b; cg and B = fa; bg. The problem is that, in this case, the Sperman's Footrule for measuring the distance between A and B is not de ned. Thus, if we apply the Sperman's Footrule to the given sets, it might return zero, even though there is a visible di erence between the two ranks. The problem is that c is not in B. However, by using the extension the di erence is clear, d(A; B) = 3. That is, there is one element with the distance of three which does not belong to one of the sets, which is the di erence among them. Furthermore, the distance is symmetric, that is, d(A; B) = d(B; A).
Now, let's discuss a more complex example. Imagine that we have a rank c = f g
d . By de nition d(A; C) = d(C; A), but what is the reason behind it? A naive thinking can lead to imagine that there is a missing information as only the elements in A are contributing to the distance between A and C. The real reason behind the distance between A and C is that the disjoint elements in C contribute as much to the distance as the disjoint elements in A. As A is bigger than C, the distance of a disjoint element c6\ of C in A is distance(c6\) = (Pa2=C\A A(a))=(Pc2=C\A 1). In a few words, while the distance of the element c 2 C with relation to A is the summation of the position of the elements in A, the distance of an element in A to C is its position. Thus, the distance of the disjoint elements in the smallest set is always equal to the disjoint elements in the biggest set. That is, Pc2=C\A distance(c) = Pa2=C\A A(a). To simplify, the proposed Sperman's Footrule extension uses the summation of the disjoint elements in the biggest set. The usability of the proposed extension will be shown in Section 4.
To overcome the problem of measuring heterogeneous ranks, we propose a variant of Spearman's Footrule. The di erence from the original formula is that it consists of the sum of the position of the element of the highest rank that does not intersect, which can be formally de ned as follows:
F (r) =(F jr = (f1; f2; :::; fn) : f 2 F ) D\(r ; r ) =
D(r ; r ) =D\(r ; r ) + D6\(r ; r )
X j r 1(f )
r 1(f )j D6\(r ; r ) = f 2F (r )\F (r ) ( P
P f 2=F (r )\F (r ) r 1(f ) f 2=F (r )\F (r ) r 1(f ) else if jr j > jr j , otherwise (1)
The extension of the original Spearman's Footrule formula makes the measurement of the maximal distance between two ranks more complex and it can be divided into three cases: (1) when the ranks are homogeneous, (2) when they intersect and (3) when they do not intersect. The simplest cases are the homogeneous and the without intersection ones. When the ranks are homogeneous, the distance can be measured by the function SFmax . In other cases, the distance is given by an arithmetic progression of the size of the biggest rank. The arithmetic progression is used as an anchor because an arithmetic progression of a rank with n entries is higher than the maximal distance of Spearman's Footrule Pjir=j1 i > SFmax (jrj). Apart from that, the similarity function for heterogeneous ranks uses the position of the element in the biggest rank. The biggest distance between two ranks occurs when they do not have elements in common. Thus, a maximal distance between two ranks is de ned by the function if r r Dmax(r ; r ) = , otherwise .
SFmax (jr j)
D6\(r ; r ) 4
In this section, we describe the evaluation performed for benchmarking nine di erent ranking functions: (1) the in (DB-IN) and (2) out (DB-OUT) degree of a resource in the dataset; the (3) in (PAGE-IN) and (4) out degree (PAGE-OUT) of the resource's Wikipedia page; the (5) DBpedia page-rank (DB-RANK); the (6) number of external links pointing to the resource's Wikipedia web page (E-PAGE-IN); the (7) Page Authority measured by SEO (SEO-PA); the (8) Wikipedia Page-Rank (PAGE-RANK); the (9) social shared links (SHARESLINKS); and the (10) best entity rank (Best). We rst describe the tasks followed by details of the crowdsourcing experiment (workers and wage). We chose to use crowdsourcing because it facilitates nding the target audience. Thereafter, we measure the rank distances and nally, we provide further details about the implementation and benchmark.
The evaluation was designed to answer the following research questions: { How di erent are the rankings performed across di erent countries? { Is there any similarity between the ranking performed by di erent users? { Which of the entity ranking functions performs better? { Is there any similarity between the entity ranking performed by a particular ranking function in any particular type of resource?
In previous works [
In our methodology, at rst, the resources that are going to be evaluated are
selected based on the connectivity. That is the number of incoming and outgoing
edges. Thereafter, those resources are used to create ranking tasks to be executed
by workers from di erent locations and crowdsourcing platforms (e.g. Amazon
Mechanical Turk). The tasks consist of sorting the resources according to their
relevance, generating rank pro les. These pro les are then used for
benchmarking di erent ranking functions. We have published the ranking functions9 and
pro les7 so that anyone can easily use and benchmark their applications.
Finding the top four classes. In order to nd the top four most used classes,
the DBpedia classes were sorted taking into consideration the number of
instances. By doing so, the top rst 11 classes sorted in descending order of
number of instances were dbo:Agent, dbo:Person, dbo:Place, dbo:CareerStation,
dbo:PopulatedPlace, dbo:Settlement, dbo:Work, dbo:Organization, dbo:Athlete,
dbo:SportTeamMembe, dbo:OrganizationTeamMember and dbo:Species.
Thereafter, we discarded classes that (1) were a super-class of a more speci c class
(e.g. dbo:Agent is a super-class of dbo:Person) or (2) were not a sub-class but
have an overlapping with any previous taken class (e.g. dbo:SportTeamMember
is not an dbo:Athlete but overlaps it). We started excluding the classes based on
these two criteria from the rst top ranked class until we reached the top four.
Task description. As discussed in Section 2, there are di erent ranking
measures for entities. Ranking measures are a mix of statistics often found inside
the datasets (e.g. number of instances of a resource) as well as outside them
(e.g. PageRank) and they can be useful in a wide range of applications such
as Search Engines [
In order to evaluate the di erent ranking functions, we designed four tasks using the DBpedia knowledge base. In Task 1, the worker was asked to sort 20 entities, which were displayed with their label and description. The entities were extracted from the top ve entities of the top four DBpedia classes (dbo:Settlement, dbo:Organization, dbo:Athlete and dbo:Species), according to their relevance (i.e. number of instances).
In Tasks 2 and 3, the user was asked to sort the top 20 most instantiated classes and predicates respectively. These classes and predicates were extracted from the highest ranked entity chosen by the user in Task 1 as the most relevant. In this manner, there is a high probability that the user is more familiar with the entitys' classes and predicates and performs better ranking.
Moreover, in all the ranking tasks the users could select one or more resource to be ranked. As can be noticed, the possibility to selecting any particular resource(s) can generate a large number of ranks with di erent resources and sizes. Nonetheless, this process can ensure that the generated rank is more likely to produce better results since this method allows the user to rank resources that she believes is relevant. For instance, a possible rank for a given list of resources l = (a; b; c) is r = (a; b).
Finally, in Task 4, the users were asked to score her con dence in performing the previous ranking tasks between one and ve, where ve is that she was most con dent. This task had two aims: (1) to validate the performed tasks and (2) point to possible weakness and improvements towards a better benchmark. For instance, a large number of workers showing poor con dence in performing the task could indicate that the task should be reformulated.
The class dbo:CareerStation was discarded because it refers to a state in a period of time rather than an entity itself. The classes dbo:Place and dbo:PopulatedPlace are super class of dbo:Settlement, thus they were also discarded. The class dbo:Work was removed as it could lead to a misunderstanding of the class referring to an occupation whereas it actually refers to creative works and products. Thus, after discarding these classes, the ve top classes obtained were: dbo:Agent, dbo:Person, dbo:Organization, dbo:Athlete and dbo:SportTeamMember. By applying the criteria of discarding classes that are a super-type of a more speci c type, the class dbo:Agent and dbo:Person were further removed. The class dbo:Agent was removed because it is a super type of class dbo:Person and the class dbo:Person a super type of dbo:SportTeamMember. The class dbo:SportTeamMember overlaps with the classdbo:Athlete since a team member can also be an athlete. By applying the second constraint of ignoring classes that are not sub-classes but overlapping classes with more instances, the type dbo:SportTeamMember was discarded because dbo:Athlete has more instances. The same constraint applies to dbo:OrganizationTeamMember regarding dbo:Athlete. Thus, dbo:OrganizationTeamMember is replaced by dbo:Species. Finally, the remaining four classes are: dbo:Settlement, dbo:Organization, dbo:Athlete and dbo:Species.
Task Execution. The tasks were performed using Amazon Mechanical Turk11.
The workers were instructed to consult any source of information available in
order to execute the given tasks such as a dictionary and/or the internet.
The Workers. The tasks were executed by a total of 60 users, out of which 30
were North Americans and 30 Indians, double the amount of users commonly
used in similar tasks for rank evaluation in previous works [
Implementation & Benchmark. All the users evaluations are available online7. The rankings can also be accessed via a library or REST API over DBtrends8. DBtrends is an open-source project and can be easily deployed in existing applications. 11 https://www.mturk.com
DRmax (R) =fdDRmax j 8r ; r 2 R; dDRmax = Dmax(r ; r )g (2) 12 https://moz.com/learn/seo/page-authority 13 http://www.seoreviewtools.com/ achieved by each entity rank are sparse when comparing the countries individually. For instance, the best rank for Americans according to the results is PAGE-RANK while for Indians is SHARED-LINKS.
The distribution of the top rst entities among countries in Table 2, produced interesting results. For instance, the rst four top entities (#Top-1) amongst India and USA were the same (dbr:New York City, dbr:Los Angeles, dbr:Animal and dbr:Political divisions of the United States). This result is interesting because cities such as New York and Los Angeles do not have as much as in uence in Indian history as London (dbr:London) that barely appears in the sixth position behind Chicago (dbr:Chicago), another city in USA. Furthermore, Chicago is not even top rst for any of the Americans. However, when comparing the average rank of Indians, London appears at third place.
Another interesting observation is that dbr:Animal is chosen as top rst for 13 Americans, in contrast of merely four of the Indians. This di erence might have to be in uenced by the American engagement in nature preservation. This also explains the occurrence of dbr:Lepidoptera as the most important entity for some users. However, this nding is not observed when comparing average results. For instance, dbr:Plant appears in rst position for Indians and dbr:Animal at ninth, where for Americans dbr:Animal appears at second and dbr:Plant at fth. Moreover, the top rst results of the Americans are less sparse than for the Indians. The top rst entity of the Americans is devised among eight entities against 13 of the Indians. Finally, the average rank similarity among the di erent users ranks (internal agreement) for entities is 63%.
In this paper, we presented a formal framework for evaluating and publishing
RDF ranking. Nine di erent ranking functions were applied to manual
generated entity ranks from two di erent countries (America and India). Moreover,
we presented a variant of the Speman's Footrule rank similarity function to
measure heterogeneous ranks and demonstrated why the proposed extension is more
accurate than the basic formula. Furthermore, the generated rank pro les are
publicly available7 and can be used for benchmarking other ranking functions.
The evaluated results show that the use of ranks from external data sources is
more e cient when ranking entities. For future work, we plan to (1) investigate
rank similarity functions for heterogeneous ranks, (2) increase the number of
rank pro les as well as (3) extend the evaluation to other countries and ranking
functions. A limitation of the present framework is regarding dynamic ranks [
This work was supported by a grant from the EU H2020 Framework Programme provided for the projects Big Data Europe (GA no. 644564), HOBBIT (GA no. 688227), CNPq under the program Ci^encias Sem Fronteiras and by Intituto de Pesquisa e Desenvolvimento Albert Schirmer (CNPJ 14.120.192/0001-84).