Hierarchical Organization of Web Documents
based on Hypertext Classification

Yusuke Suzuki, Shigeki Matsubara
and Masatoshi Yoshikawa
Nagoya University, JapanIntroduction（1/2）
z Many sites containing common information{ Academic societies, Universities, Internet service providers …

z When users want to browse particular pages on severalsites{ deadlines for paper submissions to academic conferences{ service contents provided by ISPs

they have to bother to seek the target
pages from each siteSocietyIEEE

ACL

ACM
Publication

Need for Web directories toorganize pages found in severalsites based on contentsConferenceSubmission

IEEEACM

ACL

Program

IEEEACMIntroduction（2/2）
z Present state of Web directories{Manual design and management
Costly processes
zDesign of directory structures for each category
zCategorization of pages into directories
zResponse to frequent page updatesz As the size of a directory or data increases,
the cost of manually designing and managing theWeb directory grows

Purpose
Proposal of a technique for automaticallyconstructing hierarchical Web directories{ Putting pages with same contents from several sites intoa directory and providing hierarchical Web directories
SocietyPublicationSocietySociety

Conference

Program
Conference

Publication

Conference

Society
Submission
Publication
Conference

Program
Submission

deadline

Submission

ProgramBasic Ideas（1/3）
To construct hierarchical Web directories{ Find super-sub relations between directories{ Categorize Web pages into directories

Society

Publication

Conference

Conference

Submission
Submission

ProgramBasic Ideas（1/3）
To construct hierarchical Web directories{ Find super-sub relations between directories{ Categorize Web pages into directoriesz A feature of the Web{ A relation between Web pages is represented by a hyperlink
Extract pages with a super-sub relation as a page-pair based on thehyperlinks and replace its relation with a relation between directories
Conference

Conference

Submission

Submission

Conference

Conference

＊＊＊

＊＊＊

Submission

Submission

Basic Ideas（2/3）
z Representation of pages of a super-sub relation{Anchor text
zSet by creator in order to navigate users to a linkedpage
A description representing in brief the whole contents of
the linked page
Super-pageConference

We represent each page ofthe super-sub relation using
the anchor texts

Conference
Conference

Submission

Paper Submission
Submission

Sub-pageBasic Ideas（3/3）
zConstructing the directory structures
1.
2.
3.

Extract the super-sub relation between the Web pages fromeach site
Cluster the common super-sub relations and replacing theirrelation with a super-sub relation between the directories
Construct a Web directory by iterating the integration of thedirectories
ACL

the super-pages
SocietyConference

IEEESociety

Conference

Integration
Integration

Conference

Conference Conference
Publication
Conference ConferenceConference

ACM

Submission

Submission

Submission
Submission
Submission

the sub-pages

１.

2.

3.

Program
ProgramProcess of the Proposed Method
Several sites（１） Extracting super-sub relations（２） Clustering super-sub relations（３） Constructing directory structures（４） Deciding directory names

Hierarchical Web directory

Process of the Proposed Method
Several sites（１） Extracting super-sub relations（２） Clustering super-sub relations（３） Constructing directory structures（４） Deciding directory names

Hierarchical Web directory

Process of the Proposed Method
Several sites（１） Extracting super-sub relations（２） Clustering super-sub relations
44（３） Constructing directory structures＊＊1＊1＊＊＊4

411 ＊＊＊ 11＊＊＊（４） Deciding directory names＊＊＊＊＊＊Hierarchical Web directory

＊＊＊

＊
2＊＊

2＊
3＊＊

3＊＊＊

＊＊＊

＊＊＊

Process of the Proposed Method
Several sites（１） Extracting super-sub relations（２） Clustering super-sub relations（３） Constructing directory structures（４） Deciding directory names

Hierarchical Web directory

Extracting Super-sub Relations （1/4）
z Necessary to identify the links connecting
a super-page and a sub-page{ Not all Web pages connected by hyperlinks necessarily havea super-sub relationz Website creators organize pages into folders and locate
them on the serverPublication
SocietydeadlineMember
Conference

Program
Submission

To identify a super-subrelation,
we utilize the creators’knowledge

Extracting Super-sub Relations （2/4）
z Identification of the links connecting a super-page and asub-page{ We investigated the relevance between a page’s location ona server and the links

Investigation method

Ancestral folders

1. Extract 200 links from each of four sites
2. Judge whether the linking page and thelinked page have a super-sub relation
3. Classify the links into six relative locations
and investigate the rate of a super-sub
relation in each relative location

Linking
page

Super folders
Same folder
Middle folders

Sub folders

Descendant folders

Extracting Super-sub Relations （3/4）
z Result of the investigation
Location of linked
pages

Link

Rate of Supersub relation （%）

Descendant folder

136

91.9

Ancestral folder

151

0.7

Same folder

246

58.1

Sub folder

30

Super folder

77

2.6

Middle folder

152

2.7

The case that the linking page is“index.html”

41

Ancestral folders
Linking
page

Super folders
Same folder

85.3%
Middle folders

Sub folders

Descendant folders

Extracting Super-sub Relations （4/4）
Decision rule for a super-sub relation
1. Link to the page on the same server
2. Link to the page in the descendant folders or the same folder
3. In the case of the same folder, the linking page is “index.html”(Without “index.html,” the linking page is a page which links to the most pages in the same folder）

file1.html

12
file2.html

5
file5.html

3Super-pages

/AA
4

1

3

3

2

3

2

4

5

/AA/BBindex.html file4.html/AA/BB/CC

Server １

Sub-pages

Process of the Proposed Method
Several sites（１） Extracting super-sub relations（２） Clustering super-sub relations（３） Constructing directory structures（４） Deciding directory names

Hierarchical Web directory

Clustering Super-sub Relations （1/3）
z The common super-sub relations are clustered{ Common super-sub relation
The super-sub relation where both the contents of the super-pages andthe contents of the sub-pages are similar{ In the clustering result, if the number of members in a cluster isbelow a threshold value, that cluster is excluded

Conference

Conference

Conference

Conference

Submission

Submission

Submission

similarSubmission

Clustering Super-sub Relations （2/3）
z The similarity between Web pages{ The maximal Dice coefficient value between the anchor texts
linking to each page is adopted as the similarity between the pages

sim(d i , d j ) = max (1≤ s ≤ m ,1≤ t ≤ n

2 M i s jt
M i s + M jt)

M is ： number of nouns in the anchor text a i (1 ≤ s ≤ m ) which links to the page d iMis jt ： the number of nouns common to anchor text a i (1 ≤ s ≤ m ) and a j (1 ≤ t ≤ n )sstPaper submissionOnline submission

Submissions

Paper submission
Max of dice coefficient=
The similarity between the pages

Clustering Super-sub Relations （3/3）
zClustering method (hierarchical method){

Integrating clusters
1.
2.

{

Both the similarity between the super-pages and between thesub-pages exceeds the threshold value
The average of their similarities is maximal

The similarity between the clusterszComplete linkage method
sim(disup, d jsup )The similarity between the super-sub relations

sim( pi , p j ) ＝( sim(d isup , d jsup ) ，sim(d iinf , d jinf ) )sim(diinf , d jinf )Process of the Proposed Method
Several sites（１） Extracting super-sub relations（２） Clustering super-sub relations（３） Constructing directory structures（４） Deciding directory names

Hierarchical Web directoryConstructing Hierarchical Structures （1/3）
1.

Clustered super-sub
relations are replaced by thesuper-sub directory structure

Conference
Conference

Submission
Submission

2.

Construct the directory structures by iterating theintegration of each directory{{

Integration of super-directories
Integration of a super-directory and a sub-directoryConstructing Hierarchical Structures （2/3）
z Representation of a directory{Each directory is represented as a feature vector
rxi = ( wi1 , wi 2 , K , wiN )wij = Fij

F ij ： the frequency of a noun e j in a set A i of the anchor

Submission
Paper
Submission

texts which links to the pages in a directoryz The similarity between directories{Cosign of the feature vectors
r r
xi • x j
Sim( Di , D j ) = r r
xi x j(i ≠ j )Sim( Di , D j )Constructing Hierarchical Structures （3/3）
z Integration of the directories{Integrate the directories to satisfy the nature of a tree
structure in descending order of similarity
z When the maximal similarity is less than a threshold value,
clustering is stopped＝

Process of the Proposed Method
Several sites（１） Extracting super-sub relations（２） Clustering super-sub relations（３） Constructing directory structures（４） Deciding directory names

Hierarchical Web directory

Deciding Directory Names (1/2)
z Each directory name is decided based on a set anchor
texts linking to the pages in the directory
Decision Policy
A directory name is a phrase• which appears more commonly• which has a certain length

Anchor1
Directory Name

Anchor2
Anchor3

Deciding Directory Names (2/2)
zDecision method
Extracting any morphological sequence sij from a set of anchor
texts in each directory
2. For each sij, calculate the inclusion rate for each anchor text
3. Make sij whose average value is maximal the directory name1.

Paper submission

any morphologicalsequences

Paper submission
Online submission

Cover ( sij , aik ) =Directory Name
「Paper submission」| a i | : number of morphemes in the anchor text

The inclusion rateF｛ paper，online，submission，paper submission，online submission ｝

ki
jkaik

a ik

in a directory D i

F jki : number of common morphemes in sij and（※ iff aik is included sij ．Otherwise 0）aik

Process of the Proposed Method
Several sites（１） Extracting super-sub relations（２） Clustering super-sub relations（３） Constructing directory structures＊＊＊（４） Deciding directory names

Hierarchical Web directory

＊＊＊

＊＊＊

＊＊＊

＊＊＊

＊＊＊

Experimentsz Experimental data
{Sites of graduate schools at Nagoya University
ID

SitePages

Links in same server

ⅠEngineering (www.engg.nagoya-u.ac.jp)

126

276

Ⅱ

Environmental Studies (www.env.nagoya-u.ac.jp)

281

1,192

ⅢInformation Science (www.is.nagoya-u.ac.jp)

106

267

ⅣScience (www.sci.nagoya-u.ac.jp)

280

887

Ⅴ

Economics (www.soec.nagoya-u.ac.jp)

605

3,288

z Parameter settings{Threshold values
z Similarity in the clusteringz Similarity in the construction of directory structurez Minimum number of members in a cluster

0.50.62

Experimental Resultsz Sample output of the system
A list of the root
directory of thegenerated directory
structures…13 directory structures
An overview of thedirectory structure

A collection of links
to the pages in thedirectory
http://plum.itc.nagoya-u.ac.jp/auto_directory/demo/Experimental Resultsz The directory structure : sample 1
入学案内／Admission information （1）
博士課程（後期課程）／Doctoral Course （6）採点評価・合否判定基準／
Criteria for rating and admission decision （2）入学科及び授業料／
Entrance fees and tuition （4）The accuracy ofdirectory categorization
14 / 26
Site ID

環境学専攻／
Department of Environment （2）Breakdownof pages

Ⅰ5

ホームページ／Home page （1）Ⅱ102月21日（月）／Monday 21st February （8）

Ⅲ0Ⅳ

11Ⅴ0

第3年次学士入学／Admission to 3rd bachelor （2）Experimental Resultsz The directory structure : sample 2
入試情報／Information on entrance exams （3）
博士課程／Doctoral course （14）
経済学修士号への道／Road to Master of Economy （2）
募集要項の請求方法／Charging
method of admission guideline （2）
都市環境学専攻／Departmentof Urban Environment （2）The accuracy ofdirectory categorization
21 / 23
Site ID

Breakdownof pages

Ⅰ3Ⅱ6Ⅲ0Ⅳ0Ⅴ14Experimental Resultsz Failure pattern (1){ Though the contents of the pages in two directories are different,
their directories were integrated
z because of the similarity of anchor texts between the integrated
directories

Considering also the relation between another directories
DoctoralCourse

受験案内／admission information
博士課程／Doctoral Course

Department ofEnvironment

募集要項／admission guideline

Admissionguideline

Department ofEnvironment

Index

環境学専攻／
Department of Environmentキャンパスガイド／campus guide
講座／research departments

campusguideExperimental Resultsz Failure pattern (2){The pages of a common super-sub relation were notclustered into the same categoryz because of the mismatch between words in the anchor texts

Using also information other than anchor texts
Admission Information

Guidelines for admission

×Entrance Exam

Guidelines for admission

Conclusion and Future Workz Conclusion{We have proposed a method for constructing ahierarchical Web directory from several sites{We experimentally confirmed the feasibility of ourmethodz Future Work{To represent a super-sub relation by using information
other than anchor texts{To examine the practicality of our method by increasingthe amount of the dataz Apply our method to sites of other categories

Thank you.

z出力結果（Japanese）{ http://plum.itc.nagoya-u.ac.jp/auto_directory/main.html

Experimental Resultsz The directory structure : sample 1
入学案内／Admission information （1）
博士課程（後期課程）／Doctoral Course （6）A set of the anchor texts of“博士課程（後期課程）”• 博士課程（後期課程）補欠募集/ Doctoral course (to fill vacancies)

採点評価・合否判定基準／• 博士課程（後期課程）募集要項
Criteria for rating and admission decision（2）
入学科及び授業料／
Entrance fees and tuition （4）/ Guidelines for admission to Doctoral course• 博士課程（後期課程）/ Doctoral course

環境学専攻／
Department of Environment （2） • 博士課程（後期課程）/ Doctoral course

ホームページ／Home page （1）2月21日（月）／Monday 21st February （8）• 博士課程（前期課程）募集要項/ Guidelines for admission to Master’s course• 博士課程（前期課程）/ Master’s course

Related Worksz Generation of Web directory{ [Sato et al. 1999]
z Gather the links to the sites in a category

The generation of the hierarchical structure is not based on contentsz Grouping of Web pages{ [Harada et al. 1999]
z Group the folders in which Web pages are contained{ [Kozima et al. 2002]z Extract the strongly connected components as the group by regarding
the Web as a directed graphz Group the pages in the site hierarchically

The grouping of the pages across the site is not targeted