Analysis of a Very Large Web Search Engine Query Log
Craig Silverstein

Monika Henzinger

Google Inc.

Google Inc.

2400 Bayshore, Mountain View, CA 94043

2400 Bayshore, Mountain View, CA 94043

csilvers@google.com

monika@google.comy

Hannes Marais

Michael Moricz

Compaq Systems Research

Doublebill.Com, Inc.

130 Lytton Ave, Palo Alto, CA 94301

1800 Bridge Parkway, Redwood City, CA 94065

marais@pa.dec.com

Abstract

michael.moricz@doublebill.comz

In this paper we present an analysis of an AltaVista SearchEngine query log consisting of approximately 1 billion entries for search requests over a period of six weeks. This
represents almost 285 million user sessions, each an attempt
to ll a single information need. We present an analysis of individual queries, query duplication, and query sessions. We
also present results of a correlation analysis of the log entries,
studying the interaction of terms within queries. Our data
supports the conjecture that web users di er signi cantly
from the user assumed in the standard information retrieval
literature. Speci cally, we show that web users type in shortqueries, mostly look at the rst 10 results only, and seldom
modify the query. This suggests that traditional information retrieval techniques may not work well for answering
web search requests. The correlation analysis showed thatthe most highly correlated items are constituents of phrases.
This result indicates it may be useful for search engines toconsider search terms as parts of phrases even if the user did
not explicitly specify them as such.

range allows us to identify individuals' patterns of use. Finally, by including all times of day as well as many days, weensure that input from the entire world, and not just that
portion which is awake during the period the log covers, isincluded in our results.1
Most of the questions about web use we choose to answer
do not di er signi cantly from questions others have asked
about query logs. We are interesting in counting statistics
such as which queries are most common, what is the average
number of words per query, how many queries are includedin the average user session, and so on. In addition, however,
we study correlations between query terms, and also among
other eld values. Thus, we seek to answer questions suchas, \Do users from the U.S. ask disproportionately aboutbasketball?" or, \Do people view particularly many result
pages when querying about sex?" We believe this is a fertile
area for research and present rst steps in this direction.
The paper is structured as follows: Section 2 describes
the AltaVista search environment and query log. Section 3
and 4 contain the analysis involving single items and thecorrelation analysis respectively. We conclude in Section 5.

1 Introduction

2 The AltaVista Search Environment

There is a large interest in nding patterns in and computing
statistics of search engine query logs. However there are very
few results that study the query logs of commercial searchengines. One that does, by Jansen et al. [Jansen et al., 1998],
studies only 51,000 queries (taken from the query logs of Excite), which is a small percentage of the number of queries
asked on search engines each day.
Our goal is to study a larger number of search requests,
collected over the course of several weeks. Such a large data
set has several advantages. One, because it covers a relatively large time range, it is less likely to be a ected byephemeral trends in querying (such as searches related to a
new movie being released). For another, the extended time

The AltaVista search environment consists of several components that are important for analyzing queries: the engine itself, which is accessible from the web page www.altavista.com,
and the query logs, which store information about what
queries are made to the engine.

 This work was done while visiting Compaq Systems Research.
y This work was done while at Compaq Systems Research.
z This work was done while at the AltaVista company.

2.1 The AltaVista Search Engine

AltaVista is based on weighted boolean search. There are
two major search modes: simple querying and advanced
querying. A simple query consists of a collection of words,
which are ORed together. A pair of operators allows forother boolean operations: -word instructs AltaVista to ignore documents containing word and is thus a NOT operator; +word instructs AltaVista to ignore documents not containing word and is thus an AND operator. The " operator
is a proximity operator: words within double quotes must
be adjacent in a document for the document to match thequery. Quotes are therefore used to enclose phrases.
We use the term query term to denote a word or aquotation-mark-enclosed phrase.
1 Our results, however, cover only the logs of the main AltaVista
engine and not of mirror sites outside the U.S.

An advanced query is more explicitly boolean. In advanced query mode, and, or, and not are interpreted as
boolean operators rather than as search terms. Advanced
queries may also include the boolean operator near, which
is a relaxed form of the " operator: the words on either sideof near must be close | but not necessarily adjacent | ina document for the document to match the query.
Both simple and advanced queries support web-speci c
operators. For instance, the query host: xx.yy.zz returns
all documents found on the machine xx.yy.zz. To simplify
our analysis, we ignore these operators and treat the query
as a four-word query containing the words host, xx, yy, andzz.
The user can control aspects of the search in ways otherthan modifying the query. For instance, a pull-down menu
allows the user to restrict result pages only to pages in aparticular language. In the advanced search, an input box
allows the user to restrict the results to pages last modi ed
on a certain date, or within a range of dates.
After a query is entered and the various other restrictions processed, AltaVista returns a screen consisting of 10
URLs, with information about each URL such as the title.
These URLs are ranked in order of relevance to the query, as
determined by AltaVista's internal relevance function. The
user may click on any URL to explore the associated web
page. In addition, the user may click on navigation buttons
to explore other screens of URLs. By clicking on \3," forinstance, the user would be taken to result screen 3, which
has the the 21st{30th most relevant URLs. Note this di ers
from some other search engines, where the user can jump toonly the next 10 or previous 10 relevant URLs at any time.

2.2 The Altavista Query Log

The AltaVista query log has many components, only someof which concern us here. The query log is a text le consisting of a series of requests. A request may consist of a
new query or a new result screen for a previously submitted
query. Each request includes the following elds:

on a single user, we attempt to separate two informationneeds being asked at the same time; by limiting the time
gaps in a session, we attempt to separate two informationneeds by the same user asked at di erent times.
The use of cookies is integral to identifying sessions, because in theory every user has a unique cookie. In actual use
the situation is not as clear cut: di erent people using thesame browser will share a cookie, and some users disallow
cookies altogether. The former situation is not damaging for
identifying sessions, since it is unlikely two separate users
will be using the same browser simultaneously.
For those queries in which the user has disallowed cookies, we use the pair \domain IP/web browser used" as a
substitute for the cookie. This is a poor substitute for cookies, particularly for large ISPs such as AOL, where tens of
thousands of users can share a single IP address. Over 96%
of all queries in our experiments have cookie information,
however, so even a poor substitute discriminator of users is
unlikely to bias the results. To ensure a lack of bias, we ran
our experiments on two data sets: the full data set, and adata set restricted only to those queries with cookie information. The results in both cases were very similar, so wereport only the experiments performed on the full data set.
In addition to identifying unique users, a good sessioning
algorithm has to determine when a query starts a new information need. We use the heuristic that queries for a single
information need come clustered in time, and then there isa gap before the user returns to the search engine. We used
a cuto of 5 minutes. This means that as a user is entering queries, as long as the latest query is submitted withinve minutes of the previous query from that user, the newquery is part of the same session. If the gap is more than 5
minutes, the new query starts a new session.
Since in reality a user may try to ll two informationneeds in one sitting, our session-identi cation heuristic almost certainly underestimates the true number of sessions.

2.4 The Query Log Data Set

on the result pages' language or date of last modi cation;

Much of this paper is devoted to exploring the characteristics of the data set we studied; this introductory section isintended merely to give an introduction to the data.
The data set is summarized in Table 1. Already a few
issues are apparent. For instance, fully 15% of all requests
were empty requests, i.e. requests containing no query terms.
Two thirds of these are cases were users of the AltaVista
advance query service not understanding how to ll in theform. Of the non-empty requests, 32% consisted of a request for a new result screen, while 68% (the 575,244,993
non-empty queries) consisted of a request for the rst result
screen of a new query.
The queries were collected over 43 days, from 2 August
1998 to 13 September 1998. They include all the queries
submitted to the main (US) AltaVista search engine overthis time period.

is a simple or advanced query; and2.5 Experimental Setup

 A timestamp indicating when the query was submitted. The timestamp is measured in milliseconds since
1 January 1970.

 A cookie, which can be used to say whether two queries
come from the same user (this eld is blank if the user
has disabled cookies);

 The query terms, exactly as submitted;
 The bf result screen, that is the requested range ofsearch results;

 Other user-speci ed modi ers, such as a restriction

 Submission information, such as whether the query Submitter information, such as the browser thesubmitter is using and the IP address of the submittinghost.

2.3 Sessions

A session is a series of queries by a single user made withina small range of time. A session is meant to capture a single
user's attempt to ll a single information need. By focusing

Our experiments were performed on a Compaq AlphaServer
4100 with four 465 MHz. processors and 4 gigabytes of main
memory, running OSF V4.0b. All code was compiled using
gcc 2.7.2 and compiled with the -O6 optimization option.
The experiments took about 22 hours of wall clock time torun. The duplicates analysis of Section 3.2, because of its
large memory requirement, was done separately from therest of the experiments; it took 18 additional hours of wall
clock time to run.

Table 1: Statistics summarizing the query log contents used in our experiments. Empty requests had no query terms. A
request consists of either a new query or a new requested result screen. Exact-same-as-before requests had the same queryand requested result page as the previous request. The total number of unique, non-empty queries gives the cardinality ofthe set consisting of all queries.
Total number of requests:
Total number of non-empty requests:
Total number of non-empty queries:
Total number of unique, non-empty queries:
Total number of sessions:
Total number of exact-same-as-before requests:

3 First-order Analysis of QueriesFirst-order analysis of queries consists of all analysis thatinvolves counting only single items, such as the frequencyof query terms or the number of times a query has morethan 20 result screens requested for it. This is in contrast
to second-order analysis, which requires counting pairs of
items, such as the number of times the terms computer andfree occur in the same query.
The rst-order analysis we performed falls into two categories: analysis of individual queries, and analysis of how
queries are modi ed throughout sessions.

3.1 Analysis of Individual Queries

One contrast that was noted early in the history of web
search is that searches on the web tend to have many fewer
search terms than searches in more traditional information
retrieval contexts [Jansen et al., 1998]. Though the gap has
narrowed over time, as we see in Table 2 the number ofwords per query is still small on average (2.35). The same
average query length was found by [Jansen et al., 1998].
The number of operators used per query is also small, as
is seen in Figure 3. One interesting note is that the maximum number of operators in a query is higher than the
maximum number of terms found in a query. We attribute
this to queries with a large number of dashes, which we interpret as operators in this context. Such a query could result
from a user cutting text from another source and pasting it
into the AltaVista search box.

3.2 Analysis of Query Duplicates

A di erent type of question concerning queries is how often
an individual query is asked. We conjectured that a small setof queries is repeated many times over the course of a day.
Indeed our data shows that the 25 most common queries
form fully 1.5% of the total number of queries asked in a 43
day period, despite being only 0.00000016% of the uniquequeries. We give a listing of the 25 most frequent queries
in Table 4. Note that uppercase and lowercase queries were
not collapsed in the table.
One surprising result is the frequency of the term applet.
Examination of the logs shows that almost all queries containing the term were submitted by a robot.
In Table 5 we show part of a histogram of query duplication; that is, what percent of queries are asked only once,
what percent are asked twice, and so forth. Counts are overall 43 days that we studied. We classi ed two queries as
being the same if they had the same words with the same
capitalization. (AltaVista is case sensitive.) We ignored
word order and operators. That fact that almost two-thirds

993,208,159
843,445,731
575,244,993
153,645,050
285,474,117
41,922,802

of all queries are asked only once in a 6 week period indicates that information needs on the web are quite diverse,
or at least are speci ed in diverse ways.
Determining query duplication is expensive because it
requires storing each unique query. For our analysis, withover a hundred million unique queries, it is infeasible to store
each query in memory. Instead, we stored a one word ngerprint of each query, which is merely a hash value. We thenstored the small ngerprint in a hashtable. This allowed us
to count the frequency of each query but would not let us
later say which queries were the most common. Therefore,
when a query was seen more than 1000 times, we stored
a map from the query to the ngerprint. Since almost all
queries are asked only once, this reduced the memory requirement signi cantly.
Each ngerprint is 32 bits, so even with a hundred million
queries it is unlikely two queries will have the same ngerprint value. Nevertheless, we possibly undercount slightly
the number of unique queries, and overcount slightly thefrequency of some queries, because of ngerprint collisions.

3.3 Analysis of Sessions

One of the most striking observation about sessions is mostof them are very short. Fully 63.7% of all sessions consistof only one request: meaning only one query was enteredand only one result screen was examined. Our analysis, unfortunately, does not enable us to determine how many ofthese simple sessions are so short because the informationneed was ful lled so easily, because the user gave up in despair after seeing a single screen of results, or because theuser was unaware of the usefulness of modifying the queryor requesting further result screens. Furthermore, we missthose cases where the user modi ed the query after the 5
minute session timeout had expired.
Tables 6 and 7 reinforce the idea that sessions are often
simple. However, on occasion a single query is modi ed hundreds of thousands of times, or thousands of result screens
are requested. These numbers | like the large count for
the term applet in Section 3.2{ are likely due to robots orother automatic search agents. We found that the average
number of queries per session is 2.02 and the average screens
per query is 1.39. Jansen et al. [Jansen et al., 1998] report
the average number of queries per session of 2.8, and average
number of screens per query of 2.21. We expect the di erence is due to di ering de nitions of \session": Jansen et al.
did not seem to \time out" a session, nor do they mention
using a technique for distinguishing individual users fromother agents, such as proxies, that have unique cookies. It
is also possible that Excite users di er from AltaVista users,or that Excite's relatively short query log was not representative.

Table 2: Statistics concerning the number of terms per query. Only distinct queries were used in the count; queries with many
result screen requests were not upweighted. The mean and standard deviation are calculated only over queries with at least
one term.
0 terms in query:
1 term in query:
2 terms in query:
3 terms in query:> 3 terms in query:

20.6%
25.8%
26.0%
15.0%
12.6%

max terms in query:393
avg terms in query:2.35
stddev of terms in query: 1.74

Table 3: Statistics concerning the number of operators | +, -, and, or, not, and near | per query. Only distinct queries
were used in the count; queries with many result screen requests were not upweighted.
0 operators in query:
79.6%
1 operator in query:
9.7%
2 operators in query:
6.0%
3 operators in query:2.6%> 3 operators in query: 2.1%

max operators:
avg operators:
stddev of operators:

958
0.41
1.11

Table 4: The 25 most popular queries, and how often they were asked in the 43 day test period. Only distinct queries wereused in the count; queries with many result screen requests were not upweighted. p**** is a vulgarity.
Query

Frequency
15514771169031712790613902406014398953377025356556324923321267[non-ASCII query]
263760pamela anderson
256559p****
234037sexo
226705
porn
212161nude
190641lolita179629games
166781
spice girls
162272
beastiality
152143
animal sex
150786SEX
150699gay
142761titanic
140963
bestiality
136578sex
applet
porno
mp3
chat
warez
yahoo
playboyxxx
hotmailTable 5: Statistics concerning how often distinct queries are asked. Only distinct queries were used in the count; queries withmany result screen requests were not upweighted. Percents are of the 154 million unique queries.
Query occurs 1 time:
63.7%
Query occurs 2 times:
16.2%
Query occurs 3 times:
6.5%
Query occurs > 3 times: 13.6%

max query frequency:
avg query frequency:
stddev of query freq:

1,551,477
3.97
221.31

Table 6: Statistics concerning the characteristics of query modi cation in sessions.
1 query per session:
2 queries per session:
3 queries per session:> 3 queries per session:

77.6%
13.5%
4.4%
4.5%

max queries per session:
avg queries per session:
stddev of queries/session:

1723252.02
123.40

Table 7: Statistics concerning the characteristics of result screen requests in sessions.
1 screen per query:
85.2%
2 screens per query:
7.5%
3 screens per query:3.0%> 3 screens per query: 4.3%
For those situations where a query is modi ed, we see inTable 8 that in about 12% of the cases the query is modi ed by either adding or deleting terms or operators. In
this situation, it is likely the user is satis ed with how the
information need is expressed, but the query is either too
speci c or not speci c enough. Even when adding a word, auser may be trying to restrict the search space rather thanbroaden it, since often the word is added with a - operator,
with the goal of removing non-relevant pages that share acommon word.
In over half the cases, some query terms are deleted fromthe query and other terms added. In these cases it is likely
the user is modifying the query not to change the scope ofthe query, but to restate the information need.
Over a third of the cases result in the a total change,
where no word is shared between the two modi cations.
These may result in the information need being re ned oreven changed on the basis of information gleaned in the rst
search. In some cases, a total change may result from improperly identifying sessions. Unfortunately we don't know
how many times this occurs.

4 Second-order Analysis of Queries
Second-order analysis of queries is analysis that requires
joint counts, that is, counts for pairs of items in the same
query. Unlike rst-order analysis, which requires only linear
space in the quantity being counted, second-order analysis
requires quadratic space. Because of this, we limit our attention to query terms and elds for second-order analysis,
and furthermore we limit ourselves to the 10,000 most common terms found in queries. (We include all eld values,
since there are only a small number). Because of these restrictions, the memory requirement does not grow with thesize of the data set, and it is possible to do second-orderanalysis on large data.
Our second-order analysis consists of nding correlations
between items, where an item is either a query term, such as"new york", or a eld value, such as language=fr (which indicates the user speci ed only pages written in French should
be returned). In addition to studying 2-way correlation, we
devise a method for augmenting our correlation analysis tond 3- and 4-way correlations, while keeping the space use
quadratic.
Since we limit our attention to the 10,000 most common
terms, many queries become empty because they contain
only rarer terms. We limit our attention only to queries

max screens per query: 78496(2nd most screens:5108)
avg screens per query:
1.39
stddev of screens/query:
3.74
with at least one term in the top 10,000 | for this data set,
313,454,867 distinct queries.

4.1 The Chi-squared Test for Correlation

While in reality queries consist of items, for the purpose of
discussing correlation we consider the dual formulation that
items decide whether or not to be in queries. Intuitively,
if one item is found in n1 fraction of queries and another,
unrelated item in n2 fraction, we would expect them both tooccur together in n1 n2 fraction of queries. If the actual cooccurrence percent deviates signi cantly from this expectedvalue, we must question the assumption that the two items
are independent of one another.
This intuition is captured formally in the chi-squared
statistic [Agresti, 1990]:

2 (a; b) =[E (ab) O(ab)]2 [E (ab) O(ab)]2++
E (ab)E (ab)[E (ab) O(ab)]2 [E (ab) O(ab)]2+
E (ab)E (ab)In this formula, O(ab) is the number of queries in which
items a and b co-occur. E (ab) is the expected numberof queries in which they co-occur, under the independence
assumption. As mentioned above, E (ab) = O(a)O(b)=n,where n is the total number of queries. O(a) is the numberof queries in which a does not occur.
The 2 value has a chi-squared distribution. (In particular, for boolean data it has a chi-squared distribution
with one degree of freedom.) Looking up values for the chisquared distribution in a table, we see that only 5% of thetime does the 2 value exceed 3:84 if the variables are actually independent. Therefore, if we see 2 > 3:84, we saythat a and b are correlated at the 95% con dence level.

4.2 The Correlation CoeÆcient

While the chi-squared test can detect the presence of correlation, it cannot judge its strength. For instance, if two
items are actually correlated, their 2 value will grow as n,
the size of the data, grows. The correlation coeÆcient, , istypically used to measure the strength of correlation. It isde ned as follows:P(a; b) =i (Aia )(Bip
a2 b2

b )Table 8: How queries are modi ed within a session.
Adding terms:
7.1%
Deleting terms:
3.1%
Modifying operators only:
1.4%
Totally changing the query:
35.2%
Otherwise modifying query terms: 53.2%
where a is the mean value of item a (that is, O(a)=n), a2 isthe variance of a, and Ai is 1 if and only if query i contains
a. The denominator is a scaling factor that keeps  between
1 and 1. For boolean data,  will equal 0 if A and B are
independent, 1 if they are perfectly correlated, and 1 ifthey are perfectly negatively correlated.
The correlation coeÆcient is important for data mining
applications because there is often enough data to nd weak
but signi cant correlations. The correlation coeÆcient canhelp the analyst concentrate on those correlations that arestrong enough to make an impact. For instance, supposethat once a year a user enters a query volcano baklava,
but otherwise the two terms are independent. With enoughdata, the chi-squared test will (correctly) say there is a correlation, but the correlation coeÆcient will be low, indicatingthat the correlation is weak. An analyst would be wise notto change policy based on this correlation.
It is clear, then, that 2 and  are complementary measures, and one does not supersede the other. With \toolittle" data, 2 will be low but  can be high; with \toomuch" data, 2 can be high even in cases where  is nearzero.
Despite the di ering roles of 2 and , for boolean datasuch as we have for query log analysis, the two are related.
In particular,
2 = n  2 :This relationship means that for boolean data, the strongest
correlations are also the most likely to be true correlations
rather than statistical anomalies. For mining query logs,
this is an important fact, because with over 10,000 items
there are more than 100 million statistical tests being done.
Even at the 95% con dence level, there will likely be mademillions of false judgements of correlation. Concentrating
on items with correlation coeÆcient above 0:2, however, theexpected number of false judgements is less than one.

4.3 Results for Two-way Correlation

We calculated correlation between items, consisting of 10,000
terms and 662 eld values. Field values are boolean itemsof the form field=value. For instance, domain=nl is an
item in all queries emanating from the Netherlands. After
throwing out trivial correlations, such as domain=nl being
negatively correlated with domain=kr, we were left with 110
correlated pairs. Some of these are displayed in Table 9.
One interesting pattern found in the highly correlated
pairs is that the most highly correlated items are constituentsof phrases. This indicates there are many situations whereusers are not using the " operator to tell AltaVista that the
separate words constitute a single term.
One phrase that contributes to three of the entries inTable 9 is \Bu y the Vampire Slayer," a TV show. While
presumably most queries containing one of these words contained all three, buffy and slayer are more highly correlated than pairs containing vampire. This is because terms(Adding one term: 5.4%)(Deleting one term: 2.1%)(operators everywhere: 0.4%)

like buffy and slayer are unlikely to occur in queries inother contexts, making the correlation strong. However,there are likely many queries concerning vampires but not
the TV show, making the correlation less strong in this case.
One of the most frequent of the highly correlated queries
is between www and com. The fact that www and com arehighly correlated is hardly surprising; both often occur ina URL and neither is likely to be a common query term inother contexts. This is an extreme example of the generalfact that text is naturally correlated.
The correlation between people from Korea querying andasking for result pages in Korean is hardly surprising. As
mentioned before, the term applet is often queried by arobot, which explains the correlation between the word \applet" and requesting a date-restricted set of pages.
One interesting set of correlations concern \referred" users,
which are users sent to AltaVista by an AltaVista partner,
rather than those who typed in the URL explicitly or camefrom a bookmark. These users are correlated highly withsessions with many modi cations, perhaps indicating theseusers spend more time than most modifying their query.
They are also particularly likely to \restart" their queries,
meaning they enter a query with no terms in common with
their previous query. This may indicate users sent to AltaVista to ll one information need get distracted and try
to ll others as well. Another possible explanation for bothdata points is that cookie information does not get forwarded from all the referring sites, meaning we are misidentifying sessions in this case.
A nal, unsurprising result is that the term the is correlated with long queries. It is likely that queries containing
such a contentless word are natural language queries.

4.4 Results for Three- and Four-way Correlation

If a pair of items is correlated, then by de nition all supersets of that pair are correlated as well. Therefore, to ndcorrelations involving more than two items, it is necessary tond pairs of items that are uncorrelated. In the case of text
this is diÆcult, since text is naturally correlated. Therefore,
typical methods of nding large correlated sets have provenunsuccessful for mining queries in query logs.
In order to nd these larger correlations, we implemented
a heuristic that \phrasi es" highly correlated terms. In thiscase, we took the 1000 item pairs with the largest (positive)correlation coeÆcient, as determined from the analysis in
the Section 4.3. For each pair, we constructed a new term
consisting of that pair of items. A query contains the newterm only if it contains both items in the pair. E ectively,
we are pretending the correlation coeÆcient of the pair of
items is 1 | meaning they only occur together | so thecorrelation of the pair with a third item is equal to the correlation of the pair with either of the items individually. In
reality, since the correlation of the pair is less than 1, we approximate but underestimate the true correlation between
the three items.

Table 9: Some highly correlated pairs of items. The data set consists of about 10,000 items and 313,000,000 queries.
Term A

cindy
persianpamelavisualwww
buffy
slayerbuffy
lang=kodate=restrictedreferred=yes
referred=yes
theTerm Bcrawfordkitty
andersonbasic
httpslayervampirevampiredomain=kr
appletsessmodlen=4+
sessmod=restart
qwords=6+

Count together (O(AB ))11855875716
4534671779712355010
12340
13640
12986
1030416116556576257842
46359290
2417838
0.70980.68300.6451
0.63250.3862
0.39890.30880.2766
0.72810.72730.63880.54820.1886

Table 10: Some highly correlated items. By \phrasifying" highly correlated pairs | represented by \(word1, word2)," | we
obtain sets of three and four highly correlated items. The data set consists of about 10,000 items and 244,000,000 queries.
Term A
Term B(links, kitty)(persian, adult)(www, http)(http, com)
(harvard, business) review(used, car)(used, prices)(bluemountain, com) (www, bluemountain)(anderson, lee)(pamela, lee)
(ibm, video)(highlander, newsgroups)(persian, kitty)(persian, links)

Count together (O(AB ))40375
127783
12554
24702
36722
105208
5261
45322


0.94380.93530.92150.89880.88710.73750.50370.4687

By repeating the same analysis as was done in Section 4.3
with the 1000 new items, we can nd triples of items thatare correlated, or even sets of four if two pairs are correlated.
The results are shown in Table 10. Most of the 3- and 4way correlations involve phrases with three and four words
in them, such as \Harvard Business Review" and \Persian
Kitty adult links." A connection such as \IBM video" and\highlander newsgroups" seems more obscure, and indeed
the low frequency indicates it is probably the result of asmall number of users repeatedly modifying a query withthese four words as the base.
For multi-word phrases, the choice of word grouping cana ect the correlation score. For instance, (persian, kitty,
adult, links) has a fairly weak correlation when one ofthe pairs is (persian, kitty). This is because the phrase
persian kitty is often asked alone, as a single two-wordquery; it therefore correlated relatively weakly with adultand links. On the other hand, the pairs (kitty, links)and (persian, adult) obviously each only occur when thefull query persian kitty adult links is entered.
Similary, (www, bluemountain, com) is only correlated
when considering the pairs in Table 10. The correlation
between bluemountain and (www, com) is very low.
Given these observations, it makes sense to consider atriple of words to be correlated only if all 3 pairwise partitions of the words yield strong correlations.

conjecture that an average web user di ers signi cantly fromthe user model assumed by the information retrieval community. Surprisingly, for 85% of the queries only the rst
result screen is viewed, and 77% of the sessions contain only
1 query, i.e., the queries were not modi ed in these sessions.
In the correlation analysis we considered the queries of
all users and found the strongest correlations resulted fromshort queries that were actually single-term phrase queries.
For future work it might be interesting to restrict the correlation analysis to long queries, with for instance more thanten terms, in hopes of nding correlations between concepts
rather than merely terms.
Our analysis did not distinguish between requests issued
by humans and requests issued by robots. In some cases,
robot-initiated queries in the AltaVista logs resulted in a
number of seemingly bizarre results. It is impossible for us
to judge how much automated search techniques skewed theresults of this study. It would be interesting to repeat theanalysis with the request from robots discarded, assuming
a method could be found to distinguish requests by robots
from requests by humans.

5 Conclusions and Further Research[Jansen et al., 1998] Jansen, B.J., Spink, A., Bateman, J.,
and Saracevic, T. 1998 Real Life Information Retrieval:
A Study of User Queries on the Web, SIGIR FORUM,
32 (1):5{17.

In this paper we presented an analysis of an AltaVista querylog containing almost 1 billion entries. We con rmed theReferences[Agresti, 1990] A. Agresti. Categorical Data Analysis. John
Wiley & Sons, New York, 1990.