HyPursuit: A Hierarchical Network Search Engine that Exploits Content-Link Hypertext Clustering

Ron Weiss, Bienvenido Vélez, Mark A. Sheldon, Chanathip Namprempre, Peter Szilagyi, Andrzej Duda, and David K. Gifford

ACM Hypertext ’96 · DOI: 10.1145/234828.234846

HyPursuit: A Hierarchical Network Search Engine that Exploits Content-Link Hypertext Clustering

Ron Weiss, Bienvenido V61e.z, Mark A. Sheldon Chanathip Namprempre, Peter Szilagyi, Andrzej Duda, David K. Gi#ord Programming Systems Research Group MIT Laboratory for Computer Science 545 Technology Square, Cambridge, MA 02139 USA Tel: 1-617-253-6264 E-mail: rweiss@lcs.mit.edu

ABSTRACT HyPursuit is a new hierarchical network search engine that clusters hypertext documents to structure a given information space for browsing and search act ivities. Our content-link clustering algorithm is based on the semantic information embedded in hyperlink structures and document contents. HyPursuit admits multiple, coexisting cluster hierarchies based on different prin- ciples for grouping documents, such as the Library of Congress catalog scheme and automatically created hy- pertext clusters.

HyPursuit’s abstraction functions summarize cluster con- tents to support scalable query processing. The abstrac- tion functions satisfy system resource limitations with controlled information 10SS. The result of query pro- cessing operations on a cluster summary approximates the result of performing the operations on the entire in- formation space. We constructed a prototype system comprising 100 leaf World- Wide Web sites and a hier- archy of 42 servers that route queries to the leaf sites. Experience with our system suggests that abstraction functions based on hypertext clustering can be used to construct meaningful and scalable cluster hierarchies. We are also encouraged by preliminary results on clus- tering based on both document contents and hyperlink structures.

KEYWORDS: Network Resource Discovery, Hypertext Clustering, Hyperlink Structures.

INTRODUCTION

The World- Wide- Web’s vast collection of servers can be viewed as a distributed hypertext database containing a wealth of information. Searching this information space

Permission to make digital/hard copies of all or part of this materiaI for personal or classroom use is granted without fee provided that the copies am not made or distributed for profit or commercial advantage., rhe copy- right notice, the title of the publication and its date appear, and notice is given that copyright is by permission of the ACM, Inc. To copy otherwise, to republish, to peat on servers or to redistribute to Iista, requires specific permission andlor fee. Hypertext ’96, Washington DC USA @1996 ACM o-s9791-778-2196103 ..$3.50

is a difficult problem due to the size and diversity of the data it contains. The general search problem spans a spectrum of activities ranging from a well-defined search for a specific document to a non-specific desire to un- derstand what information is available. To support all these activities, a system must impose some semantic organization on the information space. To organize the information space well, the system must use all avail- able knowledge about the data. In a hypertext environ- ment, this includes both document content and hyper- link structures.

The HyPursuit prototype is a scalable system that uses

content-hnk hypertext clustering, based on document contents and link information, to structure the infor- mation space and to support the entire range of search activities. Content-link clustering automatically com- putes sets of related documents called clusters. HyPur- suit admits multiple, coexisting cluster hierarchies based on different principles for grouping documents, such as the Library of Congress catalog scheme and institutional structures. These hierarchies may be constructed auto- matically or manually.

Clusters are important for two reasons:

G Clusters can be used to group hypertext nodes into more complete documents that can be searched or com- bined into larger clusters. In hypertext environments, hypertext nodes are generally not independent docu- ments. This is especially true on the Web where au- thors create many small pages, rather than single mono- lithic documents. Authors are motivated to create small pages to keep retrieval latencies low. This also permits retrieval of only relevant information.

G Clusters organize an information space for the user and the system by grouping related subspaces together. Subspaces may be clusters of documents or clusters of clusters. The partitioning of the information space pro- vides convenient abstraction barriers for both the user and the system. The cluster abstraction allows a large information space to be treated as a unit, without re- gard for the details of its contents. A user exploring the portion of the information space relating to biology may

180

Living Documents

paper 1

paper2

ResourceDiscovery

paper3

paper4

,–––– ~-(--- ------; 4

papar1

...

,-, =---- w -,)

II I L–––j

I Iii L–––d I II Living Documents II II

I–: L–

Figurel: Content-Link HypertextClustering Example

want toidentify all clusters (not all documents) that are and the number of the nodes across the papers varies / related to DNA computation. Thus, the user may in- teract with the system at a level of granularity that is appropriate to the specificity of the information need and the complexity of the information space. Clusters also provide convenient units for the partitioning of work and resource allocation among the distributed compo- nents of the system, For example, a separate informa- tion server on a separate host may represent each indi- vidual cluster, performing operations on its local data.

HyPursuit is the first system known to the authors that combines information about document contents and hy- perlink structures to cluster documents. Most previ- ous approaches to hypertext clustering have focused on using link structures alone to group nodes. Most tra- ditional information retrieval clustering techniques fo- cus on the text of the individual documents. Because hyperlinks and document contents provide valuable se- mantic information, we hypothesize that incorporating both will improve document clustering. The strength of the relationship between documents in HyPursuit is proportional to the number of terms, ancestors, and de- scendants in common, as well as the number of direct links between the documents.

Figure 1 provides an example of a possible hypertext organization of conference proceedings stored on a web site. The site includes a Table of Contents page that points to the cover page of every paper in the confer- ence proceedings. Each paper is organized according to some general guidelines, but the exact configuration

I TabkofContents I

.. I I

LJ LJl I LJ L––––––J

Reaouree Oiacovary II II Application

II ——————————————————— I l––––––––––––––––..–

depending on the number of sections, n~m-ber of fig- ures and number of authors. One clustering approach would be to first group together all nodes that com- prise individual papers. The clustering algorithm can rely solely on the link information to reconstruct the papers. However, any further clustering that attempts to cluster the papers into related groups, such as the ses- sions in which the papers were presented, must exploit the content information in the nodes because the graph structure alone does not reveal the grouping implied by the sessions. The links to the papers from the Table of Contents were placed in separate lists to reflect the ses- sion structure. Therefore, the clustering algorithm could have grouped together papers that were in the same list in the HTML document. However, in general, the clus- tering algorithm must rely on term similarities between the clusters in order to perform better clustering.

To support scalable query processing, HyPursuit uses manageable summaries of cluster contents, called con- tent labels, to approximate complete knowledge of the information space. A manageable summary refers to a data structure that satisfies the given resources limita- tions. HyPursuit’s abstraction functions compute the content labels, which are then transmitted up the clus- ter hierarchy as input for the abstraction functions of higher-level clusters. An abstraction function summa- rizes the contents of a cluster in support of system op- erations while controlling information loss to satisfy the resource limitations of a particular information server.

Figure 2: Content Routers Organization

For example, one abstraction function in the HyPursuit prototype ranks terms from a cluster’s index structures and extracts highly ranked terms to identify appropriate clusters for particular queries. In the event that storage is limited, lower ranked terms may be dropped from a summary. The result of performing an operation on a content label approximates the result of performing the operation on the entire information space described by the content label.

HyPursuit uses content-link clustering to provide cluster- based information browsing, scalable query refinement, result set expansion, query routing and result set cluster-

ing. The HyPursuit interface allows users to browse the information space by traversing the cluster hierarchy, and retrieving documents as well as content labels. Hy- Pursuit provides query refinement by dynamically com- puting and suggesting recall- and precision-enhancing terms for a given user query to help guide the user in further query formulation. To improve recall, HyPur- suit expands a query result set with additional relevant documents that do not match the query but which are clustered with the query-selected documents. To sup- port a variety of query processing operations, HyPursuit uses query routing to identify relevant clusters, forward queries to the information servers for those clusters, and merge the results.

We have built an experimental HyPursuit prototype com- prising 100 Web sites organized in a four-level hierarchy of 42 content routers. The hierarchy, shown in Figure 2, is constructed to reflect the structure of the domain name system (DNS) [17]. Experience with this config- uration suggests that hierarchical clustering provides a

valuable discovery service to end users, and our data

supports the ability of the system to scale with modest

increases in content label sizes.

In the remainder of this paper, we review related work, describe the design of HyPursuit, introduce content-link hypertext clustering, discuss our experimental system, provide experience and performance statistics, and offer

our conclusions and directions for future work.

RELATED WORK Related work can be classified into the following cate- gories: hierarchical network search engines, centrahzed

network search engznes, subject-based du-ectories, query

refinement and hypertext clustering.

Hierarchical network search engines address issues of scalability in terms of storage requirements and net- work communication for the task of resource discovery. The three examples of hierarchical search engines that are known to the authors include Harvest [4], GLOSS [14] and our work on content routing [8, 22, 21]. These systems reduce storage requirements at any of the dis- tributed components by generating succinct descriptions

(content iabeis) oi the contents of leaf servers. The succinct descriptions allow the resource discovery sys- tems to selectively access manageable sets of informa- tion providers that are believed to contain information relevant to the user’s needs. None of these syst ems ex- ploit hypertext clustering to provide additional infor- mation retrieval services similar to the ones HyPursuit provides.

Discover [21] implements query refinement using a re- finement database that consists of WAIS document head- lines. Discover suggests additional refinement terms for a given query based on term collocation in the docu- ment headlines. This requires every content router to keep term collocation information on a per document basis. HyPursuit supports query refinement based on term collocation on a per cluster basis. In addition, Hy- Pursuit scans entire documents for term information.

GLOSS [14] uses a probabilistic scheme to predict the size of query result sets for each subsidiary server and forwards queries to those servers likely to have matching documents. The prediction is based on a histogram of the occurrences of words within a server, GLOSS’s esti- mates are not accurate because they rely on the assump- tion that terms appear independently of other terms in documents. GLOSS offers several alternatives for us-

182

ing the histogram data, but it does not support query refinement.

Centralized Network search engines such as the Web Crawler [18], WWW Worm, ALIWEB [16], and the RBSE Spider [9], gather information about resources on the web for query-based access. However, these sys- tems are not scalable because they use a global index- ing strategy, Z.e., they attempt to build one database that indexes everything. They do not provide any or- ganization of the search space, and they do not give the user any guidance in query formulation. These sys- tems overburden network resources by transmitting en- tire documents, rather than the index data, or better still, content labels. Furthermore, a H yPursuit system allows greater autonomy to each information provider and content router to tailor its indexing mechanisms and facilities using local knowledge. Veronica [15] is a discovery system that maintains an index of document titles from Gopher [1] menus, and it suffers from the same limitations as the Web search systems. HyPur- suit provides a coherent framework for the integration of diverse centralized search engines.

Subject-based directories of information, e.g., Planet Earthl , Yahoo2 and the NCSA Mets-Index3 , provide a useful browsable organization of information. These would be useful paradigms for organizing particular hi- erarchies in a HyPursuit System. As the information content grows, it becomes cumbersome to browse them and discover relevant information in these systems with- out query routing and refinement. At present, these systems are rather ad hoc and static, requiring manual update and maintenance. Yahoo [10] classifies docu- ments manually and supports content-based access to the collection of documents gathered from either users’ submissions or web robots.

Document ctustermg has been previously studied as a mechanism to improve both searching and browsing. Salton [19] presents a summary of recent document clus- tering techniques that are used to improve collection

searching. Scatter/gather [7] dynamically clusters col- lections of documents for browsing large information space It presents summaries of clusters to the user, who can then select a subset of these clusters for further reclus- tering. The selected clusters are scattered into the orig- inal documents and re-clustered. The new clusters re- veal their contents in more detail, since the total num- ber of re-clustered documents is reduced. Unlike scat- ter/gatherl H yPursuit defines a framework for informa- tion ret rieval services, such as query routing and refine- ment, in a hierarchy of servers.

Botafogo [2] proposes a hyperlink-based document chJs-

tering algorithm based on k-edge-components to gener- ate clusters of hypertext documents. The similarity be- tween hypertext nodes is proportional to the number of

lhttp://white .nosc. mil/infO. html

2http ; //www . yakm . Com

3http://wvv .ncsa. uiuc. edu/SDG/Software/Mosaic/ lfetaIndex. html

183

independent paths between them. Botafogo et al. [3] use biconnected components and strongly connected com- ponents for hypertext clustering. First, the hypertext is converted into an undirected graph by adding links. Then, edges adjacent to so called reference and index nodes are removed. The algorithm then finds bicon- nected subgraphs and the entire process is recursively applied to each resulting subgraph until no more bicon- nected components can be isolated. Each final bicon- nected component becomes a cluster. Neither approach uses term information or implements any information retrieval service exploiting hypertext clustering.

[12] combines terms and hyperlinks to rank nodes that match a query in a hypertext document. In contrast, HyPursuit uses terms and hyperlinks to cluster large collections of hypertext documents. The strategy pro- posed by [12] represents a promising paradigm for rank- ing query results that may be incorporated in future implementations of H yPursuit. However, the algorithms require modification to handle arbitrary hyperlink struc- tures such as cyclic graphs. Also, the algorithm may not be suited to process queries in very large, distributed col- lections because it requires the dynamic propagation of weights for every node in the hierarchy on every query.

DESIGN OF HYPURSUIT

HyPursuit is a new content routing system prototype that takes advantage of content-link hypertext cluster- ing to provide cluster-based information browsing, scal- able query refinement, result set expansion, as well as query routing. This section discusses the hierarchical or- ganization of a HyPursuit system and explains how the content routing system architecture provides a frame- work for multiple coexisting cluster hierarchies in a dis- tributed network resource discovery environment. Then, it describes the abstraction of information spaces into manageable data sets in order to provide scalable ser- vices. Finally, the section describes the services sup- ported by HyPursuit together with their corresponding user interfaces.

,5. Hierarchical Organization of a HyPursuit System

HyPursuit’s architecture admits multiple, distributed, coexisting cluster hierarchies in a network resource dis- covery environment. Individual cluster hierarchies are useful for browsing and searching large document col- lections [5, 7] because they organize the information space. Because no single organization can meet all user needs, HyPursuit supports arbitrary cluster topologies, including multitrees[13]. Users browse through a hierar- chy and perform searches that exploit its organizational structure. Each hierarchy corresponds to a method of grouping related documents into clusters. Leaf nodes within the hierarchy are single documents, and interior nodes correspond to clusters of documents and clusters of clusters. The clustering method depends on the con- text and the motivation for the organization of hier- archy. For example, an article by author Smith about video databases can be grouped with articles about video databases, or with articles that Smith authored. The

- =Cmm muter m

. Led information server /’ \

~ .Dw

Figure 3: Content Routing as Cluster Hierarchies

same condition exists in higher levels of the cluster hi- erarchy. For example, documents can be clustered based on institutional boundaries or based on Library of Congress cat alog subjects.

As shown in Figure 3, HyPursuit organizes the informa- tion space into a cluster-based hierarchy. Leaf nodes are the documents of the information space, and access to leaf nodes is via leaf information servers. Internal nodes cent ain clusters of related documents (and other clus- ters), and access to internal nodes is provided by con- tent routers. Content routers support a number of in- formation retrieval services including query forwarding to relevant information providers, query refinement, re- sult set expansion, browsing of content label summaries and clustering of result sets. Content routers can in- dex and return pointers to leaf documents that reside on leaf information servers such as WAIS, Gopher and World-Wide Web sites.

In a hierarchical network search engine, it is more effi- cient to store a document and its associated index struc- tures in close physical proximity. Therefore, content routers that index leaf documents should be close to, if not on, the same host computer as the documents. This will ensure that the indexing process consumes less net- work bandwidth. In addition, if abstraction functions (see below) produce summaries that approximate the contents of the information space, then minor modifica- tions to the contents do not necessarily result in changes to content labels. Thus reindexing operations remain lo- cal until changes are significant.

Abstraction Functions Summarize Information Spaces

To support operations like query processing in a scalable way, HyPursuit uses manageable summaries of cluster contents, called content labels, to approximate complete knowledge of the information space. HyPursuit’s ab-

straction functions compute these content labels, which are then transmitted up the hierarchy as input for the

content

label

Figure 4: Abstraction Functions

that contain abstraction functions of content routers higher-level clusters. An abstraction function summa- rizes the contents of a content router’s cluster in support of a system operation while controlling information loss to satisfy the resource limitations of a particular infor- mation server. The result of performing an operation on a content label approximates the result of performing the operation on the entire information space described by the content label.

Each service provided by a router may require a different view of the information space cent ained by the router. For example, query refinement may use probabilities of term collocation in documents, whereas query routing may require information about whether documents that satisfy a particular query exist. Different services may also use the same abstract ion function.

Each content router uses its abstraction functions to compute a content label that summarizes its associated cluster. Figure 4 illustrates how information flows up the hierarchy as content labels consisting of informa- t ion generated by the abstraction functions. A content router uses the content labels of its children to sup- port the information retrieval services it offers. When a child of a content router is a document, then the con- tent label for that document is computed from the doc- ument’s contents (including outgoing links). To con- struct its own content label, a content router applies its abstraction functions to the content labels generated by its children rather than to the entire information space. This eliminates the need to transmit very large data sets to higher level content routers. In addition, a content

184

router can compute and transmit a different content la- bel to each of its parents, based on the requirements of that parent.

The following paragraphs describe the three abstrac- tions functions used in the HyPursuit prototype:

G HyPursuit’s abstraction function for query refinement computes a data structure that enables the system to as- sist users in formulating queries. This abstraction func- tion summarizes the content router’s cluster as a set of sub-clusters. The result ing data structures consists of a manageable set of sub-clusters that represent group- ings of related documents in the information space that is reachable from a content router. The sub-clusters do not necessarily correspond to the organizational struc- ture of the content routers, The information stored for each sub-cluster is the set of the most heavily weighted terms from documents in that sub-cluster. The abstrac- tion function drops the least weighted terms in order to satisfy given resource limit ations. The abstraction func- tion computes a set of sub-clusters by starting off with the set of sub-clusters received from the children routers, and reclustering until it reaches a specified resource bud- get. See below for a discussion of how this sub-cluster information is used to compute terms suggestions for query refinement. Both the result set expansion and the result set clustering services also rely on the output of the query refinement abstraction function.

G The abstraction function for query routing, on the other hand, computes a manageable set of terms that are used for identifying portions of the information space relevant to particular queries. The abstraction function uses term and term frequency information in the chil- dren’s content labels to compute term weights. The ab- straction function then selects the most heavily weighted terms for generating the content router’s content label. The abstraction function may also choose to add addi- tional terms that characterize the information space but were not among the terms transmitted up the hierarchy. For example, the abstraction function could add a term describing a poetry cluster as literature even though none of the poems mention literature explicitly.

G The abstraction function for browsing content labels

computes a summary of the information space suitable

for human comprehension. This includes extracting in-

formation from the query routing summary such as the

number of documents, the total size in bytes, a small

set of the most heavily weighted terms and links to a

sample of documents in the cluster. In addition, the ab- straction function similarly summarizes each sub-cluster computed for query refinement.

)

Figure 5 is an excerpt from an actual content label HyPursuit automatically generated from a collection of documents on a Web site. The content label in the fig- ure shows three sub-clusters that are used for computing query refinement suggestions. The sub-cluster summary always includes precise information about the number of documents it contains, the total size in bytes, and the

185

version: 1 )

url: “ http://www.psrg... /cgi-bin/crs/www-eecs. mit.edu'' )

(cluster

((cluster-num: 1) (s]ze: 6763) (num-dots 5) (num-terms: 458) (url: “ http://www-eecs /committees. html” )

(url “ http.//wweecsc,. hq/mdexdhtml”ml” )

(url: “ http://www-eecs... /sthtml”tml” )

(url. “ http.//wweecs,s stuorguhtml”tml” )

(url. “ http//www-eecs... /test”pictures html” )

(term: ((attr]b”te: header) (value admmwtrative) (tf 1) (df l)))

(term: ((attribute. header) (value committees) (tf 2) (df l)))

(term: ((attribute: header) (value: computer) (tf 5) (df 5)))

(term: ((attribute: header) (value: eecs) (tf 5) (df 5))) (term ((attribute: header) (value: department) (tf 11) (df 5)))

,..

(term: ((value: committee) (tf 13) (df l)))

(term: ((value: eecs) (tf 27) (df 5))) (term: ((value: officer) (tf 4) (df. l))) (term ((value: organizations) (tf 2) (df l)))

(term: ((value: personal) (tf 3) (df 1))) ))

(cluster:

((cluster-num: 2) (size: 17235) (num-dots: 8) (num-terms: 1030)

(url: “ http://www-eecs... /AY94-95/mnouncements/index.html'' )

(url: “ http://www-eecs... /A965-96/announcemelts/l .html” )

(url “ http://www-eecs ./AY95-96/announcements/2.html” )

[m-l: “ http://www-eecs. /AY95-96/announcements/3 .html” )

(url. “ http.//wweecscs /AY95-96/announcements/index.html” )

(url: “ http //www-eecs.. /current/announcements/kdex.html” ) ~erm ((attribute: header) (value: ay95) (tf:

(df

l))) (term ((attribute header) (value: computer) (tf

(df

8))) (term. ((attribute: header) (value: current) (tf

(df

l))) (term ((attribute header) (value: department) (tf

(df

8)))

(term: ((value: announcements) (tf 22) (df 8)))

(term ((value: department) (tf 32) (df 8)))

(term: ((value eecs) (tf 38) (df. 8)))

(term. ((attribute title) (value: announcements) (tf 8) (df 8)))

(term: ((attribute: title) (value: eecs) (tf 8) (df 8)))

))

(cluster

((cluster-num. 3) (size. 6766) (num-dots 3) (num-terms: 1105)

(url: “ http://www-eecs .../clmaterialsihtml”tml” ) (m-l. “ http://www-eecs /comment- form. html” )

(url: “ http://www-eecs ..webepagesehtml”l” )

(term ((attribute: header) (value: comment) (tf 1) (df l)))

(term ((attribute: header) (value: course) (tf. 1) (df. l)))

(term: ((attribute: header) (value: czars) (tf 1) (df l))) (term ((attnb”te: keyword) (value: mail) (tf 1) (df l)))

(term: ((attribute: keyword) (value: name) (tf 1) (df l)))

(term: ((attribute: title) (value form) (tf 1) (df l)))

(term: ((attribute. title) (value: home) (tf 1) (df l)))

(term ((attribute title) (value pages) (tf 3) (df 3)))

))

,..

Figure 5: Sample Clustered Content Label

Figure 6: Query Refinement Suggestions

total number of terms in the sub-cluster. It also in-

cludes URLS of documents in the sub-clusters and the

terms they cent ain. For each unique term, the content

label stores the term frequency (tf) and document fre-

quency (df ). The query refinement abstraction function may decide to store only a subset of the URLS and terms

depending on available resources.

Information Retrieval Services

HyPursuit provides a set of information retrieval ser-

vices including query routing, query refinement, result

set expansion, cluster-based browsing, and result set

clustering. The user explicitly invokes all but the latter

service via user interface operations. HyPursuit auto-

matically clusters result sets before they are shown to the user. This section describes H yPursuit’s informa-

tion retrieval services as well as how the HyPursuit user

interface provides a coherent set of user-level operations

based on these services.

Query Routing H yPursuit’s user interface allows the user to search for relevant information with query-based op-

erations that automatically traverse the cluster hierar-

chy. Our previous work [22] describes in detail how these

content routing operations prune the information space

and provide progressively finer-grained views of the rel- evant information. Relevant information may be either clusters (i. e., content rout ers) or documents.

Figure 6 shows the HyPursuit user interface, including

the query processing operations. The current query ap-

pears at the top of the window, followed by a text entry

region for adding terms to the query. The query-based

operations, shown in the pop-up menu in the center of

the figure, are select, expand, and search. Select prunes the current result set to the clusters and doc-

uments that match the given query. Expand selects

children documents and clusters that match the given query. search recursively searches clusters for all doc-

uments that match the query by selectively traversing

the cluster hierarchy down to the leaf nodes. Note that the result set includes both a leaf document and several

content router clusters,

HyPursuit uses query routing to support the search op-

erations. Query rout ing uses the content labels stored

in the content router to determine which of the child

servers are likely to contain documents related to the

user query. The query is forwarded to these servers,

and the results from each server are merged into a sin-

gle result set. Documents returned by more than one

child server are displayed only once.

Clustering Result Sets To helps users browse and com- prehend the information space, HyPursuit organizes and

presents the result set documents according to their

sub-clusters. Documents that belong to the same sub- cluster are placed together in the user screen. Figure 7

illustrates a clustered result set that cent ains five docu-

ments grouped into three sub-clusters. Note that two of the documents have the same title. These results have

different URLS that point to the same underlying doc-

uments. The HyPursuit prototype removes duplicate

URLS, but cannot detect this type of aliasing. However,

result set clustering helps the user detect duplication

because duplicate documents will appear in the same sub-cluster.

Query Refinement HyPursuit uses term information about sub-clusters to dynamically compute recall- and precision-

enhancing terms related to a user query. Figure 6 shows the interface of our system after an interaction with

the search facilities to produce a result set and a sub-

sequent query refinement operation. The region titled suggest ed terms in Figure 6 contains three scrollable lists of terms. A content router suggests query refine- ment terms using the sub-clusters in the content labels of its child servers. Collocated terms are the high- est weighted terms from the sub-clusters that match the query. HyPursuit’s term weights approximate con- ditional probabilities of term collocation. Term collo- cation in sub-clusters approximates term collocation in documents.

Broader and narrower terms are suggested by a the-

saurus-based query refinement mechanism. Broader terms represent general concepts related to the terms in the

query, and are expected to improve recall. They provide a means of exploring the information space. Narrower

terms can improve precision by allowing specialization of queries. The thesaurus mechanism is based on the au-

tomatic construction of thesaurus classes built offline us-

ing a Forsyth-Rada algorithm [11] modified to consider

sub-clusters rather than documents. For a given collec-

186

tion of sub-clusters, we generate a two-level hierarchy of term classes by gathering term frequencies, calculating weights and grouping high-frequency and low-frequency terms. We then establish the broader/narrower rela- tionships between the high-frequency and low-frequency terms based on similarities between the term frequency distribution functions,

Cluster-Based Browsing As shown in figure 6, users can browse through the information space by examining clus- ters, content labels, and cluster summaries. To see the contents of a cluster, i.e., its child documents and clus- ters, a user clicks on the cluster’s name. To see a clus- ter’s content label, the user clicks on the text cent ent label next to the cluster. To see the cluster’s summary, the user clicks on the text summary next to the cluster.

HyPursuit summarizes the information space of a con- tent router in a format that is suitable for human com- prehension. A cluster summary includes two parts: the most heavily weighted terms in the cluster and a sum- mary of each of the sub-clusters computed by the ab- straction function for query refinement. The summary for each sub-cluster includes a selection of the most heavily weighted terms and a list of some of the doc- uments in the sub-cluster. In the current implemen- tation, HyPursuit arbitrarily selects the sample list of documents. A future implementation may choose to select documents that are more representative of the sub-cluster. For example, the system can suggest pre- computed centroid documents [7] for each sub-cluster based on both the terms in the sub-cluster and the link structures.

Resu/t Set Expansion To improve recall, HyPursuit sug- gests additional related documents that, though not se- lected by the query, are collocated in sub-clusters with query-selected documents. Figure 7 shows the result of executing a suggest dots operation after processing the query text: file text: semantic text: system. The list labeled 5 results: contains query selected docu- ments. The list of documents labeled Similar Documents consists of documents that appear in the same sub- clusters as the query-selected documents. Currently, HyPursuit suggests all documents that appear in the same sub-cluster as any result set document. A future implementation of HyPursuit may suggest only certain documents from the sub-clusters, such as those nearest the sub-cluster centroid. A document will be compared to the centroid based on both the terms in the sub- cluster and the link structures. We also plan to provide users with a graphic representation of the relevant sub- cluster.

CONTENT-LINK CLUSTERING Content-link hypertext clustering organizes documents into groups of related documents called clusters based on the terms they contain and their hyperlink struc- tures. We first describe the generic content-link clus- tering algorithm. The algorithm uses a new document similarity function based on both term similarity and hyperlink similarity factors. We then describe a novel

187

Figure 7: Suggesting Additional Documents

hyperlink similarity function that assigns higher similar- ities to documents that have ancestors and descendants in common, as well as documents that point (directly, or indirectly) to one another. Finally, we describe how term weights are factored into the computation of hy- pertext document similarities using a traditional term- weight ing scheme.

Similarity-Based Clustering Our clustering is based on the complete link method [19]. Although faster clustering algorithms exist [6], we chose the complete link method because it was easy to imple- ment. The complete link method starts with a set where each original document represents an independent clus- ter. The algorithm iteratively reduces the number of clusters by merging the two most similar clusters un- til max.clust ers clusters remain. The algorithm uses pair-wise similarities of component clusters to compute the similarity of two compound clusters. The similar- ity of the compound clusters is the minimal similarity between any of these pairs. The complete link method avoids generating very large clusters.

Our content-link hypertext clustering uses a hybrid sim- ilarity function that includes hyperlink and term compo- nents. The first component, SkS, measures the sim- ilarity between hypertext documents di and dj based on their hyperlink structures. The second component, S~;”ms, measures the similarity between hypertext doc- uments d; and dj based on the document terms. The

similarity bet ween two hypertext documents, S&”rid, is

a function of S~ks and S$r~’, as shown in equation 1:

(1)

The similarity measurements proposed in the follow- ing sections capture qualitative notions about how link structures and document contents imply relationships between documents. The design of HyPursuit includes parameterization of these similarity functions to allow experimentation and customization based on the infor- mation space. For example, in the HyPursuit prototype, the function F that combines the hyperlink and term similarity values is max. This ensures that if either the link similarity or the term similarity is high, then the hybrid similarity is also high. In the future, we plan to investigate the quantitative behavior of the proposed hyperlink similarity function and other alternatives.

A Simple Hyperlink Similarity Function Our measure of the hyperlink similarity between two documents, S~.nks,

captures three important notions about certain hyper mk structures that imply semantic rela- tions: a path between two documents, the number of ancestor documents that refer to both documents in question, and the number of descendant documents that both documents refer to. Other notions, such as the number of independent paths between the two nodes, are also important but currently not considered by the HyPursuit prototype.

For our discussion, we use the following definitions:

splZY z length of a shortest path between d= and dy

spl~Y G length of a shortest path between dz and dy

not traversing dz

Direct Paths We hypothesize that the similarity between two documents varies inversely with the length of the shortest path between the two documents. A link be- tween documents di and dj establishes a semantic re- lation between the two documents. If we assume that these semantic relations are transitive, then a path be- tween two nodes also implies a semantic relation. How- ever, as the length of the shortest path between the two documents increases, the semantic relation between the two documents tends to weaken. Because the hyper- text links are directional, we consider both shortest path di ---+dj and dj + di. If there is no path between di and

dJ, we do not add any weight to the similarity function

for this component. Equation 2 shows S#’l, the compo- nent of the hyperlink similarity function that considers shortest paths bet ween the documents:

1 s;;’ = J- — Z(spl,j) + 2(sP1ji) (2)

The denominator ensures that as shortest paths increase in length, the similarity between the documents decreases.

Common Ancestors The similarity between two docu- ments is proportional to the number of ancestors that the two documents have in common. The analogy comes from bibliographic citations: when two or more articles al, az, . . . an cite some set of common articles c1, cz, . . . cn, then this likely implies a semantic relation between the

Ci‘s. As with Sj~~, the semantic relation tends to weaken~~

as the paths between the citing articles ai’s and the cited document Ci’s increases. Equation 3 shows S,anc,

i the component of the hyperlink similarity function t at considers common ancestors:

(3)

S~’ considers the length of the shortest path between a common ancestor and both di and dj. As the shortest paths increase in length, the similarity decreases. Also, the more common ancestors, the higher the similarity. The computation normalizes S~c to lie between O and

1 before it is included in ~~~k’. The weight contribu- tion from each ancestor x 1s divided by the number of ancestors in the same “level” as ~. The level of x with respect to di and dj is the minimum distance from either~~

d% or dj .

A common ancestor al does not contribute to S~c when the only path that reaches dj from al is through di. If d~ is an ancestor of dj, then all ancestors al, az, . . .an of

di are automatically ancestors of dj. This would imply that any document that cites di, directly or indirectly, adds to the similarity between di and dj. A path be- tween di and dj is already considered in the similarity

measurement with the Sj component. Therefore, S,~’ does not include ancestors that are not proper common ancestors. However, if there is another path al + dj that does not traverse di, then al is considered a proper common ancestor of di, and its weight contribution is added to the similarity function.

Common Descendants The similarity between two doc- uments is also proportional to the number of descen- dants that the two documents have in common. The situation is analogous to the semantic relation implied by common ancestors. If articles al, az, . . . an cite some set of common articles c1, C2, . . . Cn, then this likely im- plies a semantic relation between the a~‘s. Equation 4 shows Sd~c, the component of the hyperlink similarity function’{ hat considers common descendants:

188

The computation normalizes S$’ to lie between O and

1 before it is included in f7~k$ in the same manner as the normalization for S~c.

Complete HyperlinkSimilarity The complete hyperlink sim- ilarity function between two hyperlink documents di and

dj, S~kS, is a linear combination of the above compo- nents:

Term-Based Document Similarity Function The similarity between hypertext documents also relies on the traditional method of using weighted terms. The term-weight function should favor terms that are rep- resent at ive of the documents, but should also discrimi- nate between the documents and the servers that hold them. The best known term weighting approaches [20] use compound normalized weights with three factors: term frequency, inverse document frequency and a factor inversely proportional to the size of documents. Term

frequency is the number of occurrences of a term in a document. Document frequency is the number of docu- ments within the global information space in which the term appears. The document size factor compensates for high term frequencies of terms in large documents.

The distributed nature of hierarchical search engines complicates the task of defining an appropriate term weighting function because global collection frequencies are not available. For example, consider the task of generating a content label for the Laboratory of Com- puter Science (LCS) server at MIT. The term computer appears in hundreds of documents (high collection fre- quency) and is very frequent in many of these documents (high term frequency). Is this a good term to keep in the content label for LCS? If we weigh the term with the three factors above it may end up with a low weight because of its high collection frequency. However, if the global document space includes documents in broad ar- eas unrelated to computers, this term happens to be a good discriminator for the LCS server, and therefore should be kept in its content label.

The current weight function uses term frequency and document size factors, but does not include collection frequency. However, we are investigating possible alter- natives that yield content labels with less high global collection frequency terms.

Term weights also consider term attributes. The weight function assigns a larger factor to terms with attributes tit le, header, keyword and address than the weight factor assigned to text terms.

The total weight wkj of a term t~ in document dk is cal- culated based on the term similarity function proposed by [20], with the omission of the collection frequency factor, as follows:

189

Let

‘fk, G term fiYClUt311CJ’ of i!i h dk

tf Wki = contribution to weight from frequency tf ki

ds wk~ E contribution to weight from size of dk

w;: = contribution to weight from term attribute

then

tj ‘fki Wki = (0.5+ o.5max )

(6)

j {tf kj }

(7)

‘“= +

(8)

The weight factor Wat is configurable on a per server ba- sis, but defaults to 10 for titles, 5 for headers, keywords, and addresses, and 1 for text attribute types.

The term-based similarity function Sjer~’ between doc- d uments dj and dj is the normalized ot product of the terms vectors representing each document.

= Xw~k “Wjk (9)

S:;.ms

IMPLEMENTATION The HyPursuit prototype consists of a distributed set of content routers that interact with each other through HTTP POST queries and with users through the HTML FORM interface. Each content router is implemented as a CGI script that performs content-routing operations. HyPursuit runs on Sun SparcStations under SunOS 4.1.3. All modules in the system were implemented using GNU

c++.

Architecture The set of executable modules comprising each content router in the current HyPursuit prototype includes ab-

straction modules, transducer modules, and a single CGI engine module. The engine module is responsible for processing requests generated from users through their WWW browsers or from higher level HyPursuit routers. The HyPursuit engine is stateless and does not currently maintain any cache or history of previous requests.

The abstraction modules are responsible for summa- rizing an information space by generating content la- bels. HyPursuit’s abstraction module for query refine- ment uses both term information and link information to generate the document sub-clusters included in con- tent labels for W WW servers. However, the abstraction function for higher level routers currently uses only term information to generate query refinement sub-clusters

for higher level routers. Future HyPursuit abstraction functions will take advantage of link information at all levels of the hierarchy.

HyPursuit includes a set of transducer modules that use the abstraction function output to generate databases required by the content routing information retrieval services. Every service may potentially require a dif- ferent database, but all necessary databases must be created from the information provided in content labels. Various services may share the same database. The cur- rent H yPursuit prototype has four different databases: one for query refinement based on sub-cluster colloca- tion of terms, another for query refinement based on t he- saurus classes, a third for routing queries and a fourth for suggesting similar documents. Result set expansion and result set clustering rely on the term collocation database.

Configuration

Leaf content routers provide content-based access to col- lections of individual documents on the World-Wide Web These routers may run anywhere on the network, al- though for the sake of efficiency they should run in close physical proximity to their data, preferably on the same machines. Each such router invokes a Web robot that gathers the full text of documents on the correspond- ing web server and generates a full text index mapping terms to document URLS. The router’s robot also gen- erates a content label for the web site that includes sub- clustering information used by the daemon for providing the content routing services. For the sake of our exper- iments, the HyPursuit leaf content routers all run on our computers. They communicate with each other via HTTP.

The HyPursuit prototype uses a simple content label size budgeting scheme based on maximum numbers of terms and sub-clusters per content label. This scheme was chosen for its simplicity and ease of implementation. We are investigating other approaches.

Figure 2 shows a portion of a content routing hierarchy that was constructed for our experimental system. The system consists of 100 leaf servers (that index particular Web sites) and a series of higher-level content routers organized in a hierarchy that resembles the structure of the Domain Name System [17], For instance, the root rout er’s name is “edu” , and some of its children are “init. edu” and “emu.edu”. The pattern follows until leaf servers with full domain names are reached (e.g. www.psrg.lcs.mit .edu).

EXPERIENCE

This section presents experience with the HyPursuit pro- totype. The section first compares the clusters gen- erated by each variation of the content-link hypertext clustering algorithm on a particular collection. Then, the section discusses the HyPursuit prototype storage requirements and the performance of the query process- ing operations.

Clustering Example We ran an experiment to compare CNN’s manual clustering of pages on their mm. cnn. com web site with our automatic clustering techniques. CNN manually clusters documents into predefine cate- gories, including technology, health, business, weather, and others. The manual clustering of the docu- ments is reflected in their URLS. For example, http: //www. cnn. corn/TECH/apple/windows Aype/ is categorized as a TECH document, i.e. it is clustered with other documents about technology.

Table 1 shows the clustering result obtained by run- ning the term-based, link-based, and content-link clus- tering algorithms on a collection of documents from the www. cnn. com web site. The example collection includes 195 documents retrieved by following a breadth-first- search starting with the root http: //www. cnn. corn. Each table entry represents a cluster generated by one of our algorithms. An entry lists the documents in the cluster, giving names of their CNN categories and the number of documents from each category. The category names are literally extracted from the URL.

A subjective examination of the table reveals that both the term-based and the link-based algorithms approxi- mate CNN’S manual clustering reasonably well, but the hybrid algorithm tends to agree most closely with CNN’S scheme. For example, the term-based algorithm clusters 13 documents from the HEALTH category with other doc- uments from BIZ, POLITICS, TECH, and US. The links algorithm also clusters HEALTH documents with other documents. In contrast, the hybrid algorithm is able to group HEALTH documents in a separate cluster. We are investigating approaches that will allow us to quantify these observations.

Storage Requirements and Performance of Operations HyPursuit’s leaf content routers contain the first 100 documents in a breadth-first-search traversal of each HTTP server starting at the node whose URL has a null pathname (e.g. http: //www. psrg. lcs .mit. edu/). We choose to index only 100 documents from each site because of storage limitations and to allow us to exper- iment with different clustering techniques without over- burdening the web sites. This limitation does not re- flect any constraints of the design or implementation. The abstraction module that generates content labels for leaf servers considers the first 500 terms from each document, as well as the 500 most frequent terms ap- pearing afterwards in the document. Again, we index a limited number of terms to satisfy our resource lim- itations. We choose the first 500 terms because they possibly characterize the document well. The content label budget scheme fixes the maximum number of sub- clusters for query refinement: max.clust ers is 30 for leaf servers and 50 for higher-level routers.

Table 2 shows the storage requirements of the HyPur- suit content label, query routing, and query refinement components. Level O indicates the storage requirements of an average leaf content router. The table reflects

190

1 F

cluster #

Terms Links Hybrid BIZ (22), HEALTH (13) Programs (2), HEALTH (13) HEALTH (13) POLITICS (17) I POLITICS (16). feedback (1) I TECH (14), US (9)

1 F

WEATHER (7) WEATHER (9) WEATHER (7) EARTH (l), HLN (1) SHOWBIZ (17), INDEX (1) SHOWBIZ (16) SHOWBIZ (14), Studio (1)

US (10), WEATHER (2)

WORLD (1)

SHOWBIZ (2), SPORTS (2) I BIZ (19) BIZ (22) networks (1) I I

US (5), WOR~D (11) WORLD (18) WORLD (18)

INDEX (3), PressRelease (1) SEARCH (3), Studio (4)

networks (1)

10 11

Programs (6) us (22) us (20)

12 F=

15 1=

homepage (l), WORLD (1) SPORTS (1) SPORTS (2)

INDEX (2)

SEARCH (3) us (1) us (2)

feedback (3) feedback (1) feedback (3)

feedback (1) feedback (1) feedback (1)

Table 1: Clusters by Algorithm on http: //www. cnn. com

the different storage limitations placed on leaf content rout ers versus higher level content routers. These con- straints also limit the sizes of the routing and refinement databases.

Table 3 shows the average processing time of the HyPur- suit prototype operations, measured in whole seconds. The select operation is local, and therefore there is no difference in performance between content routers on different levels. The expand operation contacts only children routers, and therefore the level of the router does not affect the processing time of the operation. The s earth operation requires communication with descen- dent routers that match the given query, and therefore the processing time increases with the levels.

The refine and suggest docs operations consult the local query refinement sub-cluster database. For these operations and our example queries, as the level of the content router increases from zero to two, the average

191

Algorithm

. ,, ,/

AtWork (l), Radio (1) homepage (l), Airport (1) Airport (l), AtWork (1) INDEX (2) AtWork (l), BIZ (3), Programs (5) Programs (3), Radio (1)

Radio (l), EARTH (l), HLN (1) Studio (3), networks (1)

Studio (3) Programs (l), TECH (14) TECH (14)

SPORTS (8) SPORTS (9) SPORTS (8)

STYLE (17) STYLE (17) STYLE (17)

WORLD (5) POLITICS (1) INDEX (2), POLITICS (17)

PressRelease (1) feedback (1) homepage (l), EARTH (l),

SHOWBIZ (1) PressRelease (1), SEARCH (3) .,

SHOWBIZ (l), US (l), INDEX (2)

Airport (1) us (1) HLN (l), Studio (l), US (1)

WEATHER (2)

Programs (3) Programs (1) Programs (6) ‘

Databases

Level cent ent labels routing refinement o 410 3509 3378 1 678 3937 4003 2 630 4005 4057

Table 2: Average Sizes of Databases (in KB)

number of matching sub-clusters increases from four to twelve. Currently, the parsing of sub-clusters takes over a second for each sub-cluster that consists of approxi- mately 500 terms. Therefore, the processing time for the refine and suggest.dots operations increases with the content routing levels due to the increase in the num- ber of matching sub-clusters. A better data structure that maps sub-cluster identifiers to terms and reduces sub-cluster parsing times would greatly improve the per- formance of these operations.

Operation

Level select expand search refine suggest -dots o 1 1 1 6 5 1 1 3 2 11 10 2 1 2 6 18 18

Table 3: Average Processing Time (in seconds)

CONCLUSION AND FUTURE WORK

We have built a new HTTP-based prototype content routing system that exploits content-link hypertext clus- tering to provide access to over 100 web sites. This system was used to examine the feasibility of content- link clustering for the construction of meaningful and scalable cluster hierarchies. The HyPursuit prototype supports query processing operations with abstraction functions that summarize information spaces and clus- ter documents based on both term and link information. Our limited experience with the system shows that the prototype delivers adequate performance. The results are also promising with respect to the ability of the sys- tem to scale up to a very large number of web sites. It is clear that a full scale system will require better perfor- mance in both offline and online operations. In addition, we are concerned that Content Routing may be subject to performance hotspots due to intense transient inter- est in a particular subject. Preliminary results illustrate that combining term and link information offers benefits to hypertext document clustering.

We are continuing to investigate alternative approaches to hypertext clustering and methods to measure the per- formance of various clustering algorithms. We plan to build larger, automatically constructed hierarchies both to test our hypothesis about the scalability of the sys- tem as well as to apply the clustering algorithms to more diverse information spaces. Finally, we plan to compare the performance of using content-link hypertext cluster- ing for the query refinement abstraction function versus other non-clustered approaches.

ACKNOWLEDGMENTS The authors would like to acknowledge the contribu- tions of others in the original writing and formatting of this document. We are grateful to David Karger, James O’Toole, Jr., and our reviewers for valuable comments. This research was supported by the Defense Advanced Research Projects Agency of the Department of Defense contract number DABT63-95-C-0005.

REFERENCES

Bob Alberti, Farhad Anklesaria, Paul Linkner, Mark McCahill, and Daniel Torrey. The Internet

Gopher protocol: A distributed document search and retrieval protocol. University of Minesota Mi- crocomputer and Workstation Networks Center,

Spring 1991. Revised Spring 1992.

Rodrigo A, Botafogo. Cluster analysis for hypertext systems. In ACM 16th Annual International SIGIR

’93, Pittsburgh, PA, June 1993.

Rodrigo A. Botafogo and Ben Schneiderman. Iden- tifying aggregates in hypertext structures. In Hy-

pertezt ’91, December 1991.

C. Mic Bowman, Peter B. Danzig, Darren R. Hardy, Udi Manber, and Michael F. Schwartz. The harvest information discovery and access system. In Proceedings of the Second International World

Wide Web Conference, pages 763–771, Chicago, Illinois, October 1994.

Donald B. Crouch, Carolyn J. Crouch, and Glenn Andreas. The use of cluster hierarchies in hypertext information retrieval. In Hypertext ’89, November 1989.

Douglass R. Cutting, David R. Karger, and Jan O. Pedersen. Constant interaction-time scatterlgather browsing of very large document collections. In 16th

Annual International SIGIR ’93, Pittsburgh, June 1993.

Douglass R. Cutting, David R. Karger, Jan O. Ped- ersen, and John W. Tukey. Scatter/gather: A cluster-based approach to browsing large document collections. In 15th Annual International SIGIR, pages 318-329, Denmark, June 1992.

Andrzej Duda and Mark A. Sheldon. Content routing in networks of WAIS servers. In Proceed-

ings of the l~ih International Conference on Dis- tributed Computing Systems, pages 124–132, Poz-

nan, Poland, June 1994. IEEE,

David Eichmann. The RBSE spider – balancing

effective search against web load. In Proceedings

of the First International Conference on the World

Wzde Web, Geneva, Switzerland, May 1994,

David Filo and Jerry Yang. Yahoo frequently asked questions. World Wide Web Document. URL http://www. yahoo.comifaq.html.

10.

R. Forsyth and R. Rada. Machine ,Learning—

11.

Applications in Expert Systems and Information

Retrievai. Ellis Horwood, 1986.

Mark E. Frisse. Searching for information in a hy- pertext medical handbook. Comm. ACM, 31(7), July 1988.

12.

George W. Furnas and Jeff Zacks. Multitrees: En- riching and reusing hierarchical structure. In CH1

13.

94 Human Factors in Computing Systems: Ceie - bratmg Interdependence, Boston, April 1994.

Luis Gravano, Anthony Tomasic, and H&ctor

14.

Garc~a-Molina. The efficacy of G1OSS for the text database discovery problem. Technical Re- port STAN-CS-TR-93-2, Stanford University De- partment of Computer Science, October 1993.

Harley Hahn and Rick Stout. The Internet Com-

15.

plete Reference. Osborne McGraw-Hill, Berkeley, California, 1994.

192

Martijn

Koster. ALIWEB – archie-like indexing in the web. In Proceedings of the First Interna-

tional Conference on the World Wide Web, Geneva, Switzerland, May 1994.

P. Mockapetris.

Domain names

concepts

and fa- cilities. RFC 1034, 1987.

Brian

Pinkerton. Finding what people want: Expe- riences with the WebCrawler. In Proceedings of the

First International Conference on the Worid Wide

Web, Geneva, Switzerland, May 1994.

Gerard

Salton and Jose Araya. On the use of clus- tered file organization in information search and re- trieval. Technical Report TR 89-989, Cornell Uni- versity, April 1989.

20. Gerard Salton and Chris Buckley. Term weighting approaches in automatic text retrieval. Technical Report TR 87-881, Cornell University, November 1987.

Mark

A. Sheldon, Andrzej Duda, Ron Weiss, and David K. Gifford. Discover: A resource discovery system based on content routing. In Proceedings of

The Third International World Wide Web Confer-

ence. Elsevier, North Holland, April 1995. To ap- pear in a special issue of Computer Networks and ISDN Systems.

Mark

A. Sheldon, Andrzej Duda, Ron Weiss, James W. O ‘Toole, Jr., and David K. Gifford. Con- tent routing for distributed information servers. In Fourth International Conference on Extending

Database Technology, pages 109–122, Cambridge, England, March

Available

as Springer-Verlag LNCS Number 779.

193