International Journal of Cooperative Information Systems
cfWorld Scientific Publishing Company

CONSTRUCTING A PERSONAL WEB MAP
WITH ANYTIME-CONTROL OF WEB ROBOTSSEIJI YAMADA
CISS, IGSSE, Tokyo Institute of Technology
4259 Nagatsutacho, Midori
Yokohama 226-8502, JAPANNORIKATSU NAGINO
CISS, IGSSE, Tokyo Institute of Technology
4259 Nagatsutacho, Midori
Yokohama 226-8502, JAPANIn this paper, we propose a PWM (Personal Web Map) which is a personal and small
database of interesting Web pages to a user and develop a method to construct it under
the user’s control of multiple Web robots. While general search engines with very large
databases are valid for information retrieval in the WWW, it is still important that a user
constructs a small, personal database of relevant Web pages to his/her interest. For sucha Web page database, we propose a PWM and develop a PWM system. First a user gives
keywords indicating his/her interest to a system, and it constructs a PWM concerned withthe keywords. For building a useful PWM, it is necessary that a user can interrupt theconstruction of a PWM anytime and instruct a sub-field which should be explored more.
For this function, we develop an anytime-control algorithm for multiple Web robots. A
density blackboard is used for controlling Web robots, and an uniform distributed PWM
is built. Whenever a system is interrupted by a user, it provides a valid PWM in termsof keeping search space wide, and indicates many alternatives on which he/she wants
more information. From Web pages in a database, document vectors are generated andused to construct a 2D-map of a PWM by using self-organization maps. A user easily
recognizes interim results through the 2D-map, and gives instruction by clicking a node
about which he/she wants more detail information. We made experiments by subjects
and found out that our method outperformed breadth-first search for constructing a
useful PWM. As results, a PWM system is considered as a promising approach to assist
a user in gathering relevant information in the WWW.
Keywords: Information gathering, the WWW, Web robots, anytime-control, user preference, SOM.

1. Introduction
The accessible information through the Internet is increasing explosively as the
WWW becomes widespread. While the computer resource has become inexpensive rapidly. Thus a user is able to gather relevant Web pages to his/herinterest and locally store them in a personal Web page database on a hard disk.
Using such a personal Web page database, a user is able to retrieve information
12 Constructing a Personal Web Map with Anytime-Control of Web Robots
precisely because the database is ﬁltered by user interest, and to investigate
interesting Web pages locally without inﬂuence on network traﬃc. Hence constructing a personal Web page database is important and our research aim isconcerned with it.
A practical and simple way to construct a personal Web page database is
to use a search engine with the interesting information as a query. The searchengine provides a list of relevant Web pages (called a hit list) to a user, and we
can implement a software agent that gathers the Web pages through the links
indicated in the hit list. However, since a database of a search engine is huge
and adequate ﬁltering is hard, many irrelevant Web pages may be indicatedin a hit list and gathered by the software agent. Also though a database of asearch engine is very large, it includes only a small part of all Web pages in
the WWW15. Furthermore a search engine hardly have suﬃcient recency ofgathered Web pages because the updating them by fetching a lot of modiﬁed
Web pages is very expensive18 . Consequently the gathered Web pages using asearch engine include many useless ones and do not include many useful ones.
This is why we do not use a search engine for constructing a personal Web page
database.
For building a personal database of Web pages, it is important that a user
can control the construction of a database to customize it. We propose a
PWM(Personal Web Map) as a database which a user can control its construction. PWM is a layered database consisting of classiﬁed Web pages andconstructed under user’s control. A user can determine keywords as input to a
PWM system and a PWM is gradually built by gathering relevant Web pages
to the keywords and classifying the gathered Web pages. Also a user interrupt
the gathering anytime and a PWM system show a 2D-map of a PWM througha Web browser. The 2D-map consists of nodes indicating classiﬁed subsets ofgathered Web pages, and a user can give feedback to the system by selecting anode on which he/she wants more information. The construction of a PWM isinteractive since a user can control the granularity on a PWM.
WebWatcher10 and Letizia16 are able to indicate the Web pages which auser wants to see next. Using browsing history, they learn to predict useful
Web pages for a user. These systems are consider as customizing systems thatlearn user’s preference in searching Web pages. Unfortunately the systems do
not build personal Web page databases.
SPHINX20 is a framework in which a user can achieve the personal crawlingtasks. However the customization is on searching of Web pages, not building apersonal Web page database. Thus the purpose is diﬀerent from ours.
Fish search2 is a distributed search algorithm for gathering relevance information. Agents have energy which is gained from relevant Web pages and lostfrom irrelevant pages. Agents having hight-energy can reproduce themselves
and others having low-energy may die. ARACHNID 17 is a more excellent system that can gather information by learning information agents. In the similar

International Journal of Cooperative Information Systems

3

way to ﬁsh search, agents reproduce themselves or die depending on their energy, and obtain energy from relevant Web pages. Furthermore ARACHNID isadaptive to the change of an environment. These systems do distributed controlof agents, however the control method is inspired by an artiﬁcial life approachand diﬀerent from our anytime-control.
Kohonen’s SOM (Self-Organizing Map) have been used to classify documentsin the WWW. WEBSOM7,8 is able to classify articles in network news groups
and display the clustered results. WEBSOM just does clustering documents
when they are given, and has no contribution to information gathering. In thisresearch, we use SOM for clustering gathered Web pages.
There are studies on planning to generate procedures for gathering information through computer networks. The Softbot 6 provides a framework and ainterface for describing operators. A complete partial-ordering planner is used.
Occam 14 is also a planner for gathering information. It is more eﬃcient andable to reason about the capabilities of diﬀerent information sources. Sage 11
was developed for integrating planning, execution, replanning, and sensing togathering information in distributed resources. The aim of these studies is togenerate a plan as a procedure of gathering information, and a plan consists ofUNIX commands, database operations. In contrast with these studies in which
a operational procedure of information gathering is generated automatically, a
PWM system actually gathers relevant Web pages under user’s preference.
Our research is concerned with the Web Robot 9 which is used to gather Web
pages for a search engine database. However it is not controlled and traces toonly linked pages with breadth-ﬁrst search-like fashion. A PWM system utilizes
more sophisticated search and the experimental comparison will be describedlater.
Some learning systems have been developed for information gathering andbrowsing in the WWW. ShopBot 4 learns the text pattern indicating the priceof CD-ROMs, and searches for the cheapest one more eﬃciently than a human.
The purpose of ShopBot is diﬀerent from our research. WebWatcher 10 and
Letizia 16 are able to indicate the Web pages which a user wants to see next.
Using browsing history, they learn to predict useful Web pages for a user. Thesestudies focused on how to extract knowledge from gathered Web pages. In
contrast with that, a PWM system is concerned with how to gather Web pages.
Navigation planning 23 automatically generates a sequence of Web pages bywhich a user can understand a concept systematically. First a user inputs aquery indicating his/her a target concept and a navigation planning does planning using operators which are generated automatically from Web pages. In
this system, action corresponds to understanding a Web page, and a navigation
planning system is able to generate such operators from Web pages by utilizing
tag structure and a indexing method. Unfortunately the system cannot acquireuser’s interest interactively.
We summarize the contents of this paper. In section 2, we describe the4 Constructing a Personal Web Map with Anytime-Control of Web Robots
overview of a PWM system and a PWM as a structured database. Next we
explain the construction of W P S and a density blackboard. Anytime-control ofmultiple Web robots which is suitable to build a PWM is described. In section 3,
we describe human computer interaction in a PWM system. Using SOM, a 2Dmap is generated for indicating the interim results of Web page gathering, anda user can select a node on which he/she wants more information. In section
4, we make experiments for evaluating our approach. Web robot search likebreadth-ﬁrst search is experimentally compared with our approach. In section
5, limitations and open problems are discussed. Finally section 6 concludes thisresearch.
2. Information gathering with multiple Web robots
2.1. Overview of a PWM system
Fig.1 shows the overview of a PWM system. It roughly consists of a PWM, a
2D-map, SOM and Web robots. A user can control to construct a PWM. The
input of the system are keywords on which a user wants to build a PWM, anda system outputs a 2D-map of a PWM to him/her. A user can click a node on
the 2D-map for gathering more information about it.
Multiple Web robots gather relevant Web pages to keywords. They monitor
a density blackboard in a PWM, and try to gather pages in the most sparsearea. This is called anytime-control, and we will mention its detail later. The
anytime-control makes a database of Web pages uniform and provides a valid
2D-map with many alternatives a use can select. Web pages gathered by Web
robots are stored in a Web page database. All Web robots work asynchronously.
A density blackboard in a PWM is updated with keyword vectors detectedfrom Web pages in the database. A 2D-map is generated depending on document
vectors by SOM.
After gathering, using PWM and a IR system, a user is able to retrieve information precisely because of ﬁltering by user interest and investigate interesting
Web pages locally without inﬂuence on network traﬃc. Also the tree structureof W P Ss may be utilized for constructing a directory structure like YaHoo’s
interface.
2.2. PWM
As seeing from Fig.1, a PWM (Personal Web Map) is consisting of a Web pages
database, tree-structured W P Ss and a density blackboard. A W P S is a set of
keyword vectors generated from Web pages in the Web page database. A density
blackboard indicates the distribution of keyword frequency in the gathered Web
pages.
Fig.2 shows more detailed W P Ss and a density blackboard. The ﬁrst layer
includes a W P S00 including keyword vectors of directly relevant Web pages toInternational Journal of Cooperative Information Systems

5

PWM system
2D-map
Request for detail WPS
Node selection
Keywords

User

PWM

SO

M
WPS
Density
blackboard
keywordvectorWeb page
database

Web robot-1...

Web robot-n

The WWW
Fig. 1. A PWM system.

keywords given by a user as input. W P Sji means the jth W P S in the ith-layer,
and a layer may include multiple W P Ss. A single W P S is constructed by
Web robots’ information gathering at once and it is called a current W P S. In
Fig.2, if the current W P S is W P S01 , the density blackboard is generated froma current W P S01 and Web robots fetch Web pages by monitoring the density
blackboard under anytime-control.
During Web page gathering, the Web pages are classiﬁed by SOM and clusters (white circles of W P S in Fig.2) are generated whenever a user requests it.
Then the 2D-map, in which a node corresponds to a cluster in W P S, is indicated to a use. If he/she points a cluster in a W P Sjn about which he/she wants

6 Constructing a Personal Web Map with Anytime-Control of Web Robots
Deisity
blackboard

0

WPS 0

Layer- 0

granurality
High
WPS 01
Layer-1. . . .

. . . .

Figure 2 W P S and a density blackboard.
to know more, a system will generate the more detail W P Skn+1 for the cluster k
in a (n+1)th layer. With such a procedure, a user is able to control constructionof a PWM for including detail information about which he/she wants to know
more.
In a PWM, each W P S contains about hundreds of Web pages. You may
claim a PWM must be a small subset of a large database for a large searchengine. However we often face the facts that many interesting Web pages are
not captured by such a search engine. We consider a PWM which is controlled
by a user is promising for a fast personal search engine with a necessary andsuﬃcient Web page database.
2.3. Constructing WPS
For constructing a W P S, a system generates keyword vectors using the occurrence frequency of keywords in a Web page. A keyword vector is similar toa term vector used for the vector space model22 in information retrieval. A
keyword vector Vp of a Web page p is described in the following.
Vp=(vp1 , vp2 , · · · , v pN )=f(p, tN )f(p, t1 ) f(p, t2 ),, · · ·,m(D, t1 ) m(D, t2 )m(D, tN )

where m(D, t) = max f(p, t).
p∈D

The D is a set of Web pages and the f(p, ti ) indicates the occurrence frequency of the input keyword ti in a Web page p. The value vpi stands for normalized f(p, ti ) by the maximum value in Web pages of a Web page database

Vector value of keyword-2

International Journal of Cooperative Information Systems

7

1
[6]

[5]

[3]

[9]

0.5

0

0.5

1

Vector value of keyword-1
Fig. 3. A density blackboard.

D. The range of vpi is [0, 1] and the v pi shows the importance of ti in the Web
page. Also N is the number of keywords inputed by a user. Finally a set ofthese keyword vectors Vp s is a W P S.
2.4. A density blackboard
A blackboard system5 provides a useful architecture to control a distributed
multi-agent system. Agents read and write the information to layered sharedmemory, called a blackboard, and share them ﬂexibly. Thus we use a blackboard
for Web robots to share the information. The shared information is a density
distribution which is the distribution of the number of keyword vectors in a Web
page database in the keyword vector space.
The range [0, 1] of each axis in a n-keyword vector space is divided into m
patches. Since the n-keyword vector space has n dimensions in the keyword
vector space, mn patches are generated in total. Next the densities for eachpatches are computed, and they are stored in a density blackboard. Fig.3 showsa two dimensional density blackboard for two keywords. Each axis is divided
into two patches. The black points and the numbers within blankets indicate
keyword vectors of Web pages and densities of patches respectively. As mentioned later, if a patch has high density, it has been explored well and Web
robots do not need to investigate there. If a patch has low density, it was not
explored suﬃciently and Web robots should investigate there more.
2.5. Anytime-control of Web robots using a blackboard modelKeyword-2

Keyword-2

8 Constructing a Personal Web Map with Anytime-Control of Web Robots

A

0

Keyword-1(a) An uneven PWM

B

0Keyword-1(b) An uniform PWM

Fig. 4. An uniform PWM.

2.5.1. Control policy
Though many search engines use multiple Web robots for gathering Web pages,
few ones control them eﬀectively. Thus we propose anytime-control: a novel
method for controlling Web robots to build a PWM.
An important point to build a PWM interactively is that the building process
may be interrupted anytime by a user. A PWM system allows a user to interrupt
information gathering to see intermediate results and control it. Hence it shouldbe able to indicate appropriate results whenever a user requests. We consider theappropriate results are Web pages which were gathered uniformly on keywords.
If it does not control Web robots, the obtained PWM will be uneven and its
coverage will be far more narrow than an uniform one.
Fig.4 shows an uneven PWM and an uniform PWM when ten Web pages weregathered. The two keywords were given to a PWM system, and the X and Y
axes indicate the relevance to keyword-1 and keyword-2 respectively. The black
circles stand for start Web pages, and the crosses indicate keyword vectors ofgathered Web pages. Though both of the PWM started from the same keyword
vector, the results are diﬀerent in the coverage (the circle A and B). Since auser selects a keyword vector about which he/she wants to gather more detail
information, the coverage of subsequent layers is restricted within circle A and
B. Thus the coverage of an uneven PWM becomes far more narrow than that of
the uniform one. Obviously we prefer a PWM with a wide coverage.
2.5.2. A procedure for a Web robot
Thus we need an algorithm that returns an uniform PWM whenever a userinterrupts. We developed such an algorithm which is called anytime-control∗ .
∗ This name is inspired by an anytime-algorithm 1 which, returns valid results anytime, hasbeen studied in real-time problem solving in artificial intelligence.

International Journal of Cooperative Information Systems

9

The control is a simple distributed procedure shown in the following. Each Web
robot acts using the algorithm asynchronously, and stops when a user interrupts
it or the number of obtained Web pages becomes the given limit number or alimit time has come.
Anytime-control procedure for a Web robot(1) See a density blackboard and determine the most sparse patch.
(2) Select a Web page α randomly in the patch.
(3) Select a linked Web page β randomly in the Web page α.
(4) Fetch a html ﬁle of the page β.
(5) Generate a keyword vector from the obtained ﬁle and write it into a density
blackboard. Also store the ﬁle in a Web page database.
(6) Go to (1).
In the above procedure, Step (1) makes a PWM uniform. Each Web robot
tends to explore more in an area with the least information, and this keeps thedensity of Web pages uniform. Additionally, URLs of the fetched Web pages
are stored, and the Web pages are not selected in Step (2) and (3) again.
Note that in order to gather Web pages in the same patch to the Web page
α for Step (3) and (4), a system tries to get Web pages linked from α. This is avalid way supported by some evidences. Menczer17 pointed out R > G, where
R is the conditional probability that a Web page is relevant given that it islinked by another Web page that is relevant with the same query, and G is thegenerality of the query, i.e., the fraction of Web pages that are relevant. Since
R > G means that is is more likely to hit a relevant Web page from anotherrelevant Web page than from any random Web page, the linked Web pages in
Step (3) and (4) tend to be within the same patch to α. Another evidence is areal-time search mode of WebCrawler3 . The algorithm assumes that following
links from Web pages that are similar to what the user wants is more likely tolead to relevant Web pages than following any link from any Web page. Under
the assumption, WebCrawler works well.
2.6. A procedure of a PWM system
Eventually the procedure of a PWM system is described in the following.
(1) Initialize a W P S00 as a empty set, and set a current W P Sji by W P S00 .
(2) A system inputs MetaCrawler19 the keywords as a query, and obtains themost relevant 13 Web page. A PWM system initializes a density blackboard
by giving it the document vectors of the 13 Web page as a start point.
(3) Start Web robots under anytime-control for gathering relevant Web pages.
(4) If interrupt of a user is given, work SOM to make a 2D-map of PWM anddisplay it to a user. If a user clicks a node in the 2D-map, set a current
W P S by W P Ski+1 , and go to Step (2).

10 Constructing a Personal Web Map with Anytime-Control of Web Robots(5) If the number of gathered Web pages becomes the limit number, stop andwait a user’s request.
3. Human computer interaction
3.1. SOM-based display
SOM (Self-Organizing Maps)12,13 have been widely applied to build 2-dimensional
visualization from a large text database. Because the learning algorithm is simple, and the input of high-dimensional vectors are automatically classiﬁed. For
example, WEBSOM7,8 has been developed for clustering a lot of articles for
network news.
Since the keyword vector has the identical dimension to the number of keywords and it is usually more than three, a system needs to reduce the dimension
to two in order to indicate a PWM to a user. Thus we can construct a 2D-map ofa PWM by using SOM. We explain the SOM-based procedure in the following.
The SOM learns with random input vectors in the document vector space, andthe document vectors of gathered Web pages are given to the learned SOM andclassiﬁed.
(1) Generate a set S of document vectors from Web pages of the current W P S
in a Web page database. The document vector is slightly diﬀerent from a
keyword vector in normalization. It is normalized as a unit vector using thefollowing formula. The E p and f(p, t) are the document vector of a Web
page p and the occurrence frequencies of a word t in a Web page p.
Ep=(ep1 , ep2 , · · · , e pN )=f(p, t1 ) f(p, t2 )f(p, tN ),, · · ·,
l(p)
l(p)
l(p)

 N

f(p, ti )2
where l(p) = i=1(2) Fig.5 shows the structure of SOM. Construct SOM using the number of
keywords as the number of the input nodes and 25 (= 5×5) as the numberof competitive nodes. The competitive layer is set to two dimension.
(3) Generate a set R of random document vectors with random values through[0, 1] in each dimension of a document vector. Give the R to SOM repeatedly, and update the weights between input nodes and competitive nodes
using the following procedures12 .
(a) Let an input vector and weights of links from all input nodes to a competitive node ui be Ep = [e1 ,e2 ,· · ·,e n ] and Ui = [ui1 ,ui2,· · ·,u in ] respec-

International Journal of Cooperative Information Systems

11Competitive
layer

...
Input layer
Input vector

Node-1 Node-2 Node-n(e 1, e 2, ..., en )Fig. 5. Self-Organizing Network.

tively. In a PWM system, the n is set with the number of keywords
N.
(b) SOM compute the similarity between the input vector and competitive nodes. The similarity is evaluated by Euclidean distance using thefollowing formula.
(epj − uij )2
Ep − Ui  =j(c) Since we need a 2D-map, a square having the winner as the center is usedas neighborhood. The formula for updating the weights of neighbors isshown in the following, where the α is a learning rate.
old
unew
ij = uij + ∆uij

∆uij =α(ej − uij )0: i in the neighborhood: otherwise

With the following equations, the α and the size of neighborhood arescheduled to decrease as learning progresses.




t
t
d= 5 1−
α = 0.5 1 −
10000
10000
(4) After learning, the set S of document vectors of gathered Web pages is
inputted to a learned SOM, winner nodes for each vector are determined,
and classiﬁcation is done. The winner node of a Web page indicates theclass. Also unit keyword vectors are inputed to a learned SOM and thewinner nodes are labeled with corresponding keywords. The winner nodes
are called keyword nodes, and the unit keyword vector of the nth keyword

12 Constructing a Personal Web Map with Anytime-Control of Web Robots

Fig. 6. A 2D-map of a PWM.

is (0, · · ·, 1, 0, · · ·, 0) where only the nth value is 1. The keyword nodes
are colored diﬀerently, and the other nodes among them are colored in
graduation. Furthermore the size of a node is in proportion to the numberof keyword vectors included in the node.
Labeling and coloring the nodes enables a user to easily understand which anode include the relevant Web pages to a keyword. Also learning with random
unit vectors makes the positions of keyword nodes widely distributed in a 2Dmap. This helps a user to select a node on which he/she wants to know more.
An executed example of 2D-map for ﬁrst layer PWMs is shown in Fig.6.
The 2D-map was generated from keywords “application”, “database”, “foil”,“learning”, “ontology”, “progol”, “relation”. You can see the keyword nodes,
and the distance between them stands for their similarity. The size of a nodestands for the number of Web pages classiﬁed in the node.
3.2. User feedback
Using a 2D-map, a user can easily point nodes about which he/she wants toknow more. When a node is pointed by a user, a system opens a dialog windowcalled a node info window like Fig.7. With a node info window, a user can see
the URLs of the Web pages included in the pointed node and the occurrenceInternational Journal of Cooperative Information Systems

13

Fig. 7. A node info window.

frequencies of all keywords in the Web page. A user determines whether he/shewants to know more about the node, and clicks the more detail button forrequest. Note that a 2D-map provides the access to intermediate nodes except
keyword nodes. This makes user’s selection of intermediate concepts easy.
If the more detail button is clicked, a PWM system will gather Web pages
for constructing the more detail W P S in the next deeper layer. The procedure is basically similar to one described in section 2.5.2, however the density
blackboard is restricted. The occurrence frequencies of n keywords is restrictedminmax≤ vN ≤ vN, wherewithin the region R satisfying v 1min ≤ v1 ≤ v1max , · · · , v Nminmax= minp∈S v(p, i)，vi= maxp∈S v(p, i)，N is the number of input keyvi
words, v1 , v2 , · · · , v N are variables in nth axis, S is a set of keyword vectors
included in the pointed node, and v(p, i) is a nth value of a keyword vector p.
This is the minimum region including all the keyword vectors in the pointed
node, and a system gathers only the Web pages having keywords included in
the restricted region. This restricts the next W P S within the neighborhood of
the pointed node. Fig.8 shows this process in 3-dimensional W P Sji . The node
G is selected by a user and W P Ski+1 is created in the restricted region R.
4. Experimental evaluation
In order to verify the eﬀect of anytime-control in a PWM system, we madeexperiments with 10 subjects. The subjects were master course students in acomputer science department, and the keywords which they used are shown in
Table.1. We did not restrict the user’s keyword selection.
To compare anytime-control used in a PWM system through all the ex-

14 Constructing a Personal Web Map with Anytime-Control of Web Robots

G
i

WPS j

2D-mapNode G is selected.

R

i

WPS j

i +1

WPS k

Fig. 8. Generating a W P S by user feedback.

periment, we used general Web robot search used in many search engines. In
most search engine, Web robots are not control eﬀectively and the strategy is abreadth ﬁrst search. Thus we call it Web robot search described in the following.
Web robot search(1) Initialize the Web page list F = [ ].
(2) Set current Web pages α by starting Web pages P0 , and append all linked
pages from α to F . The P 0 is generated in the same way to a PWM systemdescribed in Step (2) of section 2.6.
(3) Pick the head page β in F and remove it from F .
(4) Fetch the page β.
(5) Add all linked pages in β into the tail of F .
(6) Go to Step (1).
Two methods: a PWM system using anytime-control and a Web page gathering system using Web robot search were compared through the following identical procedures in same settings. The 2D-map consisted of 25 nodes (5×5), andthree Web robots worked as diﬀerent processes. We implemented the systems
using Perl, Java, SQL and a parser program on Linux in a Celeron (433M Hz)
PC-AT machine with 128M RAM.

International Journal of Cooperative Information Systems

15

Table 1. Keywords given by 10 subjects.

Subject
p1
p2
p3
p4
p5
p6
p7
p8
p9
p10

Keywords
director, mystery, actress, movie, actor
php3, postgreSQL, JDBC, JAVA
genetic, programming, GP, intron, tree
cribbage, crib, card, board, game, run, skunk,doublelinux, kernel, install, distribution, debian,dpkg
agent, www, navigator, personalize, proﬁle,AIpet, zoo, food, cat, ﬁshing
relation, learning, ontology, database, progol,
foil, application
multiple, robot, agent, cooperate, strategy
slither, link, puzzle, faq, tips

4.1. Evaluating uniformity of gathered Web pages
For verifying that anytime-control can construct a uniform PWM, we investigate the standard deviation SD of the number of Web pages in each patch,which is described like the following formula. The x i and x are the number of
Web pages in a patch i and the average of them for all the patches. The n is
the total of Web pages. The SD indicates the scattering of Web pages, thus a
PWM is more uniform as the SD is smaller.


n
1
(xi − x)2
SD = 
ni=1

Fig.9 shows the experimental results. In the graph, the x-axis and y-axis
stand for the number of gathered Web pages and SD. As seeing from the graph,anytime-control is able to keep a PWM more uniform than Web robot search as
gathered Web pages increases.
The above uniformity was evaluated in a density blackboard. However weneed an uniform 2D-map because a user can actually operate only it. Thus wealso investigated the uniformity in a 2D-map. For each subject, Web page gathering using both of anytime-control and Web robot search were done for threehours, and 2D-maps were generated by SOM. Fig.10 shows the experimental
results. The x-axis and y-axis stand for subjects and the standard deviation
for the number of Web pages classiﬁed in nodes of a 2D-map. Seeing fromthis ﬁgure, the standard deviation of a 2D-map by anytime-control is less thanthat by Web robot search for all subjects. Hence we veriﬁed the uniformity ofanytime-control in a 2D-map was also larger than that of Web robot search.

Standard deviation

16 Constructing a Personal Web Map with Anytime-Control of Web Robots
70
60
50
40
30
20
Web robot search
Anytime control

10
0

500

1000 1500 2000 2500 3000 3500 4000
The number of gathered Web pages

Standard deviation

Fig. 9. Uniformity of gathered Web pages.

60: Web robot search: Anytime control

50

40

30

20

10

0
p1

p2

p3

p4

p5

p6

p7

p8

p9

p10
Subject

Fig. 10. Uniformity in a 2D-map.

4.2. Evaluating the gathered relevant Web pages
The purpose of a PWM system is to gather relevant Web pages to a user’s interest
eﬀectively. Thus we made experiments for evaluating Web pages gathered by
a PWM system. Then we investigate the number of relevant Web pages ingathered Web pages in the 1st and 2nd layer W P Ss.
First Web page gathering was done in the ﬁrst layer for three hours, and a
2D-map was generated. Then a subject selected a node on which he/she wants
to know more in the 2D-map and next gathering was done in the second layer
for three hours again. After gathering, a subject scores Web pages using thefollowing scores.

# of Web pages in the 2nd-layer

International Journal of Cooperative Information Systems

17900: Web robot search

800: Anytime control
700
600
500
400
300
200
100
0
p1

p2

p3

p4

p5

p6

p7

p8

p9

p10
Subject

Fig. 11. The number of Web pages gathered in the 2nd-layer.

• 2 for a Web page which is significantly relevant to user’s interest.
• 1 for a Web pages which is slightly relevant to user’s interest.
• 0 for a Web pages which is not relevant to user’s interest.
Fig.11 shows the number of Web pages gathered in the 2nd-layer. Seeing
from the graph, the numbers of Web pages have large variance. We consider
this variance is caused by the network traﬃc which is signiﬁcantly dependent on
Web sites. Another interesting results is that for almost subjects, the number of
Web pages gathered by anytime-control is less than that by Web robot search.
The reason for this results will be discussed in section 5.1.
Next we investigated the total scores for each subject and normalized themby dividing by the maximum score. The results are shown in Fig.12, where
the x-axis and y-axis stand for subjects and normalized total scores. Seeing
from the ﬁgure, anytime-control outperformed Web robot search for almost
subjects. Thus we found out a PWM system is promising for gathering relevant
information to user’s interest in the WWW.
5. Discussion
We evaluated a PWM system through several experiments and veriﬁed the utility. In this section, we discuss limitation and open problems in our approach.
5.1. Overhead for constructing a PWM
In comparison with Web robot search, a PWM system needs additional processing like parsing Web pages, computing keyword frequency and updatinga density blackboard. This costs signiﬁcantly because the text processing isNormalized total score

18 Constructing a Personal Web Map with Anytime-Control of Web Robots
0.25: Web robot search: Anytime control
0.2

0.15

0.1

0.05

0
p1

p2

p3

p4

p5

p6

p7

p8

p9

p10
Subject

Fig. 12. The relevance of gathered Web pages.

generally expensive. This cost is why the number of Web pages gathered byanytime-control was less than that by Web robot search in Fig.11. It is ouropen problem to decrease the overhead.
5.2. The timing to stop Web page gathering in the 1st-layer
In a PWM system, a user can stop Web page gathering whenever he/she wants
to do so. However, when should a user interrupt Web page gathering in the 1stlayer for obtaining the maximum relevant Web pages to his/her interest? Since
this problem seems to be solved analytically, we made additional experiments
by varying the ratio of the time for 1st-layer gathering and the time 2nd-layerone. Fig.13 shows the experimental results, where the x-axis and y-axis standfor the ratio of the 1st-layer gathering time to the 2nd-layer gathering timeand normalized total scores. As seeing from this graph, we did not obtain any
tendency. Thus we conclude the relevance of gathered Web pages to user’s
interest is hardly dependent on the timing to stop Web page gathering in the
1st-layer.
6. Conclusion
We proposed a PWM (Personal Web Map) for a user to gather interesting Web
pages, and developed a PWM system consisting of PWM, multiple Web robots
and a 2D-map. The PWM includes a Web pages database, tree-structured
W P Ss and a density blackboard. The system is able to do anytime-control for
multiple Web robots to gather relevant Web pages eﬀectively. For controlling
Web robots, a density blackboard is used, and an uniform distributed PWM

Normalized total score

International Journal of Cooperative Information Systems

19

0.3: Web robot search
0.25: Anytime control

0.2

0.15

0.1

0.05

0
p1

p2

1st-layer: 1 hour
2nd-layer: 5 hours

p3

p4

p7

p8

1st-layer: 2 hours 1st-layer: 4 hours
2nd-layer: 4 hours 2nd-layer: 2 hours

p9

p10

1st-layer: 5 hours
2nd-layer: 1 hourFig. 13. The relevance of gathered Web pages as varying the timing to interrupt.

is built. Using anytime-control, the Web robots search the areas in which theleast Web pages have been gathered in the keyword vector space. From Web
pages in the database, document vectors are generated and used to SOM-basedclassiﬁcation for constructing 2D-map. A user easily recognizes a PWM throughthe 2D-map, and gives feedback by selecting a node about which he/she wants
more detail information. The selected node is expanded into a next-layer node
including detail information.
We implemented a PWM system and made experiments by comparing withWeb robot search. For evaluating the utility of anytime-control, the uniformity of gathered Web pages was investigate. Then the relevance of gathered
Web pages to user’s interest was also evaluated. As results, we found out that
our PWM is a promising approach to assist a user in gathering the relevant
information to his/her interest in the WWW.
Acknowledgments
The authors would like to acknowledge the suggestions of Prof. K. Nitta, Prof.
S. Kobayashi, Prof. T. Kobayashi, Prof. M. Watanabe and Prof. H. Kinukawa.
This work has been supported by “Biologically Inspired Adaptive Systems”
of Research for the Future Program in Japan Society for the Promotion of
Science. We would like to express our gratitude to it.

20 Constructing a Personal Web Map with Anytime-Control of Web Robots
References
1. M. Boddy and T. Dean, Solving time-dependent planning problems, in Proc. of
the 11th Int. Joint Conf. on Artificial Intell. (1989) 979–984.
2. P. De Bra and R. Post, Information retrieval in the world-wide web: Making clientbased searching feasible, in the 1st Int. WWW Conference (1994).
3. F.C. Cheong, Internet Agents: Spiders, Wanderers, Brokers, and Bots (NewRiders, 1996).
4. R. B. Doorenbos, O. Etzioni, and D. S. Weld, A scalable comparison-shopping agent
for the World-Wide Web, in Proc. of the 1st Int. Conf. on Autonomous Agent(1997) 39–48.
5. L. D. Erman, F. Hayes-Roth, V. R. Lesser, and D. R. Reddy, The Hearsay-II
speech-understanding system: Integrated knowledge to resolve uncertainty, Computer Surveys 12 (1980) 213–253.
6. O. Etzioni and D. Weld, A SoftBot-based interface to the Internet, Communicationof the ACM 37, 7 (1994) 72–76.
7. T. Honkela, S. Kaski, K. Lagus, and T. Kohonen, Newsgroup exploration withWEBSOM method and browsing interface, TR-A32, Helsinki University of Technology of Computer and Information Science (1996).
8. T. Honkela, S. Kaski, K. Lagus, and T. Kohonen, WEBSOM—self-organizing mapsof document collections, in Proc. of WSOM’97, Workshop on Self-Organizing
Maps (1997) 310–315.
9. K. Jamsa, S. Lalani, and S. Weakley, Web Programming, (Jamsa Press, 1996).
10. T. Joachims, D. Freitag, and T. Mitchell, Webwatcher: A tour guide for the World
Wide Web, in Proc. of the 15th Int. Joint Conf. on Artificial Intell. (1997)
770–775.
11. C. A. Knoblock, Planning, executing, sensing, and replanning for information gathering, in Proc. of the 14th Int. Joint Conf. on Artificial Intell. (1995) 1686–1693.
12. T. Kohonen, The self-organizing map, in Proc. of the IEEE (1990) 1464–1480.
13. T. Kohonen, Self-Organization Maps (Springer-Verlag, 1995).
14. C. T. Kwok and D. S. Weld, Planning to gather information, in Proc. of the 13th
National Conf. on Artificial Intell. (1996) 32–39.
15. S. Lawrence and L. Giles, Accessibility and distribution of information on the Web,
Nature 400 (1999) 107–109.
16. H. Lieberman, Letizia: A agent that assists Web browsing, in Proc. of the 14th
Int. Joint Conf. on Artificial Intell. (1995) 924–929.
17. F. Menczer, ARACHNID: Adaptive retrieval agents choosing heuristic neighborhoods for information discovery, in Proc. of the 14th Int. Conf. on Machine
Learning (1997) 227–235.
18. F. Menczer and A. E. Monge, Scalable Web search by adaptive online agents: an
InforSpiders case study, in Intelligent Information Agents, eds. M. Klusch (Springer,
1999) 323–347.
19. MetaCrawler, http://www.metacrawler.com/.
20. R. C. Miller and K. Bharatb, Sphinx: a framework for creating personal, site-specific
Web crawlers, Computer Networks and ISDN Systems 30 (1998) 1–7: FP12.
21. J. J. Rocchio, Relevance feedback in information retrieval, The Smart system –experiments in automatic document processing (Prentice Hall Inc, 1971) 313–
323.
22. G. Salton, Automatic Text Processing, (Addison-Wesley, 1989).
23. S. Yamada and Y. Osawa, Planning to guide concept understanding in the WWW,in AAAI 1998 Workshop on AI and Information Integration (1998) 121–126.