\documentclass[pdftex]{article}
\usepackage{alltt,hyperref,color}
\textwidth 6.5in \textheight 9in
\oddsidemargin 0in \evensidemargin 0in
\topmargin 0in \headsep 0pt \headheight 0pt
\parskip .8ex plus .3ex
\renewcommand{\topfraction}{.9}
\renewcommand{\dbltopfraction}{.9}
\renewcommand{\bottomfraction}{.9}
\renewcommand{\textfraction}{.1}

\def\parent{\mathop{\smash{\rm parent}}\nolimits}
\def\good{\mathop{\smash{\rm good}}\nolimits}
%\def\exturl#1{\htmladdnormallink{#1}{#1}}
\def\exturl#1{\url{#1}}
\def\altavista{Alta\,Vista}
\def\yahoo{Yahoo!}
\def\apache{Apache}

\def\figpath{figure}
\long\def\todo#1{\textcolor{red}{#1}}

\begin{document}

\title{Automatic Web Resource Discovery}
\author{Soumen Chakrabarti\thanks{Email: \texttt{soumen@cs.berkeley.edu}}}
\date{IBM Almaden Research Center}
\maketitle



\section{Introduction}

Classical information retrieval (IR) is concerned with indexing a
collection of documents and answering queries by returning a ranked
list of relevant documents~\cite{FrakesB92,WordNet593,SaltonM83}.
With the growth of the web, the problems of ambiguity, context
sensitivity, synonymy and polysemy that are inherent in natural
languages, together with the \emph{abundance} of web pages related to
prominent topics, have exacerbated the difficulty of narrowing
down the user's information need.

%Stopword elimination and word morphing or stemming have been deviced
%to facilitate more robust matches~\cite{WordNet,Frakes}.  The user may
%also provide relevance feedback into the system after and initial
%query by marking the initial responses as good or bad; this can be
%used by the system to compute a more informed query
%response~\cite{RAT}. Although widely used for reference searches in libraries

%The emphasis on relevance, coverage and quality
%has never been as critical as on the web today.

Most search sites
%Following \yahoo, most portals such as \altavista, Excite, HotBot and others
have added directory-based topic browsing.  The web is organized as
a tree of topics, similar to the Dewey decimal
system, the Library of Congress catalog, or the
Patent and Trademarks Office subject codes.  Tree nodes are
maintained by ontologists, ranging from
paid college grads (\yahoo) to specialist volunteers (The Mining Co.).
Directory sites are very popular.  Because of human judgement,
pages placed in a topic directory tend to be not only relevant, but
also exemplary and influential.  However, human judgement is
slow, subjective and noisy.  It is labor-intensive to keep
these directories comprehensive.  The \yahoo{} strategy is
adequate for common users and shallow topics.  However, the
information needs of web-savvy users who are using the web for serious
research for extended periods are very hard to address.  The Mining
Co. strategy may be biased because of sparsity of experts; at
any rate it is biased away from the most accomplished and busiest
people.

%Some organizations such as \yahoo{} directly employ
%ontologists, whereas others like the Mining Co. and the Mozilla
%Directory Project solicits specialist volunteers to develop topics
%autonomously.  In either case, this is a labor-intensive process.



\section{Topic distillation}

The web is an example of a \emph{social network}.
Social networks have been extensively
researched~\cite{WassermanF93}.  Social networks are formed between
academics by co-authoring, advising, serving on committees; by movie
personnel by directing and acting; by musicians, football stars,
friends and relatives; infection transmitted by contact;
papers citing other papers, and web pages
hyperlinked to other web pages.
Social network theory is in part concerned with finding
influential nodes in the graph, representing important papers,
core of epidemics, etc.


\subsection{Social network analysis in IR}

IR literature includes insightful
studies of citation, co-citation, and influence of academic
publication~\cite{Larson96}.  Starting in 1996, a series of applications
of social network analysis were made to the web graph, with the
purpose of identifying the most authoritative sites and pages about a
user query.


\paragraph*{Google:}
If one wanders on the web for infinite time,
following a random link out of each page, then
%Imagine one had infinite time to browse the web.  Starting at some
%arbitrary page, one of the out-links is chosen at random to visit the
%next page.  Over an infinite number of link clicks,
different pages will be visited at different rates; popular pages with
many in-links will tend to be visited more often.  PageRank and
Google, invented by Brin and Page~\cite{BrinP98} crawl the
web and simulate such a random walk on the web graph in order to
estimate the visitation rate, which is used as a score of popularity.
Given a keyword query, matching documents are
ordered by this  score.


\paragraph*{HITS:}
Hyperlink induced topic search (HITS) \cite{Kleinberg98} is slightly
different: it does not crawl or pre-process the web, but depends on a
search engine.  A query to HITS is forwarded to \altavista, which
retrieves a subgraph of the web whose nodes (pages) match the query.
Pages citing or cited by these pages are also included.  This expanded
graph is analyzed for popular nodes using a procedure similar to
Google, the difference being that not one, but two scores emerge: the
measure of a page being an authority, and the measure of a page being
a \emph{hub} (a compilation of links to authorities).


\paragraph*{ARC and CLEVER:}
HITS's graph expansion sometimes leads to topic \emph{contamination}
or \emph{drift}.  E.g., the community of \emph{movie awards} pages on
the web is closely knit with highly cited (and to some extent
relevant) home pages of movie \emph{companies}.  Although \emph{movie
awards} is a finer topic than \emph{movies},
the top movie companies emerge as the victors upon running HITS.
This is partly because in HITS (and Google)
all edges in the graph have the same importance.
Contamination can be reduced by recognizing that hyperlinks that contain
\emph{award} or \emph{awards} near the anchor text are more relevant for
this query than other edges.  Such heuristic modification of edge
weights significantly improve the quality of query results.  In user
studies, the results compared favorably with lists compiled by humans,
such as \yahoo{} and Infoseek~\cite{Clever1}.


\paragraph*{Bharat and Henzinger:}
Another way to integrate textual content to avoid contamination of the
graph is to model each page according to the ``vector space''
model~\cite{SaltonM83}, and then prune the graph expansion at nodes
whose corresponding vectors are outliers with respect to the set of
vectors corresponding to documents directly retrieved from the search
engine~\cite{BharatH98}.  Impressive improvements in precision have
been observed.


\subsection{Discussion}

In principle, all the topic distillation systems discussed above can
handle ad-hoc queries, because of the dependence on a search engine in
the first step.  In practice, these systems produce good answers if
the query response induces a graph that is dense enough to derive
robust popularity scores.  Because it uses a precomputed page rank
independent of the query, Google is the fastest system.  Graph
construction at query time is involved in all the other methods.
Bharat and Henzinger describe several heuristics that cut down the
query time substantially.




\section{Portholes and focused crawling}

All the distillation systems depend on large, comprehensive web crawls
and indices.  The best crawlers running on heavy-duty servers can
cover 35--40\% of the web, currently over 340 million
pages~\cite{BharatB98}.  Googol has crawled about 60 million pages to
date.  There is a sobering maturity that size is not
everything~\cite{Gillmor98,Mirapaul98,LidskyS99}; seasoned users need deep,
specific \emph{portholes}, not shallow, generic \emph{portals}.  There
is a great need for topic-specific crawlers that
build focused libraries of web resources.  We will first discuss
why this cannot be done using topic distillation and then discuss a
new approach called \emph{focused crawling}.




\subsection{Exploiting topic distillation}

Topic distillation systems work well
for well-connected communities concerning broad topics.
%Many of the pages listed in the major web directories can be verified
%to already belong to large and dense subgraphs of the web, comprising
%many good hubs and authorities.
It is thus tempting to use a topic distillation system to generate a
web taxonomy in the following trivial way: with each node in
the taxonomy, associate a keyword query that describes the topic,
and run a distillation program.  While the simplicity is
appealing, it is not easy to make this succeed.

First, constructing the query involves trial and error, and a fair
amount of thought.  E.g., we needed the query \texttt{+"power suppl*"
"switch* mode" smps -multiprocessor* "uninterrupt* power suppl*" ups
-parcel} to do a good job for
\texttt{/Business\&Economy/Companies/Electronics/PowerSupplies}.
(\texttt{SMPS} stands for Switch Mode Power Supply, but also matches
pages containing \texttt{SMPs}, or Symmetric Multi-Processors!
Similarly with UPS and parcel.)  In a study with 966 nodes from
\yahoo, in order to match (in the opinion of blind testers) the
quality of \yahoo, queries had to be tuned by hand until the average
query had 7.03 terms and 4.34 operators (\texttt{"+-*}), in sharp
contrast to the average \altavista{} query having 2.35 words and only
0.41 operators.  These queries are not a one-time effort, because
inclusion of additional topic vocabulary, which may not be known a
priori, improved the results.  E.g., good results were obtained for
``European Airlines'' using the query \texttt{+lufthansa +iberia +klm}
(the fourth response from \altavista{} was itself a hub).

The second issue arises from the aforesaid susceptibility to
contamination from popular but irrelevant nodes.  The contamination
problem can be addressed in a few ad-hoc ways: stop-sites, term
weighting and edge weighting.  Stop-sites are nodes forcibly removed
from the graph before the iterations.  Query terms can be assigned
weights by humans to be used for better ranking.  The weights of links
incident with example pages, or lexically close to links to example
pages, can be increased artificially.  These fixes are ad-hoc; there
are no principles for setting edge weights guided by a precise model
of hyperlinkage.



\subsection{Learning from example}

The most successful way to combat contamination has been the use of
examples.  In 86\% of the test cases, specifying an example page
improved the results.

An example page offers more than just a forced node in the web graph
(as it was used above).  It has textual content, and is linked to
neighbors with more textual content.  In fact, extensive literature in
relevance feedback, automatic feature selection and classification
suggests that given examples, it is not even necessary to provide a
keyword query---the learning process will implicitly recognize the
important terms and compute the decision boundaries that can be used
to determine whether a given web page is relevant to a topic.

These decision boundaries can be derived implicitly and without any
human effort, given the example documents.  Most types of classifiers,
such as nearest neighbor (NN)~\cite{Swami},
bayesian~\cite{TAPER98,KollerS97}, support vector~\cite{SVM98}, are
capable of more reliable discrimination than keyword search, even if
boolean constructs were used.  (Boolean search induces hard and
brittle rules that tend to overfit, whereas well-designed learning
algorithms protect against overfitting.)

In the hypertext domain, it is
extremely important to build models and classifiers that take
link-based features into account.  The topic of a page influences its
text and the topics of pages in its neighborhood.  The latter
influence induces circularity, but this can be resolved by an
\emph{iterative relaxation} algorithm such as
HyperClass~\cite{HyperClass}.  Classification error reduced from 36\%
to 21\% in an experiment with US Patents.  With \yahoo, a more
dramatic reduction from 69\% to 20\% was observed.



\subsection{Guiding a focused crawler}

Provided a crawler is started off from connected examples of  topics,
it can be guided and scheduled by HyperClass.
The goal of a focused crawler is to
selectively seek out pages that are relevant to a pre-defined set of
\emph{topics}.  The topics are specified not using keywords, but using
exemplary documents that are analyzed by HyperClass.
The focused crawler analyzes its crawl boundary to find
the links that are likely to be most relevant for the crawl.  It
avoids irrelevant regions of the web.  This leads to significant
savings in hardware and network resources, and helps keep the crawl
more up-to-date.

Extensive focused-crawling experiments have been performed using
several topics at different levels of
specificity~\cite{Focus2}.  The system acquires relevant pages
steadily while standard crawling quickly loses its way, even though
they are started from the same root set.  Focused crawling is robust
against large perturbations in the starting set of URLs.  It discovers
largely overlapping sets of resources in spite of these perturbations.
In contrast with topic distillation systems, it is also capable of
exploring out and discovering valuable resources that are dozens of
links away from the start set, while carefully pruning the millions of
pages that may lie within this same radius.  These results suggest
that focused crawling is very effective for building high-quality
collections of web documents on specific topics, using modest desktop
hardware.


\begingroup \footnotesize
\bibliographystyle{abbrv}
\bibliography{acmcs}
\endgroup


\end{document}


problem spec and desirable features in the web domain
brief overview of main techniques-- k-nn, cosine, tfidf, bayes,
bayes net, neural net, support vector
popular wisdom and performance
hypertext and new challenges


relevance can be judged for each ad-hoc query, as in classical ir
role of topic directories and taxonomies
disambiguate queries
precompute frequent query answers
add intentional attributes to search
collect compact user profiles
targeted marketing
community formation



The initial euphoria about ``knowledge management'' is now all but
history, and there is evidence of realization that search technology
has been relatively stagnant in the last couple of years.  There is
also a sobering maturity that size isn't everything.

\begin{quotation}
Their biggest strength---massive size and reach---can also be a
drawback.  Even the best of the wide-ranging portals, such as Yahoo,
can't catalog every relevant site for every topic.
%Unless you're an
%expert at searching, even the best search engines, such as AltaVista,
%can overwhelm you with too many results that too often are irrelevant
%or out of date.
The most interesting trend is the growing sense of natural limits, a
recognition that covering a single galaxy can be more practical---and
useful---than trying to cover the entire universe.
%Sometimes, less really is more.
\begin{flushright}
Dan Gillmor \\
Technology Columnist, San Jose Mercury News
\end{flushright}

The emergence of portholes will be one of the major Internet trends of
1999.  As people become more savvy users of the Net, they want things
which are better focused on meeting their specific needs.  We're going
to see a whole lot more of this, and it's going to potentially erode
the user base of some of the big portals.

\begin{flushright}
Jim Hake\\
Founder, Global Information Infrastructure Awards
\end{flushright}

What's on the horizon?
... a continued proliferation of sites focused on individual needs.
\begin{flushright}
David Lidsky And Nancy Sirapyan \\
ZDNet
\end{flushright}

\end{quotation}
