What’s Really New on the Web? Identifying New Pages
from a Series of Unstable Web Snapshots
Masashi Toyoda
toyoda@tkl.iis.u-tokyo.ac.jp

Masaru Kitsuregawa
kitsure@tkl.iis.u-tokyo.ac.jp

Institute of Industrial Science, University of Tokyo
4-6-1 Komaba Meguro-ku, Tokyo, JAPANABSTRACT

over time, by plotting occurrences of keywords in newly appeared pages. This technique can also be used to examine
the penetration of brands or concepts on the Web.
Basically, the evolution of the Web is examined by periodic crawling. Using a time series of crawled Web snapshots,
its evolution can be examined, such as changes in page content, increases in the number of pages on topics, and changes
in the hyperlink structure. Recent research on the evolutionof the Web is based on ideal crawls. For example, in [10],a ﬁxed set of pages was crawled periodically to examinechanges in these pages, and in [19], all of the pages comprising 154 popular web sites were crawled periodically toidentify newly appeared pages on these sites.
In practice, however, such periodic crawling has inherentdiﬃculties in tracking the evolution of the Web. Even with
ideal crawls, some aspects of its evolution will be missed. If
the set of pages is ﬁxed, the appearance of new pages will beoverlooked. If the set of sites is ﬁxed, the appearance of newpages on these sites will be captured, but the appearance of
new sites will be overlooked. To capture such evolution, it isnecessary to crawl a massive amount of the Web during eachperiod. However, this causes diﬃculty in keeping snapshots
stable. Recently, it has become essentially impossible tocrawl every web page on the Web. As mentioned in [11],the number of uncrawled pages overwhelms the number ofcrawled pages, even after crawling over a billion pages, andthere are numerous dynamic URLs generated by databases.
Moreover, the evolution of the structure of the Web changes
the order of link traversal drastically. These facts make it
impossible to fully crawl the entire growing Web, and tobuild stable web snapshots.
In this situation, can we tell whether newly crawled pages
are really new? Even if a page is found that did not exist in
previous snapshots, the novelty of the page is still uncertain;
it might have been misidentiﬁed as new because:

Identifying and tracking new information on the Web is important in sociology, marketing, and survey research, since
new trends might be apparent in the new information. Suchchanges can be observed by crawling the Web periodically.
In practice, however, it is impossible to crawl the entire expanding Web repeatedly. This means that the novelty ofa page remains unknown, even if that page did not exist
in previous snapshots. In this paper, we propose a novelty
measure for estimating the certainty that a newly crawled
page appeared between the previous and current crawls. Using this novelty measure, new pages can be extracted froma series of unstable snapshots for further analysis and mining to identify new trends on the Web. We evaluated theprecision, recall, and miss rate of the novelty measure using
our Japanese web archive, and applied it to a Web archive
search engine.

Categories and Subject Descriptors
H.3 [Information Storage and Retrieval]: Information
Search and Retrieval

General Terms
Algorithms, Experimentation, Measurements

Keywords
Link analysis, Web evolution, novelty, information retrieval

1.

INTRODUCTION

The dramatic growth in the volume and diversity of the
Web has enhanced the possibility of using the Web as atool for sociology, marketing, and survey research. People in these disciplines, such as sociologists and market researchers, are interested in how the Web evolves over time
based on events in the real and virtual worlds, and try toobserve and track trends on their topics through the Web.
Identifying and tracking new information on the Web isimportant for such research, since new trends might be apparent in the new information. For example, we can determine when and how topical keywords emerge and evolve• The crawler did not access that page in the previous
crawl.
• The site containing the page was temporarily unavailable due to sever or network troubles during the previous crawl.
• The page was not linked to the starting points of theprevious crawl.
The only time information available for pages is the LastModiﬁed time in its HTTP response. However, this guarantees only that the page is older than that time, and gives no
indication of when the page ﬁrst appeared.

Copyright is held by the International World Wide Web Conference Committee (IW3C2). Distribution of these papers is limited to classroom use,and personal use by others.
WWW 2006, May 23–26, 2006, Edinburgh, Scotland.
ACM 1-59593-323-9/06/0005.

233

In this paper, we propose a novelty measure for estimating
the certainty that a newly crawled page p appeared between
a previous and current crawls. Basically, we consider thatpage p does not exist on the Web until p can be retrieved bysearch engines. This means that page p appears when it canﬁrst be crawled by following links from existing pages. Page
p can therefore be considered novel when it is pointed to only
by links that have appeared since the previous crawl. The
novelty measure is discounted when links for which the creation time is unknown point to p. In addition, if only novel
pages point to p, p may also be novel. This implies a recursive deﬁnition of the novelty measure, and it can be calculated in a similar way to PageRank [7], although the purposeof our ranking is quite diﬀerent. The novelty measure also
has an inverse relationship with the decay measure [2], which
represents the decay of a page in terms of the probability
that a random surfer reaches a dead page. This means thatthe novelty measure can be calculated in a similar way tothe decay measure, except for inverted link direction. Whileboth PageRank and the decay measure are calculated using
a single snapshot, our novelty measure is calculated using
temporal changes in multiple Web snapshots. We evaluate
the precision and recall of our novelty measure using ourJapanese web archive, and show that novel pages can be
identiﬁed with reasonable precision and recall.
Using the novelty measure, novel pages can be extracted
from a series of unstable snapshots for further analysis andmining to ﬁnd novel trends on the Web. This study presents
an application of the novelty measure to our archive searchengine, displaying changes in the number of novel pages related to query keywords, and ranking search results according to their novelty.
The rest of this paper is organized as follows. Section 2
discusses related work. The notion of the novelty measure
is described in Section 3. In Section 4, we present our experiments and evaluations. Section 5 shows an applicationof the novelty measure to our archive search engine. Finally,
Section 6 concludes the paper.

2.

as the PageRank algorithm [7] by Brin and Page, and the
HITS algorithm [14] by Kleinberg. These algorithms andtheir variants calculate the relevance and relationships ofweb pages. Recently, Bar-Yossef et al. [2] proposed a different measure of the page importance, the so-called decay
measure, to reveal the death and decay of web pages. The
decay is explained in terms of the probability that a random
surfer stopping at a dead page. Its calculation process is similar to that of PageRank, but it can be calculated without
computation for all pages. Our novelty measure is similar
to the decay measure, but diﬀers in using temporal changes
in the Web graph, and in the direction of random surﬁng.
Various studies have attempted to reveal trends in theWeb. The Internet Archive [25] once provided a full-text
search engine called Recall [20] that had a keyword search
future for 11 billion pages in its archive. Based on the search
results, Recall provided a graph showing changes in the frequency of the search keyword over time. From that graph, it
was possible to determine when keywords emerged or faded.
Amitay et al. [1] proposed a method to detect trends using
time-stamped links. The authors assumed that links weretime-stamped with the Last-Modiﬁed time of their source
pages. In response to given keywords, they extracted the
top pages of the search result and pages that pointed tothe top results. Then, they conﬁrmed the trend from a histogram of time-stamped links for this set of pages. Our
previous work [23, 24] examined the evolution of web communities. A web community is a set of web pages with acommon interest in a topic. In [23], we proposed a method
for extracting all web communities and their relationships
from a single web archive. In [24], we extracted all the web
communities from periodically crawled web snapshots, andvisualized changes in these communities, such as growth andshrinkage. These studies assumed that newly crawled pages
were novel, and were not concerned with whether the pages
really were novel. Recently, tracking trends in blogspace has
become a hot topic (e.g., [15, 13]), since blogs are good information sources for extracting individual reputations andopinions. In blogs, all of the articles have already been timestamped using blog tools, which makes it easier to track theevolution of topics. However, blogspace is a rather small
subset of the entire Web, and we are interested in the moreglobal evolution of topics, not only in blogs but also in pagesof governments, companies, newspapers, magazines, etc.

RELATED WORK

Brewington and Cybenko [6], and Cho and Garcia-Molina[10] studied the frequency of changes and the lifetime of web
pages. They estimated the frequency of web page modiﬁcations, and showed that the results were useful for web
crawlers to determine the timing of further crawls. Fetterly
et al. [12] extended these studies by crawling a set of 150
million pages once every week, and showed various statistics
for changes in the pages. Since they focused on the changes
in the pages, their results were based on periodic crawls of a
speciﬁc set of pages; consequently, they could not detect theappearance of new pages. Ntoulas et al. [19] periodicallycrawled all the pages on popular 154 sites, and examinedthe volume of newly appeared information on these sites.
However, such crawling is possible only for a small subset of
the Web.
There has been much work on the Web graph structure
and modeling its evolution, for example [9, 16, 5, 22, 17].
The macroscopic structure of the Web was studied in [9, 16],and a site (or server) level analysis of Web graph evolution
was studied in [5]. In [22, 17], emerging cyber communities
were extracted based on a graph evolution model.
Based on the structure of the Web, various link analysis
methods have been proposed for information retrieval, such

3. NOVELTY MEASURE
Let tk (1 < k < n) be the time when each snapshot was
crawled. Let W (tk ) be the snapshot at time tk , which is aset of crawled pages. Let G(tk ) = (V (tk ), E(tk )) be the Webgraph of W (tk ) where nodes in V (tk ) represent web pages,
and edges in E(tk ) represent links. V (tk ) includes pages
outside W (tk ), if they are pointed to by pages in W (tk ).
Outside pages in the previous snapshots at least show their
existence in the past.
In the following, we ﬁrst classify pages in W (tk ) as old
pages O(tk ) and unidentiﬁed pages U (tk ), where W (tk ) =O(tk ) ∪ U (tk ) and O(tk ) ∩ U (tk ) = ∅. O(tk ) is the set ofpages that existed before tk−1 . U (tk ) is the set of pages
that were newly crawled at tk , but their novelty remains
unknown. Then, we deﬁne the novelty measure N (p) of apage p in U (tk ). The score of N (p) is a number between 0
and 1. The score 1 represents the highest certainty that p
appeared between tk−1 and tk . The score 0 represents the234novelty of p as totally unknown; note that it does not meanthat p is old. Finally, we describe the relationship between
the novelty measure and the decay measure.
Old pages can be identiﬁed by checking previous snapshots, and by checking the Last-Modiﬁed time in the HTTP
responses. A page is old when it exists in previous snapshots
or if old pages point to it. Formally, page p is in O(tk ) when:

Time
1999
2000
2001
2002
2003
2003
2004
2004

• p is in V (tj ) for existing j ≤ tk−1 ,• The Last-Modiﬁed time of p is earlier than tk−1 , orPeriodJul to Aug
Jun to Aug
Oct
Feb
Feb
Jul
Jan
May

Crawled pages
17M
17M
40M
45M
66M
97M
81M
96M

Links
120M
112M
331M
375M
1058M
1589M
3452M
4505M

Table 1: Number of pages and links in each web
snapshot.

• p is pointed to by q with a Last-Modiﬁed time earlier
than tk−1 .
Then, we deﬁne the novelty measure N (p) for each page
p in U (tk ) using the novelty of links pointing to p. N (p)represents the certainty that p appeared between tk−1 andtk . Basically, we consider that page p does not exist on the
Web until p can be retrieved by search engines. This meansthat page p appears when it can be crawled by following links
from existing pages. Formally, page p appears at tk when
p is pointed to only by links that newly appeared between
tk−1 and tk .
The novelty of a link (q, p) can be identiﬁed by changes
in the source page q as follows:Time|L2 (tk )||O(tk )\L2 (tk )||U (tk )||W (tk )|Jul 2003
49M
23M
25M
97M

Jan 2004
61M
14M
6M
81M

May 2004
46M
20M
30M
96M

Table 2: The number of old and unidentiﬁed pages
in each snapshot.

• The link (q, p) was created between tk−1 and tk , if thesource page q is in O(tk ), and was crawled at bothtk−1 and tk (i.e. q ∈ W (tk−1 ) and q ∈ W (tk )). Since
we know the contents of q at both tk−1 and tk , andthat there was no link from q to p at tk−1 from thedeﬁnition of U (tk ) (p is not in V (tj )(j < k)). In thefollowing, we use L2 (tk ) ⊆ O(tk ) as the set of pages
that was crawled at both tk−1 and tk .

number of links overwhelms the number of pages). We temporarily assign the constant novelty 1 to pages in L2 (tk ),and 0 to other pages in O(tk ). Then the deﬁnition of N (p)becomes the following:• If q is in O(tk ) and does not follow the above condition,
the novelty of the link (q, p) is uncertain because wecannot know when that link was created. This casecan occur when q was crawled intermittently or q was
outside W (tj )(j < k). This makes the novelty of p
somewhat uncertain.

Interestingly, from this reﬁned deﬁnition, we can see theinverse relation between the novelty measure and the decay
measure [2]. This means that the main diﬀerence is the direction of score propagation. The decay measure assigns thescore 1 to dead pages, and propagates scores to backward
pages with a damping factor. Conversely, the novelty measure assigns the score 1 to the sources of newly created links,
and propagates scores to forward pages with a damping factor.
As with the decay measure, the novelty measure can beconsidered as the absorption probabilities in a random walkon the Web graph, in which the direction of each link isinverted, and the success and failure states are added. Whena walk reaches a page in L2 (tk ), it is absorbed in the successstate at the next step (with probability 1). When a walkreaches a page in O(tk )\L2 (tk ), it is absorbed in the failurestate at the next step. In addition, from all pages in U (tk ),walks are absorbed in the failure state with the probability
δ. Therefore the novelty measure of page p is the absorption
probability in the success state when starting from page p.

 1
0
N (p) =
 (1 − δ) (q,p)∈I(p) N (q)• If q is in U (tk ), the novelty of link (q, p) depends on
the novelty of q. That is, if q is identiﬁed as novel,(q, p) is also novel.
This implies a recursive deﬁnition of the novelty measure
as follows:
N (p) = (1 − δ)(q,p)∈I(p) n(q, p)|I(p)|

 1 q ∈ L (t ))\L (t )n(q, p) = 0N (q) qq ∈∈ O(tU (t )
2

k

k

2

k

(1)

k

where I(p) is the set of links in E(tk ) pointing to p. The parameter δ represents the probability that there were links top before tk−1 outside the snapshots, and works as a damping
factor that decreases the novelty measure as it propagatesto other pages. It follows the intuition that the certainty ofnovelty decreases with the distance from novel pages.
We can rewrite this deﬁnition of the novelty measure without using the novelty of links. This reﬁnement is importantfor calculating the novelty measure, since we do not needmemory space to store the score for each link (usually, the|I(p)|

p ∈ L2 (tk )p ∈ O(tk )\L2 (tk )(2)otherwise.

4. EXPERIMENTS AND RESULTS
4.1 Dataset
For the experiments, we used large-scale snapshots of ourJapanese web archive, built during periodic crawls conducted
between 1999 and 2004 (See Table 1). Basically, our crawler
is based on breadth-ﬁrst crawling [18]; except that it focuses on pages written in Japanese. Until 2002, we collected

235

Time(tk )Old (t < tk−1 )New (tk−1 ≤ t ≤ tk )Future (tk < t)Total

Jul 2003
299,591
593,317
24,286917,194

(33%)
(65%)
(2%)
(100%)Jan 2004
87,878
270,355
7,679
365,912

(24%)
(74%)
(2%)
(100%)

May 2004
402,365
776,360
36,476
1,215,201

(33%)
(64%)
(3%)
(100%)

Table 3: The number of unidentiﬁed URLs (U (tk )) including time strings.

pages in the .jp domain. Beginning in 2003, we started tocollect pages outside the .jp domain if they were written
in Japanese. We used a web site as a unit when ﬁltering
non-Japanese pages. The crawler stopped collecting pages
from a site, if it could not ﬁnd any Japanese pages on thesite within the ﬁrst few pages. In our experiments, we used
three snapshots obtained between July 2003 and May 2004
to examine the novelty measure, since there were no serious
changes in the crawling strategy in that period.
From each snapshot, we built databases of URLs and links
by extracting anchors from all of the pages in the snapshot.
Our link database stores G(tk ) for each snapshot. To checkold URLs, we also built a database of the URL status ofeach snapshot, which stores whether each URL was crawled
or was on the fringe of the Web graph, and also stores thetime when the URL was crawled and when it was last modiﬁed. For eﬃcient link analysis, each link database was implemented as a main-memory database that provides theout-links and in-links of a given URL. The implementation
is similar to [4, 21], except that the same ID is used foreach URL over time.

Figure 1: Convergence of the novelty measure calculation for diﬀerent delta parameters (May 2004
snapshot).

4.2 Old and Unidentified Pages

Figure 1 shows the convergence of the novelty measurecalculation with the May 2004 snapshot for δ values of 0.0,
0.1, and 0.2. The x-axis is the number of iterations, andthe y-axis is the total diﬀerence in the novelty measure fromthe previous iteration. This shows that in practice 10 to 20
iterations are suﬃcient for any δ value. The convergence israther slow when using δ = 0.0, and at least 20 iterations areneeded for convergence. This is because propagated scores
are not dampened by iterations. Using 0.1 and 0.2, convergence becomes faster, and 10 iterations are suﬃcient forpractical use. In the following, we use the novelty measure
after 20 iterations.

First, we show that there are a signiﬁcant number ofunidentiﬁed pages in each snapshot. Table 2 shows thenumber of old and unidentiﬁed pages in each snapshot. To
calculate the number of old pages, we used all of the snapshots from 1999. In July 2003 and May 2004, about half ofthe pages were crawled during the last two crawls (L2 (tk )).
The percentage of unidentiﬁed pages was 25% and 30% in
in July 2003 and May 2004, respectively. This means thatthese portions of snapshots were replaced by newly crawled
pages.
Our snapshots are somewhat unstable. The number ofcrawled pages was rather small in Jan 2004; 75% of pages
were in L2 (tk ), and only 7% were unidentiﬁed. In thiscrawl, our crawler tended to collect old pages, and could
not crawled new pages as well as in the other crawls.

4.4 Distribution of the Novelty Measure
In Figures 2 to 4, we show the distribution and cumulative
curve of the novelty measure for pages in U (tk ) calculatedusing diﬀerent δ values. Each distribution has two peaks,
one around 0.0 and the other at the maximum value, because
the calculation of the novelty measure propagates 0 and 1
values of old pages with the damping factor δ.
The overall distribution does not change drastically withthe δ value, while the maximum value of the novelty measurechanges with the δ value. When δ increases, the maximum
value of N (p) decreases by δ.
These distributions are sensitive to the fraction of L2 (tk )and U (tk ). The peak around the maximum value rises as
the fraction of L2 (tk ) increases and that of U (tk ) decreases(Jan 2004), since more 1 values are propagated to a smaller
set of U (tk ). The peak around the maximum value falls as
the fraction of L2 (tk ) decreases and that of U (tk ) increases(July 2003, and May 2004).

4.3 Convergence of Calculation
The novelty measure is calculated in almost the same way
as the PageRank [7] calculation. We computed the novelty
scores of all unidentiﬁed pages (U (tk )) in a batch process asfollows:
1. Identify all old pages (O(tk )), and assign initial scoresto them according to deﬁnition (2) in Section 3. Thatis, if page p is in L2 (tk ), the initial score of p is 1, andthe score is 0 in other cases.
2. For all pages in U (tk ), calculate the novelty measureaccording to deﬁnition (2). This calculation is repeated iteratively until the novelty of all pages converges.

236

Figure 2: Distribution of the novelty measure for
newly crawled pages in Jul 2003.

Figure 5: Precision and recall of the novelty measurein Jul 2003.

Figure 3: Distribution of the novelty measure for
newly crawled pages in Jan 2004.

Figure 6: Precision and recall of the novelty measure
in Jan 2004.

Figure 4: Distribution of the novelty measure for
newly crawled pages in May 2004.

Figure 7: Precision and recall of the novelty measurein May 2005.

237

4.5 Precision and Recall
In practice, we judge a page to be novel if the novelty
measure of the page exceeds some threshold value. In thisexperiment, we evaluated the precision and recall of thisjudgment by changing the minimum threshold value. The
precision in this context is the ratio of the number of novel
pages to the number of pages judged to be novel. The recall
is the ratio of the number of pages judged to be novel to thenumber of all novel pages.
Since it is impossible to build accurate benchmarks, we
perform a rough estimation using URLs that include time
strings, such as foo.com/2004/05/ and bar.com/200405/.
We assume that such URLs appeared at their included times,
and use them as answers. Table 3 shows the number of
URLs in U (tk ) including time strings. We extracted URLs
that include a year (from 1993 to 2010) and a month in thefollowing patterns:
Figure 8: Distribution of the novelty measure forold and unidentiﬁed pages with the Last-Modiﬁed
time before Feb 2003 in the Jun 2003 snapshot.

• YYYYMM• YYYY/MM• YYYY–MM
Table 3 also shows the percentages of old URLs (with time
strings before tk−1 ), new URLs (between tk−1 and tk ), andfuture URLs (past tk ). We use the new and future URLs
as novel URLs for measuring the precision and recall. If wejudge all URLs to be novel, the precision values are 0.67,
0.76, and 0.67 for July 2003, Jan 2004, and May 2004, respectively. These precision values are baselines for evaluation.
This benchmark is partially incorrect, since some URLs
might have appeared before or after their included times.
However, the probability that a URL appeared before its
time is small. The number of future URLs in Table 3 showsthat this probability for each snapshot was only a few percent. We cannot know the probability that a URL appeared
after its time, but it is also expected to be small.
Figures 5 to 7 shows the precision and recall for diﬀerent
δ values by changing the minimum threshold. The x-axis
is the threshold value. We judge a page to be novel when
the novelty measure of the page is greater or equal to thethreshold. The y-axis shows the precision and recall.
In all snapshots, any positive threshold gives higher precision than the baseline. In Figures 5 to 7, the precision
jumps from the baseline when the threshold becomes positive. Using a higher threshold value makes the precisionslightly higher, but this increase does not exceed the ﬁrst
jump. Using positive δ values gives slightly better precision
than using δ = 0.0, but the diﬀerence between 0.1 and 0.2
is essentially zero.
The recall decreases drastically as the threshold increases
in Figures 5 and 7, but the decrease is slower in Figure 6.
This arises from the distribution of the novelty (See 2 to 4).
In the July 2003 and May 2004 snapshots, the number ofpages with low novelty scores exceeds the number of pages
with high novelty scores. This makes the decrease of the recall faster. Using a positive δ value also decreases the recall,since it slows the novelty score propagation (See Section 3).
When using the novelty measure to extract novel pages,
one has to select appropriate parameters. If higher precision
is required, one should use a positive δ value, and a higher
threshold value. If higher recall is required, one should use
δ = 0, and a small positive threshold value.

Figure 9: Distribution of the novelty measure forold and unidentiﬁed pages with the Last-Modiﬁed
time before Jul 2003 in the Jan 2004 snapshot.

Figure 10: Distribution of the novelty measure forold and unidentiﬁed pages with the Last-Modiﬁed
time before Jan 2004 in the May 2004 snapshot.

238

Figure 11: Screen snapshot of the search engine interface for our Web archive.

4.6 Miss Rateare old and unidentiﬁed. About 80% of these old pages are
assigned 0 as the novelty value in both snapshots. If wejudge the pages with positive scores to be novel, the missrate is about 20%. Using 0.1 as the minimum threshold, themiss rate decreases to about 10%. In Jan 2004, the missrate is about 40%, but the eﬀect is limited, because there
are only 0.17 million old and unidentiﬁed pages. This is only
3% of all unidentiﬁed pages.

Finally, we evaluate the miss rate of the novelty measureusing the Last-Modiﬁed time of pages. We know that page
p is older than tk−1 , if the Last-Modiﬁed time of p is before
tk−1 . According to the Last-Modiﬁed time, we extract a setof old pages, and examine how many of the pages have been
assigned positive novelty measures. The deﬁnition of themiss rate is the ratio of the number of pages judged to be
novel to the number of all old pages.
Figures 8 to 10 shows the distribution of the novelty measure for old and unidentiﬁed pages in each snapshot. The
novelty measure was calculated using 20 iterations with δ =0.1. In this calculation, we do not use the Last-Modiﬁed
time for identifying old pages (See Section 3). Comparedwith the overall distributions (in Figures 2 to 4), these distributions are shifted largely to lower values. This showsthat old pages tend to be assigned low novelty values.
We can see the miss rate from cumulative curves. In July
2003 and May 2004, there are 3.5 to 4.5 million pages that

5. APPLICATION
Currently, we are building a search engine for our Web
archive that uses the novelty measure to display changes
in the number of novel pages related to query keywords,
and to rank search results. The engine searches documents
according to given keywords in each snapshot. Figure 11 isa screen snapshot of the search engine. It includes a graphthat shows cumulative curves of the number of novel pages
over time. In keyword search results, we should consider
three types of novel page:239

• Old pages in which the keywords are newly appeared,

7. ACKNOWLEDGMENTS• Newly crawled pages that are judged to be novel using
the novelty measure, andThis work was partially supported by the Comprehensive Development of e-Society Foundation Software programof the Ministry of Education, Culture, Sports, Science andTechnology, Japan.

• Newly crawled pages that are judged to be uncertain
using the novelty measure. (Note that a low novelty
score does not mean that the page is old.)

8. REFERENCES[1] E. Amitay, D. Carmel, M. Herscovici, R. Lempel, and
A. Soﬀer. Trend Detection through Temporal Link
Analysis. Journal of the American Society for
Information Science and Technology,55(14):1270–1281, 2004.
[2] Z. Bar-Yossef, A. Z. Broder, R. Kumar, andA. Tomkins. Sic Transit Gloria Telae: Towards anUnderstading of the Web’s Decay. In Proceedings ofthe 13th International World Wide Web Conference,
pages 328–337, 2004.
[3] M. K. Bergman. The Deep Web: Surfacing Hidden
Value. Journal of Electronic Publishing, 7(1), 2001.
[4] K. Bharat, A. Broder, M. Henzinger, P. Kumar, and
S. Venkatasubramanian. The Connectivity Server:
Fast Access to Linkage Information on the Web. In
Proceedings of the 7th International World Wide Web
Conference, pages 14–18, 1998.
[5] K. Bharat, B.-W. Chang, M. Henzinger, and M. Ruhl.
Who Links to Whom: Mining Linkage between Web
Sites. In Proceedings of the IEEE International
Conference on Data Mining (ICDM), pages 51–58,
2001.
[6] B. E. Brewington and G. Cybenko. How Dynamic is
the Web? In Proceedings of the 9th International
World Wide Web Conference, pages 257–276, 2000.
[7] S. Brin and L. Page. The Anatomy of a Large-Scale
Hypertextual Web Search Engine. In Proceedings ofthe 7th International World Wide Web Conference,
pages 107–117, 1998.
[8] A. Broder, S. Glassman, M. Manasse, and G. Zweig.
Syntactic Clustering of the Web. In Proceedings of the
6th International World Wide Web Conference, pages
391–404, 1997.
[9] A. Broder, R. Kumar, F. Maghoul, P. Raghavan,
S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener.
Graph Structure in the Web. In Proceedings of the 9thInternational World Wide Web Conference, pages
309–320, 2000.
[10] J. Cho and H. Garcia-Molina. The Evolution of the
Web and Implications for an Incremental Crawler. In
Proceedings of the 26th International Conference on
Very Large Databases (VLDB), pages 200–209, 2000.
[11] N. Eiron, K. S. McCurley, and A. Tomlin. Ranking the
Web Frontier. In Proceedings of the 13th International
World Wide Web Conference, pages 309–318, 2004.
[12] D. Fetterly, M. Manasse, M. Najork, and J. Wiener. A
Large-Scale Study of the Evolution of Web Pages. In
Proceedings of the 12th International World Wide
Web Conference, pages 669–678, 2003.
[13] D. Gruhl, R. Guha, D. Liben-Nowell, and A. Tomkins.
Information Diﬀusion through Blogspace. In
Proceedings of the 13th International Conference on
World Wide Web, pages 491–501, 2004.
[14] J. M. Kleinberg. Authoritative Sources in aHyperlinked Environment. In Proceedings of the

In the graph in Figure 11, the numbers of these three typesof pages are stacked and accumulated over time.
The results of the keyword search are provided for eachsnapshot, as shown in the bottom of Figure 11. These results
are normally sorted using a simple ranking method. They
can also be sorted using the novelty measure in ascending
or descending order. By sorting the results in descendingorder of the novelty measure, a user can extract novel pages
for further analysis and mining to ﬁnd novel trends.
Figure 11 shows search results using the keyword “Prius”,
which is the name of a hybrid vehicle made by Toyota. We
can see that the number of novel pages jumped in Jan 2004,
as a result of a full model change in Sep 2003. By sorting theresults for Jan 2004 by the novelty measure, we can extract
pages about the model change, such as news releases andblogs.

6.

CONCLUDING REMARKSIn this paper, we proposed the notion of a novelty measure
for identifying newly appeared pages in a series of unstable
Web snapshots. By using the novelty measure, a set of novel
pages can be extracted with reasonable precision and recall for further analysis and mining to identify novel trends
on the Web. We also applied the novelty measure to ourarchive search engine, and showed an example of tracking
novel pages on the Web.
The novelty measure can also be used for a kind of focused crawling that collects mainly novel pages. Such focused crawling is important to ﬁnd emergent informationaccording to the user’s interest. Once the novelty measurehas been calculated for the current snapshot, the focused
crawler can use the distribution of the novelty measure tocollect novel areas from the Web.
The novelty measure is available for pages that are generated dynamically only if they have unique URLs that do
not change over time. Recently, such permanent URLs aresupported in most web publishing tools, such as blogs andWikis. Estimating the novelty of the deep Web [3] is anothermajor research area, and is beyond the scope of this paper.
The novelty measure cannot discriminate copied, moved,
and mirrored pages. Therefore, a page with old information
might be judged to be novel if the page has newly appeared
but its contents are old. Such pages should be preprocessedor post-processed using a mirror detection method, such as[8].
The snapshots used in our experiments are rather small
subsets of the entire Web, and the crawling interval is quite
long. We are interested in applying the novelty measure to
more global snapshots, and in investigating how changing
the snapshots aﬀects the results. We are now crawling larger
portions of the Web more frequently to try to observe ﬁnergrained evolution.

240

ACM-SIAM Symposium on Discrete Algorithms, pages
668–677, 1998.
[15] R. Kumar, J. Novak, P. Raghavan, and A. Tomkins.
On the Bursty Evolution of Blogspace. In Proceedingsof the 12th International Conference on World Wide
Web, pages 568–576, 2003.
[16] R. Kumar, P. Raghavan, S. Rajagopalan,
D. Sivakumar, A. Tomkins, and E. Upfal. Stochastic
Models for the Web Graph. In Proceedings of theIEEE Symposium on Foundations of Computer
Science (FOCS), pages 57–65, 2000.
[17] R. Kumar, P. Raghavan, S. Rajagopalan, andA. Tomkins. Extracting Large-Scale Knowledge Basesfrom the Web. In Proceedings of the 25th International
Conference on Very Large Databases (VLDB), pages
639–650, 1999.
[18] M. Najork and J. L. Wiener. Breadth-First Crawling
Yields High-Quality Pages. In Proceedings of the 10th
International World Wide Web Conference, pages
114–118, 2001.
[19] A. Ntoulas, J. Cho, and C. Olston. What’s New on the
Web? The Evolution of the Web from a Search Engine
Perspective. In Proceedings of the 13th International
World Wide Web Conference, pages 1–12, 2004.

[20] A. Patterson. CobWeb Search.
http://ia00406.archive.org /cobwebsearch.ppt.
[21] K. Randall, R. Stata, R. Wickremesinghe, and
J. Wiener. The Link Database: Fast Access to Graphsof the Web. SRC Research Report 175, Compaq
Systems Research Center, 2001.
[22] S. R. Ravi Kumar, Prabhakar Raghavan and
A. Tomkins. Trawling the Web for Emerging
Cyber-Communities. In Proceedings of the 8thInternational World Wide Web Conference, pages
403–415, 1999.
[23] M. Toyoda and M. Kitsuregawa. Creating a Web
Community Chart for Navigating Related
Communities. In Proceedings of the Twelfth
Conference on Hypertext and Hypermedia (Hypertext2001), pages 103–112, 2001.
[24] M. Toyoda and M. Kitsuregawa. Extracting Evolutionof Web Communities from a Series of Web Archives. In
Proceedings of the Fourteenth Conference on Hypertext
and Hypermedia (Hypertext 2003), pages 28–37, 2003.
[25] Wayback Machine, The Internet Archive.
http://www.archive.org/.

241