<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">In this chapter we conclude this dissertation and we report the most important results of the
research conducted here.

In chapter~\ref{chap:ch2} we studied issues regarding the improvement of the query throughput of
Web search engines. Query throughput is a metric which reflects the rates at which a search engine
responds to the incoming requests in a time unit. It is an extremely important measure of the
efficiency, since the modern Web search engines now accept user queries at rates touching 10
thousands per second. Such tremendous workloads dictate that all the underlying subsystems of a
search engine must be fully optimized.

Our effort was towards the proposal of efficient methods for the organization and the compression
of the data stored within the inverted index. The inverted index is the most important data
structure maintained by search engines in order to generate ranked results in response to user
queries. They are mainly composed i) by the lexicon, a list which contains all the terms appearing
in the document collection, and ii) the inverted file which stores for each term of the lexicon,
one list (the inverted list) with the representations (or postings) of all the term occurrences in
the document collection.

According to the recent literature, the most robust algorithms for compressing that data stored in
the inverted index are those which are capable of encoding entire bundles of integers, such as
PForDelta~\cite{h2005}, and VSEncoding~\cite{sv2010}. These methods combine satisfactory
compression effectiveness with high decompression speed and are considered ideal for encoding the
document identifiers (docIDs) and the frequency values of the postings of an inverted list.
Nevertheless, regarding the positional data accompanying each posting they are not equally useful
because during query processing it is required that we decode only limited data; consequently, the
decompression of entire blocks of integers is apparently redundant. Furthermore, these methods do
not support direct access to the desired data and they introduce a costly look-up operation.

To address these drawbacks we introduce \textit{PFBC} (Positions Fixed Bit Compression)
\cite{ab2012}, a method which encodes the positions of an inverted list block by using a fixed
number of bits. PFBC also dictates that we store within the skip table one additional pointer value
for each block of an inverted list; this pointer shows the exact location of the starting point of
the compressed positions. We show that such an organization allows direct access to the positional
data, since we are able to compute the location of the required data instead of looking up for it.
Moreover, we decode only the information actually needed. The experiments on various experimental
index setups demonstrated that PFBC:

\begin{itemize}
\item{Decodes 7--11 times fewer data than PForDelta and VSEncoding.}
\item{Decodes the positional data required to process a query 5 times faster than the adversary
approaches.}
\item{Accesses the desired data instantly and no costly look-ups are required.}
\item{Does not require the existence of an additional positions look-up data structure.}
\item{Requires much fewer pointers than the other approaches such as indexed lists.}
\item{Introduces a compression loss of about 3\%, resulting in slightly increased index sizes.
However, this cost is amortized by the smaller size of the accompanying data structures.}
\end{itemize}

We also investigated strategies of including additional information within the inverted index by
considering the structure of the Web documents. This structure is expressed by the usage of zones
(or fields) and in chapter~\ref{chap:ch2} we discussed how this additional information can be
integrated in the index. We replaced the plain positional information by the notion of the
\textit{term occurrence}, an enriched representation which apart from the positional value, also
stores the identifier of the zone where the term is located within the document.

Almost immediately, a new problem was created: how can we encode the additional information without
suffering prohibitively large index sizes and without decreasing query throughput? To address this
problem we were based on the main ideas behind PBFC. We introduced \textit{TZP} \cite{akb2012i}, a
method for compressing the aforementioned word occurrences. TZP dictates that each document zone is
assigned a unique zoneID value and that each zoneID is accompanied by the corresponding positional
value. This position-zoneID pair is initially encoded in a 32-bit space by reserving the $z_b$ most
significant bits for the zoneID. In the sequel, these encoded representations are again encoded by
employing a fixed number of bits, in a fashion similar to that of PFBC. Due to this strategy TZP
exhibits the same advantages over the competitor compression algorithms, as PFBC. The experimental
evaluation of TZP showed that the enriched inverted index which includes zone information is only
11--13\% larger than a plain positional index, and it introduces no additional time costs during
the evaluation of a query.

Chapter~\ref{chap:ch3} was dedicated to the identification of influential bloggers in community
blog sites. Since this is a relatively new problem, there was only one competitor approach: the
influence-flow model of~\cite{agarwal2}. In this chapter we exposed the main drawbacks of this
model and we introduced MEIBI and MEIBIX, two new metrics which eliminate these drawbacks. In
short, the benefits of these two methods are:

\begin{itemize}
\item{They are \textit{time-sensitive}: Blogosphere, is extremely volatile; millions of blog posts
are produced in short periods of time, new bloggers enter the community whereas others leave it at
rapid rates. Therefore, a robust influence evaluation metric should not overlook this crucial
parameter. MEIBI assigns influence scores to the bloggers by taking into consideration the elapsed
time since the publication of his/her articles. On the other hand, MEIBIX considers an article
influential if the article receives references in the present, regardless of its publication date.
In contrast to the preliminary influence-flow model, both metrics identify the bloggers who are
\textit{presently} influential.}
\item{They take into consideration the \textit{productivity} of a blogger: The existing approach
assigns scores to the bloggers by accounting only the best post, however, this is apparently
inadequate; a blogger who publishes only a few very influential posts in log periods of time
cannot be considered more influential than a frequent writer whose posts are equally influential.}
\item{They are \textit{simple}: The $\iota$-scores of the influence-flow model are defined in a
recursive manner similar to PageRank. This requires multiple iterations before the system converges
and it could lead to stability problems due to the negative influence assigned to the outgoing
links. On the other hand, the proposed approaches are based on simple algebraic scores which can
be computed directly.}
\item{They do not require \textit{fine-tuning}: In contrast to the influence-flow model, MEIBI
and MEIBIX do not include user-defined parameters.}
\end{itemize}

Nevertheless, the plain identification of influential bloggers may not be adequate since the matter
of productivity is equally important. For this reason we posed the issue of the bloggers
classification not by assigning a single evaluation metric, but by determining a point on a two
dimensional productivity-influence plane. We introduced a new metric, \textit{BP/BI-index}, an
indicator which is used to classify the bloggers of a community into one of the following
predefined classes: $\mathcal{A}$ (contains bloggers who are both productive and influential),
$\mathcal{B}$ (contains those who are influential but not productive), $\mathcal{C}$ (the opposite
of $\mathcal{B}$, consists of productive but not influential bloggers), and $\mathcal{D}$ (nor
productive, nor influential)~\cite{akritidis2011}.

The proposed MEIBI, MEIBIX and BP/BI-index where attested by using data crawled from real-world
community blog sites. The experiments demonstrated the usefulness of our methods by providing
more sensible and effective blogger rankings and classifications.

In chapter~\ref{chap:ch4} we dealt with the problem of improving the retrieval effectiveness in Web
search engines and the blog vertical search engines. Regarding the former, we examined the
usefulness of combining robust scoring schemes such as term proximity and zone weighting into a
single ranking function. We introduced BM25TOPF~\cite{akb2012i}, a scheme which is based on the
field structure of the Web documents discussed in chapter~\ref{chap:ch2}, and requires that both
zone and positional information is stored within the index. The main characteristics of BM25TOPF
are summarized into the following list:

\begin{itemize}
\item{It takes advantage of the enriched index representation of chapter~\ref{chap:ch2}, which
stores both positional and zone data within the inverted lists' postings.}
\item{It combines the essence of BM25F which rewards the words appearing in specific locations
(such as the title, or the URL) with the spirit of BM25TP which rewards the documents having
the query terms in a close proximity.}
\item{It takes into account the correct term ordering, that is, it boosts the documents which
have the query terms in the same order as they appear in the submitted query.}
\end{itemize}

The retrieval effectiveness of BM25TOPF was experimentally measured by using a set of 50 queries
from the Adhoc task of the TREC 2009 conference. The document collection we employed was the
ClueWeb09-B dataset, a large repository comprised of about 50 million Web pages, whereas the
underlying index structure was of the form of chapter~\ref{chap:ch2}. Our method outperformed
BM25F, the most effective competitor function, by a margin of approximately 6\%.

The second contribution of chapter~\ref{chap:ch4} concerns the opinionated document retrieval in
blog search engines. The problem is of remarkable importance, since a high-quality opinion
expressed by an influential blogger affects a large number of users and its impact is large. As
mentioned in chapter~\ref{chap:ch4}, a positive opinion about a product can significantly increase
its commercial success whereas in contrast, multiple negative statements about a politician can
decrease his/her publicity and affect the success of his/her political career. Similar examples
include artists, events, travel locations, service providers, and generally every judgeable aspect
of life.

Until now, the opinionated retrieval models did not consider the issue of the objective quality of
a blog post. In other words, the retrieved documents were scored by accounting only their relevance
to the given query, and the grade of their ``opinionatedness''. In this work we highlighted that
similarly to the traditional Web retrieval, it is essential that we develop special
query-independent metrics which indicate the overall importance of a blog entry in combination with
the other two criteria. We introduced the \textit{QUIQS (Query-Independent Quality Metrics)}, a set
of indicators which determine the importance of a blog post according to the reputation of their
author, the importance of the hosting blog site, and several query-independent statistics (i.e.
number of incoming references, number of comments, word length etc). After the introduction of
QUIQS, we developed a model which assigns scores to the blog posts by linearly combining its
IR-score, its opinion score, and the value of QUIQS.

The experimental evaluation of this model was performed by using 20 queries from the Blog Track of
the TREC 2009 conference, against Blogs08, a large repository of 28 million blog entries.
Compared to the other state-of-the-art approaches which did not consider objective quality metrics,
our model exhibited better MAP by about 7.5\%.

In chapter~\ref{chap:ch5} me presented numerous solutions to problems which are related to the
academic search engines, digital libraries and scientific databases. Initially we studied the most
important scientometrics, that is, indicators which evaluate the research work of a scientist. We
introduced the notion of coterminal citations and we presented them as a form of self-citations and
co-citation. Based on this spirit, we introduced the $f$-index, a new metric for quantifying the
impact of coterminal citations in scientific networks.

The current academic search engines and digital libraries have recently included the scientometrics
in the automated (or semi-automated) profile pages of the authors. Since until recently the sizes
of these systems was small the problem of computing these values was of no special interest.
However, the quick growth of their repositories\footnote{Google Scholar's repository consists of
hundreds of millions of scientific documents, whereas as of April 2013, Microsoft Academic
contained approximately 40 million articles and 19 million author profiles.} in combination with
the increased users' interest have rendered such large-scale problems particularly challenging.
In chapter~\ref{chap:ch5} we presented four strategies for computing the most popular scientometric
indicators in parallel by using Hadoop/MapReduce, a fault-tolerant framework for solving problems
in large scales~\cite{ab2012c}. The experimental efficiency measurements of these strategies was
performed on two different clusters by using the CiteSeerX dataset, a 30 GB collection of research
articles. These experiments revealed that the usage of in-Mapper Combiners improves running times
by about 35\%, whereas it reduces network bandwidth by 43\%.

In the sequel, we introduced the problem of identifying the most attractive research areas for new
scientists~\cite{akb2012b}. Although this problem may seem similar to the generic determination of
the emerging research areas, the one we study here is different, since there are emerging fields of
science which are not suitable for starters. We defined the primary characteristics of the starters
and we referred to their lack of experience and trust, two factors which may render some research
topics ``hostile'' to them. The model we proposed is based on a number of features which combine
these characteristics to the attributes of the emerging research areas. In the sequel, we
experimentally demonstrated the effectiveness of this model and we concluded that not all popular
or emerging research fields are suitable for new scientists.

The fourth contribution of chapter~\ref{chap:ch5} concerns a popular data mining task, that of
document classification. In our study we were mainly interested in proposing a robust method for
classifying research articles, a problem which is slightly different than the one of standard
document classification. Although these problems are different, their usefulness is equally high;
an effective research article classification method can be exploited to develop robust search tools
such as searches for relevant items, suggestions of similar papers and scientists, query expansion
methods and several others.

In this chapter we also introduced a supervised machine learning (ML) algorithm~\cite{ab2013}. Our
method is based on a predefined set of labels and a set of papers (training set) which have already
been assigned one or more labels from the label set. It extracts the keywords, authors, journals,
and co-authorship information from the elements of the training set and constructs a data model
comprised of three relevance description vectors. Each of these vectors stores some information
which indicates and quantifies the relationship of each keyword, author/co-author, and journal to
each candidate label. In the sequel, we apply this model in combination with a scoring function
(i.e. inverse document frequency, logarithmic, etc) to assign labels to the elements of the testing
set. The evaluation of our algorithm was performed by using the cross validation rule and the
CiteSeerX dataset. We compared it against the two state-of-the-art ML algorithms, the Support
Vector Machines and AdaBoost.MH; our algorithm was steadily more accurate than both of its
adversaries, whereas AdaBoost.MH failed to complete some tests due to its enormous memory
consumption.

Finally, in chapter~\ref{chap:ch6} we dealt with the generic problem of rank aggregation and with a
specialization of it, the ranking fusion in Web metasearch engines. The issue in question concerns
the determination of effective algorithms in order to merge and rearrange ranked lists of results
deriving from a number of information sources. Here we introduced a family of such methods,
comprised of the \textit{KE} algorithm, and a number of variants which takes into consideration
additional parameters~\cite{akb2007,akb2008}. The basic KE methodology introduces a scoring formula
which is based on several statistics such as the items' individual rankings, the number and the
length of the component lists', and the total number of each item appearances. We also introduced a
set of variants with the aim of improving the effectiveness of KE in the context of metasearching.

Based on the strong points of the KE family, we defined another rank aggregation method, namely
\textit{QuadRank} \cite{akb2011el} which also 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 \textit{QuadSearch} \cite{akb2007}, 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. An operational
implementation of QuadSearch can be accessed under http://quadsearch.csd.auth.gr.

</pre></body></html>