Local time: Monday, 24-Nov-2008 03:53:18 EST
Last update at /special/conference/apwww95,Friday, 21-May-2004 09:47:28 EST

A Three Dimensional Index Visualizer on World Wide Web

Mansoo Kim
Natural Language Processing Section
Electronics and Telecommunications Research Institute
Korea

mskim@com.etri.re.kr http://p_hpserver1.etri.re.kr/document/mskim/mansoo.htm

Abstract
In this paper, we define browsing objects which can describe various relationships among information structure, and implement a visualization system which will automatically transform index information into the objects. The index information will be described by SGML, which is the standard for the document exchange. Unlike three dimensional viewers, the system focuses on the visualization of the relationships among information structures, and it supports various browsing functions - expanding, shrinking, centralizing, etc.
Keywords
Three dimensional index information visualization, Three dimensional web browser, Information visualization, Information retrieval.

1. Introduction

WWW has recently grown to be the most popular service available on the internet because it supports multimedia presentation and hypertext retrieval under an integrated communication environment. In particular web browsers which enable a user to see interactive multimedia information dispersed on the internet, have made a great contribution to the astonishing growth of WWW. Three dimensional web browsers, which make users experience a virtual reality with three dimensional graphics technologies, are presently appearing on the stage [1, 3]. As computer networks and protocols developed, such browsers will be accepted as standard in the near future. However, despite of all these developments, conventional web browsers can provide only low retrieval efficiency, and weak recognition about information structures because they depend on simple browsing methods.
The most common browsing object supported by web browsers is the linear list. When selecting one item from the anchor's list, a user can move to another list of information ,but can't easily understand the relationship among information structures because of its simplicity. Thus the use of image maps is more recommended, but these are slow to represent dynamic changes to information relationships because large image data should be transmitted from a server to a client whenever any relation is modified. The latest browsing method is to browse the relationships among information structures in three dimensions using a three dimensional web viewer ,which translates the description by modeling languages like VRML or WOOGL into three dimensional objects [6, 10]. However, the methods can't immediately reflect changed values, and support various functions required for effective browsing because current viewers are focusing mainly on data visualization with their attributes, and depending on a data model designed manually. A new browser is needed for displaying exactly the relationships among information structures, not the information itself, and reflecting immediately the updated relationship.
In this paper, we define browsing objects which can describe various relations among information, and implement a visualization system which will transform automatically index information into the objects. The index information will be described by SGML, which is the standard for the document exchange. Unlike three dimensional viewers, the system focuses on the visualization of the relationsips among information structures, and supports various browsing functions - expanding, shrinking, centralizing, etc. In the second section we provide an overview of the system, and in the third section we define several three dimensional objects and their operations. In the fourth section we explain functions for a server to provide index information to clients, and finally we show how the system is implemented.

2. System Overview

The three dimensional index information visualization system is a client-server application. A three dimensional index visualizer on the client's side gets index information from a server, and visualizes the information as a corresponding visual object. Scripts for the index information retrieval on the side of a server get data posted from a client, and send index information or document information, (which are results from querying server's database with the posted data), to a client from a database on the server. Figure 1. shows the overall data flow of the visualization system.
There are three kinds of indices in the system, which are the tree, the network and the timeline as the followings.

Figure 1. The overall data flow of the index information visualization system

Tree
In general, this structure classifies information by subject or purpose. The aim of the structure is to rearrange mixed information using a major concept and a minor concept. It can be used to express hierarchical information such as organizational charts and file directories.

Network
The network is an appropriate structure to visualize the weighted, labeled and many-to-many connected relationships among information structures. This structure can represent various relationships and links among information structures. For example, the network can visualize the relationships among items of a thesaurus, and the hyperlinks to each HTML document.

Timeline
The timeline structure useful in browsing information which can be ordered sequentially. Names may be ordered by alphabetically, articles by the submission time, and historical events by the date of occurrence.

The index document, which includes index information is written by SGML. Its structure is the same for each application - only the content varies. The index visualizer computes geographical information of the index document from a server, and represents it as a visual object, by which a user can travel in information space. The visual object may be a tree, a network or a timeline. The visualizer generates URLs, which practically refer the scripts filling up a gap between a database and a web server, from a user's operation on visual objects, and sends the URLs again to a server through a web browser. The database internally stores tables of HTML documents and index information. The CGI scripts return the results, which may be the tables retrieved from a database by embedded queries, to a client. Of course, the returned index document should conform to the MIME protocol.

3. Three dimensional index information visualization

We may consider three dimensional index information visualization as the process of exchange among three data - a user's input, index documents, and visual objects. A user's input on the visualization module is sent to a server. The scripts on a server then return the index document. The visualization module maps the index document to a visual object. This process may be repeated continuously. In this section, we will define the index document, which includes information about the index structure and content, and the operations on the visual objects. We also explain the processes which connect a URL to the corresponding script, and discuss what data are exchanged between a server and a client.

3.1. Visual objects for three dimensional browsing

First, the index document for a tree object may be described below.
<TreeIDX maxLevel=>
<R> rootNodeName
<Ci type=> childNodeName
</TreeIDX>
<TreeIDX> and </TreeIDX> indicate respectively a beginning and an end point of a tree index description part. An attribute maxLevel in <TreeIDX> has the maximum level of the tree at the left of '='. <R> tag describes a root node, and <Ci> a child node in i level. The attribute type has a value indicating whether the node is a terminal node or not. The following description is about the index document of a network object.
<NetworkIDX maxDepth= enabledRelations= thresholdWeights= >
<C> centralNodeName
<Ri relation= weight=> relatedNodeName
</NetworkIDX>
<NetworkIDX> and </NetworkIDX> indicate respectively a beginning and an end point of a network index description part. An attribute maxDepth in <NetworkIDX> has the maximum depth of the network index, and the pair of other two attributes - enabledRelations and thresholdWeights - includes the relations and their least weights enabled within the network index. An attribute <C> indicates that this node is a central node in this network, and <Ri> a node of level i. An attribute relation has the relation between a node and the central node, and weight the node's weight. As for the above descriptions, we can also define an index document of a timeline.
<TimelineIDX>
<L start= end= interval=>
<E start= end=> eventName
</TimelineIDX>
<TimelineIDX> and </TimelineIDX> indicate respectively a beginning and an end point of the timeline index description. start , end, and interval attributes, which are in <L> indicating the properties of a basis, have respectively a starting point, an end point, and the interval of the basis. <E> describes an event that occurred between the value of start and the value of end in <L>. start and end attributes in <E> indicate the period of the event. After parsing, each index document above is showed to users as the following:

(a) a tree visual object

(b) a network visual object

(c) a timeline visual object
Figure 2. The three dimensional visual objects
There are some operations on a tree object, which are expanding nodes, and rotating a tree or a level of a tree. Expanding is needed to retrieve future information into lower levels, and rotating to makes clear what nodes are in the level. The relationships and link between types of information should be visualized in the network visual object. We can distinguish the relationship from other relationships by a link-line type, and an adjacency by a link-line length. For example, a shorter length may represent a more related relationship. The operations which repeatedly expand a node to other related nodes, and locate a node on the center of the screen are supported by a network visual object with the same causes as respectively expanding and rotating on the tree object. Nodes at the same order can be located at different positions in three dimension at a timeline object. If an event in the timeline object has a period, then it may be arranged according to the starting point. The operation expanding the global period in the background is required to fetch more index documents from a server. All of the visual objects support general graphics operations, such as rotation, translation, zooming, and so on.

3.2 Information exchange between a client and a server

A URL for a retrieval query is generated when a user clicks or moves nodes on visual objects. The retrieval query is then processed by scripts. The results, which are the list of HTML documents or index documents, will be returned and visualized in three dimensional objects. The graphics operations such as rotation, zooming, and translation of a visual object are performed without communication between a server and a client, but the operations which expand the node should get the information documents from a server. The visualization part on a client again updates the visual objects with the information document returned by CCI. Scripts related to the visualization on a server play a role in analyzing the posted data, get the information of indices and HTML documents, and return the document of MIME type through CGI. The procedure of information exchange to each visual object is as follows:

The procedure of visualizing information of a tree index
Clicking a specific node invokes the operation which gets child nodes of it, in other words, an index document for nodes in next levels from a server. The operation sends a URL, which refers to the corresponding script, to a server with some information through CCI to a web browser. The posted data includes the clicked node's name (r), which informs a server what a root node of the nodes to be expanded is, and a level of the tree (i), which a server returns nodes within. The script analyzes the data, gets an index information for child nodes to the level i from the root node (r) from a database, and returns an index document of MIME type by CGI. Through a three dimensional index visualizer, the returned index document is appended below the clicked node of the tree object displayed previously. If the clicked node is not a nonterminal node, a web browser shows the list of HTML documents related to the node name by the natural language processing or the keyword processing.

The procedure of visualizing information of a network index
The procedure whereby nodes are related directly to the clicked node is the same procedure as that of the tree. The posted data includes a clicked node's name c, pairs of a relation type and its least weight (r, w) enabled, and the depth of the network object (d), which a server returns nodes expanded to. The script analyzes the posted information, gets an index information , which should include the nodes below the depth (d) beyond the least weight w with relations (r ) enabled, from a database, and returns an index document converted to MIME-typed document to a client by CGI. Because nodes in the visual object can not be discriminated from each other like the case of a tree object, users should perform a different operation from that of getting an index document in order..

The procedure of visualizing information of a timeline index
Information exchange between a server and a client in a timeline object is the same as that of the two above. Just posted data and user's interactions are slightly different from the others. When a user wants to see more items than those listed now, he or she can generate a URL with the expanded interval using a simple input. For example, the input operation may be the operation dragging a mouse beyond the current boundary. The script then returns the index document of MIME type which includes all nodes within the interval from a database. When a user clicks a specific node, the list of HTML documents related to the node will be displayed on a web browser.

According to each visual object, there exists proper user's inputs and a URL with it. At the point of overall view we however know that the information exchange between a server and a client is achieved through CCI and CGI.

4. Implementation

The system has been implemented as a prototype of the multimedia information retrieval system. The server platform is a Windows NT 3.5 Server on Pentium, and the client platform is a Windows NT 3.5 Workstation on Pentium. The system uses a HTTPS for Windows NT as a web server, and Netscape Navigator for Windows NT as a web browser. The system adopted NCAPI implemented by DDE for the communication between a Netscape Navigator and a three dimensional index visualizer, and CGI for HTTPS as a gateway between a web server and an Oracle DB [2, 5]. The information of encyclopedias, technical memos , and articles have been stored in the database. Further, there are the information of indices for natural language processing, the index information of browsing, and dictionaries [8]. The system has adapted the tree object to a topic tree, the network to a keyword network, ant the timeline to historical table.

4.1 A three dimensional index visualizer

The three dimensional index visualizer is a client application resulted from the implementation process of the visualization system. It is an information browser which analyzes an index document, and browses the information using three dimensional objects. The visualization methods and visual objects proposed in the paper have been implemented in this browser. Figure 3. shows the structure of the index browser.

Figure 3. The structure of the three dimensional index browser
The three dimensional index visualizer can fetch an index document, which had been edited stand-alone by a SGML editor [4, 7], directly from a local site, or a remote index document, which had been generated by scripts, through a web browser by DDE from a server. The MIME type of an index document has been defined as application/x-index. Major DDE topics - WWW_RegisterViewer, WWW_UnregisterViewer, WWW_OpenURL and WWW_ViewDocFile - have been used for DDE conversations. An index parser, which has been implemented using a SGML parser, extracts necessary information from an index document, and sends it to a visualization module. The visualization module has been programmed by APIs for three dimensional index information visualization. The module for processing user's inputs evaluates the mouse operation, and generates a URL referring a script on a server. A post method has been used as the request method. We have implemented the graphics operations - rotation, zooming, translation, etc.

4.2 APIs and scripts for three dimensional index information visualization

APIs for three dimensional index information visualization have been implemented by OpenGL built in Windows NT 3.5. An application programmer can write a specific browsing application easily using the APIs. The APIs may be divided into three categories, which are APIs to set common values, APIs to generate a starting node, APIs to add or delete nodes , APIs to perform graphics operations, and APIs to fetch the document for indices or HTML documents. (a) in Table 1. shows APIs related to the visualization.

(a) APIs for the visualization

(b) Scripts for the visualization
Table 1. APIs and scripts for three dimensional index information visualization
The CGI scripts to support the retrieval for index information return index documents or HTML documents after querying with the input data of FORM type from a web browser to a database. The CGI scripts should call interface functions to DB and functions for MIME-typed document generation. There are scripts to return index documents, the list of HTML documents, and HTML documents. (b) in Table 1. shows the scripts in the system.
When an API for loading documents has been operated, it is determined which kind of scripts are called, depending on the document type to be loaded.

4.3 An example

Here is an example. Firstly, a user can query the events between time a and time b by entering the period in a form. expandList then analyzes the URL, and produces the document below from the index information, which was fetched from an Oracle DB.
<TimelineIDX>
<L start=1901 end=1920 interval=10>
<E start=1942 end=1942> The Midway Sea Battle
<E start=1942 end=1945> The Pacific War
<E start=1943 end=1943> The Cairo Declaration
<E start=1945 end=1945> The Potsdam Declaration
<E start=1945 end=1945> The Birth of the United Nations
<E start=1946 end=1946> The Paris Peace Talks
<E start=1947 end=1947> The Independence of India
<E start=1955 end=1955> The Bandung Meeting
</TimelineIDX>
The index parser gets the document from a netscape navigator through DDE, and sends the parsing result to the visualization module. The module then translates the parsing result into a proper three dimensional object. Figure 4. shows the browsing object according to a historical table. A user may expand the period with dragging the mouse beyond the current boundary, which will call again expandList with the expanded period as arguments. He or she also can retrieve the list of HTML documents related to the clicked event. Clicking a event invokes getDocumentRelatedList.

Figure 4. An example of index visualization

5. Conclusion

We have described the method for three dimensional index information visualization and implemented the visualization system in the paper. We have proposed three dimensional visual objects for efficient browsing, and showed the method for realizing the visualization on WWW, which is a client-sever environment, and implemented a three dimensional index browser, APIs and scripts for visualization as the results.
The commercial web browsers on WWW have represented much information in two dimensions and support only simple browsing methods. To overcome such a limitation the research for a three dimensional viewer is in progress. However, the research topic has been only about the addition of the hyperlink to conventional three dimensional data modeling tools. We need browsers more specific to information browsing [9]. The three dimensional index information visualization system implemented here represents various relations among information into three dimensional objects and provides the means for a user to retrieve the information more intuitively. APIs for visualization can also be used in developing another system which is designed not to model data themselves but to visualize the relationships among data, and to represent dynamic information because it provides the automatic generation of visual objects from index documents, and exchanges small data with a server.
At present, we are developing more three dimensional visual objects dedicated to information retrieval. The current research topic is to design a method which can automatically represent semantic relations in three dimensions. An example of such a visualization is to represent the semantic precedence among events occurring in newspapers but not according to the simple order of time. We also give attention to intercommunication among visual objects. We will expand visualization of index information on a server to several servers, and consider the interface with VRML. We will develop a three dimensional index information visualization system for a complex electronic library, which will soon be implemented in our laboratory.

6. References

[1]
Clay Graham: "Database Visualization and VRML", http://reality.sgi.com/employees/clay/article/article.html.
[2]
David Robinson: "The WWW Common Gateway Interface Version 1.1", http://www.ast.cam.ac.uk/%7Edrtr/cgi-spec.html.
[3]
Ed H. Chi: "Webspace Visualization", http://www.geom.umn.edu/software/weboogl/webspace/.
[4]
Eric van Herwijnen: Practical SGML: Second Edition, Kluwer Academic Publishers, 1994.
[5]
Garrett Arch Blythe: "Netscape's DDE Implementation", http://home.netscape.com/ newsref/std/ddeapi.html.
[6]
Gavin Bell, Anthony Parisi, and Mark Pesce: "The Virtual Reality Modeling Language : Version 1.0 Specification", http://vrml.wired.com/vrml.tech/vrml10-3.html.
[7]
Heekuck Oh, Dongsee Choi, Miseon Jun, and SeYoung Park: Design and Implementation of a Markup Editor for an Electronic Book System, pp.383~388, May, 1995.
[8]
HyunKyu Kang, ChangYeol Lee, HoWook Jang, and SeYoung Park: "An implementation of an automatic keyword extraction system", pp. 163~166, May, 1994.
[9]
Takuji Imai: "The Next-Generation User Interface: From GUI to Mutimodal", NIKKEI Electronics Asia, September, 1992.
[10]
Tamara Munzner, Paul Burchard, and Stuart Levy The Geometry Center: "WebOOGL: Integrating 3D graphics and the Web", http://www.geom.umn.edu/software/weboogl/.

[Return to Table of Contents]
COPYRIGHT © 1995 by AUUG95 and APWWW95 Charles Sturt University. ALL RIGHTS RESERVED.