Information Visualization - Proc. Asia Pacific Symposium on Information Visualization (APVIS2006)

Information Gathering Support Interface by the Overview
Presentation of Web Search Results
Takumi Kobayashi

Kazuo Misue

Buntarou Shizuki

Jiro Tanaka

Graduate School of Systems and Information Engineering
University of Tsukuba,
Tennoudai 1-1-1, Tsukuba, Ibaraki, Japan 305-8571
Email: {takumi, misue, shizuki, jiro}@iplab.cs.tsukuba.ac.jp

Abstract
The Internet consists of several billion documents.
Choosing information from such a great number of
Web pages is not easy. We do not think that the interfaces of traditional search engines that divide search
results into dozens of pages regardless of genre anddisplay the results as a text-based list are necessarily
useful. We propose an interface that helps the user
to intuitively understand the entire Web search result
and to gather information. Our system analyzes andclassiﬁes Web search results and presents the classiﬁcation results to the user on one screen.
Keywords: Web search, Information gathering, Clustering, Visualization, Interface, Hyperbolic tree
1

Introduction

The Internet is used by people all over the world. As it
spreads, the volume of information available and thenumber of Web pages is increasing rapidly. According to Internet Systems Consortium, Inc., the numberof hosts connected to the Internet is more than 350
million (Internet Systems Consortium, Inc. 2005).
Having such a huge amount of information, we
need to use a search engine to retrieve the information that is relevant to us. When we conduct a Web
search, we can use diﬀerent kinds of retrievals to obtain diﬀerent kinds of information. We may conduct
a Web search that ﬁnds one or more Web pages related to a speciﬁc topic. One example is a retrieval
to obtain information on various topics about Japan.
Andrei Broder calls such a Web search an ”informational Web search”(Broder 2002). When a user conducts such a search, (s)he must view a great numberof Web search results from various viewpoints andchoose from them. A search for information about
Japan is abstract and includes information on politics, traﬃc, tourist spots, and so on. Therefore, theuser should not gather information from a speciﬁc
Web page alone but should gather information froma variety of pages.
A conventional keyword search interface presents
various problems when we conduct an informational
Web search. These problems make the Web searchdiﬃcult. Gathering information eﬃciently is diﬃcult
when using a conventional Web search interface that
presents search results as a text-based list becausesuch a one-dimensional list consists of various genresof Web pages. In addition, the display method, whichc
Copyright 2006,
Australian Computer Society, Inc. This paper appeared at Asia-Paciﬁc Symposium on Information Visualization (APVIS 2006), Tokyo, Japan, February 2006. Conferences in Research and Practice in Information Technology, Vol.
60. K. Misue, K. Sugiyama and J. Tanaka, Ed. Reproduction
for academic, not-for proﬁt purposes permitted provided thistext is included.

divides search results into dozens of pages, does notallow the user to intuitively understand the featuresof the entire search result. Therefore, the user mightoverlook proﬁtable information.
We propose a system that classiﬁes Web search
results according to the content of the pages. Our
system presents the classiﬁcation results with somelabels on one screen.
2

Overview Presentation System

We propose an interface that aids information gathering with the following features to solve the problemsof conventional Web search interfaces.
1. The interface arranges similar Web pages inneighborhoods in a two-dimensional space.
2. The interface presents classiﬁcation results to theuser on one screen.
Our system categorizes Web search results into clusters according to the content of the Web pages toarrange similar Web pages in neighborhoods. The
concept of feature 1 is shown in Figure 1. The user
can gather information more eﬃciently because thesystem does not scatter various genres of Web pages
but arranges them in neighborhoods. Web pages thatthe user does not want in the search results are arranged in neighborhoods according to their genres.
Thus, the user can avoid looking through distracting
scattered Web pages which (s)he does not want.
Our system presents search results in a twodimensional space. This display method oﬀers theuser a retrieval that is more ﬂexible than a onedimensional presentation interface because the user
does not have to sequentially check a one-dimensional
list.

Figure 1: Feature 1
Conventional Web search engines visualize search
results as text-based lists. However, one problem withthese search engines is that they return too much information. The user cannot intuitively understandthe entire search result. In addition, the result list isdivided into small portions, but only 5 to 10 results
can feasibly be viewed on the screen at any one time
without scrolling, which forces the user to click on

103

CRPIT Volume 60

the next button to view the next set of results. Our
system presents classiﬁcation results to the user on
one screen. Thus, the user can easily understand theentire Web search result in an intuitive manner rather
than having an interface that divides the search results into dozens of pages. The user also can obviate
the need to frequently click the next button to view
multiple search results.
When our system presents search results, it uses
labels and the titles of classiﬁed Web pages. The labels are composed of several words that represent thefeatures of the cluster. The user can easily ﬁnd multiple relevant Web pages by referring to the labels.
3

Prototype of the Overview Presentation
System

Our overview presentation system consists of twoparts: the clustering of the Web search results andthe presentation of the clustering result. The composition of our system is shown in Figure 2emphasize. META tags might contain explanations
and features of the page not included directly in the
page. Our system can extract information from thewords on pages with such structures. Web pages thatuse FRAME tags or IFRAME tags can be recursively
analyzed by obtaining the URLs the tags refer to.
After the system analyzes the HTML tags, it
forms clusters based on the document vectors obtained using the analysis. We used hierarchicalclustering(Everitt 1993). First, our system considers each Web page as one cluster. Next, the systemcompares the inner products of vectors that represent the features of each Web page. The two clusters
with the biggest inner product value are combined
and considered a new cluster. The feature vector of
the new cluster is a composite of the feature vectorsof the two original clusters. The system repeats thiscombination process until all the Web pages are partof one cluster. Finally, the system makes a tree diagram in which similar Web pages are arranged inneighborhoods.
When the system combines two clusters, it determines three words that are highly related to both clusters. These words represent a common feature of thetwo clusters. The system obtains them when it calculates the inner product value of the two clusters.
They are important words that compose the label ofthe two clusters in the presentation of the clusteringresult.
3.2

Figure 2: Search
1query, GoogleAPI,
2
Search3
results, Analyzes
4
Web pages and conducts clustering,Clustering5
result, Visualization
6
3.1

The Clustering of Web Search Results

To cluster Web search results, multiple Web pages
found by a Web search engine are analyzed according
to their content and classiﬁed into clusters based on
the result. When the user enters a search query, oursystem uses GoogleAPI(Google 2005) to get the relevant URLs. Next, the system generates the HTMLﬁles corresponding to the URLs and analyzes them.
To analyze the HTML ﬁles, the system extracts
words that appear in the HTML ﬁles using morphological analysis. The system expresses each HTMLﬁle with the vector space method, using the tf-idf algorithm. An HTML ﬁle does not consist of simple
sentences but has a tree structure of commands called
tags. We think that our system can better extract thefeatures of Web pages by using the structural information of HTML ﬁles.
For example, we think that parts of Web pages
modiﬁed with TITLE tags, H tags, and STRONG
tags contain words that represent the features of Web
pages because these parts are highly likely to containthe main points of pages and be words the author of
the page wants to emphasize. The words that appear
in such parts are given heavier weights by the systemthan the words that the author does not intend to104

The Presentation of the Clustering Result

In general, because Web search results are huge, thetree diagram of the clustering is also huge. Our system uses Hyperbolic Tree to ﬁt such huge tree diagrams on one screen and present them to the user.
Hyperbolic Tree is a technique proposed by John
Lamping for arranging huge tree diagrams on the hyperbolic plane(Lamping, Rao & Pirolli 1995). Hyperbolic Tree can visualize and manipulate large hierarchies. Using Hyperbolic Tree, partial trees near thecenter of the screen are displayed larger, and those far
from the center are displayed smaller. The user canmove the focus by moving a partial tree to the centerusing the mouse. This movement of focus is shown in
Figure 3. These features enable more information to
ﬁt on one screen than does a usual tree diagram. By
moving the focus, the user can focus on relevant portions of the hierarchy while still seeing it embeddingin the context of the entire hierarchy.
When the user collects information, (s)he cannot
obtain the necessary amount of information by only
displaying the tree diagram of the clustering result
using Hyperbolic Tree. Thus, our system determines
three words that strongly show the relationship between the parents nodes of two clusters to help theuser gather information. The relationship between
Web pages A, B, and C, and words 1-6 is shown in
Figure 4.
In Figure 4, Web pages A and B have a strong relationship with words 1, 2, and 3. Cluster AB, which
consists of Web pages A and B, has a strong relationship with words 4, 5, and 6. The user can gather
information more eﬃciently because the system adds
these labels that show the features of the clusters.
The clustering technique we used sometimes composes clusters that consist of Web pages that are
not so similar. As a result, tree diagrams that look
like staircases might be formed. We have improved
the display interface to solve this problem. Our system bring Web pages that cluster in a staircase pattern together in one cluster under the label ”Others.”
The system oﬀers an attractive presentation screenby transforming the tree diagram.

Information Visualization - Proc. Asia Pacific Symposium on Information Visualization (APVIS2006)⇒⇒

Figure 3: Movement of focus.

⇒

Figure 5: Improved display interface.

105

CRPIT Volume 60

Figure 4: Relationship between clusters and labels.

educational institutions that deal with Japanese history, and academic societies and theses concerning
Japanese history.
When using an interface where search results arepresented in a one-dimensional text-based list, theuser must check each Web page on the list, including various genres of Web pages. When using oursystem, only the partial trees composed of similar
Web pages must be checked. Thus, when the userneeds to gather information from various genres of
Web pages, (s)he can eﬃciently choose relevant information in each partial tree without changing the idea.
The user can easily understand the whole search result by referring to the partial trees because the result
is displayed on one screen.
5

The left side of Figure 5 shows a cluster in which
the Web pages are not so similar. This part has astaircase shape and might confuse the user if displayed as it is. On the right side of Figure 5, oursystem has brought the Web pages in the staircase
pattern together in an ”Others” node. In this chart,
the useless labels in the chart on the left have been
eliminated. Thus, the system increases the numberof Web pages that can be displayed at a time. The
user can intuitively understand the entire Web search
result and gather information eﬃciently using our improved display interface.
4

Example Application of Prototype System

When the user wants to examine Japanese history
from various viewpoints, (s)he can search the Web using the query ”Japan, History.” A conventional searchengine sequentially displays the pages that include thewords ”Japan” and ”History”. The result is displayed
in a one-dimensional text-based list, and the list orderdepends on the search engine. Thus, the user must
sequentially check each item on the list because various genres of Web pages are mixed together. Manyof these pages may be irrelevant to the user. In our
example, the user wants to ﬁnd pages about Japanese
history, but many pages about fortune-telling (which
the user does not intend) are included in the list of
the search results. We think that this is annoying for
the user and makes information gathering diﬃcult.
Our system’s presentation screen for the search
query ”Japan, History” is shown in Figure 6. The system formed clusters according to the algorithm andpresented the results. In Figure 6, the lower rightpartial tree consists of fortune-telling pages including
the words ”Japan” and ”History.” Thus, the user neednot check any further because (s)he can understandat a glance that the Web pages in this partial tree areconcerned with fortune-telling (which the user does
not intend). The Web pages that could not be clustered by the algorithm are gathered in the lower leftpartial tree under the label ”Others.” They can besaid to be unique Web pages in the search result.
The partial tree shown in Figure 6 is rather large.
The user can gather information by moving the focus
with the mouse while viewing the labels and tracesof the partial tree. A snapshot of the partial treeof pages related to the word ”Geography” and including the words ”Japan” and ”History” is shown in
Figure 7. A snapshot of the partial tree of pages related to the word ”Textbook” and including the words”Japan” and ”History” is shown in Figure 8. Whenthe tree is observed in detail, the user can see thatsome Web pages are about the problem of military
prostitution and textbooks. The partial trees are ofvarious genres, e.g., books about Japanese history,

106

Enhancing the User Interface

In this section, we introduce our intended enhancements to the user interface. The user will be able toconduct an informational Web search more eﬃciently
by using these enhancements.
5.1

Using Ranking Information

Our system uses GoogleAPI to acquire Web search
results. We plan to reﬂect the GoogleAPI rankingof search results in the display interface. Google
uses Page rank to calculate the importance of a Web
page. Page rank automatically calculates the relative importance of Web pages(Page, Brin, Motwani& Winograd 1998) based on a recursive relationship:
Web pages that many high-quality Web pages havelinks to are high-quality. Page rank is a brilliant technique for oﬀering the user high-quality Web pages.
Our system allows the user to eﬃciently retrieve highquality pages by combining the ranking information
provided by Page rank with the search result presentation method using Hyperbolic Tree.
Our system presents clustering results by using
Hyperbolic Tree. Therefore, our system does not sequentially display Web pages in the order of page rank
from highest to lowest, like the Google interface does.
Instead, our system oﬀers the user the ranking information by shading the nodes. The system colors
the nodes of important Web pages with dark colors
and those of unimportant Web pages with lighter colors. Thus, the user can easily ﬁnd the important Web
pages in a large search result. In addition, the user
can more intuitively understand the whole search result by using the shading information.
5.2

Generating Summaries of Web Pages

In our system, each node of a hyperbolic tree shows
the title of a Web page. However, oﬀering only titles
does not necessarily help the user gather enough information because (s)he may ﬁnd the content of the
Web pages diﬃcult to guess. We plan to oﬀer the user
some additional text that summarizes the content of
Web pages. A summary of a Web page can be obtained by using the interface of GoogleAPI. However,
because a summary obtained this way is mechanically
excerpted text, the user still may have diﬃculty understanding the content of the Web page. Thus, oursystem generates comprehensible summaries for theuser by using the tag information of Web pages.
For instance, a Meta tag modiﬁe the summary of
the Web page that the author of the page gave. H tags
modify headings that reﬂect the content of pages well.
Our system can help the user gather information by
oﬀering a summary that expresses the content of the
Web page remarkably well. The summary is displayed

Information Visualization - Proc. Asia Pacific Symposium on Information Visualization (APVIS2006)

Figure 6: Presentation screen of our system for search query, ”Japan, History.”

Figure 7: Partial tree related to ”Geography.”

Figure 8: Partial tree related to ”Textbook.”

107

CRPIT Volume 60

in a pop-up window when the user clicks the node that
contains the title of the page.
5.3

Classiﬁcation based on the User’s Purpose

Web pages can be classiﬁed using standards otherthan their content. When we search the Web, webrowse many types of Web pages. For instance, wemight browse the top page of a certain site, a collection of Web links, a page with many characters, apage with many images, a page for shopping, and a
Weblog or BBS. This means that Web search results
can be classiﬁed based on the user’s purpose. We
considered a classiﬁcation method and presentationinterface that helps the user to intuitively understandmany types of Web pages in the search result basedon the user’s purpose. The system uses colors to appropriately classify each type of Web page. Thus, thesystem can help the user gather information by combining the colors with the previously mentioned node
shading.
6

Discussion and Future Work

Our system generates binary tree diagrams to display
search results using our clustering method. When asearch result is very large, the grain size of the clusters
in the diagram might be too small . In that case,the grain size of the clusters is increased and user’s
information gathering might become easy by bringing
the certain size of partial tree together in one cluster.
A common feature of multiple Web pages must be
extracted and used as a label.
The execution time of the entire system must be
considered for practical use. Web searches take a longtime if the system analyzes HTML code and clusters
for each Web search. To solve this problem, the system forms clusters by using document vectors withthe dimensions compressed. Thus, the computationaleﬀort for clustering is reduced, and the calculation
time is shortened. In addition, the computational effort when the Web is searched can be reduced if thesystem collects Web pages and processes them beforehand.
7

Related Work

Periscope is a Web search interface that presents Web
search results using a method other than a text-basedlist(Wiza, Walczak & Cellary 2004). Periscope arranges search results in a three-dimensional space.
When Periscope classiﬁes Web pages, it considers thehost names, languages, sizes, etc. of the pages. A
system that classiﬁes Web pages by host names andarranges them in a two-dimensional space was developed by Roberts, Boukhelifa, and Rodgers(Roberts,
Boukhelifa & Rodgers 2002). These interfaces do notclassify Web pages based on their content. Thus,
these systems do not oﬀer enough information for theuser.
Our system takes advantage of the tag informationof Web pages and clusters pages based on their content. It presents classiﬁcation results on one screenwith additional information that represents the features of the clusters.
8

Conclusion

We considered the problems of informational Web
searches using conventional Web search interfaces;
these problems are caused by the rapid increase in108

the volume of information on the Internet. We developed an interface that solves these problems. Our system can classify Web search results according to thecontent of Web pages by analyzing HTML tree structures. Our system presents the classiﬁcation results
to the user on one screen. The user can eﬃciently
conduct informational Web searches by referring to
the labels presented in a hyperbolic tree.
References
Broder, A. (2002), ‘A taxonomy of web search’, SIGIR Forum 36(2), 3–10.
Everitt, S., B. (1993), Cluster analysis, 3rd edn, London:E.Arnold.
Google (2005), ‘Google Web APIs’, http://www.
google.co.jp/apis/.
Internet Systems Consortium, Inc. (2005), ‘ISC Internet Domain Survey’, http://www.isc.org/
index.pl?/ops/ds/.
Lamping, J., Rao, R. & Pirolli, P. (1995), A focus+context technique based on hyperbolic geometry for visualizing large hierarchies, in ‘CHI
’95: Proceedings of the SIGCHI conference on
Human factors in computing systems’, ACM
Press/Addison-Wesley Publishing Co., pp. 401–
408.
Page, L., Brin, S., Motwani, R. & Winograd, T.
(1998), The pagerank citation ranking: Bringing order to the web, Technical report, Stanford
Digital Library Technologies Project.
URL: citeseer.ist.psu.edu/page98pagerank.html
Roberts, J., Boukhelifa, N. & Rodgers, P. (2002),
Multiform Glyph Based Web Search Result Visualization, in ‘the Sixth International Conference on Information Visualisation (IV ’02)’,
IEEE, pp. 549–554.
Wiza, W., Walczak, K. & Cellary, W. (2004),
Periscope: a system for adaptive 3D visualization of search results, in ‘Web3D ’04: Proceedings of the ninth international conference on 3D
Web technology’, ACM Press, pp. 29–40.