\chapter{Introduction}\label{ch:intro}

Efficient execution of Y and Z style queries is critical to
effective query processing in the domain of web portals.
As discussed in \cite{ride2004}, if such queries are not
handled well, the consequences can be dramatic for web portal
providers.
Previous efforts at efficient execution of Y queries have
revolved around the use of M-trees~\cite{spie99}. Other
researchers~\cite{apweb00,bncod98} have documented the poor
performance of these index structures for realistic data
sets.
Z queries have not been addressed at all in the literature.
This thesis proposes a new indexing structure, the X-tree,
that provides substantial performance gains over M-trees,
and makes some progress towards efficient execution of Z
queries.

The next chapter gives a background to Y and Z queries, and
discusses the various approaches to answering them efficiently.
It also gives a method for evaluating the effectiveness of
index methods on large data sets. Chapter~\ref{ch:xtrees}
describes our new indexing method, the X-tree, and
chapter~\ref{ch:eval} demonstrates that it is indeed effective
for a large class of Y queries, and for some Z queries.
Chapter~\ref{ch:concl} concludes the discussion and points
out areas where further work on X-trees may yield efficient
evaluation of a wider range of Z queries.
