Automated Alignment of Multiple Internet Directories
ICHISE Ryutaro

TAKEDA Hideaki

HONIDEN Shinichi

National Instituteof Informatics
2-1-2, Hitotsubashi,
Chiyoda-ku, Tokyo, Japan

National Instituteof Informatics
2-1-2, Hitotsubashi,
Chiyoda-ku, Tokyo, Japan

National Instituteof Informatics
2-1-2, Hitotsubashi,
Chiyoda-ku, Tokyo, Japanichise@nii.ac.jp

takeda@nii.ac.jp

honiden@nii.ac.jp

ABSTRACT

Directory services are tools for making useful information
more accessible, but individual internet directories in directory services are of limited use in nding user-relevant
web pages. In this paper, we propose a method for aligning
URL information from one internet directory to another.
This method can discover an appropriate position in a directory for a web page which is not shown in that directory
but shown in another directory. By using this method, one
can extend a favorite directory with information on otherdirectory services. Discovery of alignment is based on categorization similarity in the concept hierarchies of the twointernet directories. We adopted the \ statistic" method
to measure the similarity syntactically. We conducted anexperiment using real-world internet directories. The results of this experiment show that the proposed method
is promising, i.e., it can classify unknown web pages into
appropriate categories within an internet directory.

Keywords

Machine learning, internet directory, Web, categorization

1.

INTRODUCTION

With the rapid growth of the WWW, it is getting diÆcultfor us to nd information that we want. To nd useful
information, people often use search engines which show
web pages including the speci ed keywords. But if they do
not have knowledge well on thir searching domain, searchengines are useless because they can not choose appropriate keywords. One answer to this kind of problem is touse directory service which have the pages evaluated andorganized by humans before they are registered within thesearch engine archive. However, a single directory service
is not enough for use since the search engine tends to havesome speciality both in collecting pages and in categorizing them. To solve those problems, we propose a method
in which multiple internet directories are used. There aremany public internet directories which have been formulated by humans. Some of them are provided to cover awide domain and some are for special domain. Such internet directories are hard to align, because of their varietyof conceptual hierarchy and their wide distribution aroundthe world. We propose a method for solving this problem.
In this paper, we describe a machine-learning method foraligning multiple internet directories.

2.

INTERNET DIRECTORY MODEL

Most internet directories are managed via a system of hierarchical categorization. Each internet directory contains
only one conceptual hierarchy for the organization of its
categories. Each category contains links to web pages(URLs). The diagram on the left side of Figure 1 represents a single internet directory.
C1C2

URL 1
URL 2
URL 3

Figure 1: Internet Directory Model

In Figure 1, there are two di erent internet directories(C1 and C2 ) and three di erent URLs (URL1 , URL2 andURL3 ). Some of URLs are shared between two directories
and some are not. It is important to keep in mind thatthese internet directories do not have the same conceptual
hierarchy. The next step is to consider an appropriate way
to align a URL from C1 into C2 . In the example shownin Figure 1, C2 does not contain URL2 . If URL2 can beplaced in the concept hierarchy of C2 , the user can then use
C2 to nd useful information (at URL2 ), because URL2
has already been evaluated and categorized. In the next
section, we propose a method of de ning a rule for alignment from the concept hierarchy of C1 to that of C2 , sothat a web page which has already been categorized in C1
can subsequently be categorized in C2 . The most important point of this approach is that the concept hierarchyof C2 does not need to be adjusted to t the concept hierarchy of C1 . Thus, a user can continue to use whicheverinternet directory they are accustomed to.

3. FINDING SIMILAR CATEGORYIn our method, alignment is discovered as alignment rules
between two directories. We rstly nd categories which
are similar to each other (\similar categories"); the web
page will then map one to another based on similarity
between categories. To nd similar categories, our algorithm starts by comparing the most general categories of
the two internet directories. For each pair of categories,
we can determine similarity based on URLs categorized inboth categories. For each category, we can decide whether
a particular URL belongs to that category. If the categorization methods of two categories are similar, then thesystem generates an alignment rule for them. It should be
noted that, because internet directories are structured astrees, we can easily categorize URLs according to a nodalstructure, such that URLs in lower (more speci c) categories are included in higher (more general) categories.
To nd similar categories, we used a statistical methodfor determining the degree of similarity between two categorization criteria. The \ statistic" method [2] is anestablished method of evaluating similarity between twocriteria. The relationship between two categorization criteria is examined from \top" to \bottom". First, the mostgeneral categories in the two internet directories are compared using the \ statistic". If the comparison con rms
that the two categories are similar, then the algorithm outputs an alignment rule for them. At the same time, thealgorithm pairs one of these two similar categories with a\child" category of the other similar category. This newpair is then evaluated recursively using the \ statistic"
method. When a similar pair is not generated, the algorithm outputs the alignment rule between the two internet directories. We can then apply this rule to deciding
whether a particular URL in C1 ts the concept hierarchyin C2 .

4.

EXPERIMENTAL EVALUATION

In order to evaluate our algorithm, we conducted experiments using the Yahoo! Japan [6] and LYCOS Japan [3]directories as internet directories. The Yahoo! directory
contains approximately 41,000 categories and 224,000 URLs.
In contrast, LYCOS contains approximately 5,700 categories and 48,000 URLs. Approximately 25,000 URLs canbe found both in Yahoo! and in LYCOS. Generally speaking, Yahoo! contains more knowledge than LYCOS as aninternet directory, but half of the URLs contained in LYCOS are not contained in Yahoo!. This fact implies that,to ensure access to useful Web pages, it is not suÆcientthat a single directory contains enormous number of URLs.
In this experiment, we used the categories Yahoo!:Arts/Humanities/Literature (and sub-categories) and LYCOS:
Arts/Literature (and sub-categories) as our two internet
directories. We conducted 10-fold cross validation for theshared URLs; i.e., the shared URLs were divided into ten
data sets, and nine of these sets were used for training
while the remaining set was used for testing. Ten experiments were conducted for each data set. The parameterof signi cance level for \ statistic" was set at 5%.
The results of the experiments are shown in Figure 2. The
vertical axis denotes average accuracy of the test data.
\Use Exact Rules" denotes values of accuracy for a system which only uses the alignment rules for the category towhich the URL belongs. \Use Parent Rules" denotes that,
if the system does not generate an alignment rule for a category to which the URL belongs, it will use a rule generated for the parent category instead. \Criterion 1" meansthat a URL is categorized in the same category as the test
data. \Criterion 2" means that a URL is categorized in
the same category or its parent category as the test data.
\Criterion 1" is very strict criterion because the target
directory should have enough intermediate categories incomparison with the source directory, while \Criterion 2"
is more general and more realistic because it does not matter which directories are rich in categorization. \Yahoo toLycos" means that URLs are aligned from the concept hierarchy of Yahoo! to the concept hierarchy of LYCOS, and\Lycos to Yahoo" denotes vice versa.

5.

DISCUSSION

More than 80% of the URLs we used in our experiments
were categorized appropriately by our system. The data in
Figure 2 imply that Yahoo-to-Lycos aligning was more accurate than the inverse operation. As implied by the total
number of categories, the categorical hierarchy in Yahoo!
is more complex than that of LYCOS. Thus, for Yahoo-Figure 2: Result of Experiment

to-Lycos aligning, the learned rules are likely to involve
transfer of URLs from relatively complex categories to relatively general categories. Such a trend is likely to result
in relatively accurate rules. For example, suppose concept hierarchy A contains category S under category X ,and concept hierarchy B also has category X but does nothave sub-categories under X . In such a case, it would bemuch easier to learn a rule for "A:/X/S -> B:/X" than tolearn a rule for "B:/X -> A:/X/S", because "B:/X" contains URLs that belong in S and URLs that do not. The
data shown in Figure 2 re ect this. In the above situation,nevertheless, our method works properly. When regarding
parent categories as right answers (\Criterion 2'), both directions are almost the same results, i.e., "B:/X -> A:/X"is learned instead of "B:/X -> A:/X/S".
The bookmark-sharing systems of Siteseer [5] and Blink [1]are similar to our system. The main di erence between oursystem and theirs is the use of hierarchy in categorization.
Their systems only consider the number of URLs in a given
category, but our method uses hierarchy structures. Oneof the merits of this approach is that, if there is no exact category into which a given URL ts, then the URL
is aligned into the parent category. Bookmark-Agent [4]uses another approach to sharing bookmarks, based on
keywords. Unlike a bookmark agent, our system only uses
link information, not the contents of the page. Our system
would therefore categorize "Sherlock Holmes" and "ConanDoyle" under the same concept, although they contain different words.

6. CONCLUSION

In this paper, we propose aligning internet directories asa new approach to integrate multiple directories and its
method based on statistical method. To test our ideas, we
conducted experiments using Yahoo! and LYCOS. Our experimental results show that the alignment rules learned
by our system are reliable so that URLs in a directory
can be located to the appropriate positions in the otherdirectory. The advantage of using our method is that it
can extend directories automatically with information inother directories. For example, a user can expand her/hisfavorite directory as she/he likes by introducing information in other directories.

7. REFERENCES[1] Blink, 2000. http://www.blink.com/.
[2] J. L. Fleiss, Statistical Methods for Rates andProportions, John Wiley & Sons, 1973.
[3] LYCOS JAPAN, 2000. http://www.lycos.co.jp/.
[4] M. Mori and S. Yamada, Bookmark-Agent:
Information Sharing of URLs, Poster Proc. of the
8th Int. WWW Conf, 1999.
[5] J. Rucker and M. J. Polanco, Siteseer: PersonalizedNavigation for the Web, Comm. of the ACM, pp.
73-75, vol. 40, No. 3, 1997.
[6] Yahoo! JAPAN, 2000. http://www.yahoo.co.jp/.