http:^^www.cc.gatech.edu^gvu^people^phd^sougata^chi95^sm_bdy.html

This data set contains WWW-pages collected from computer science departments of various universities

for identifying hierarchies from hypermedia structures. Although using just structural 
analysis to identify hierarchies works for hypertext systems with simpler underlying 
structures, identifying meaningful hierarchies by structural analysis alone is difficult 
for real-world systems. Content analysis is also essential as is evident from the paper. 
<!WA28><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_bdy.html#Ich93">[6]</A> describes a method to linearize complex hyper-networked
nodes to facilitate browsing using a book metaphor. However, this work also uses structural analysis only. 
<P>This paper is also related to systems that deal with graphical presentation of 
information automatically or semi-automatically. Examples include APT 
<!WA29><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_bdy.html#Mac86">[8]</A> and SAGE <!WA30><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_bdy.htm#Rot94">[16]</A>. However,
our information domain is different from these systems - these systems deal with highly 
structured information. The views that we want to develop are also different. The previous
systems generally produced bar diagrams, scatter plots and such graph views.

<H2>CONCLUSION</H2>
One of the best ways to comprehend a large complicated information structure is to form
multiple simpler structures each highlighting different aspects of the original
structure. Our work tries to use this philosophy to make a complex hypermedia system
understandable to the user. We believe that by forming various effective views of the 
underlying space, we would allow the user to better understand the complex information. 
We give examples of the hierarchization process from two complicated hypermedia systems to
illustrate our point. These examples show that our algorithm was able to extract 
meaningful hierarchies which gave better insights into the complex information spaces.<BR><BR>Future work is planned along the following directions:
<UL>
<LI> <em>Visualizing Larger Databases:</em> Although a  detailed complexity analysis is 
beyond the scope of this paper, it can be shown that the major bottleneck of the algorithm
is the structural analysis to identify roots. <!WA31><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_bdy.html#Bot92">[2]</A> uses an 
<!WA32><IMG ALIGN=BOTTOM SRC="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_fg11.gif"> algorithm to identify roots. On the other hand we use
a <!WA33><IMG ALIGN=BOTTOM SRC="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_fg12.gif"> algorithm to identify roots (by calling the 
breadth-first search for each node). Although in the worst case <em>l</em> = 
<!WA34><IMG ALIGN=BOTTOM SRC="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_fg13.gif">, on average <em>l</em> = 
<!WA35><IMG ALIGN=BOTTOM SRC="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_fg14.gif"> and our algorithm will perform better. For the WWW 
database with about 400 nodes and 800 links our algorithm took about 7 seconds on a SGI 
reality engine. Although this is acceptable, we will face problems for larger databases. 
We are investigating ways to enhance the performance by improving the efficiency of the 
code and using probabilistic algorithms to identify roots.  Moreover, even cone trees and 
treemaps are not able to visualize larger databases effectively. New visualization techniques are needed.
<LI> <em>Usability Studies:</em> A limitation of our system is that no evaluation of how 
useful our views really are have been done so far. We plan to do serious usability studies
in the near future. These studies may give us new insights that will help to improve our system.
</UL>

<H2>ACKNOWLEDGEMENT</H2>
This work is supported by grants from Digital Equipment Corporation, Bell South
Enterprises, Inc. and Emory University System of Health Care, Atlanta, Georgia as part of 
the Hypermedia Interface for Multimedia Databases project. We would also like to thank
the reviewers of this paper for their useful comments.

<H2>REFERENCES</H2>
<DL COMPACT>
<DT><A NAME=Bat93><STRONG>1</STRONG></A><DD>
G. Battista, P. Eades, R. Tamassia, and I. Tollis.
Algorithms for Drawing Graphs: an Annotated Bibliography.
Technical report, Brown University, June 1993.
<P>
<DT><A NAME=Bot92><STRONG>2</STRONG></A><DD>
R. Botafogo, E. Rivlin, and B. Shneiderman.
Structural Analysis of Hypertexts: Identifying Hierarchies and
  Useful Metrics.
<em>ACM Transactions on Office Information Systems</em>, 10(2):142-180,
  1992.
<P>
<DT><A NAME=Fai88><STRONG>3</STRONG></A><DD>
K. Fairchild, S. Poltrok, and G. Furnas.
Semnet: Three-dimensional Graphic Representations of Large Knowledge
  Bases.
In R. Guindon, editor, <em>Cognitive Science and its Applications
  for Human-Computer Interaction</em>. Lawrence Erlbaum, 1988.
<P>
<DT><A NAME=Fur94><STRONG>4</STRONG></A><DD>
G. Furnas and J. Zacks.
Multitrees: Enriching and Reusing Hierarchical Structures.
In <em>Proceedings of the ACM SIGCHI '94 Conference on Human Factors
  in Computing Systems</em>, pages 330-336, Boston, Ma, April 1994.
<P>
<DT><A NAME=Har75><STRONG>5</STRONG></A><DD>
J. Hartigan.
<em>Clustering Algorithms</em>.
John Wiley and Sons, 1975.
<P>
<DT><A NAME=Ich93><STRONG>6</STRONG></A><DD>
S. Ichimura and Y. Matsushita.
Another Dimension to Hypermedia Access.
In <em>Proceedings of Hypertext '93 Conference</em>, pages 63-72,
  Seattle, Wa, November 1993.
<P>
<DT><A NAME=Joh91><STRONG>7</STRONG></A><DD>
B. Johnson and B. Shneiderman.
Treemaps: A Space-filling Approach to the Visualization of
  Hierarchical Information.
In <em>Proceedings of IEEE Visualization '91 Conference</em>, pages
  284-291, San Diego, Ca, October 1991.
<P>
<DT><A NAME=Mac86><STRONG>8</STRONG></A><DD>
J. MacKinlay.
Automating the Design of Graphical Presentation of Relational
  Information.
<em>ACM Transactions on Graphics</em>, 5(2):110-141, April 1986.
<P>
<DT><A NAME=Mac91><STRONG>9</STRONG></A><DD>
J. D. Mackinlay, S. Card, and G. Robertson.
Perspective Wall: Detail and Context Smoothly Integrated.
In <em>Proceedings of the ACM SIGCHI '91 Conference on Human Factors
  in Computing Systems</em>, pages 173-179, New Orleans, La, April 1991.
<P>
<DT><A NAME=Muk94a><STRONG>10</STRONG></A><DD>
S. Mukherjea and J. Foley.
Navigational View Builder: A Tool for Building Navigational Views of
  Information Spaces.
In <em>ACM SIGCHI '94 Conference Companion</em>, pages 289-290, Boston,
  Ma, April 1994.
<P>
<DT><A NAME=Muk94b><STRONG>11</STRONG></A><DD>
S. Mukherjea, J. Foley, and S. Hudson.
Interactive Clustering for Navigating in Hypermedia Systems.
In <em>Proceedings of the ACM European Conference of Hypermedia
  Technology</em>, pages 136-144, Edinburgh, Scotland, September 1994.
<P>
<DT><A NAME=Neu87><STRONG>12</STRONG></A><DD>
C. Neuwirth, D. Kauffer, R. Chimera, and G. Terilyn.
The Notes Program: A Hypertext Application for Writing from Source
  Texts.
In <em>Proceedings of Hypertext '87 Conference</em>, pages 121-135,
  Chapel Hill, NC, November 1987.
<P>
<DT><A NAME=Par89><STRONG>13</STRONG></A><DD>
H. Parunak.
Hypermedia Topologies and User Navigation.
In <em>Proceedings of Hypertext '89 Conference</em>, pages 43-50,
  Pittsburgh, Pa, November 1989.
<P>
<DT><A NAME=Pit94><STRONG>14</STRONG></A><DD>
J. Pitkow and K. Bharat.
WEBVIZ: A Tool for World-Wide Web Access Log Visualization.
In <em>Proceedings of the First International World-Wide Web
  Conference</em>, Geneva, Switzerland, May 1994.
<P>
<DT><A NAME=Rob91><STRONG>15</STRONG></A><DD>
G. G. Robertson, J. D. Mackinlay, and S. Card.
Cone Trees: Animated 3D Visualizations of Hierarchical Information.
In <em>Proceedings of the ACM SIGCHI '91 Conference on Human Factors
  in Computing Systems</em>, pages 189-194, New Orleans, La, April 1991.
<P>
<DT><A NAME=Rot94><STRONG>16</STRONG></A><DD>
S. Roth, J. Kolojejchick, J. Mattis, and J. Goldstein.
Interactive Graphic Design Using Automatic Presentation Knowledge.
In <em>Proceedings of the ACM SIGCHI '94 Conference on Human Factors
  in Computing Systems</em>, pages 112-117, Boston, Ma, April 1994.
<P>
<DT><A NAME=Utt89><STRONG>17</STRONG></A><DD>
K. Utting and N. Yankelovich.
Context and Orientation in Hypermedia Networks.
<em>ACM Transactions on Office Information Systems</em>, 7(1):58-84,
  1989.
<P>
<DT><A NAME=Wer94><STRONG>18</STRONG></A><DD>
J. Wernecke.
<em>The Inventor Mentor: Programming Object-Oriented 3D Graphics
  with Open Inventor</em>.
Addison-Wesley Publishing Company, 1994.
</DL>
<P>
</BODY>