%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// CHAPTER 6 - RANK AGGREGATION AND METASEARCHING
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////



%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// SECTION 6.1: INTRODUCTION
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
\section{Introduction}
\label{ch6_sec1}

The lack of any specific structure and the vast amount of information published on the Web, makes
it extremely difficult for the user to find the information s/he desires without any external help.
As of September~2012, there are at least 19 general-purpose search
engines\footnote{See http://www.searchenginewatch.com}, as well as numerous special-purpose search
engines (called vertical search systems). Their population is mainly justified by two reasons: a)
no ranking algorithm is broadly acceptable, although many users tend to consider \textit{Google}'s
ranking method as the most successful; b) no engine can achieve large coverage and high
scalability. It is a common belief~\cite{se00,mrs2008} that a single general purpose search engine
for all Web data is unrealistic, since its processing power cannot scale up to the rapidly
increasing and unlimited amount of Web data.

The tool which attracted the acceptance among the users is \textit{metasearch engines}
\cite{myl02}. These systems operate like a filter of the various crawler-based or directory-based
search engines which they combine. Metasearch engines run simultaneously a user query across
multiple \textit{component search engines}, retrieve the generated results and then aggregate them.
Finally, they present the best among them to the user.

The advantages of metasearch engines against search engines are significant~\cite{myl02}:

\begin{itemize}
\item{They increase the search coverage of the Web, providing a higher \textit {recall}. The
overlap among the major search engines is usually very small~\cite{sjbk06} and it can be as small
as 3\% of the total results retrieved. On the other hand, the unique results can be as high as 85\%
of the total results retrieved by all component engines.}
\item{They solve the scalability problem of searching the Web and they facilitate the exploitation
of multiple search engines enabling consistency checking~\cite{am01}.}
\item{They improve the retrieval effectiveness providing higher precision, due to the ``chorus
effect'' \cite{vogt99}.}
\end{itemize}

Consequently, metasearch engines and their Web 2.0 successors, mash-up services are important tools
and they are becoming increasingly popular. The core of any such system is the ranking function it
employs, because this function defines the final ranked result list from the results provided by
the component search engines. Hence, devising effective ranking algorithms is a problem of
particular importance for metasearch engines and mash-up services.

The problem of rank aggregation is quite old and has been studied for a century, starting from a
need to design fair elections. It can be thought of as the unsupervised analog to regression, with
the goal of discovering a combined ranking which minimizes the distance to each individual ranking.
Despite its seeming simplicity it is surprisingly complicated; finding the optimal combined ranking
is NP-hard \cite{dkns01} under certain conditions. Thus, several recent efforts describe
approximation algorithms for the rank aggregation problem~\cite{acn05,ailo07,cfr06}, after showing
its relation to the \textit{feedback arc set problem on tournaments}~\cite{acn05}. Some of these
are extensively applied to many different research domains such as bioinformatics \cite{dchfcke06},
Web spam detection \cite{dkns01}, pattern ordering~\cite{tj04}, Web metasearching
\cite{llqml07,rs03,scul07,shok07,okk02} and many more.

Web metasearching in combination to rank aggregation, is a problem posing its own unique
challenges. The results that a metasearch system collects from its component engines, are not
similar to votes or any other single dimensional entities: Apart from the individual ranking it is
assigned by a component engine, a Web result also includes a title, a small fragment of text which
indicates its relevance to the submitted query (textual snippet) and a uniform resource locator
(URL). Apparently, the traditional rank aggregation methods are insufficient for providing a robust
ranking mechanism suitable for metasearch engines, because they ignore the semantics accompanying
each Web result.

Based on these remarks, we conclude that ranking in Web metasearching is a more complex problem
than rank aggregation. Individual rankings might be noisy, incomplete or even disjoint, hence they
should not be the only parameter affecting ranking. Further processing is required in order to
filter the results and allow the final result list of the metasearch engine to be free of unwanted,
devious and unfairly highly ranked Web pages. Since commercial interests might frequently and
unpredictably affect the results of searching, the user is not clearly protected against the
interests of individual search engines. Therefore, the ranking algorithm employed by a real
metasearch engine, should be able to provide results that are as free as they can be from paid
listings and links.

In this chapter we introduce a family of rank aggregation methods suitable for Web metasearch
engines. The basic family members are the \textit{KE Algorithm} and \textit{QuadRank}, accompanied
by a group of special-purpose variations. All the approaches we present in this chapter are
positional ranking methods designed to deal with top-$k$ lists returned by Web search engines.
Their main features are:

\begin{itemize}
\item {They assign scores to the candidate results by considering multiple parameters such as the
number of the search engines where a particular item appeared, the total number of exploited search
engines, the size of the top-$k$ list returned by each search engine, and others.}
\item {They refrain from using any training data in order to perform the rank aggregation, because
there is usually no evidence about the underlying data properties and their distributions.}
\item {They do not count upon the \textit{scores} of the individual search engine rankings in
order to perform the rank aggregation, because most of the search engines do not provide such
scores.}
\end{itemize}

The algorithms are evaluated on real-world data retrieved from four major search engines against
individual search engines listings as well as results returned by the most popular metasearch
engine Dogpile\footnote{http://www.dogpile.com}, using \textit{QuadSearch} \footnote{A publicly
accessible prototype of QuadSearch is available under http://quadsearch.csd.auth.gr.}, a metasearch
engine developed, among others, as a testbed for rank fusion and rank aggregation. There is also an
independent performance study of metasearch engines~\cite{Allen-TR09}, comparing QuadSearch,
Dogpile and Mamma, which showed that QuadSearch outperformed its adversaries in that limited query
load.

We also compare our proposed methods to two other existing rank aggregation methods. The first is
the well-established \textit{Borda Count} method which assigns scores to the collected documents,
by accumulating the individual rankings they received by the component engines. The second method
is the \textit{Outranking Approach}, an order-based method presented in \cite{fv07}, which orders
the items by specifying a set of thresholds and by comparing each document with all the other
collected documents. You can see section \ref{ch6_sec2} for a brief description of these two
methods and a discussion on their differences from our proposed algorithm.

Initially, we test these methods by utilizing the results from the Web Adhoc task of the Web Track
of the TREC-2009 Conference \cite{trec09}. In the sequel, we report the performance of the examined
methods in the real-world environment of QuadSearch.

The rest of this chapter is organized as follows: in section~\ref{ch6_sec2} we provide some
necessary background material and survey the relevant rank aggregation methods. In section
\ref{ch6_sec3} we present the KE Algorithm and its accompanying variants, whereas in section
\ref{ch6_sec4}, we describe QuadRank and its implementation details behind the developed metasearch
engine. In section \ref{ch6_sec5} we present an evaluation of the proposed methods, and finally,
section \ref{ch6_sec6} contains the basic architectural elements of QuadSearch along with some
performance benchmarks.



%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// SECTION 6.2: PRELIMINARIES AND RELATED WORK
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
\section{Preliminaries and related work}
\label{ch6_sec2}

We start with a universe $U$ of items (documents in the context of metasearching); eachitem has a
unique identifier~$c$. A ranked list $r$ of items $c_1, c_2, \dots, c_n$ drawn from the universe
$U$, is an ordered subset $S \subseteq U$, such that $r=[c_1 \geq c_2 \geq \dots \geq c_n]$, where
$\geq$ is an ordering relation on $S$. Each item $c\in S$, has the attribute $r(c)$ which
represents the ranking of $c$ in list $r$. Rankings are always positive, the best ranking an item
could get is~1, and higher ranks show lower preference (reduced relevance to a query, in the
context of metasearching).

If $r$ contains all the items of $U$, then it is said to be a \textit{full or complete list}; if
$|r| < |U|$, then it is said to be a \textit{partial list}, and if $|r| = k$, where $k$ is a fixed
constant, it is said to be a \textit{top-$k$ list}. Apparently, a top-$k$ list is a special case of
a partial list. The ideal scenario for rank aggregation is when each search engine gives a complete
list of all the items of the universe related to the keyword terms of a given query. Unfortunately
this is not possible since either each component engine has a partial coverage of the Web, or for
reasons of speed or protection of the proprietary ranking algorithms, the engine returns only a
top-$k$ list. The worst but unusual scenario is when the result lists of component search engines
have no overlapping elements. In this case there is nothing that a standard rank aggregation
algorithm can do. However, as we will see later, QuadRank takes into account the metadata
accompanying each item, in addition to the individual rankings of the search engines and this is an
advantage of our method over the other methods.

Two families of rank aggregation techniques exist~\cite{rs03}: a) the \textit{score-based} policies
\cite{vc99}, which assign a score to each entity of the individual ranking lists and then use these
scores to perform the ranking, and b) the \textit{order-based} (or \textit{rank-based}) policies
\cite{dkns01,scul07,ba03}, which work upon the order (rank) information that each entity received
in the individual ranking lists. Although there have been proposed a lot of algorithms for rank
aggregation, when it comes to applying these techniques to real-world metasearch engines the
problem becomes even more complicated.

The methods belonging to the first category, were utilized by the first metasearch engines and they
assign a weight to each item of a ranked list, which usually originates from the respective
component search engine. The aggregation is performed using these scores; examples of this practice
include the works in~\cite{vc99,am01b}. Although almost no search engine provides the ranking
scores, it is possible to convert local ranks into ranking scores. Although score-based methods
appear to be more effective for rank fusion \cite{rs03}, the absence of scores (or denial to
reveal) from many search engines' rankings turns these methods problematic.

This shortcoming of the score-based algorithms lead to the generation of the second family of rank
aggregation methods, i.e., the rank-based methods, the mainstream for modern metasearch engines.
The methods of this family exploit only the relative position of the items in each ranked list to
perform the fusion, thus they are also called {\it positional} methods. A primary advantage of
positional methods is their efficiency in calculation, since they can be implemented in time linear
w.r.t.\ the number and size of ranked lists. Unfortunately though, this efficiency in calculation
is not accompanied by guarantees to satisfy the Condorcet criterion~\cite{yl78}.

A popular positional aggregation method is the Borda Count method~\cite{dkns01,rs03}, which assigns
scores based on the positions of the item in the ranked lists. Using terminology from the voting
literature, we can see each item of a ranked list as a candidate and each search engine as a voter.
Each candidate receives points from each voter according to its rank in the voter's list. For
example, the top ranked candidate will receive~$n$ points, where~$n$ is the number of candidates in
the respective ranked list. The total Borda score of the candidate will be the sum of its scores
due to each ranked list where it appears. In case that the candidate is not in the top-$k$ list of
some voter, then it will receive a portion of the remaining points of the voter (each voter has a
fixed number of points available for distribution) or a constant number (0~or~1), depending on the
variation of the method~\cite{saari00}. The Borda Count method can be found in different versions,
like the weighted Borda Count method \cite{sds05}, where each voter also takes a score and
therefore his opinion for a candidate is not treated equally against other voters.

A relatively recent method is the Outranking Approach introduced by \cite{fv07}, which is based on
decision rules identifying positive and negative reasons for judging whether a document should get
a better rank than another. The method operates by performing pairwise comparisons of each item to
all other items in the set $S$. If $c_1$ and $c_2$ are two documents of the set and $r(c_1)$,
$r(c_2)$ are their rankings in the list $r$, then the item $c_1$ should be ranked higher than $c_2$
(symbolized as ${c_1}\sigma{c_2}$) if the two following conditions are satisfied:

\begin{itemize}
\item{The concordance condition which ensures that the majority of the input rankings are
concordant with the ordering ${c_1}\sigma{c_2}$. Formally, the concordance coalition is
$C_{s_p}({c_1}\sigma{c_2})=\{r(c_1)~\leq~r(c_2)-s_p\}$, where $s_p$ is a preference threshold which
determines the boundaries between an indifference and a preference situation between documents.}
\item{The discordance condition which ensures that none of the discordant input rankings strongly
refutes the ordering the ordering ${c_1}\sigma{c_2}$. Formally, the discordance coalition is
$D_{s_u}({c_1}\sigma{c_2})=\{r(c_1)~\geq~r(c_2)+s_u\}$, where $s_u$ is a veto threshold which
determines the boundaries between a weak and a strong opposition to ${c_1}\sigma{c_2}$.}
\end{itemize}

Based on these conditions, a generic outranking relation is defined by the following formula:

\begin{equation}
O({c_1}\sigma{c_2})~\Leftrightarrow~|C_{s_p}({c_1}\sigma{c_2})|~\geq~c_{min}~~AND~~|D_{s_u}({c_1}\sigma{c_2})|~\leq~d_{max}
\end{equation}

where $c_{min}$ and $d_{max}$ are the concordance and discordance thresholds respectively.

Other positional aggregation methods include the Markov chain based on~\cite{dkns01}, soft
computing techniques~\cite{ba03}, and median rank aggregation~\cite{fks03sigmod}. The first methods
``blend" the ranked lists into a Markov chain (MC), where each distinct item of the lists
corresponds to a state of the MC and the transition probabilities correspond in some way to the
(partial) ranked lists. The goal of this modeling is to find the stationary distribution vector of
this MC, which provides a total ordering upon the states of the MC, and thus an ordering upon the
items of the ranked lists. Unfortunately creating such a MC takes time $\Theta(n^2k+n^3)$, where
$n$ is the number of distinct items and $k$ the size of the (top-$k$) lists; this computational
cost can be reduced to $O(n^2k)$ to obtain a very rough approximation. Soft computing methods make
use of genetic or fuzzy logic algorithms to perform the rank fusion, whereas median rank
aggregation uses the media rank for each item to perform the final ranking.

Improved positional methods for rank aggregation of partial lists by exploiting the similarity
among the items are described in~\cite{scul07}, whereas positional methods which are firstly
trained and then used for rank aggregation (i.e., supervised rank aggregation) are described in
\cite{llqml07}. Nevertheless, when the rank fusion method is going to be implemented as the heart
of a metasearch engine, then fast computation of the aggregated rank and effective fusion are the
major challenges to be met. Therefore, Markov chain based methods although claimed to be superior
among the positional ones, are not the preferred choice over methods with linear time complexity
computation cost.



%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// SECTION 6.3: KE ALGORITHM AND VARIATIONS
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
\section{KE algorithm and variations}
\label{ch6_sec3}

The first member of our rank aggregation family is a positional method able to deal with partially
ranked lists; actually it deals with top-$k$ lists. The basic algorithm treats all four component
search engines equally. The reason we do this is due to the following plain but significant
observations: (i) all of them are considered by experts as the ``major'' search engines, (ii) they
have been proved reliable during their lifetimes, and (iii) most users and metasearch engines
prefer them to perform their searches. Later in this article, we present a variation of the main
algorithm which gives the users the ability to define the importance of each component engine.

Let $\tau_1, \tau_2, \tau_3, \tau_4$ be four ranked lists corresponding to each component search
engine. For each item $c \in S$ and list $\tau_i$, we compute the quantity
$K_i(c)=\mathit{position\ in\ }\ \tau_i$ and $\mathfrak{S}(c) = \sum_{i=1}^4 K_i(c)$. The algorithm
assigns to each returned ranked item a score based on the following formula:

\begin{equation}
\label{ke-equation}
\textit{ke}(c) = \frac{\mathfrak{S}(c)}{n^m * (\frac{k}{10}+1)^n},
\end{equation}

where $\mathfrak{S}(c)$ is the sum of all rankings that the item has received, $n$ is the number of
search engine top-$k$ lists the item is listed in, $m$ is the total number of search engines
exploited, $k$ is the total number of ranked items collected from each component engine. We named
this weight as \textit{KE}. The less the KE value for an item, the larger the final rank this item
will take is.



%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// SUBSECTION 6.3.1: KE VS BORDA COUNT
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
\subsection{KE Algorithm vs Borda Count}
\label{ch6_sec3_subsec1}

In this point, we must stress some differences between Borda Count and the KE method.

\begin{itemize}
\item{The Borda Count method takes into consideration the total number of candidates, whereas KE
takes into consideration the number of voters.}
\item{Some Borda Count variations assign scores to each and every candidate; a candidate which is
not included in the top-$k$ list of a particular search engine takes a part of the remaining
points. This does not hold for the KE method: a candidate will be assigned a score only when it is
contained in the top-$k$ list of a particular search engine, otherwise its score is zero.}
\item{The KE method takes into consideration the total number of exploited search engines, the
number of search engines where a candidate has been appeared and the size of the top-$k$ list.}
\item{The KE method has better ``resolution'', in the sense that the possibility of two scores
being the same is less than that of the Borda Count.}
\item{The lower the KE weight an item has the higher will be ranked in the final result list. In
Borda Count holds the opposite.}
\end{itemize}



%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// SUBSECTION 6.3.2: ANTISPAM FILTER
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
\subsection{Antispam version of KE algorithm}
\label{ch6_sec3_subsec2}

Informally, we say that a search engine has been spammed by a page in its result list when it ranks
the page too highly with respect to the other pages, according to the view of a ``typical"
(average) user. This is unavoidable for search engines, because their ranking algorithms have
``defects" that can be exploited by Web page developers in order to achieve an unfairly high page
rank~\cite{ggm05vldb}. Thus, if a page spams all or even most of the search engines, then the
metasearch engine could not handle this problem efficiently as well, because the aggregation
function would work with bad data.

This method takes into consideration the {\it Condorcet Criteria}~\cite{yl78}. In the context of
metasearching, these criteria tell us, in a few words, that an item which is enlisted in the
top-$k$ lists of some search engines should be ranked above an item that is ranked in the top-$k$
lists of fewer search engines. The antispam method attempts to satisfy the intuition that if a page
spams fewer than half of the search engines, then the majority of search engines will prefer a
relatively good page to a spam page. The following pseudocode describes the antispam version:

\begin{enumerate}
\item {\it Find which items appear in more than half pages (let the number of these items be~$c$).}
\item {\it Apply the KE method on these items.}
\item {\it Position them in the result list, starting at rank~$1$.}
\item {\it Apply the KE method on the rest of the items.}
\item {\it Position them in the result list, starting at rank $1+c$.}
\end{enumerate}




%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// SUBSECTION 6.3.3: GEOKE
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
\subsection{The GeoKE method}
\label{ch6_sec3_subsec3}

The analysis of a result's URL can lead to valuable information about the page hosted under it. The
two or three final characters of the domain name (also known as the domain extension), usually
reveal the originating country of that page.

A significant number of queries submited to a search engine is directly connected to a specific
geographic region. Travelling, vacation and news are cases that fall into this category, as they
are usually linked to two types of questions: \textit{where} and \textit{when}. Indeed, travel
related queries usually return results that are relative to the travel's destination. Without any
doubt, there is a significant possibility that pages hosted under affiliate domain extensions are
the most informational.

The possibility that a page is written in a language that a user does not understand is also
significant. Hence, an English user querying for \textit{``flights to Moscow''} and is not familiar
to Russian, will find the pages written in this language totally useless; these pages usually have
the \textit{.ru} domain extension. Apparently, pages having the \textit{.uk} domain extension would
probably be the best results. Pages with \textit{.us}, \textit{.au} or \textit{.ca} domain
extensions would also be good choices, as there is a great possibility that they are all written in
English.

To cover such cases, we present an expansion to the KE algorithm; the GeoKE method that turns it
into a geography-aware ranking algorithm. Based on the user's location that is automatically
received by the system, the GeoKE method assigns scores to the collected results according to the
following formula:

\begin{equation}
\textit{geoke}(c) = G \frac{\sum_1^4 K_i(c)}{n^m * (\frac{k}{10}+1)^n},
\end{equation}

where $G$ is the the $GeoKE(c)$ which receives values depending on three parameters; the user's
locality, the result's geographic origin (revealed by the domain extension) and a comparison
between the user's speaking language and the language that the page is written in. Taking the above
parameters into consideration, the value of the $GeoKE(c)$ is determined when:

\begin{itemize}
\item{The result's domain extension and the user's region are the same.}
\item{The user can understand the language the page is written in. In these cases, the system makes
use of a local database table is used to store the relationships between the geographical regions
and their respective languages.}
\item{The domain's extension of the page does not reveal any information about its locality.}
\item{When the page is written in a language that the user can't understand and does not fall to
the former case.}
\end{itemize}

In all four cases described above the $GeoKE(c)$ can have fixed values, but our implementation
gives the user the ability to define these values himself. This indicates the flexibility of
$GeoKE(c)$ and enables its use in personalized search systems. By altering these values, the
algorithm can lead to different rankings according to the user's selections.

The user's locality is automatically obtained by using a database that is specially designed for
matching IP addresses against geographical areas. With this strategy the user is not obliged to
submit any information about his/her locality, but there is always a small possibility that the
module makes an erroneous prediction.



%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// SUBSECTION 6.3.4: WEIGHTED KE
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
\subsection{The weighted KE method}
\label{ch6_sec3_subsec4}

The basic KE algorithm treats all four component engines equally; in the same section we justified
this choice. Nevertheless, there is an intuition, that a single search engine can't perform equally
well for all types of queries. There are occasions where it can present qualitative results and
others, in which the results are of medium or lower informational value. This derives from the fact
that each engine maintains its own document index and every time a query is submitted, it searches
among different documents and presents different results than another engine does.

In addition, users' confidence to a search engine cannot be ignored. For instance, some of them
prefer using a search engine for certain types of queries and another engine for other types. On
the other hand, some users prefer using only one search engine to conduct all their searches.

For these reasons, an effective rank aggregation method must provide the user with the ability to
modify the importance of each component engine. The proposed Weighted KE algorithm takes this
remark into consideration and assigns scores to the collected results according to the following
equation:

\begin{equation}
\textit{wke}(c) = \frac{\sum_1^4 [11 - e(c)] K_i(c)}{n^m * (\frac{k}{10}+1)^n},
\end{equation}

where $e(c)$ is the Weight factor of the $c$-th Engine (EWF), which can receive integer values
between 1 and 10. The equation above leads to the same outcome as the basic version of the KE
algorithm (\ref{ke-equation}), unless a different EWF is assigned to at least one engine. The
results with lower scores will receive higher rankings, meaning that an engine considered to be
more important than another, must receive a lower EWF. To make it more comprehensible for the user
we subtract EWF from eleven, so that the the most important component receives the greatest EWF.




%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// SUBSECTION 6.3.5: URL-AWARE KE
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
\subsection{The URL-aware KE method}
\label{ch6_sec3_subsec5}

The use of subdomains when publishing pages on the Web, is a quite common option that the
developers have. In fact, subdomains are simple folders in a Web server's public directory and are
usually identified by the first part of their URL (after the communication protocol). All
subdomains are tied to a domain name and may, or may not have similar contents. For example, the
URL \textit{http://inf.uth.gr} is a subdomain of the \textit{uth.gr} domain name; it provides
information regarding a University's Faculty.

Until now, all search engines treat subdomains as different domains. The top-10 list that Google
returns for the query \textit{Aristotle University of Thessaloniki} contains 10 Web pages, all
hosted under the \textit{auth.gr} domain name. It is obvious that the limitation of no more than
two pages with the same domain name in the same result list does not cover subdomains. This policy
introduces the problem of \textit{domain spamming}, which occurs on situations similar to the one
mentioned above.

Hence, there is a significant possibility that many pages with similar contents, or many pages from
one source would appear in the engine's result list. This possibility becomes even greater in
metasearch engines, where more than one component engines are being exploited. To confront this
problem, two solutions are available. The first settlement that can be done is to completely block
a number of results having the same domain name, including subdomains.

The second solution focuses on giving these pages a lower score; that is, reducing their ranking.
The URL Aware algorithm has been implemented for this purpose. According to this method, the weight
for each Web page is computed by using the following formula:

\begin{equation}
\textit{uke}(c) = (11 - D) \frac{\sum_1^4 K_i(c)}{n^m * (\frac{k}{10}+1)^n},
\end{equation}

where $D$ is the \textit{Domain Awareness Constant} (DAC). Its value is subtracted from eleven to
indicate that a higher value will decrease the result's weight, therefore improve its ranking. The
value of DAC depends on how many times the domain name of a specific result is repeated in the list
of candidates. If a candidate has a domain name that is not repeated more than two times, we set
DAC = 10. In the opposite case, DAC is set equal to 5.

Similarly to GeoKE, the implementation of the URL Aware KE algorithm allows the definition of the
value of DAC by the user for both cases.




%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// SECTION 6.4: QUADRANK
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
\section{The QuadRank scoring}
\label{ch6_sec4}

In this section we present another positional method able to deal with partial ranked lists. The
proposed method, namely QuadRank, deals with top-$k$ lists originating from single crawler-based
search engines. The algorithm treats all component search engines equally. The reason we do this is
due to the following plain, but significant observations: (i) all of them are considered by experts
as the ``major'' search engines, (ii) they have been proved reliable during their lifetimes, and
(iii) most users and metasearch engines prefer them to perform their searches on.

Let $r_{1}, r_{2}, \dots r_{m}$ be $m$ ranked lists corresponding to each component search engine.
We assume that the each of these lists consists of a fixed number of $k$ items, consequently, the
entire process involves in total $km$ elements that have to be merged and ranked. Merging is a
procedure which we employ in order to combine the $m$ different result lists into a single list, by
removing all the overlapping elements. Notice that this list remains unranked until the scoring
function is applied to each of the list's elements.

The overlapping between two component engines varies across different queries and cannot be
predicted, hence we assume that our final result list consists of $N$ items. In Table
\ref{table-summary} we describe the symbols we use in our presentation and the parameters employed
by QuadRank.

In the sequel we present the main ideas implemented by our proposed method. In particular, we
describe the methodology employed by QuadRank in order to deal with individual rankings and zone
weighting and we examine the significance of the results' URL analysis. Finally, we discuss how all
these different components can be combined together into a single scoring formula.

\begin{table}[h]
\small
\begin{center}
\begin{tabular}{|c|l|}\hline
{\bf Symbol} & {\bf Meaning}                                                             \\\hline
$m$          & The number of exploited component engines                                 \\\hline
$c$          & A single result (document) in a component list                            \\\hline
$r_i(c)$     & The ranking of $c$ in the $i^{th}$ component list                         \\\hline
$n_c$        & The number of component lists containing $c$                              \\\hline
$k$          & The number of items included in each component list                       \\\hline
$q$          & An arbitrary user query                                                   \\\hline
$t_q$        & A term of $q$                                                             \\\hline
$Q$          & The number of terms of $q$                                                \\\hline
$N$          & The number of items included in the final merged list                     \\\hline
$N_{t_q}$    & The number of items containing $t_q$                                      \\\hline
$z_c(i)$     & The $i^{th}$ zone of $c$ (see Table~\ref{table-zones})                    \\\hline
$W_{z_c(i)}$ & The weight of $z_c(i)$                                                    \\\hline
$f(c,t_q,z_c(i))$ & The number of occurrences (frequency) of $t_q$ in $z_c(i)$           \\\hline
\end{tabular}
\end{center}
\caption{Summary}
\label{table-summary}
\end{table}



%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// SUBSECTION 6.4.1: DEALING WITH INDIVIDUAL RANKINGS
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
\subsection{Dealing with individual rankings}
\label{ch6_sec4_subsec1}

The ranking that each element receives by the component engines is of primary importance for a rank
aggregation method and the majority of the proposed ranking algorithms are mainly based on these
rankings. Consequently, we must design our function in order to reward a result which achieves high
rankings, since such entries are considered to be more relevant to a given query than others placed
in lower positions.

Therefore, for each item $c \in S$ we introduce and evaluate the quantity

\begin{equation}
\label{eq-rank-quantity}
K(c) = \sum_{i=1}^m \Bigl(k+1-r_i(c) \Bigr)
\end{equation}

where $r_i(c)$ is the ranking that the item is assigned by the $i^{th}$ component engine. In the
special case where the item $c$ is not ranked by list $r_i$, we assume that $r_i(c)=k + 1$.
Obviously, the best score an item can receive is $km$ (if it is ranked first on every component
list), whereas the lower score is $1$ and it is assigned on a result which was ranked last only in
one component list.

The introduced score rewards the items which received high rankings by multiple component engines,
however it is relatively frequent that two or more results are assigned equal $K(c)$ values. For
instance, consider the occasion where two different items $c_1$, $c_2$ receive the following
rankings by four top-10 lists $r_1$, $r_2$, $r_3$ and $r_4$.

\begin{table}[h]
\small
\begin{center}
\begin{tabular}{|c|c|c|c|c|}\hline
{\bf Item} & {\bf $r_1$} & {\bf $r_2$} & {\bf $r_3$} & {\bf $r_4$}                       \\\hline
$c_1$      &     1       &      -      &      -      &     -                             \\\hline
$c_2$      &     7       &      7      &     10      &    10                             \\\hline
\end{tabular}
\end{center}
\caption{Example}
\label{table-example}
\end{table}

In the example of Table \ref{table-example} it holds $K(c_1)=K(c_2)=10$. Nevertheless, we firmly
believe that $c_2$ should be ranked higher than $c_1$ since:

\begin{itemize}
\item{it appears in more input rankings, consequently it outperforms $c_1$ according to the
democratic symmetry \cite{saari00}.}
\item{it appears in more than half of the input rankings and hence, there is a smaller probability
of being a spam entry according to the Condorcet criterion.}
\end{itemize}

To handle such cases, we must reward the results which are considered as relevant to a given query
by as many component engines as possible. If $n_c\leq{m}$ is the number of the component engines in
which a result $c$ occurs, then we introduce the $rank-based$ score which is determined by the
following equation:

\begin{equation}
\label{eq-rank-based}
R(c) = mlog \Bigl( n_c K(c) \Bigr)
\end{equation}

Where $m$ is the total number of the exploited engines. Note that the logarithm in
\ref{eq-rank-based} is employed in order to reduce the deviation among the different values that
$R_i(c)$ can receive. Additionally, although multiplying the logarithm with $m$ makes no difference
(since $m$ is constant for all items), it is justified by our intention to assign the $R(c)$ score
a larger value.



%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// SUBSECTION 6.4.2: ZONE WEIGHTING
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
\subsection{Zone weighting}
\label{ch6_sec4_subsec2}

Zone weighting is a well established methodology for ranking documents in traditional search
systems. The main idea it is based on suggests partitioning each Web document into locations of
special interest, namely \textit{zones} or \textit{fields}. Such partitioning is usually performed
in structured or semi-structured documents (i.e. XML files), where the available information is
distributed across multiple zones and represents different semantics (i.e. authorship, publication
date, title, etc).

The introduction of zones allows us to compute scores by taking into consideration the physical
location of a term within a document (i.e. in which field of an XML document a term appears). An
example of such ranking scheme is the BM25F function presented in \cite{lu2006field}.

The main difficulty hidden behind the idea of using zone scoring in a rank aggregation method is
that a Web result retrieved by a component search engine is not a complete document and only some
limited representative information is provided to a metasearch engine. This information comprises
of three individual semantics: the title, a small fragment of the document's text, called snippet,
which indicates the relevance of the document to the user query and a uniform resource locator
(URL).

\begin{table}[h]
\small
\begin{center}
\begin{tabular}{|c|c|c|c|}\hline
{\bf Zone} & {\bf ID} & {\bf Weight}                                                     \\\hline
Title      &    1     &      10                                                          \\\hline
Snippet    &    2     &       3                                                          \\\hline
URL        &    3     &       5                                                          \\\hline
\end{tabular}
\end{center}
\caption{Zones}
\label{table-zones}
\end{table}

In this paper we attempt to integrate zone scoring characteristics to our ranking function. The
idea we introduce here is to treat the three aforementioned semantics as separate document zones.
Although zone weighting is not a new scheme in information retrieval, to the best of our knowledge
we are the first to apply its principles in the field of rank aggregation. Our motives are
multiple: A Web result which contains the query terms on its title is possibly more relevant than
another which does not. This is also valid for results containing the query terms in their snippets
more times than others. Hence, the number of the occurrences of the query terms in the individual
zones is another parameter which should be taken into consideration by an efficient ranking method.

As we have mentioned, there already exists a zone scoring scheme, BM25F. Nevertheless, we found
that this method is not suitable for our case since:

\begin{itemize}
\item{The BM25F function requires the length of each zone (in number of terms) to be computed,
which undoubtedly is a time consuming operation.}
\item{The second reason that turns the usage of zone lengths problematic is that the Web results
returned by the component engines are not complete documents. The small fragments of text used to
represent the similarity of each document to the submitted query, have similar or identical lengths
for each entry. Consequently, zone lengths have a small contribution to the score of an item.}
\item{It depends on several (typically three) user-defined parameters.}
\end{itemize}

In this subsection we propose our own policy for zone scoring and we believe that our suggestions
are more suitable for metasearch applications. At first, in Table~\ref{table-zones} we determine
the weights assigned to each zone. Based on these weights, we use the following formula to compute
a weight factor:

\begin{equation}
\label{eq-zone-weighting}
Z(c)=\sum_{t=1}^Q{log{\frac{N}{N_{t}}}\sum_{z=1}^3{W_{z}f(c,t,z)}}
\end{equation}

where $N$ represents the total number of items included in the final merged list and $N_{t}$ is the
number of items containing the query term $t$. Furthermore, $W_{z}$ denotes the constant weight of
a zone, which we show in Table~\ref{table-zones}, whereas $f(c,t,z)$ represents the frequency of
the query term $t$ within zone~$z$.

The logarithm $log{N/N_{t}}$ is drawn from the traditional tf/idf scoring functions used by search
engines to rank Web documents (i.e. BM25, BM25F). It is used to reward the documents containing the
query terms appearing a few times only, because such terms are expected to reveal the information
need hidden behind each query.

Note that the $Z(c)$ score rewards the documents which include the query terms on their title,
snippet or URL as many times as possible since it is sensitive to the corresponding frequency
values. Consequently, the documents which include all or some of the query terms in their title
multiple times are considered more relevant to the given query and they are assigned higher scores.

To compute the desired frequency values, the text accompanying each result must be appropriately
processed. Therefore, each document is tokenized (that is, we obtain all of its distinct terms) and
each of the extracted distinct terms passes multiple filters which sequentially perform punctuation
removal, case folding and stemming. These are CPU-intensive procedures and one would expect query
processing to decelerate significantly. However, the small document population as well as their
limited size (titles and snippets consist of a few terms only) render this delay rather
inconsequential (see experimental subsection~\ref{ch6_sec6_subsec1}).


%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// SUBSECTION 6.4.3: URL ANALYSIS
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
\subsection{URL analysis}
\label{ch6_sec4_subsec3}

To the best of our knowledge, the current publicly known rank aggregation methods do not take into
consideration the URLs of the results that the component engines return. In this subsection we
attempt to mine the information revealed by the URLs, in order to improve the quality of the
produced results.

Since a metasearch engine is a system which exploits multiple resources, it is possible that
several results under the same domain name would appear in the final merged list. Although these
entries have different URLs and probably include different content, their origin is identical. This
observation forces us to conclude that this domain possibly contains adequate information relevant
to the given query. Consequently, we should enhance our ranking function in order to reward such
results.

On the other hand, a result list comprised of different items from the same resource is hardly
informative. An effective search system must provide qualitative results from many sources, because
this wide variety partially ensures that the user can locate the desired information. For this
reason, the major crawler-based search engines include at most two documents with the same domain
name in their result lists, even if there are additional relevant documents.

The problem is now becoming straightforward: from a pool of $X$ documents having the same domain
name we must identify and reward the best two among them, whereas we should discard the rest $X-2$
of them. The challenge becomes even greater if maximum efficiency is required and fast system
response is a key issue. QuadRank solves the problem by employing an auxiliary table of
\textit{domain accumulators} which it populates during the component engines' result list merging.
When an item enters the list, we also search for its domain name into this accumulator table. If
the record is not present we insert it and set the corresponding accumulator value equal to 1. In
the opposite case we increase the accumulator by one.

During the scoring process we consult the accumulator table and we assign additional scores
according to the following formula:

\begin{equation}
\label{eq-url}
u(c)=log \Biggl(10 \frac{2m-1+acc_c}{2m} \Biggr)
\end{equation}

where $acc_c$ is the domain accumulator of $c$. Later, when the results are going to be presented
to the user, only the two highest scored results with the same domain name are used; the rest of
them are simply discarded. Note that for the results having domain names appearing only once, it
holds that $acc_{c}=1$ and the quantity $U(c)$ is assigned a value equal to 1.

The analysis of a result's URL can lead to additional information regarding the page it represents.
More specifically, the two or three trailing characters of the domain name (also known as the
domain extension), usually reveal the originating country of that page.

Additionally, a significant number of queries submitted to a search engine is directly connected to
a specific geographic region. For instance the travel, vacation and news oriented searches are
cases falling into this category. When such information is required, there is a significant
possibility that the pages hosted under affiliate domain extensions are the most satisfactory.

To address such issues, we introduce an expansion to our ranking function, the $Geo Factor$, a
parameter which is determined by the relationship between the geographic locality of the user and
the proximity of each result $c$. The Geo Factor receives values according to the following
formula:

\begin{equation*}
G(c)=\begin{cases}
    1& \text{if domain extension and user locality are not identical},\\
    \lambda, \lambda>1& \text{otherwise}.
\end{cases}
\end{equation*}

where~$\lambda$ is a predefined constant receiving values $\lambda>1$; a typical option which we
have used in our experiments is to set~$\lambda=1.2$.

By integrating the Geo Factor into the scores of equation~\ref{eq-url} we introduce the $URL Aware$
scores determined by the following formula:

\begin{equation}
\label{eq-url-aware}
U(c)=G(c)log \Biggl( 10 \frac{2m-1+acc_c}{2m} \Biggr)
\end{equation}

The lowest value that $U(c)$ can receive is 1, for results appearing under a domain name
encountered only once in the $m$ component lists and when this domain does not match the geographic
locality of the user. On the other hand, if we assume that each component engine returns at most 2
results having the same domain name, then the largest value that $U(c)$ can be assigned is
$\lambda{log\Bigl((20m-5)/m\Bigr)}$.




%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// SUBSECTION 6.4.4: QUADRANK SCORES
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
\subsection{QuadRank scores}
\label{ch6_sec4_subsec4}

In this subsection we merge all the aforementioned components into a single scoring function,
namely QuadRank. According to our proposed method, each collected result is assigned a score which
is determined by the following formula:

\begin{equation}
\label{eq-quadrank}
Q(c)=U(c) \Biggl( R(c) + \frac{1}{Q}Z(c) \Biggr)
\end{equation}

where $Q$ is the total number of the query terms. As one may notice from equation
\ref{eq-zone-weighting}, the $Z(c)$ score representing our zone weighting policy, is strongly
depended on the number of query terms and increases proportionally to $Q$. Consequently, to
regulate the contribution of zone weighting to the final scores, with respect to the other terms
$R(c)$ and $U(c)$, we introduce the quantity $1/Q$.




%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// SUBSECTION 6.4.5: QUADRANK VS BORDA COUNT
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
\subsection{QuadRank vs.\ Borda count}
\label{ch6_sec4_subsec5}

In this point, we must stress some differences between Borda Count and the scores of QuadRank.

\begin{itemize}
\item{QuadRank is a rank aggregation method designed to operate on metasearch engines. Therefore,
its scoring formula takes much more parameters into consideration such as the zone weighting, the
domain characteristics and the number of the occurrences of each query term within each result.}
\item{Some Borda Count variations assign scores to each and every candidate; a candidate which is
not included in the top-$k$ list of a particular search engine takes a part of the remaining
points. This does not hold for the QuadRank method: a candidate will be assigned a score only when
it is contained in the top-$k$ list of a particular search engine, otherwise its score is zero.}
\item{QuadRank also takes into consideration the total number of exploited search engines, the
number of search engines where a candidate has been appeared and the number of items of each
top-$k$ list.}
\item{The QuadRank method has better ``resolution'', in the sense that the possibility of two
scores being the same is less than that of the Borda Count.}
\item{Since our proposed method does not assign scores based completely on the individual rankings,
it is more difficult to be ``deceived'' by a spam entry, that is a result which received an
unfairly high ranking.}
\end{itemize}



%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// SUBSECTION 6.4.6: QUADRANK VS OUTRANKING APPROACH
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
\subsection{QuadRank vs. Outranking approach}
\label{ch6_sec4_subsec6}

In this subsection we describe the main differences between our proposed method and the Outranking
approach.

\begin{itemize}
\item{The Outranking approach takes into account only the individual rankings that each document
received by the component engines. On the other hand, QuadRank takes much more parameters into
consideration.}
\item{The Outranking approach is an order-based method, therefore it is only based on comparison
among the ranks only. It neither considers scores, nor hits whereas QuadRank assigns scores
according to the ranking each item received by the component engines.}
\item{The Outranking approach introduces four user-defined parameters (preference, veto,
concordance and discordance thresholds). Selecting different values for these parameters can lead
to significant modifications in the produced output ranking. In \cite{fv07} it is shown that small
changes in the values of these parameters lead to rankings with significant quality fluctuations.
On the other hand, QuadRank involves settings of weights for each document zone (See subsection
\ref{ch6_sec4_subsec2} for more details).}
\item {Since the Outranking approach requires a pairwise comparison of each item to every other
collected item, it can turn significantly slow particularly when multiple long input lists are
involved (because there are more items to be compared).}
\end{itemize}




%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// SUBSECTION 6.5: EXPERIMENTS
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
\section{Experimental Evaluation}
\label{ch6_sec5}

The most important measure of a search system's performance is the quality of its search results.
Quality is a decision made after the results evaluation by one or more human users. Moreover, it
should not be assumed that quality is absolute; one user may well judge that a result is
qualitative, while another says it is not.

In addition, quality is usually identified with the relevancy of the returned results to a given
query. Every query represents an information need; the user who submits it, seeks for information
that is somehow related to the terms of the query. Consequently, a document is judged to be
relevant only if it addresses the stated information need, not because it happens to contain all
the words of the query.

To evaluate the performance of a metasearch engine, a basic difference from search engines must be
considered. A metasearch engine does not maintain its own document collection. It neither employs
crawlers, nor indexers to construct a repository and an underlying index structure. Its output is
based on the results that its component engines return. It does not even retrieve the entire set of
these results; it works only with the first parts of this set, as these parts are the most
promising to contain the best answers to a specified query. Therefore, in the extreme situation
where all component engines send irrelative results, there is nothing a metasearch engine can do.
But as we show later, a metasearch engine having an effective ranking fusion method, can mine the
individual result sets and fuse them to a list that ranks the best items at the top.

A number of methods have been suggested for evaluating the effectiveness of a search system and its
ranking algorithm. None of these methods are entirely satisfactory, but this is a natural
consequence of attempting to represent multidimensional behavior with a single representative
value.

To ensure a fair evaluation of QuadRank against its competitors in the context of retrieval
effectiveness, we divide our experimentation into two phases: At first, we use data from the
TREC-2009 conference which apart from the result sets, it also provides a list containing a set of
queries and the corresponding relevant documents.

In the sequel, we measure the performance of the involved algorithms in the real-world environment
of QuadSearch. For this series of experiments there is no ground truth regarding the relevancy of
each document to our test queries. For this reason, we asked from six of our colleagues to judge
the relevancy of each document and in our analysis we consider a document to be relevant if and
only if more than half (four or more) of our colleagues judged its relevance positively.



%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// SUBSECTION 6.5.1: EXPERIMENTS WITH TREC
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
\subsection{Retrieval effectiveness evaluation with TREC data}
\label{ch6_sec5_subsec1}

The first phase of our experiments includes the application of our proposed method to the Web Adhoc
(WA) Task of TREC-2009 Web Track \cite{trec09}. This task contains 50 topics (test queries) and 72
participating teams. For each query, each team provides a ranking of about 1000 documents which is
later evaluated by using a separate file containing all the documents that are relevant to the
given topic. The performances of the 10 best runs of the WA task are reported in Table
\ref{table-trec-10-best}.

\begin{table}[hbt!]
\small
\begin{center}
\begin{tabular}{|l|c|c|c|c|c|}\hline
{Run}         &  $MAP$  &  $P@5$  &  $P@10$  & $P@20$  & $R$-Precision \\\hline
uvamrftop     &  10.2\% &  41.6\% &  37.4\%  &  28.8\% &  13.6\%       \\\hline
UMHOOsd       &  10.2\% &  34.8\% &  37.2\%  &  35.4\% &  17.5\%       \\\hline
UMHOOsdp      &  10.2\% &  34.8\% &  37.2\%  &  35.4\% &  17.5\%       \\\hline
NeuLMWeb300   &  10.0\% &  44.8\% &  44.2\%  &  38.0\% &  16.7\%       \\\hline
NeuLMWeb600   &   9.8\% &  39.6\% &  39.8\%  &  36.1\% &  16.9\%       \\\hline
uogTrdphCEwP  &   9.8\% &  42.4\% &  37.4\%  &  32.1\% &  15.4\%       \\\hline
UMHOObm25B    &   9.8\% &  34.8\% &  36.4\%  &  34.3\% &  16.8\%       \\\hline
WatSdmrm3we   &   9.5\% &  16.0\% &  16.4\%  &  16.6\% &  14.4\%       \\\hline
udelIndDMRM   &   9.4\% &  26.0\% &  31.8\%  &  33.1\% &  17.0\%       \\\hline
udelIndDRSP   &   9.4\% &  28.0\% &  32.8\%  &  31.9\% &  15.8\%       \\\hline
\end{tabular}
\end{center}
\caption{Performances of the 10 best runs of the WA task of TREC-2009.}
\label{table-trec-10-best}
\end{table}

For evaluation, we used the `trec\_eval' standard program utilized by the TREC community in order
to calculate several measures indicating the retrieval effectiveness of a system. These measures
are Mean Average Precision ($MAP$), $R$-Precision and Precision@$n$ ($P@n$) for $n=5, 10$ and $20$.

QuadRank is compared against the other two rank aggregation algorithms as well as against some high
performing official results from TREC-2009. For each topic, we retrieve one list from each
participating team, that is 72 rankings. From these rankings we retain only the first $k$ documents
and in the sequel, the 72 top-$k$ lists are merged into one large list which is finally ranked by
employing QuadRank, Borda Count and the Outranking approach. In the following tables we present
results for different values of $k$.

To measure the performance QuadRank, it was necessary retrieve the full text of each candidate
document in order to compute the $Z(c)$ scores. Since all the candidate documents are from the
Clueweb09 dataset, we have developed the appropriate software which operates on the collection and
extracts the desired information. $Z(c)$ scores are computed by considering the document's title
and URL only, because of the absence of textual snippets. Furthermore, the locality of the user is
unknown and the geographical relationship between the user and a document can not be determined.
For this reason, we have disabled the Geographic extensions of the $U(c)$ scores in this
experimental phase.

Regarding the setting of the parameters introduced by the Outranking approach, we used the same
values as those mentioned by \cite{fv07}. Therefore, we considered that each input ranking is a
complete order ($s_p=0$) and that an input ranking strongly refutes an ordering between two
documents when the difference of both document positions is large enough ($s_u=75\%$). We also
supposed that the majority of the rankings must be concordant ($c_{min}=50\%$) and that every input
ranking can impose its veto ($d_{max}=0$).

\begin{table}[hbt!]
\small
\begin{center}
\begin{tabular}{|l|c|c|c|c|c|}\hline
{Run}                        &  $MAP$  &  $P@5$  &  $P@10$  & $P@20$  & $R$-Precision \\\hline
Best TREC Run                &  10.2\% &  41.6\% &  37.4\%  &  28.8\% &  13.6\%       \\\hline\hline
Borda Count (30)             &  18.5\% &  39.2\% &  37.8\%  &  33.8\% &  26.0\%       \\\hline
Outranking Approach (30)     &  15.5\% &  42.0\% &  38.4\%  &  36.8\% &  22.2\%       \\\hline
QuadRank (30)                &  19.5\% &  43.2\% &  39.2\%  &  36.4\% &  25.4\%       \\\hline\hline
Borda Count (100)            &  19.0\% &  44.0\% &  42.8\%  &  41.1\% &  23.4\%       \\\hline
Outranking Approach (100)    &  18.4\% &  50.0\% &  48.0\%  &  40.5\% &  25.1\%       \\\hline
QuadRank (100)               &  20.9\% &  46.4\% &  43.8\%  &  42.3\% &  25.0\%       \\\hline\hline
Borda Count (200)            &  18.8\% &  47.6\% &  44.2\%  &  42.4\% &  23.1\%       \\\hline
Outranking Approach (200)    &  18.8\% &  51.6\% &  47.6\%  &  44.9\% &  24.3\%       \\\hline
QuadRank (200)               &  20.6\% &  49.8\% &  45.9\%  &  44.7\% &  24.0\%       \\\hline\hline
Borda Count (500)            &  18.2\% &  50.4\% &  47.8\%  &  42.1\% &  22.9\%       \\\hline
Outranking Approach (500)    &  18.7\% &  50.4\% &  47.4\%  &  41.3\% &  23.7\%       \\\hline
QuadRank (500)               &  19.8\% &  50.4\% &  48.2\%  &  42.6\% &  23.4\%       \\\hline\hline
Borda Count (1000)           &  17.3\% &  49.6\% &  48.0\%  &  42.7\% &  22.0\%       \\\hline
Outranking Approach (1000)   &  18.2\% &  50.8\% &  45.8\%  &  39.4\% &  22.0\%       \\\hline
QuadRank (1000)              &  19.9\% &  51.2\% &  49.0\%  &  43.1\% &  21.4\%       \\\hline
\end{tabular}
\end{center}
\caption{Performance of different rank aggregation methods for $m=72$ and variable numbers of retained documents.}
\label{table-ram-performance-ontrec-72-30}
\end{table}

Table \ref{table-ram-performance-ontrec-72-30} shows the performance of the three examined rank
aggregation methods in the WA task for variable number of retained documents. If we consider Mean
Average Precision (MAP) as the comparison measure between the three methods, it is apparent that
QuadRank outperforms both Borda Count and the Outranking Approach for all values of $k$. It is also
remarkable that Borda Count performs better than the Outranking Approach for small values of $k$,
whereas the situation is reversed as $k$ increases.

Regarding the average Precision values at cut off points 5, 10 and 20, the performance of the three
methods varies significantly. For instance, QuadRank achieved the highest $P@10$ values for $k=500$
and $k=1000$, but for smaller values of $k$ the Outranking Approach becomes the winning method.
Furthermore, for $k=100$ QuadRank achieves the highest $P@20$ value whereas for $k=200$ the
Outranking Approach fetched the most qualitative top-20 list.



%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// SUBSECTION 6.5.2: EXPERIMENTS WITH TEST QUERIES
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
\subsection{Retrieval effectiveness evaluation with test queries}
\label{ch6_sec5_subsec2}

To examine the retrieval effectiveness of the new ranking algorithm, we have integrated its
implementation within \textit{QuadSearch}, our experimental metasearch engine. Various queries were
submitted to the system and the results' lists that the proposed ranking fusion methods returned
are recorded and analyzed in this subsection. For all tests demonstrated here we exploited four
major component engines (Google\footnote{http://www.google.com},
Yahoo!\footnote{http://search.yahoo.com}, Live\footnote{http://www.live.com} and
Ask\footnote{http://www.ask.com}). The system dispatched our submitted queries to each of these
component engines and requested top-30 lists to be returned. Consequently, for the setup that we
examine here it holds that~$m=4$ and~$k=30$.

Let us suppose that a user searches for tickets for the forthcoming UEFA Champions League final
game and thus, he/she phrases and submits the query \textit{``tickets for uefa champions league
final 2010''}. The informational need is overt in this query. As mentioned above, a document not
only has to contain the query terms, but also to address the stated information need to be
considered as relevant. For the specified example query, a document is relevant only when:

\begin{itemize}
\item{it is relevant to the \textit{``uefa champions league''} and}
\item{it provides information about \textit{``tickets''} and}
\item{is about the \textit{final} game that will be conducted in \textit{``2010''}.}
\end{itemize}


\begin{table}[t]
\small
\begin{center}
\begin{tabular}{|c|l|c|c|c|c|c|c|c|c|}\hline
{} & {\bf URL}                            & {\bf R}  & {G}& {Y}& {L}& {A} & {BC} & {OA}  \\\hline
1  & www.championsleagueticketservice.com & $R_{1}$  & 1  & 1  & -  & 6   &  3   &  5    \\\hline
2  & www.championsleagueticketshop.com    & $R_{2}$  & 15 & 3  & 5  & 11  &  2   &  2    \\\hline
3  & www.worldticketshop.com              &   -      & 6  & -  & 14 & -   &  16  &  15   \\\hline
4  & en.wikipedia.org                     & $R_{3}$  & 8  & -  & 1  & -   &  7   &  10   \\\hline
5  & www.soldoutentertainments.com        & $R_{4}$  & 10 & 2  & 7  & 7   &  1   &  1    \\\hline
6  & www.1st4footballtickets.com          & $R_{5}$  & -  & -  & 13 & -   &  45  &  62   \\\hline
7  & www.uefa.com                         &   -      & 3  & -  & 9  & -   &  9   &  14   \\\hline
8  & www.1st4footballtickets.com          & $R_{6}$  & -  & -  & 3  & -   &  28  &  61   \\\hline
9  & www.livefootballtickets.com          & $R_{7}$  & 16 & -  & 10 & -   &  18  &  13   \\\hline
10 & www.championsleagueticketservice.com &   -      & 2  & -  & -  & -   &  10  &  78   \\\hline
11 & www.nwtix.com                        & $R_{8}$  & 29 & -  & 22 & -   &  23  &  21   \\\hline
12 & www.roadtrips.com                    & $R_{9}$  & 4  & 4  & 12 & -   &  4   &  3    \\\hline
13 & www.globalticketshop.com             & $R_{10}$ & -  & -  & 16 & -   &  31  &  51   \\\hline
14 & www.uefa.com                         &   -      & -  & -  &  6 & 4   &  8   &  9    \\\hline
15 & www.1st4footballtickets.com          & $R_{11}$ & -  & -  &  - & 3   &  29  &  27   \\\hline
16 & www.ticketcity.com                   &   -      & 12 & 11 &  8 & -   &  5   &  4    \\\hline
17 & soccerlens.com                       &   -      & 14 & -  & 11 & -   &  17  &  11   \\\hline
18 & www.webuytickets.net                 & $R_{12}$ & 23 & -  & -  & -   &  27  &  81   \\\hline
19 & www.livefootballtickets.com          & -        & -  & 24 & 26 & -   &  19  &  20   \\\hline
20 & www.freetickets.org.uk               & $R_{13}$ & 5  & 9  & -  & -   &  15  &  17   \\\hline
\end{tabular}
\end{center}
\caption{Top-20 list and relevant documents for the query
\textit{``tickets for uefa champions league final 2010''} when the~\textit{QuadRank} algorithm is applied.}
\label{table-query-1}
\end{table}

All documents containing information about the \textit{``uefa cup''} or past \textit{``uefa
champions league finals''} (e.g. 2008,~2009) are considered as irrelevant, since they do not
satisfy the user's information need.

\textit{QuadSearch} requested and received 120 results (thirty results from each component engine).
After the merging of the results' lists, a set of candidates comprised of 88 unique items is
constructed.

The top-20 list that \textit{QuadRank} produced for this query, is displayed in ranked order in
Table~\ref{table-query-1}. The first column denotes the QuadRank ranking, whereas in the second
column we choose to display only the domain name of the returned result, to form a compact and
legible table. The next column shows which of the documents are relevant to the given query (with
respect to the judgement made by our colleagues) and the symbol $R_i$ is used to indicate the
$i^{th}$ relevant document of the QuadRank's top-20 list. The next four columns signify the ranking
that the component engines gave to this document\footnote{Column headers: \textit{G} for Google,
\textit{Y} for Yahoo!, \textit{L} for Live Search and \textit{A} for Ask}. The dash symbol
represents the absence of this result from an engine's top-20 list. In the last two columns we
compute and display the ranking generated by the Borda Count method  and the Outranking approach
(column headers \textit{BC} and \textit{OA} respectively), when they are applied on the same result
set.

\begin{table}[t]
\small
\begin{center}
\begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c||c|}\hline
{\bf Engine}        &{\bf 1}& {\bf 2} & {\bf 3} & {\bf 4} & {\bf 5} & {\bf 6} & {\bf 7} & {\bf 8} & {\bf 9} & {\bf 10} & {\bf R} \\\hline
QuadRank            &   R   &    R    &    -    &    R    &    R    &    R    &    -    &    R    &    R    &    -     &    7    \\\hline
Google              &   R   &    R    &    -    &    R    &    -    &    R    &    -    &    -    &    R    &    R     &    6    \\\hline
Yahoo!              &   R   &    R    &    R    &    R    &    -    &    R    &    -    &    R    &    -    &    -     &    6    \\\hline
Live Search         &   -   &    R    &    R    &    -    &    R    &    -    &    R    &    -    &    -    &    R     &    5    \\\hline
Ask                 &   -   &    R    &    R    &    -    &    -    &    R    &    R    &    -    &    -    &    -     &    4    \\\hline
Dogpile             &   S   &    S    &    S    &    R    &    -    &    -    &    -    &    R    &    R    &    -     &    3    \\\hline
Borda Count         &   R   &    R    &    R    &    R    &    -    &    R    &    -    &    -    &    -    &    -     &    5    \\\hline
Outranking Approach &   R   &    R    &    R    &    -    &    R    &    R    &    -    &    -    &    -    &    R     &    6    \\\hline
\end{tabular}
\end{center}
\caption{Relevant Documents in the Top-10 Lists for the Query \textit{``tickets for uefa champions league final 2010''.}}
\label{table-top10-query-1}
\end{table}

A significant number of results that the search engines returned, were about past
\textit{``champions league finals''}. Particularly we found that all component lists contained
results regarding the final game of 2009 in their top-10 lists. Some other entries were about
tickets for the uefa cup final, whereas others included no information about tickets at all. All
these results were considered as irrelevant.

Now let us examine the first ten results returned by each algorithm. Ask performed poorly in this
query, since it produced only four relevant documents in its top-10 list, whereas Google and Yahoo
were more accurate as they returned six relevant documents. On the other hand, the top-10 ranking
that QuadRank produced was the most qualitative, since it included seven relevant results. Note
that QuadRank achieved to construct a result list which is improved compared to the rankings of the
combined component engines. These notations are all summarized in Table~\ref{table-top10-query-1}.
The symbol $R$ is used to signify a relevant document, the dash symbol is used to mark the
irrelevant ones, whereas $S$ is used for sponsored entries. The last column shows the total number
of relevant documents returned by each component engine or ranking algorithm in their top-10 list.

In the same Table we present the top-10 list provided by the most widespread metasearch engine,
Dogpile. The top three results are sponsored links found on Google
Ads\footnote{https://www.google.com/adsense}, an online advertisement service maintained by Google.
The fourth result which is organic, is relevant to the query, but it leads to the same location as
the second result. It is clear that Dogpile's policy to include paid listings within organic
results leads to a confusing top-10 list, which contains different results leading to the same
location. In total, Dogpile's top-10 list for this query contains three paid and only seven organic
results. From these seven results, only three are relevant to the query, as the other four concern
past \textit{``Champions League finals''}.

\begin{figure}[!hbt]
\begin{center}
\centerline{\epsfig{file=Chapter6/figs/q1,width=4.7in}}
\caption{Measurements of Precision@10 and Precision@20 for various search engines for the query \textit{``tickets for uefa champions league final 2010''}}
\label{fig-q1}
\end{center}
\end{figure}


In Figure~\ref{fig-q1} we illustrate the effectiveness of the search engines which we examine in
our experiments. The two diagrams depict the precision values measured for the first 10 and 20
results respectively. QuadRank outperformed all of its opponents, since it produced the most
qualitative result list compared to the component engines, Dogpile, Borda Count and the Outranking
approach

The QuadRank algorithm outperformed all of its components including the component engines, Dogpile
and the Borda Count and Outranking methods, since it achieved the highest precision values for both
the top-10 and top-20 lists. Google, Yahoo and Dogpile constructed top-10 lists of equal quality,
whereas the latter's ranking algorithm performed better than the component engines. Regarding Borda
Count, the top-10 and top-20 lists included five and eleven relevant results respectively,
consequently, our algorithm presented more qualitative results. The Outranking approach was
slightly more effective than Borda Count but it was also outperformed by QuadRank.

\begin{table}[t]
\small
\begin{center}
\begin{tabular}{|l||c|c|c|c|c|c|c|c|}\hline
{\bf Engine}        & {QuadRank} &  {G}  &  {Y}  &  {L}  &  {A}  &  {BC}  &  {OA}        \\\hline
QuadRank            &     -      & -0.26 & 0.16  & -0.20 & -0.07 &  0.41  &  0.31        \\\hline
Google              &   -0.26    &   -   & 0.09  &  0.05 & -0.09 &  0.09  &  0.25        \\\hline
Yahoo!              &    0.16    & 0.09  &   -   & -0.46 & -0.42 &  0.03  &  0.16        \\\hline
Live                &   -0.20    & 0.05  & -0.46 &   -   & -0.32 & -0.05  & -0.03        \\\hline
Ask                 &   -0.07    & -0.09 & -0.42 & -0.32 &   -   & -0.30  & -0.63        \\\hline
Borda Count         &    0.41    & 0.09  &  0.03 & -0.05 & -0.30 &    -   &  0.84        \\\hline
Outranking Approach &    0.31    & 0.25  &  0.16 & -0.03 & -0.63 &  0.84  &    -         \\\hline
\end{tabular}
\end{center}
\caption{Rankings Correlation for the Query \textit{``tickets for uefa champions league final 2010''}.}
\label{table-corel-query-1}
\end{table}

In addition, the reader should note an interesting case. If we compare the $8^{th}$ and $10^{th}$
entries of Table~\ref{table-query-1}, we conclude that the latter received better ranking from the
component engines than the former. However, since QuadRank is not relied completely on the
individual rankings of the component engines, it positions them in the opposite manner. That
decision was vindicated, since the $8^{th}$ entry is relevant to the given query, whereas the
$10^{th}$ is not. There are many such cases in the rankings generated by QuadRank: For example,
compare the $6^{th}$ entry to the $7^{th}$ and $15^{th}$ to $16^{th}$ where the individual rankings
were correctly overlooked. On the other hand, the competitor rank aggregation methods could not
distinguish the difference and provided incorrect rankings.

Now let us examine how the involved result lists correlate. To evaluate the correlation of the
produced rankings, we employed the Spearman's rho measure. The results illustrated in Table
\ref{table-corel-query-1}, reveal that all algorithms produce lists that diverge significantly.

\begin{table}[t]
\small
\begin{center}
\begin{tabular}{|c|l|c|c|c|c|c|c|c|}\hline
{} & {\bf URL}                    & {\bf R}  & {G}& {Y}& {L}& {A} & {BC} & {OA}          \\\hline
1  & nlp.stanford.edu             & $R_{1}$  & 2  & 1  & 2  & 1   &  1   &  1            \\\hline
2  & www.reedconstructiondata.com &    -     & 4  & 4  & -  & 3   &  2   &  5            \\\hline
3  & www.ims.uni-stuttgart.de     & $R_{2}$  & -  & 8  & 5  & -   &  8   &  6            \\\hline
4  & www.reedconstructiondata.com &    -     & 5  & -  & -  & 4   &  6   &  12           \\\hline
5  & ilpubs.stanford.edu:8090     & $R_{3}$  & 7  & -  & 3  & 9   &  4   &  2            \\\hline
6  & nlp.stanford.edu             &   -      & -  & -  & 4  & -   &  10  &  21           \\\hline
7  & www.ics.uci.edu              & $R_{4}$  & -  & -  & 10 & -   &  41  &  28           \\\hline
8  & lecs.cs.ucla.edu             & $R_{5}$  & -  & 16 & 14 & 22  &  5   &  3            \\\hline
9  & www.ics.uci.edu              & $R_{6}$  & -  & -  & 12 & -   &  49  &  27           \\\hline
10 & nlp.stanford.edu             & $R_{7}$  & 3  & 2  & -  & 2   &  3   &  4            \\\hline
11 & ilpubs.stanford.edu:8090     & $R_{8}$  & -  & -  & 15 & -   &  74  &  19           \\\hline
12 & en.wikipedia.org             &   -      & -  & 7  & 28 & -   &  25  &  7            \\\hline
13 & ilpubs.stanford.edu          & $R_{9}$  & -  & 9  & -  & -   &  28  &  42           \\\hline
14 & www10.org                    & $R_{10}$ & -  & 10 & -  & -   &  30  &  53           \\\hline
15 & docs.huihoo.com              & $R_{11}$ & 9  & -  & -  & 11  &  10  &  9            \\\hline
16 & portal.acm.org               &   -      & -  & 24 & -  & -   &  77  &  43           \\\hline
17 & www.reedconstructiondata.com & $R_{12}$ & -  & 3  & -  & -   &  18  &  52           \\\hline
18 & www10.org                    & $R_{13}$ & -  & -  & 11 & -   &  46  &  32           \\\hline
19 & www.dcs.bbk.ac.uk            & $R_{14}$ & -  & 30 & -  & -   &  97  &  85           \\\hline
20 & citeseerx.ist.psu.edu        &   -      & 6  & -  & -  & 5   &  6   &  8            \\\hline
\end{tabular}
\end{center}
\caption{The top-20 list for the query \textit{``distributed index construction''} when the \textit{QuadRank} Algorithm is Applied.}
\label{table-query-2}
\end{table}

In the sequel, we measure the performance of the proposed algorithm for another situation, where a
hypothetical engineer seeks information about how to construct an inverted index in a distributed
environment. The submitted query is phrased as \textit{``distributed index construction''} and
dictates out metasearch engine to request 30 results from each of its component engines.
\textit{QuadSearch} received 120 results and after the merging process, a set of 100 candidates is
generated and ranked.

A document is considered relevant to the given query, only if its content is relevant to
\textit{``indexes''} and it contains some instructions regarding \textit{``distributed
construction''} in its body. All the results that provided information regarding index
compression, organization or single-node construction were marked as irrelevant.

Compared to the previous case (where the set of candidates contained 88 items), we conclude that
for this query, the engines' coverage is significantly smaller. At first, the ranking that our
algorithm generates, is studied. Table~\ref{table-query-2} illustrates the top-20 list returned by
QuadRank and also displays the individual rankings that each result received by the component
engines. The last two columns record the rankings that the Borda Count method and the Outranking
approach produced.

\begin{figure}[!hbt]
\begin{center}
\centerline{\epsfig{file=Chapter6/figs/q2,width=4.7in}}
\caption{Measurements of Precision@10 and Precision@20 for various search engines
for the query \textit{``distributed index construction''}}
\label{fig-q2}
\end{center}
\end{figure}

\begin{table}[t]
\small
\begin{center}
\begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c||c|}\hline
{\bf Engine}         & {\bf 1} & {\bf 2} & {\bf 3} & {\bf 4} & {\bf 5} & {\bf 6} & {\bf 7} & {\bf 8} & {\bf 9} & {\bf 10} & {\bf R} \\\hline
QuadRank             &    R    &    -    &    R    &    -    &    R    &    -    &    R    &    R    &    R    &    R     &    7    \\\hline
Google               &    -    &    R    &    R    &    -    &    -    &    -    &    R    &    R    &    R    &    -     &    5    \\\hline
Yahoo!               &    R    &    R    &    -    &    -    &    -    &    R    &    -    &    R    &    R    &    R     &    6    \\\hline
Live Search          &    R    &    R    &    R    &    -    &    R    &    R    &    -    &    -    &    -    &    R     &    6    \\\hline
Ask                  &    R    &    R    &    -    &    -    &    R    &    R    &    -    &    -    &    R    &    -     &    5    \\\hline
Dogpile              &    -    &    R    &    -    &    -    &    -    &    -    &    R    &    R    &    R    &    R     &    5    \\\hline
Borda Count          &    R    &    -    &    R    &    R    &    -    &    -    &    -    &    R    &    -    &    R     &    5    \\\hline
Outranking Approach  &    R    &    R    &    R    &    R    &    -    &    R    &    -    &    -    &    R    &    -     &    6    \\\hline
\end{tabular}
\end{center}
\caption{Relevant documents in the engines' top-10 lists for \textit{``distributed index construction''}.}
\label{table-top10-query-2}
\end{table}

The Google and Ask component engines provided answers of medium quality for this query; only five
results out of ten were considered relevant, as only five contained the required information.
Google concentrated on presenting scientific papers about \textit{``indexing''} but some of these
works were originating from other sciences such as biology. In addition, PageRank played its role,
as most of the results are well known and institutional sources of scientific information. In
addition, Ask returned a top-20 list of low quality, since it was deceived by the term
\textit{``index''}, a word that is commonly used to describe the home page of a Web site.

On the other hand, Yahoo! and Live Search performed better in this case, since their top-10
rankings contained six pages containing useful information. These engines also presented
satisfactory top-20 lists containing twelve relevant entries each.

QuadRank outperformed all of its opponents, since its top-10 and top-20 lists included 7 and 14
relevant results. Dogpile's top-10 list was of equal quality to Google and Ask, but its top-20 list
was more informative only than Ask's. Unlike the previous case where several sponsored links were
included in the top-10 list of Dogpile, for this query the metasearch engine provided only organic
results. Five of them were relevant to the query, whereas the others provided information regarding
distributed audio and video communication systems and distributed process control systems.

The Borda Count method generated results of equal quality to Dogpile; five relevant items in the
top-10 list and only eight in the top-20. It becomes obvious that a simple rank aggregation method
that is heavily depended on the individual rankings of the component engines, cannot always provide
robust ranking. On the other hand, the component of the QuadRank algorithm (equation
\ref{eq-zone-weighting}) which examines the titles, the snippets and the URLs of the collected
elements, leads to result lists of improved quality.

Once again the Outranking approach was more effective than the Borda Count method since it fetched
six relevant documents in its top-10 list and twelve in its top-20. However, the method did not
produce as qualitative rankings as QuadRank.

In Table~\ref{table-top10-query-2} we depict the relevancy of each item of the examined top-10
lists to the query in question. Moreover, in Figure~\ref{fig-q2} we illustrate the precision of
each ranking algorithm, measured at cutoff points 10 and 20.

Finally, in Table~\ref{table-corel-query-2} we evaluate the correlation of the various rankings of
the experiment, by recording the values of the Spearman's rho measure.

\begin{table}[ht!]
\small
\begin{center}
\begin{tabular}{|l||c|c|c|c|c|c|c|}\hline
{\bf Engine}        & {QuadRank} &  {G}  &  {Y}  &  {L}  &  {A}  &  {BC}  &  {OA}        \\\hline
QuadRank            &     -      & -0.42 & 0.16  & -0.09 & -0.44 &  0.56  &  0.64        \\\hline
Google              &   -0.42    &   -   & -0.53 & -0.33 & -0.50 & -0.31  & -0.32        \\\hline
Yahoo!              &    0.16    & -0.53 &   -   & -0.18 & -0.35 & -0.20  & -0.41        \\\hline
Live                &   -0.09    & -0.33 & -0.18 &   -   & -0.27 & -0.12  &  0.35        \\\hline
Ask                 &   -0.44    & -0.50 & -0.35 & -0.27 &   -   & -0.38  & -0.48        \\\hline
Borda Count         &    0.56    & -0.31 & -0.20 & -0.12 & -0.38 &    -   &  0.89        \\\hline
Outranking Approach &    0.64    & -0.32 & -0.41 &  0.35 & -0.48 &  0.89  &    -         \\\hline
\end{tabular}
\end{center}
\caption{Rankings Correlation for the Query \textit{``distributed index construction''}.}
\label{table-corel-query-2}
\end{table}

The third query we present here originates from the broader fields of health and medication. Here
we are interested in locating the symptoms of the cancer of lungs, hence the query we phrase is
\textit{lungs cancer symptoms}. The information need is quite targeted in this query, since we
desired to attest the accuracy of our algorithm in similar cases. Hence, the documents containing
information regarding only the causes or the treatments of the disease are considered as
irrelevant. The same holds for results whose content is about other types of cancers or other types
of lungs maladies.

\begin{table}[hbt!]
\small
\begin{center}
\begin{tabular}{|c|l|c|c|c|c|c|c|c|}\hline
{} & {\bf URL}                     & {\bf R} & {G}& {Y}& {L}& {A} & {BC} & {OA}          \\\hline
1  & lungcancer.about.com          & $R_{1}$ & 13 & 7  & -  & -   &  10  &  15           \\\hline
2  & www.merck.com                 & $R_{2}$ & 5  & -  & 6  & 9   &  5   &  6            \\\hline
3  & www.cancerssociety.org        & $R_{3}$ & -  & -  & -  & 14  &  42  &  74           \\\hline
4  & www.webmd.com                 & $R_{4}$ & 10 & 2  & 7  & -   &  4   &  4            \\\hline
5  & www.emedicinehealth.com       & $R_{5}$ & 2  & -  & 3  & 5   &  2   &  3            \\\hline
6  & www.cancerhelp.org.uk         & $R_{6}$ & 4  & -  & -  & 2   &  7   &  9            \\\hline
7  & www.medicinenet.com           & $R_{7}$ & 1  & 4  & 1  & 3   &  1   &  1            \\\hline
8  & lungcancer.about.com          &   -     & 12 & 6  & -  & 18  &  6   &  5            \\\hline
9  & www.webmd.com                 & $R_{8}$ & -  & 1  & 5  & -   &  8   &  7            \\\hline
10 & www.emedicinehealth.com       &   -     & 3  & 5  & -  & 6   &  3   &  2            \\\hline
11 & www.macmillan.org.uk          & $R_{9}$ & -  & -  & -  & 4   &  26  &  75           \\\hline
12 & www.mayoclinic.com            & $R_{10}$& 11 & 11 & -  & -   &  13  &  19           \\\hline
13 & health.yahoo.com              & $R_{11}$& 14 & 13 & -  & -   &  14  &  14           \\\hline
14 & www.cancerhelp.org.uk         & $R_{12}$& -  & -  & -  & 11  &  38  &  73           \\\hline
15 & www.lungscancer.com           &   -     & -  & -  & 2  & -   &  24  &  34           \\\hline
16 & www.cancer.gov                & $R_{13}$& -  & 24 & 21 & -   &  21  &  8            \\\hline
17 & www.wrongdiagnosis.com        & $R_{14}$& -  & 8  & -  & -   &  31  &  63           \\\hline
18 & www.cancerbackup.org.uk       &   -     & -  & -  & -  & 22  &  63  &  71           \\\hline
19 & www.webmd.com                 &   -     & 9  & -  & -  & -   &  33  &  88           \\\hline
20 & www.cancercenter.com          & $R_{15}$& -  & 17 & -  & -   &  50  &  50           \\\hline
\end{tabular}
\end{center}
\caption{The top-20 list for the query \textit{``lungs cancer symptoms''} when the
\textit{QuadRank} algorithm is applied.}
\label{table-query-3}
\end{table}

A page is considered relevant to the specified query, only if it contains the desired information
itself; not because it includes sets of links to other pages which ``claim'' to provide such
information. This rule was strictly followed by our colleagues during the identification of
relevant results.

\begin{table}[!hbt]
\small
\begin{center}
\begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c||c|}\hline
{\bf Engine}        & {\bf 1} & {\bf 2} & {\bf 3} & {\bf 4} & {\bf 5} & {\bf 6} & {\bf 7} & {\bf 8} & {\bf 9} & {\bf 10} & {\bf R} \\\hline
QuadRank            &    R    &    R    &    R    &    R    &    R    &    R    &    R    &    -    &    R    &    -     &    8    \\\hline
Google              &    -    &    R    &    -    &    R    &    R    &    R    &    R    &    -    &    -    &    R     &    6    \\\hline
Yahoo!              &    R    &    R    &    R    &    -    &    -    &    -    &    R    &    R    &    R    &    R     &    7    \\\hline
Live Search         &    -    &    -    &    R    &    R    &    R    &    R    &    R    &    R    &    -    &    R     &    7    \\\hline
Ask                 &    R    &    R    &    -    &    R    &    R    &    -    &    -    &    -    &    R    &    R     &    6    \\\hline
Dogpile             &    -    &    -    &    -    &    -    &    -    &    R    &    R    &    R    &    R    &    R     &    5    \\\hline
Borda Count         &    R    &    R    &    -    &    R    &    R    &    -    &    R    &    R    &    -    &    R     &    7    \\\hline
Outranking Approach &    R    &    -    &    R    &    R    &    -    &    R    &    R    &    R    &    R    &    R     &    8    \\\hline
\end{tabular}
\end{center}
\caption{Relevant documents in the engines' top-10 lists for \textit{``lungs cancer symptoms''}.}
\label{table-top10-query-3}
\end{table}

Similarly to the previous experiments, our metasearch engine requested 30 results from each
component engine and after the merging process, a set of 91 elements is generated and ranked. In
Table~\ref{table-query-3} we record the elements of the top-20 list that QuadRank produced and
also, the individual rankings that each one received by the component engines. As before, that dash
symbol represents the absence of the element from an engine's result list.

QuadRank presented the most qualitative top-10 list, since 8 results were relevant to the given
query. Furthermore, the first seven results were all of high informational quality, as they
included adequate reference regarding the subject of the query. Live search and Yahoo! were also
effective, although their top-10 rankings included one result less than QuadRank's list. Regarding
the other two component engines, Google and Ask, they were slightly less efficient, by including
six relevant results in their top-10 rankings.

The first opponent rank aggregation method, Borda Count, constructed a top-10 list comprised of
seven relevant documents and it was outperformed by our proposed method. On the other hand, the
Outranking approach returned results that were of equal quality to those of QuadRank. The other
metasearch engine that we examine in our experiments, Dogpile, exhibited poor performance and it
was the worst among our examined search engines, by building a top-10 list which contained only
five relevant results. Table \ref{table-top10-query-3} provides a detailed image of the top-10
rankings of the examined search engines.

The top-20 ranking of Borda Count is significantly improved compared to the top-10 list and was
equally qualitative compared to the ones constructed by our QuadRank algorithm and the Yahoo!
component engine. In total, the top-20 lists of these three ranking methods included 15 relevant
documents. The left and right diagrams of Figure~\ref{fig-q3} illustrate the precision values of
the various systems and algorithms for the top-10 and top-20 listings respectively.

\begin{figure}[!hbt]
\begin{center}
\centerline{\epsfig{file=Chapter6/figs/q3,width=4.7in}}
\caption{Measurements of Precision@10 and Precision@20 for various search engines
for the query \textit{``lungs cancer symptoms''}}
\label{fig-q3}
\end{center}
\end{figure}

Finally, in Table~\ref{table-corel-query-3} we record the correlation of the rankings by using the
Spearman's rho measure.

\begin{table}[ht!]
\small
\begin{center}
\begin{tabular}{|l||c|c|c|c|c|c|c|c|}\hline
{\bf Engine}         & {QuadRank} &  {G}  &  {Y}  &  {L}  &  {A}  &  {BC}  &  {OA}       \\\hline
QuadRank             &      -     & -0.41 &  0.22 & -0.26 & -0.26 &  0.65  &  0.50       \\\hline
Google               &   -0.41    &   -   & -0.14 & -0.48 & -0.01 &  0.82  &  0.63       \\\hline
Yahoo!               &    0.22    & -0.14 &   -   & -0.58 & -0.39 & -0.07  &  0.06       \\\hline
Live                 &   -0.26    & -0.48 & -0.58 &   -   & -0.50 & -0.62  & -0.59       \\\hline
Ask                  &   -0.26    & -0.01 & -0.39 & -0.50 &   -   &  0.16  & -0.07       \\\hline
Borda Count          &    0.65    &  0.82 & -0.07 & -0.62 &  0.16 &   -    &  0.73       \\\hline
Outranking Approach  &    0.50    &  0.63 &  0.06 & -0.59 & -0.07 &  0.73  &   -         \\\hline
\end{tabular}
\end{center}
\caption{Rankings Correlation for the query \textit{``lungs cancer symptoms''}.}
\label{table-corel-query-3}
\end{table}

The example queries we have studied here reveal that a single search engine cannot perform equally
well for all types of queries. Although Google was effective for \textit{``tickets for uefa
champions league final 2010''}, it did not provide equally informative results for the query
\textit{``distributed index construction''}. The opposite behavior was exhibited by Live Search and
Yahoo, which presented informative top-10 lists in the second and third cases.

On top of that, our QuadRank scoring method performed steadily well on all submitted queries. This
sense is present on most cases, as our metasearch engine manages to eliminate the component engines
weak spots and combine their advantages efficiently.

Regarding the competitor rank aggregation methods, QuadRank outperformed Borda Count by a
significant margin for all of the three queries we have tested. QuadRank was also more effective
than the Outranking approach on two cases and equally accurate on the third.



%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// SECTION 6.6: QUADSEARCH
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
\section{QuadSearch}
\label{ch6_sec6}

In this paper we briefly describe QuadSearch, an experimental metasearch engine that provides
simultaneous access in four major conventional, crawler-based search engines. The heart of the
system is based on the rank aggregation algorithms we presented previously in this chapter. The
engine aims to combine speed, reliable rank aggregation method, ``spam" free results, and detailed
and enriched information. A publicly accessible interface for the new metasearch engine can be
found at http://quadsearch.csd.auth.gr/.

Initially, we describe the core components of the system and in the sequel, we present some
performance benchmarks which demonstrate the efficiency of QuadSearch.




%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// SUBSECTION 6.6.1: QUADSEARCH ARCHITECTURE
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
\subsection{Architecture}
\label{ch6_sec6_subsec1}

The most significant modules of QuadSearch are the Quad Bot, the Object Builder, the Classification
Module and the Presentation Module. These modules are described in the next subsections.
A schematic diagram of the architecture is depicted in the left part of Figure~\ref{fig-arch}.

\vspace*{-\baselineskip}
%
\begin{figure}[!hbt]
\begin{center}
\begin{minipage}{2.4in}
\centerline{\epsfig{file=Chapter6/figs/fig1,width=2.4in,height=1.5in}}
\end{minipage}
\begin{minipage}{2.11in}
\centerline{\epsfig{file=Chapter6/figs/qsearch,width=2.1in}}
\end{minipage}
\end{center}
\vspace*{-10pt}
\caption{(Left) Architecture of QuadSearch.\ \ \  (Right) Quad Search's homepage.}
\vspace*{-10pt}
\label{fig-arch}
\end{figure}



\subsubsection{User interface and database selector}
\label{ch6_sec6_subsec1_subsubsec1}

The static content of Quad Search's user interface is built with plain HTML, while the dynamic
procedures are being processed by PHP. Additionally, we invoked Cascading Style Sheets (CSS) for
page formatting. We decided that the Web pages' layout should be as simple as possible, in order to
ensure: a) short download times, b) compatibility with all major browsers, and c) convenient usage.

For these reasons we avoided using large graphics files, or embedded objects like ActiveX
Controls, or Flash presentations. We also rejected Javascript, because many experienced users tend
to deactivate it, due to security reasons. Until now, Quad Search supports the classic Web search
and also searching procedures for news, images, video and audio sources. The ability to search for
scientific articles in the most popular scientific databases is also supported, but not very
efficient. The user can switch among these features from either the home page or the results page.
Regarding the database selector, the default search will be run using all four search engines. The
user however, has the option to choose which search engines will be exploited, as shown in the
right part of Figure~\ref{fig-arch}.

Apart from the classic text box, we included the most significant search preferences in the home
page. The user can select the query resources (the search engines that will participate in the
search process), the number of results to be retrieved per resource, the number of results that
will be displayed per page etc. The interface provides the ability to store the values of these
parameters, by setting cookies in the client's computer. Thus, the user is not obliged to define
again these parameters for future queries. The interface includes an extra option to filter the
results, to prevent spam records from entering the KE list. Finally, in the options page the user
can select the ranking algorithm (KE or Borda Count).


\subsubsection{QuadBot}
\label{ch6_sec6_subsec1_subsubsec2}

QuadBot receives its inputs from both the database selector and the user interface. It is
responsible for validating the input data and parameters, passing the query to the selected
databases and collecting the results. Its internal structure is depicted in the left part of
Figure~\ref{fig-qbot-objbuilder}.

\begin{figure}[!hbt]
\begin{center}
\begin{minipage}{4cm}
\centerline{\epsfig{file=Chapter6/figs/fig4,width=2.0in}}
\end{minipage}
\hspace*{1.5cm}
\begin{minipage}{4cm}
\centerline{\epsfig{file=Chapter6/figs/fig3,width=1.5in}}
\end{minipage}
\end{center}
\vspace*{-10pt}
\caption{(Left) Quad Bot's structure.\ \ \  (Right) Object Builder's architecture.}
\label{fig-qbot-objbuilder}
\end{figure}

{\it Parameter Receiver/Validator}.
It accepts all the data coming from the data\-ba\-se selector and the user. The validation process
includes transformation of the inputs in a way that can be sent to the search engines. For example,
the procedure removes all leading and trailing spaces from the query string and replaces all spaces
by the character ``+". The Result Validator also performs security checks to ensure that a
``should-be" numeric parameter is really numeric, or that an attacking user does not send a
malicious script instead of a query string. We developed this compartment by keeping in mind that
all data coming from the Internet should be treated as suspicious. There are over a dozens of
security checks that are performed for each parameter.

{\it Query Dispatcher}.
The Query Dispatcher is the QuadBot's heart. It gets the validated data and creates http requests
to the selected search engines. This is the slowest procedure of the whole system; its speed
depends on the number of the invoked search engines, the requested results, the server's Internet
connection, etc. We have accelerated this procedure by submitting all the requests to the search
engines simultaneously. To achieve that, we had to employ the {\it libcurl} library with cURL
(client URL) extensions~7.16.0 for PHP~5.1, that support multiple connections at a time. By
building the Query Dispatcher this way, we managed to shrink the idle time to no more than~1 or~2
seconds.

{\it Result Collector}.
The Result Collector embraces the http responses transmitted by the search engines. Each involved
search engine must respond to the Query Dispatcher's request, by sending the source code of its
result page. The source code is being filtered by using pattern matching techniques. The module
retrieves the ranking, the URL, the title and the snippet for each candidate. When it receives all
the information, it stores it in temporary arrays and sends them to the next module for validation.

{\it Result Validator}.
The Result Validator is the most complex compartment of this module, as it performs multiple
conversions to the collected data. The URL validation part is responsible for the appropriate
formatting of the collected URLs, so that the overlapping candidates could be correctly detected
later. At first, a UTF-8 decoding function converts all UTF-8 encoded characters to their ISO
equivalent. For example, the \%27 set of characters is being converted to an opening single
apostrophe character ('). At next, a formatting function trims the trailing slash from a URL (if
exists), a third procedure checks if an engine has returned two identical URLs etc. As already
mentioned above, most of these conversions will be presented later on.



\subsubsection{Object builder}
\label{ch6_sec6_subsec1_subsubsec3}

The Object Builder is a connecting bridge between the Quad Bot and the Classification module. We
concluded that it is a good idea to treat our data as objects, so that we can use all the
object-oriented programming features (such as inheritance, or support for multiple instances). This
coding approach makes things very easy for the classification and presentation modules. In this
section we describe how the collected results are being converted to objects. The Object Builder's
architecture is depicted in the right part of Figure~\ref{fig-qbot-objbuilder}.

{\it Array with validated data}.
The Object Builder's input is the array that the Quad Bot produces. It contains all the collected
results that passed the Result Validator's checks.

{\it Property Constructor}.
This module implements a class that describes the properties of our objects. The properties that
are being assigned to the objects are the URL, the Title, the Abstract and one to four Rankings
(depending on the number of the selected search engines).

{\it Object Containers~1 and~2}.
The first advantage of using objects in the system's implementation comes almost immediately, as we
are provided with the ability to create multiple copies (not just references) of the objects. In
this compartment, all the objects (the results) are being transferred to two new, identical object
containers. The results enter the containers in groups. The first group consists of the results
that the first search engine returns, the second group consists of the results that the second
engine returns, etc. These containers will be the main tool in our effort to compare the search
engine rankings and generate the final ranked list.


\subsubsection{Classification module}
\label{ch6_sec6_subsec1_subsubsec4}

The Classification Module accepts the two result containers from the Object Builder and performs
the result ranking according to the selected ranking algorithm. Its architecture is illustrated in
the left part of Figure~\ref{fig-classification-presentation}.

\begin{figure}[!hbt]
\begin{center}
\begin{minipage}{4cm}
\centerline{\epsfig{file=Chapter6/figs/fig4,width=1.4in}}
\end{minipage}
\hspace*{2.5cm}
\begin{minipage}{4cm}
\centerline{\epsfig{file=Chapter6/figs/fig5,width=2in}}
\end{minipage}
\end{center}
\vspace*{-10pt}
\caption{(Left) Classification Module.\ \ \  (Right) Presentation Module.}
\label{fig-classification-presentation}
\end{figure}

{\it Overlapping Detector}.
This section is responsible for detecting the overlapping candidates and for creating the final
candidate list. It receives input from the two object containers and compares each object from the
first container, to all objects from the second container. When the URL properties of two objects
are identical, this object is marked as overlapping. Finally, the procedure constructs one
container that holds all candidates, overlapping or not. The overlapping candidates appear only
once in this container.

{\it Ranking Module}.
The Ranking Module accepts the candidate container that the Overlapping Detector constructs, but it
also receives the ranking algorithm that the user selected. The Ranking Module will apply the
QuadRank algorithm by default, unless the user selects another supported algorithm. Next, it
computes the weight factors and/or the Borda Scores. Finally, it sorts the candidate list on
ascending (for weight factors) or descending (for Borda Scores) order and passes the classified
list to the Presentation Module.


\subsubsection{Presentation module}
\label{ch6_sec6_subsec1_subsubsec5}

The task of this module is to construct the result page that will be presented to the user. In
comparison to the other system compartments, this one has the simplest architecture. In the right
part of Figure~\ref{fig-classification-presentation}, we illustrate a schematic diagram of its
internal structure.

{\it Parameter Receiver}.
In this section, a set of parameters and user preferences are being transferred to the module.
These preferences may either derive from user's direct selections, or from a previously stored
cookie. The innovative element here is the view selector. QuadSearch is capable of displaying the
results with the classic way that a search engine displays its results, but also can present the
results by using the array view. The array view will present a matrix that shows only the titles of
the candidates and the rankings they received from each search engine. This feature has been
developed because it offers an easier way to compare the candidates.


{\it Result Page Builder}.
The Result Page Builder is a HTML code production factory. It accepts the ranked result list and
the user preferences and constructs the source code of the result page from the scratch. Finally,
the page is displayed to the user through the user interface.



%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// SUBSECTION 6.6.2: QUADSEARCH FEATURES
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
\subsection{Features}
\label{ch6_sec6_subsec2}

In this section, a brief list of QuadSearch's primary features is presented.

{\it 1. Classic/Array view switch}.
This feature has already been mentioned earlier. The user is able to view the results in the
classic way, but can also select the array view that provides an easier way of comparing the
collected results.

\begin{figure}[!hbt]
\centerline{\epsfig{file=Chapter6/figs/results,width=4.7in}}
\vspace{-10pt}
\caption{The results' page}
\label{fig-inno-1}
\end{figure}

{\it 2. Related searches}.
Apart from the desired results, the QuadBot is capable of grabbing almost everything from the
results' pages that the exploited search engines transmit. In order to provide more specific
results, the search engines prompt their users to submit the queries that they propose. The QuadBot
can fetch these query strings and present it to the result page through the Presentation Module.

{\it 3. File type filter}.
Many users tend to search the Web for specific file types (e.g., Adobe Acrobat or Microsoft Word
files) and QuadSearch includes a similar feature. The user can select one of the most popular file
extensions and perform a Web search. At this time, the QuadSearch engine supports searches for the
following file formats: PDF, DOC, XLS, PS, RTF and PPT.

{\it 4. Search for scientific articles}.
QuadSearch supports searches for scientific articles in the richest scientific databases. Google
Scholar is also included in these databases. This type of search can be accessed from the
``Science" link and will return papers, technical reports and books approved by the scientific
community related to the query terms.

{\it 5. Query string explosion feature}.
This feature (see Figure~\ref{fig-inno-1}) splits the query string to its search terms and gives
the user the ability to perform `single term' searches. For example, the query string `electronic
engineering' is being split to the terms `electronic' and `engineering'. By clicking on any of
these words QuadSearch will perform a Web search.

\begin{figure}[!hbt]
\centerline{\epsfig{file=Chapter6/figs/options,width=4.7in}}
\vspace{-10pt}
\caption{Part of the options' page is where the Ranking Algorithm Selector and the Engine Bombing Protection lay.}
\label{fig-inno-2}
\end{figure}

{\it 6. Ranking Algorithm Selector}.
This feature (see Figure~\ref{fig-inno-2}) is only accessible from the options page and provides the user
with the facility to determine how the collected results will be ranked, by employing one (or more) of the
supported algorithms. At this time, QuadSearch supports our KE Algorithm and the Borda Count method. It also
provides a third option that utilizes both algorithms and presents the results in array view (comparison mode).
It is in our intentions to include more ranking algorithms in the system (e.g., Markov Chains).

{\it 7. Engine Bombing Protection}.
When various search resources are being exploited, a possibility that many similar results will enter
the result's list always exists. This phenomenon is called {\it engine bombing}. For example, it is not
very informative and useful for a user to submit a query and receive five or more results from the same
domain in the top, say, twenty listing. Thus, we developed a feature (which can be enabled or disabled)
to prevent multiple results coming from the same domain to enter into the result list; alternatively the
user can select the maximum number of such results.


%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// SUBSECTION 6.6.1: QUADSEARCH EFFICIENCY
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
\subsection{Efficiency Evaluation}
\label{ch6_sec6_subsec3}

In the previous subsection, we have demonstrated how the use of the proposed rank aggregation
method can lead to better rankings, when compared to the rankings that the component engines
produce. We have indicated that the term ``better'', concerns both Precision and quality of the
returned results.

The second most important measure of a system's performance, is how quickly it responds to a given
query. It may well produce qualitative results, but this could be close to useless, unless these
results are produced in reasonable times.

Before we proceed to the evaluation of \textit{QuadSearch}'s response, we discuss all the time
penalties that any metasearch engine has to suffer, before it presents a list of results to the
user. We also define \textit{idle time}, as the total intermediate time between the moment the user
submits a query and the moment that the engine presents the results. All idle times presented here,
are expressed in seconds. In addition, henceforth, we will use the term \textit{server}, to refer
to the machine that hosts the search system.

The idle time is affected by numerous factors. Generally, we cannot exactly calculate it
beforehand; we can only estimate a value, which is computed by using the following relationship:

\begin{equation}
\label{time-equation}
t_{tot}=t_{req}+t_{res}+t_{ret}+t_{pr},
\end{equation}

where

\begin{itemize}
\item{\textit{$t_{req}$} represents the request time, that is, the time that the system needs to
send the request to its component engines. It depends on the server's upload capabilities. This
time is usually infinitesimal.}
\item{\textit{$t_{res}$} is the total time the metasearch engine has to wait for the component
engines to respond. In other words, this is the time a single engine consumes to search its index
structure and apply its own ranking algorithm to form the results' list. As it is obvious, there is
no technique that can be applied to improve this timing.}
\item{\textit{$t_{ret}$} signifies the results' pages downloading duration. This is the most
unstable factor that affects a metasearch engine's response. It depends on the server's download
capability, the number of concurrent users, the daytime and other parameters that are rigorous to
manage. In general, improving the network capacity of the server, leads to smaller download
delays.}
\item{\textit{$t_{pr}$} indicates the overhead added by the execution of the fusion and ranking
algorithms of the metasearch engine. The application of additional filters (such as the anti-spam
filter and engine bombing protection), further increases this time.}
\end{itemize}

To evaluate the \textit{QuadSearch}'s speed, we have formed a set of fifteen queries. During the
tests we tried to identify some terms whose inverted lists were stored in the component engines'
caches and some that were not. These queries have been submitted to \textit{QuadSearch} with
various parameters enabled and disabled, for all the proposed rank aggregation methods. We also
exploit all of the four component engines available.

\begin{table}[hbt!]
\small
\begin{center}
\begin{tabular}{|l|c|c|c|c|c|}\hline
\multirow{2}{*}{Query}  & \multirow{2}{*} {$t_{ret}$} & \multirow{2}{*} {$N$}       & \multicolumn{3}{|c|} {$t_{pr}$}           \\\cline{4-6}
                        &                             &                             & {Borda Count} & {Outranking} & {QuadRank} \\\hline
tokyo~hotel             &           1.53              &             90              &    0.04       &     0.09     &    0.05    \\\hline
artificial~fertilizers  &           1.41              &             87              &    0.04       &     0.08     &    0.05    \\\hline
free~flv~player         &           1.34              &             80              &    0.03       &     0.07     &    0.04    \\\hline
lewis~hamilton          &           1.56              &             90              &    0.04       &     0.09     &    0.05    \\\hline
markov~chains           &           1.38              &             79              &    0.03       &     0.07     &    0.04    \\\hline
greenhouse~effect       &           1.30              &             77              &    0.02       &     0.07     &    0.04    \\\hline
h-index                 &           1.42              &             87              &    0.04       &     0.08     &    0.04    \\\hline
marine~biology          &           1.38              &             85              &    0.04       &     0.08     &    0.05    \\\hline
public~key~encryption   &           1.64              &             90              &    0.04       &     0.11     &    0.06    \\\hline
voice~over~ip           &           1.55              &             89              &    0.04       &     0.10     &    0.06    \\\hline
waterfall               &           1.29              &             94              &    0.04       &     0.10     &    0.04    \\\hline
scorched~earth          &           1.34              &             85              &    0.04       &     0.08     &    0.05    \\\hline
apple                   &           1.21              &             92              &    0.04       &     0.09     &    0.04    \\\hline
cold~war                &           1.22              &             84              &    0.03       &     0.08     &    0.04    \\\hline
iran~nuclear~weapons    &           1.54              &             99              &    0.05       &     0.11     &    0.07    \\\hline
AVERAGE                 &           1.41              &             87.2            &    0.037      &     0.086    &    0.048   \\\hline
\end{tabular}
\end{center}
\caption{\textit{QuadSearch} response times for various rank aggregation methods and 30 requested results per engine.}
\label{table-perf-30}
\end{table}

In Table~\ref{table-perf-30} we record the time performance of various rank aggregation methods in
the environment of QuadSearch for each query of our set, when the system requests $k=30$ results
from its component engines. The second column shows the retrieval times $t_{ret}$, that is, the
time the metasearch engine needs to download the result lists from the component engines. In the
third column we record the length of the list which derives from the fusion of the input rankings,
whereas the three last columns contain the times each algorithm needs to rank the merged list.

Borda Count is the fastest algorithm and this is expected since the score of each document is
computed by simply adding the individual rankings it received by the component engines. QuadRank is
somehow slower (by a margin of about 23\%) since the evaluation of the $Z(c)$ and $U(c)$ scores is
slightly more expensive. The Outranking approach is by far the slowest method since each document
must be compared with the rest $N-1$ documents in all 4 input rankings. Therefore, it is
approximately 2.3 times slower than Borda Count and 1.8 times slower than QuadRank.

Notice that processing times for Borda Count and the Outranking Approach depend only on the number
of documents of the merged list. Therefore, the more documents the merged list contains, the slower
Borda Count and the Outranking Approach become. On the other hand, apart from the number of
documents of the merged list, the timings of QuadRank also depend on the length of the submitted
query due to the existence of zone weighting. Consequently, we expect from longer queries to be
processed at lower rates.

\begin{table}[hbt!]
\small
\begin{center}
\begin{tabular}{|l|c|c|c|c|c|}\hline
\multirow{2}{*}{Query}  & \multirow{2}{*} {$t_{ret}$} & \multirow{2}{*} {$N$}       & \multicolumn{3}{|c|} {$t_{pr}$}           \\\cline{4-6}
                        &                             &                             & {Borda Count} & {Outranking} & {QuadRank} \\\hline
tokyo~hotel             &           2.01              &            276              &      0.23     &     0.82     &    0.31    \\\hline
artificial~fertilizers  &           1.95              &            295              &      0.25     &     0.94     &    0.37    \\\hline
free~flv~player         &           1.94              &            259              &      0.21     &     0.74     &    0.35    \\\hline
lewis~hamilton          &           2.13              &            277              &      0.22     &     0.85     &    0.30    \\\hline
markov~chains           &           1.98              &            267              &      0.21     &     0.78     &    0.36    \\\hline
greenhouse~effect       &           1.99              &            255              &      0.21     &     0.71     &    0.28    \\\hline
h-index                 &           2.03              &            297              &      0.26     &     0.97     &    0.31    \\\hline
marine~biology          &           2.13              &            269              &      0.22     &     0.80     &    0.29    \\\hline
public~key~encryption   &           2.07              &            292              &      0.25     &     0.93     &    0.38    \\\hline
voice~over~ip           &           2.22              &            296              &      0.26     &     0.96     &    0.57    \\\hline
waterfall               &           2.25              &            306              &      0.26     &     1.02     &    0.33    \\\hline
scorched~earth          &           1.99              &            278              &      0.22     &     0.85     &    0.32    \\\hline
apple                   &           1.91              &            274              &      0.22     &     0.82     &    0.26    \\\hline
cold~war                &           2.07              &            286              &      0.24     &     0.88     &    0.33    \\\hline
iran~nuclear~weapons    &           2.40              &            314              &      0.27     &     1.08     &    0.40    \\\hline
AVERAGE                 &           2.07              &            281.6            &      0.24     &     0.87     &    0.34    \\\hline
\end{tabular}
\end{center}
\caption{\textit{QuadSearch} response times for various rank aggregation methods and 100 requested results per engine.}
\label{table-perf-100}
\end{table}

In Table~\ref{table-perf-100} we repeat the experiment by requesting top-100 lists. Apparently, in
this case the average retrieval time increases significantly as more time is required to download
larger lists. Furthermore, the fusion and ranking duration increases, since now we have to process
more documents. Notice that while QuadRank remains slower than Borda Count by a relatively stable
percentage of 24\%, the performance of the Outranking Approach degrades considerably faster (2.5
times slower than QuadRank and 3.6 times slower than Borda Count).



%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
%///////////////////////////// SUBSECTION 6.7: CONCLUSIONS
%///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
\section{Conclusions}
\label{ch6_sec7}

In this chapter we discussed the problem of rank aggregation and we studied the current
state-of-the-art approaches for solving the problem. We introduced QuadRank, a method which is
especially designed for aggregating results collected from Web search engines (component engines),
that is, it primarily concerns Web metasearch engines. QuadRank takes into consideration multiple
attributes such as the individual rankings assigned by the component engines, the number of
appearances of an item in the result lists of the component engines, and the physical location
(zone or field) of a document where a query term occurs. QuadRank also performs a URL analysis and
compares the locality of the page to the locality of the user and assigns scores accordingly.

QuadRank was exhaustively attested by using data from the 2009 Text Retrieval Conference. Moreover,
we used results from our own test queries; in both experimental phases we concluded that QuadRank
outperformed Borda Count, the Outranking Approach and the Condorcet method by a significant margin.
Furthermore, we examined another family of rank aggregation methods, the KE family. The member
functions of KE can be seen as the ancestors of QuadRank.

All the proposed methods have been implemented within QuadSearch, a prototype metasearch engine
which have been developed as a testbed for designing new rank aggregation methods and general
solutions for the wider problem of metasearching.


