Using navigation data to improve IR functions in the context of web search.
As part of the process of delivering content, devices like proxies and gateways log valuable information about the activities and navigation patterns of users on the Web. In this study, we consider how this navigation data can be used to improve Web search. A query posted to a search engine together with the set of pages accessed during a search task is known as a search session. We develop a mixture model for the observed set of search sessions, and propose variants of the classical EM algorithm for training. The model itself yields a type of navigation-based query clustering. By implicitly borrowing strength between related queries, the mixture formulation allows us to identify the "highly relevant" URLs for each query cluster. Next, we explore methods for incorporating existing labeled data (the Yahoo! directory, for example) to speed convergence and help resolve low-traffic clusters. Finally, the mixture formulation also provides for a simple, hierarchical display of search results based on the query clusters. The effectiveness of our approach is evaluated using proxy access logs for the outgoing Lucent proxy.
INTRODUCTION
Searching for information on the Web can be tedious. Traditional
search engines like Lycos and Google now routinely
return tens of thousands of resources per query. Navigating
these lists can be time consuming and frustrating. In this
paper, we propose narrowing search results by observing the
browsing patterns of users during search tasks. The data to
support our work comes from devices in the network that
log requests as they serve content. We will focus primarily
on proxy access logs, but it is easy to see how these ideas
will carry over to the kinds of data collected by an Internet
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
service provider (ISP). From these logs, we first extract the
search path that a user follows. Then, we apply a statistical
model to combine related searches to help provide guidance
to people beginning searches on related topics.
We capture the interesting part of the search path in a
search session, which is a user's query together with the
URLs of the Web pages they visit in response to their query.
Implicit in our approach is a form of query clustering that
combines similar search terms on the basis of the Web pages
visited during a search session. These clusters are then used
to improve the display of search engine results. In this paper,
we illustrate the technique by creating a directory consisting
of two levels; each query is related to one or more groups
of URLs. When a user submits a query to a search engine,
we display the most relevant URLs from the most relevant
directory groups. Here "relevance" is based on the data
gathered from previous searches.
While clustering has been proposed previously in the IR
literature, our use of passively collected data to build search
sessions is new. With data of this kind we have access to
orders of magnitude more searching activity than is possible
with specialty search engines or opt-in systems. In addition
to exploring this new source of search session data, we
also propose techniques for leveraging existing (manually de-
rived) content hierarchies or labeled URLs to improve the
relevance of identified resources. Finally, to make this work
practical in a real proxy, we must consider a number of new
implementation issues, including online versions of our clustering
algorithms.
The balance of the paper is organized as follows. In Section
2 we discuss our search session extractor. In Section 3
we describe a particular mixture model for query cluster-
ing, and illustrate some of the groups it finds. In Section 4
we examine the kind of improvement our recommendations
represent over a standard search engine. Related work is
presented in Section 5, and we conclude with a discussion of
future work in Section 6.
2. SEARCH SESSION EXTRACTION
To formalize the extraction process, we introduce our basic
data element, the "search session." A search session is
the collection of words a user submits to a search engine
(also known as a "query string") together with the URLs
of the Web pages they visit in response to their request.
As users browse the Web, a proxy server will record every
URL they access, including HTML and PDF documents,
embedded GIF and JPEG images, and Java class files. Because
search engines deal primarily in Web pages, we filter
xxx.xxx.xxx.xxx 02/Dec/2000:01:48:55 "GET http://www.google.com/search?q=infocom+2001"
xxx.xxx.xxx.xxx 02/Dec/2000:01:49:03 "GET http://www.ieee-infocom.org/2001/"
xxx.xxx.xxx.xxx 02/Dec/2000:01:49:27 "GET http://www.ieee-infocom.org/2001/program.html"

Figure

1: A subset of the fields available in the proxy server log corresponding to a search session. The fields
are: the IP address of the client, a timestamp recording when the request was handled, the HTTP request
method, and the URL.
user requests by file type and keep only HTML documents.
Therefore, from this point on we will use the terms "Web
page," "HTML document" and "URL" synonymously. In

Figure

1 we present three lines of a proxy log that represent
a single search session. (The IP address of the user's
computer has been masked.) The query "infocom 2001" is
extracted from the URL in the first line of this figure using
a set of manually-derived rules for www.google.com. We
maintain a list of such rules for each of the most popular
search engines, allowing us to automatically tag and parse
log lines corresponding to search queries. Every time a user
posts a query to one of the search engines in our list, we
initiate a new search session.
Once a new session has been initiated, we then examine
the link structure of the URLs subsequently requested by
the user. Those pages that can be traced back to the list of
search results (either directly or indirectly through one or
more links) are included in the search session. We determine
that the session has ended if either the user makes another
request to a search engine, or if an hour has passed since
the last addition to the session. 1 In Figure 2 we list the
search session extracted from the log fragment in Figure 1.
We refer to a search session as completed if it contains at
least one URL. In the remaining cases, we assume the user
examined the search engine results and decided that none
of the Web pages were relevant.
Search session
session id 1001
user id 873
query infocom+2001 1914.59305
urls www.ieee./2001/ 1914.59340 1

Figure

2: Sample search session. The fields include
a session ID, user ID (based on the IP address of
the client), the query and the time it was submitted
(a truncated Julian date), and the requested URLs,
again with timestamps. The last column records
whether or not the URL was linked directly to the
search results page (1 or 0, respectively).
We have implemented a search session extractor that takes
as its input the access log file from a proxy server. By using
a historical log, however, we are forced to "replay" part
of a user's actions to reconstruct the path they followed.
1 Unfortunately, this process is complicated by the fact that
some users maintain several browser windows and launch
multiple concurrent (but related) search sessions. The simplified
algorithm presented here is sufficient for the purposes
of the present paper, but the precise details of our extraction
algorithm are given in [14].
This means we must re-retrieve pages previously visited and
hence the extractor process is usually scheduled when the
server is not busy handling primary requests. This overhead
can be reduced by examining pages as they are being
served by a proxy. The link structure as well as various
other aspects of the requested pages can be extracted by a
background process having access to the proxy's cache. We
are currently building a system of this kind and examining
how data collection impacts proxy performance.
We consider data collected by a proxy server handling all
of the outgoing HTTP requests made by a portion of the
Lucent employees based in Murray Hill, New Jersey. In the
log maintained by this proxy, we find an essentially complete
record of the sites visited by a population of 2,000
researchers, developers and support staff. Between January
and May of 2001, this server logged over 42 million requests.
In

Table

1 we list the ten most frequently accessed search engines
by the Lucent employees during this period. 2 We also
recorded 13,657 search sessions, of which 44% were com-
pleted. Roughly 60% of the completed sessions consisted of
only 1 or 2 URLs, with 20% having length 3 or 4. In gen-
eral, the longer the search sessions the larger the percentage
of pages that were not linked directly to the results page.
For sessions of length 5 or more (comprising 20% of the total
number of search sessions), 55% of the pages were not
among the search results seen by the user. This number is
for sessions of length 3 or 4, and only 12% for those
with only 1 or 2 URLs.

Table

1: A list of frequently accessed search engines
compiled from the Lucent proxy logs for January 1,
2001 through May 23, 2001.
% of queries Search engine
53.0 www.google.com
search.yahoo.com
11.2 www.altavista.com
4.4 hotbot.lycos.com
4.2 www.lycos.com
2.7 search.excite.com
0.3 search.msn.com
0.3 www.northernlight.com
In terms of time, of the queries that were exactly repeated
in our session data set, about 50% were issued within a day
of each other. These tend to be made by the same user, the
only exceptions being queries related to paper deadlines for
2 It is worth noting that www.google.com is much more
popular among this research community than one would
expect from standard ratings offered by Media Metrix
or NetRatings [15] which rank yahoo.com, msn.com and
search.aol.com as the clear market leaders.
Query: bridal+dresses bridesmaid+dress flower+girl+dresses
URLs: www.priscillaofboston.com www.martasbridal.com www.bestbuybridal.com
www.bestbuybridal.com weddingworld.net www.martasbridal.com
weddingworld.net
weddingworld.net/htm/.
www.ldsweddings.com/bridal dress.
www.usedweddingdresses.com

Figure

3: Three search sessions initiated by three different users. The query strings are all related to wedding
dresses of some kind, and the URLs visited by the users are similar.
major computer science conferences and searches for online
greeting card services near major holidays. On larger time
scales, 80% of the repeated queries were posted by different
users.
So far, we have focused on proxy logs as the primary
source of data for constructing search sessions. Many search
engines collect abbreviated navigation data to help improve
their service [6]. So-called "click-through" statistics record
the pages that users select from the list of search results. By
design, the redirection mechanism used to collect these data
cannot capture any information about a user's activities beyond
their selections from the search results list. Given the
fact that long search sessions consist mainly of pages not
returned by the search engine, click-through data does not
have the same potential to uncover relevant pages. To see
this, we applied the heuristic relevance measures introduced
at the end of this paper, and found that the "desired pages"
in over half of the long sessions were not linked directly to
the list of search results examined by a user. Even if a page
is included among the search results, click-through statistics
cannot identify requests for the page that are referred by
other URLs linked either directly or indirectly to the search
results list, missing valuable information about the relevance
of sources in the search engine database. For these reasons,
we see our approach as potentially much more powerful than
traditional schemes that rely on tracking click-throughs.
3. CLUSTERING QUERIES
Preliminary data analysis on our collection of search sessions
led to the simple observation that semantically related
query terms often draw users to the same sets of URLs. In

Figure

3 we present three search sessions (each initiated by
different users) that all relate to wedding dresses of different
kinds, and all produce requests for many of the same Web
pages. In this section, we consider improving search results
by first forming groups of queries based on the similarity
of their associated search sessions. In turn, by combining
search sessions with queries in a given group, we can better
identify relevant URLs.
In the IR literature, there are several examples in which
the pattern of retrieved items is used to form so-called "query
clusters," see [16, 17]. In our context, these schemes would
involve the queries submitted by users together with the
top L relevant pages returned by a given search engine. Our
technique is different in that we consider only those pages
that were actually selected by a user during a search task.
This has the effect of reducing spurious associations between
queries. In addition, we include pages that are not listed by
the search engine at all, effectively making up for deficiencies
in spidering. By including user choices, we have developed
an improved search scheme that is similar in spirit to collaborative
filtering. When this kind of approach has been
discussed previously in the IR literature, it has typically
required the user to report details of their search and manually
tag pages according to their relevance, for example, [9].
This level of involvement is unrealistic in the context of Web
searching, and hence the impact of these schemes is somewhat
limited. We avoid such problems by basing our work
on passively collected proxy logs.
Our initial intuition for navigation-based query clustering
came not from the IR literature, but rather from an often-cited
motivation for the popular PageRank algorithm [5].
Broadly speaking, PageRank is based on the amount of time
a "random surfer" would spend on each page. Random
walks on the link structure of the Web are also discussed
in [11]. We felt that actual user data would be a better
measure of importance than this random walk idea.
3.1 The mixture model
In this section, we consider models for both forming query
groups as well as determining the most relevant URLs for
each group. We construct a statistical mixture model to
describe the search session data. This model has as its parameters
the probability that a given query belongs to a
particular group as well as a set of group-specific relevance
weights assigned to collections of URLs. The algorithms we
present all attempt to fit the same model to the data. Our
first approach makes use of the standard EM (Expectation-
Maximization) algorithm to find maximum likelihood estimates
of the model parameters. At the end of the paper, we
discuss various alternatives that work in real time and can
be incorporated in a proxy implementation. To help guide
the cluster process, we also introduce labeled data from an
existing topic hierarchy that contains over 1.2 million Web
sites. We present an ad hoc algorithm for dealing with labeled
pages, and at the end of the paper discuss a more
formal statistical approach that uses the content hierarchy
to specify a prior distribution for the model's parameters.
Let q denote queries and u URLs. Each query q i is associated
with one or more groups, where the subscript i runs
from 1 to the number of queries seen in the training data,
I. For the moment, we assume that the number of groups,
K, is fixed. The group relation is captured by the triple
denotes a group ID and w ik is the probability
that q i belongs to group k. Then, for each group, we
identify a number of relevant URLs. This is described by
the triple (k; is a URL and -kj is a weight
that determines how likely it is that u j is associated with
the queries belonging to group k. We let the index j range
from 1 to the number of URLs seen in the training data, J
(which might include URLs from a content hierarchy). An
example of a query-group triple (q
while the associated group-relevance triples (k;
be
As mentioned above, sets of such triples constitute the parameters
in a statistical model for the search sessions. These
triples can be used by a search engine to improve page rank-
ings. When a user initiates a new search, we present them
with a display of query groups most related to their search
terms. For each such group, we select the most relevant
URLs arranged in a display like that in Figure 4. Here,
we arrange the query groups and URLs by weight, with the
most relevant appearing at the top. In this example, we
have used the data from a content hierarchy to name the
separate query groups (e.g., Medications in Figure 4). At
the end of the paper, we discuss model extensions that will
purely automated group naming.
Finally, we see our clustering as an addition to a standard
page of search results. By presenting the user with
a small, organized set of URLs from our system together
with a spider-based search list, we allow new resources to
be added to our system in a natural way. In fact, estimates
of confidence can be used to suppress our display entirely,
forcing the user to help train the system when we have insufficient
navigation data. Our clustering can also be used
to modify the rankings of results from a traditional search
engine; to guarantee that new resources will be visible to the
user, the modified rankings can be displayed only a fraction
of the time.

Figure

4: Example of cluster results for a query of
'hypertension'.
A mixture model is employed to form both the query
groups as well as the relevance weights. Assume that in our
dataset we have I queries which we would like to assign to
K groups, and, in turn, determine group-specific relevance
weights for each of J URLs. For the moment, we simplify
our data structure and let n ij denote the number of times
the URL u j was selected by some user during a search session
under the query q i . Let n the
vector of counts associated with query q i . We model this
vector as coming from a mixture of the form
where the terms ff k sum to one and denote the proportion of
the population coming from the kth component. Also associated
with the kth component in the mixture is a vector of
parameters From a sampling perspec-
tive, one can consider the entire dataset
as being generated in two steps: first, we pick one of the K
groups k   according to the probabilities ff k and then use the
associated distribution p(\Deltaj- k   ) to generate the vector n i .
We now consider the specification of each component in
the mixture (1). We assume that in the kth component the
data come from a Poisson distribution with mean -kj ,
where the counts for each different URL u j are independent.
Then, setting the likelihood of the kth
component associated with a vector of counts n i is given by
Y
e \Gamma- kj
To fit a model of this type, we introduce a set of unobserved
(or missing) indicator variables fl ik , where
group k, and zero otherwise. Then, the so-called complete
data likelihood for both the set of counts n i and the indicator
variables can be expressed
as
Y
Y
Y
e \Gamma- kj
We refer to the parameters -kj as relevance weights, and
use the probability that fl as the kth group weight
for query q i (the w ik mentioned at the beginning of this
section).
3.2 Basic EM algorithm
The Expectation-Maximization (EM) algorithm is a convenient
statistical tool for finding maximum likelihood estimates
of the parameters in a mixture model [8]. The EM algorithm
alternates between two steps; an E-step in which we
compute the expectation of the complete data log-likelihood
conditional on the observed data and the current parameter
estimates, and an M-step in which the parameters maximizing
the expected log-likelihood from the E-step are found.
In our context, the E-step consists of calculating the conditional
expectation of the indicator variables fl ik , which we
l -
ff l
where p(\Deltaj -k ) is given in (2). In this expression, the quantities
-k denote our current parameter estimates.
Note that - fl ik is an estimate of the probability that query q i
belongs to group k, and will be taken to be our query group
weights. Then, for the M-step, we substitute -
(3), and maximize with respect to the parameters ff k and
-k . In this case, a closed form expression is available, giving
science:math:statistics:conferences www.beeri.org.il/srtl/
computers:computer science:conferences www.computer.org/conferen/conf.htm
computers:computer science:conferences www.acm.org/sigmod/
computers:computer science:conferences www.acm.org/sigmm/Events/./sigmm conferences.html
computers:computer science:conferences www.acm.org/sigkdd/events.html

Figure

5: A subset of the fields available in the DMOZ data. The fields are directory label and URL.
us the updates
l
Clearly, these simple updates make the EM algorithm a convenient
tool for determining query group weights and relevance
weights. Unfortunately, the convergence of this algorithm
can be slow and it is guaranteed only to converge to
a local maximum. To obtain a good solution, we start the
EM process from several random initial conditions and take
the best of the converged fits.
In

Figure

6 we present an example of three of the groups
found by this standard EM approach. For each group we
display those query terms with the highest weights. It is
arguable that the last group is fairly loose, combining different
countries in Africa. From the standpoint of searches
typically conducted by the Lucent employees served by our
proxy, however, this degree of resolution is not surprising.
With proxy logs from an ISP, we would have sufficient sample
size to further subdivide this topic area.
3.3 Approximate algorithm with labeled data
The query groups formed by the mixture model introduced
in Section 3.2 allow us to borrow strength from search
sessions initiated with different, but semantically, related
query strings. The mixture approach, however, is highly unstructured
in the sense that we only incorporate user data to
learn the groups and relevance weights. In this section, we
consider a simple method for incorporating existing information
about related URLs from, say, a directory like DMOZ
(www.dmoz.com) or Yahoo!. Essentially, we use the directory
labels obtained from these sources to seed our query groups.
In

Figure

5 we present a subset of the data available from
the DMOZ hierarchy.
We assume that the data in such a structure can be represented
as a set of pairs (l; u lj ) where l indexes groups of
URLs and u lj is a URL in the lth group (here j runs from 1
to J l , the number of URLs in group l). The weights associated
with these data, - jl , are not specified in the directory so
we assume they have a value of ff. In Figure 7, we present a
simple algorithm to establish mappings between queries and
nj+transit bridal+dresses kenya
njtransit bridesmaid+dress tanzania
nj+train+warren flower+girl+dresses africa
new+jersey+train

Figure

Three query groups found by fitting the
mixture model via the standard EM algorithm. In
each case, only the top ranking queries per group
are displayed.
URLs when either the query or the URL has been seen in either
the labeled data or the sessions that have already been
processed. The remaining sessions are processed in a batch
using the basic EM algorithm in Section 3.2. The algorithm
can be tuned with a threshold value T (0 - T - 1) to force
more of the URLs in the session to exist in a previously
created group.
The approximate algorithm has the advantage of incorporating
labeled data, but has the disadvantage of slowly
adding to the set of clusters when a new topic is found in
the data. At the end of the paper, we describe a more formal
statistical approach to using content hierarchies that avoids
this problem.
4. EXPERIMENTAL RESULTS
To evaluate our methods, we used Lucent proxy data and
computed search session lengths with and without query
clustering. We began by selecting a "desired URL" from
each search session. Since the users did not provide relevance
feedback on the pages they viewed, we developed a
simple heuristic for making this choice. In our first set of
experiments, we took the desired URL to be the last URL
that the user visited before moving on to a new task. Since
users may continue to browse after they have found a relevant
page, this simple choice is not correct for all of the
search sessions. In subsequent experiments, we defined the
second-to-last URL to be the desired URL, and so on. We
found that the results of these experiments were all very sim-
ilar, each suggesting that clustering can considerably reduce
session length. Therefore, in this paper, we present only the
experiments with the the last URL being the desired URL.
We consider two metrics to judge the effectiveness of our
algorithms: the percent of queries where the desired URL is
in a cluster; and the position of the desired URL in a group
(i.e., the session length). Our claim is that the location of
the desired URL in our system's output can be compared
against the number of URLs that a user visited during their
assign each URL in labeled data to a URL group
based on its directory label with weight 0
for each session s
largest overlap with URLs
in s
if (query in s was NOT seen before) and
(# URLs in s existing in g/# URLs in s ! T)
add s to B
else
for each URL in s
if URL is not in g, add it
increment weight of URL by ff
if query is not in query groups associated
with g, add it
output mappings
cluster sessions in B using the BasicEM algorithm

Figure

7: Pseudo-code for approximate algorithm.
number
of
URLs
visited

Figure

8: Experiment results: the number of URLs
visited without and with clustering on 46 days of
testing data.
searching task to measure the improvement of our system.
Averaging these values across search sessions provides us
with a measure of expected search length.
To study our algorithms, we used a portion of the search
sessions extracted from the access logs of the Lucent Murray
Hill proxies to train with, and then tested with another
portion, distinct in time. Given our performance metrics,
we conducted a number of experiments involving different
time-based divisions into training and test sets and varying
the parameters required for the basic and approximate EM
algorithms. We then used our experience with these different
trials to choose a reasonable set of parameters for the
experiments (on new data) reported here. We used
groups when training with the basic EM algorithm. We decided
on 0:1, and the labeled
data from the DMOZ image from May 19, 2001 when training
with our approximate algorithm.
The results presented below are representative of our many
experiments. They correspond with training on 95 days
worth of data, and testing on 46 days of data. The percent
of queries where the desired URL is in a cluster is 93%.
Thus, 93% of the time, when both the query and desired
URL were seen in the training data, our algorithms display
the desired URL. Figure 8 presents our position results; we
see that both algorithms reduce the number of URLs visited
by 43% for the basic EM algorithm (38% for the approximate
algorithm). The means are slightly misleading due
to the presence of a small number of outliers (queries with
very large search sessions). Thus, we also computed median
positions; without our clustering algorithms, the median
number of URLs visited is 2, and with either clustering
algorithm, the median position of the desired URL is 1.
Perhaps most importantly, for 43% of the cases (29% for the
approximate algorithm) we provide a strictly shorter search
session length.

Figure

9 presents our results with testing with six months
of data. (The difference in the height of the "without" bars
is due to different ranges of training data being used.) We
found the value of the percentage of queries where the desired
URL is in a cluster is dependent on the length of the
number
of
URLs
visited

Figure

9: Experiment results: the number of URLs
visited without and with clustering on 6 months of
testing data.
testing data. For example, when 6 months of testing data
was used, the percent matched is 60-69%, and when only
were used, the percent matched is 93%. In some
sense, this effect is an obvious byproduct of our experimental
refitting the model periodically, the set of
URLs become out-of-date. In a real system, we would incorporate
frequent model updates. At the end of this paper, we
consider an online version of the EM algorithm that would
provide incremental updates with each search session.
While the results with the basic EM algorithm are en-
couraging, it does not scale well at all. Even the modest
data sizes entertained here can take many hours to con-
verge. For the approximate algorithm, roughly 60% of the
search sessions were passed into the basic EM. This allowed
the approximate algorithm to run in much less time (1 hour
compared to half a day). Since a smaller set of data is clustered
in the approximate setup, a smaller value of K can be
used. We note that the percentage of queries on the list for
the approximate algorithm is only a few points less than the
basic EM algorithm.
Varying the value of K affects both the time needed to
form the clusters and the quality of results. For example,
when clustering 142 days of data, twice as
long to form the clusters as
times as long.
5. RELATED WORK
There are many systems which involve users ranking or
judging Web sites as they visit them; [9, 2] are examples.
We feel that systems which require the users to explicitly
comment on the Web sites place too burden on the user.
Therefore, while the data can be considerably cleaner than
our search sessions, it is necessarily of limited coverage. The
database in [9], for example, contains very few of the queries
seen in the Lucent logs.
Many techniques exist for automatically determining the
category of a document based on its content (e.g., [18] and
its references, [10] and its references, [1]) and the in- and
out-links of the document (e.g., [7, 12]). We are currently
investigating techniques to include content in our clustering
algorithms, with the advantage that by working with the
proxy cache we do not require extra spidering.
Another approach to document categorization is "content
ignorant." [3], for example, uses click-through data to discover
disjoint sets of similar queries and disjoint sets of similar
URLs. Their algorithm represents each query and URL
as a node in a graph and creates edges representing the user
action of selecting a specified URL in response to a given
query. Nodes are then merged in an iterative fashion until
some termination condition is reached. While similar in
spirit to our algorithms, this algorithm forces a hard clustering
of queries, limiting its ability to easily incorporate prior
information. In addition, our system relies on much richer
data, namely proxy logs.
Finally, the literature contains a large number of distance-based
methods for clustering; [4, 19] present two well-known
algorithms for handling large amounts of data. The approach
taken by these types of algorithms might not work
well on our problem where there should be tens of thousands
of clusters.
6. CONCLUSIONS AND FUTURE WORK
We have developed a method to extract search-related
navigation information from proxy logs, and a mixture model
which uses these data to perform clustering of queries. We
have shown that this kind of clustering can improve the display
of search engine results by placing the target URL high
in the displayed list.
The basic mixture approach using the basic EM algorithm
is highly unstructured in the sense that we only incorporate
user data to learn the groups and relevance weights. Having
taken a probabilistic approach to grouping, we can easily
incorporate prior information about related URLs from
DMOZ in a more formal way. A natural prior for our coefficients
- lj (the relevance weights) is a Gamma distribution.
Suppose that for each URL contained in category l, we assign
- lj a prior Gamma distribution with parameters ff and
while those URLs not listed under the directory in category
l receive a Gamma distribution with parameters ff 0
and fi, where ff ff. The ingredients necessary for the EM
algorithm in Section 3 can be carried out under this simple
model as well. In this way, we can force a stronger tendency
toward maintaining the existing hierarchy topics, while still
allowing new URLs to be added. The approximate algorithm
presented in the paper can be viewed as a very rough
approximation to this approach.
Next, while the standard EM algorithm is sufficient for
the relatively small data sets presented in this paper, it is
known not to scale very well as either the number of queries
or the number of query clusters increases. To combat this,
we have started working with on-line versions of the EM algorithm
[13] that can process individual search sessions as
they arrive. This requires a reformulation of the model as
presented here, but we believe it will give reasonable perfor-
mance. We are also extending our model to treat the query
string as a collection of query terms and not simply a sorted
list as we have done here. The same kind of Poisson structure
used for the collection of URLs in a search session is
applied to the query terms. This allows us to be much more
flexible in how we form query clusters and how we treat
new queries. Finally, by extending our probability models
to include content of the pages beyond the link structures,
we hope to generate even greater improvements in cluster-
ing. In a proxy-based implementation, processing the pages
to extract content represents very little overhead as we are
already examining pages for links.
Another direction that we are exploring avoids the aggregation
across users that we described in Section 3. In this
case, a model for user's searching habits will replace the
simplifying assumption that URLs associated with a query
group are sampled independently. Directly describing how
a user moves within and between sites will improve our calculation
of relevance weights. In addition, user-level parameters
can be introduced that capture the time scale over
which a user is likely to be refining a query and not changing
topics.

Acknowledgments

. Tom Limoncelli and Tommy Reingold
were invaluable in helping us access the proxy server
logs that we used for our experiments.
7.



--R

Theseus: categorization by context.

Agglomerative clustering of a search engine query log.
Scaling clustering algorithms to large databases.
The anatomy of a large-scale hypertextual web search engine
User popularity ranked search engines.
Finding related web pages in the World Wide Web.
Maximum likelihood for incomplete data via the EM algorithm (with discussion).
Capturing human intelligence in the Net.
Information retrieval on the Web.
The stochastic approach for link-structure analysis (SALSA) and the TKC effect
Clustering hypertext with applications to web searching.

Mining Web proxy logs: a user model of searching.
Nielsen//netratings search engine ratings
Learning collection fusion strategies.
Multiple search engines in database merging.

BIRCH: an efficient data clustering method for very large databases.
--TR
Learning collection fusion strategies
Fab
Multiple search engines in database merging
The anatomy of a large-scale hypertextual Web search engine
A re-examination of text categorization methods
Finding related pages in the World Wide Web
Clustering hypertext with applications to web searching
Capturing human intelligence in the net
The stochastic approach for link-structure analysis (SALSA) and the TKC effect
Agglomerative clustering of a search engine query log
Information retrieval on the web

--CTR
Bernard J. Jansen , Amanda Spink , Chris Blakely , Sherry Koshman, Defining a session on Web search engines: Research Articles, Journal of the American Society for Information Science and Technology, v.58 n.6, p.862-871, April 2007
Mathias Gry , Hatem Haddad, Evaluation of web usage mining approaches for user's next request prediction, Proceedings of the 5th ACM international workshop on Web information and data management, November 07-08, 2003, New Orleans, Louisiana, USA
Mark Truran , James Goulding , Helen Ashman, Co-active intelligence for image retrieval, Proceedings of the 13th annual ACM international conference on Multimedia, November 06-11, 2005, Hilton, Singapore
Bernard J. Jansen , Amanda Spink, How are we searching the world wide web?: a comparison of nine search engine transaction logs, Information Processing and Management: an International Journal, v.42 n.1, p.248-263, January 2006
web searching;proxy access logs;model-based clustering;query clustering;expectation-maximization algorithm