Accessing hyperdocuments through interactive dynamic maps.
We propose a new navigation paradigm based on a spatial metaphor to help users access and navigate within large sets of documents. This metaphor is implemented by a computer artifact called an Interactive Dynamic Map (IDM). An IDM plays a role similar to the role of a real map with respect to physical space. Two types of IDMs are computed from the documents: Topic IDMs represent the semantic contents of a set of documents while Document IDMs visualize a subset of documents such as those resulting from a query. IDMs can be used for navigating, browsing, and querying. They can be made active, they can be customized and they can be shared among users. The article presents the SHADOCS document retrieval system and describes the role, use and generation of IDMs in SHADOCS.
INTRODUCTION
According to many authors, disorientation is a major
problem in hypertext systems:
-The biggest problem in hypertext, which most of us
admit in footnotes toward the end of papers extolling
the virtues of our systems, is of getting lost.-
Permission to copy without fee all or part of this material is
granted provided that the copies are not made or distributed for
direct commercial advantage, the ACM copyright notice and the
title of the publication and its date appear, and notice is given
that copyright is by permission of the Association for
Computing Machinery. To copy otherwise, or to republish,
requires a fee and/or specific permission.
One reason for getting lost in a hypertext system is the
large quantity of information that is accessible. Another
reason is the complexity of the graph that links the
different documents. One can get lost in a small
hypertext system if the number of links is large.
In the results of a user study, [Nielsen90] reports :
-56% [of the users] agreed fully or partly with the
statement: when reading the report I was often
confused about where I was. 44% agreed with the
statement: when reading the report I was often
confused about how to get back where I came from.-
In this paper, we propose a new paradigm based on a
spatial metaphor to help users access and navigate within
large sets of documents. We use an Interactive Dynamic
Map (IDM) to implement this metaphor. Just as a real
map is a concise, abstract representation of a large
territory, an IDM is a concise, abstract representation of
a large set of documents. Real maps take advantage of
the ability of the human brain to memorize and manage
spatial information. Similarly, we expect IDMs to
facilitate the navigation in a large set of documents and
reduce the "lost in hyperspace" syndrome.
The paper is organized as follows. We first describe
previous work on this topic. We then present the rationale
for our approach, give an overview of the prototype
system we are developing and describe the various types
of navigation that it offers. Next, we provide a more
detailed description of IDMs and then present the results
of a sample use of the system in the next section. We
conclude with open problems and future work.
Many researchers have investigated the navigation
problem in hypermedia systems. Early research led to
techniques and design strategies for finding the proper
structure of a hyperdocument. Most attempted to reduce
the graph structure to a hierarchical or semi-hierarchical
structure and differ primarily in the stage at which the
structure of hyperdocuments is made hierarchical (or
semi-hierarchical). While some authors suggest that
hypertext designers choose this structure at the design
stage of the hypertext [Meyrowitz86, Acksyn88], others
suggest that existing hypertext documents with complex
underlying structures can be transformed into hierarchical
hypertext. Experimental techniques that provide the
necessary automatic transformation have been proposed
in [Rivlin94], based on some critical measures of
hypertext systems [Shneiderman92]. Other techniques are
based on the aggregation of nodes [Crouch89].
Another body of research led to visual tools such as
overview diagrams or maps that help users navigate
through complex hypermedia structures [Halasz87,
Yankelovich88]. Other works have extended maps by
providing footprints [Bernstein88], which help users know
where they are, where they come from and where they
can go.
Although the purpose of overview diagrams was to help
users navigate a complex hypertext, most research was
conducted on hierarchical structures or on restricted
substructures. For example, Notecards [Halasz87]
automatically provides tree diagrams while Intermedia
automatically provides local overview
diagrams of the current node and the links adjacent to it.
In other systems, e.g. [Nielsen90], overview diagrams that
display more complex graph structures are hardcoded. In
a user study of the navigation problems in Nielsen's
hypertext, Foss [Foss89] concluded that the overview
diagrams would have been much more helpful if they had
been designed more carefully.
Unfortunately, designing good overview diagrams for
complex structures has proven to be very difficult.
According to [Bernstein91]:
- . while visualization tools have made great
progress toward representing hierarchical structures,
the representation of more complex webs has proven
to be much more challenging. Visualization
approaches depict regular hierarchies well but are
much less effective at revealing regular structures in
more complex hypertext webs.-
Furthermore, most overview diagrams do not share
conventions or common features. In fact, to our
knowledge, few guidelines have been developed for
designing maps for complex hypertext structures.
Large hypermedia are likely to be changing constantly in
structure. As a consequence, hard-coded maps are
inappropriate and hierarchical structures are too
constraining with respect to the concepts and paradigms
of hypertext. In contrast, well-designed overview
diagrams can be of great help to users [Bernstein91], not
only for navigation but also for querying. Since designing
maps for complex hypertext structures is a cumbersome
task when the number of nodes grows, and since it is hard
for designers to provide maps that fit all users, we
propose to automatically compute approximate maps of
complex webs of documents. These maps are interactive
and can be customized by the users.
3.1
SHADOCS (SHAring DOCument System) is a prototype
of a graphical interface between one or more users and
one or more information sources. It combines information
retrieval techniques with visualization and interaction
techniques in order to facilitate tasks such as the
indexing, retrieving and filtering of information by one or
several users. SHADOCS uses Interactive Dynamic Maps
(IDMs) as the central mechanism to support these tasks
and to access and navigate the information space.
The interaction model in SHADOCS is based on a
metaphor of navigation in the real world. A collection of
documents is considered to be a territory that contains
resources (documents and topics) and maps of these
territories can be drawn. Since these maps are computer
artifacts, they offer more possibilities than those of the
real world:
. users lost in hyperspace can always find a map
showing where they are, where they came from and
where they can go;
. maps can change dynamically as new documents are
added to the web;
. maps support navigation, querying and browsing
through direct manipulation;
. maps can be customized, stored, and reused. This is
very useful for extensive search tasks, which are often
interrupted: the map can be stored at any point in the
navigation and reused at a later time when the user
wants to resume;
. maps can be shared among a group of users. This is
valuable when several users share a common interest
since they can customize a common, shared map.
We have adapted real-world conventions about the
design of geographical maps to meet our needs. Maps are
made up of regions, cities and roads. SHADOCS uses
these features to convey information about the structure
of the web. For example, a region represents a set of
documents and the size of a region reflects the number of
documents in that region. Similarly, the distance between
two cities reflects the similarity relationship between
those two cities. Thus, in maps where cities represent
documents, if two cities are close to each other, then the
documents have similar or strongly related contents.
Unlike other systems that use maps or overview
diagrams, we have taken advantage of such features of
real maps. For example, real maps fill the space
available, according to certain information. In SHADOCS
uses a space-filling mechanism in a similar way, as a
basic design function.
Time invariance is another important aspect of real maps.
Although a map of a given territory may change over
time, the changes are local: the overall look remains the
same. Human spatial memory takes advantage of this to
store information efficiently. Maps used in overview
diagrams should therefore remain stable over time,
otherwise the spatial metaphor would fail.
3.2 System architecture

Figure

1 shows the architecture of SHADOCS. At the
heart of the system is the IDM library which stores IDMs.
The engine computes maps from the documents stored in
the different document sources (described in the
implementation section). The IDM editor acts as the
interface between the system and the users, who can
view, customize and store IDMs in the library. Users can
also issue queries that are sent to the interpreter to
create new maps. The interpreter is also used to
implement active maps by regularly querying the
document sources.
The interface to the document sources accesses the
documents themselves. Since documents may be stored
in various formats and may be accessible through various
protocols (e.g. WAIS, Gopher, World-Wide Web, FTP),
this component shields SHADOCS from dependencies on
the document sources.
The prototype system being developed is implemented
with the O2 object-oriented database management
system [O2, Delobel91]. We have used a local O2
database in this prototype to act as the interface to the
different document sources. We are also developing
interfaces to remote document sources.
An Interactive Dynamic Map is a document that provides
a global view of either a set of documents or the
semantic contents of a large collection of documents.
Interpreter Engine
Interface to the document sources
IDM Library
IDM Editor

Figure

- The architecture of SHADOCS
Users can use IDMs to issue queries and to
navigateamong thedocuments. IDMs are active: they are
automatically created and dynamically updated from sets
of documents. Furthermore, IDMs are interactive: they
act as the interface between users and documents.
Finally, IDMs are customizable: they can be stored for
re-use in a library that is shared by a group of users. This
encourages users to collaborate on the usual information
retrieval tasks (indexing, searching, filtering, etc.
We have defined two kinds of IDMs: Topic IDMs
represent the semantic contents of a large collection of
documents, and Document IDMs display and allow
access to subsets of documents.
Topic IDMs (figure 2) provide an overview of the topics
represented in a collection, their importance, and
similarities or correlations among them. The areas of the
map are the classes of an intermediate thesaurus. Each
class contains a set of topics represented by cities on the
map and depicted by icons. Roads between cities
represent relationships between topics.

Figure

2: Topic IDM

Figure

3: Document IDM
Topic IDMs provide an overview of a large number of
documents by extracting semantic information from them
rather than displaying the documents themselves. Users
can issue queries by selecting regions, cities and roads of
the map. The result of the query is displayed in a
Document IDM.
Document IDMs (figure collections of
documents either generated automatically from a user
query or gathered manually by a user or designer. Unlike
Topic IDMs, the cities of these maps are documents.
Cities are laid out such that similar or highly correlated
documents are placed close to each other. The size of a
city reflects its importance with respect to a given
criterion, which varies according to how the map was
created. If the map gathers documents resulting from a
query, document importance (and therefore city size) is
computed as the relevance of the document to the given
query. If the map contains documents that were gathered
manually by a user or designer, document importance is
the subjective importance given by the users.

Figure

4: Fisheye View of a Document IDM
4.1 Using IDMs
The first role of IDMs, described above, is to visualize
the contents of a set of a document in a synthetic way.
The second role of IDMs is to support interactive
document retrieval tasks. Traditional systems have
supported retrieval tasks in a rather conversational way:
the user issues a command and the system processes that
command and displays a result. Such an approach might
suit users who are familiar with both the set of documents
and the subset they are looking for. But most retrieval
tasks are less deterministic and require a trial and error
approach. The second-person nature of conversational
systems does not encourage trial-and-error usage because
of the difficulty of specifying commands and slow
response time.
We believe that a first-person approach facilitates the
exploration of a web of documents because users feel
more engaged and more in control of the system. IDMs
support two forms of interactive navigation, browsing and
querying, which are achieved by direct manipulation of
the maps. IDMs also support customization, which aids

Figure

5: Semantic Scaling of a Document
navigation tasks and increases the
sense of engagement by the users.
4.2 Browsing
Browsing allows users to explore an
unknown set of documents or when
they don't know how to describe
what they are looking for. We
found t ha t brows i ng w
SHADOCS requires several levels,
akin to using maps at various
scales. Large scale maps provide
an overview at the expense of
detail, while smaller scale maps
provide increased detail at the
expense of context. Fortunately, computer-generated
maps provide more facilities than traditional paper maps.
The scale can be defined by the user, and it can vary for
a given map over time (e.g. zoom) and space (e.g.
fisheye views [Furnas86]).
We have identified three levels of browsing: the wide
browsing level uses semantic fisheye views, the medium
browsing level uses a semantic zoom, and the narrow
level uses multiple windows.
4.2.1 Semantic fisheye views
The wide browsing level is intended for fast scanning
over the web of documents. Few details are shown about
the items except for those under the focus area, which
displays more detail. To achieve this, we use fisheye
views and scaling (see figure 4).
Fisheye view transformations make it possible to
increase the size of parts of the map without losing the
remaining items. With such a transformation, the position
and size of each item is computed from the normal view,
the distance between the focus and the given item and its
a priori importance [Sarkar92]. The initial layout of the
map serves as the normal view and initial sizes of items
serve as their a priori importance. The focus is set at a
position defined by the user. Ideally, the focus should
follow the mouse pointer but our current software and
hardware platform does not support interactive response
time.
We combine the fisheye view transformation with a
semantic scaling transformation: the type of information
that is visible for a given item varies with the size that
was computed by the fisheye transformation for that item.
For example (see figure 5), an item with a small display
size shows a name and icon, while the same item with a
larger display size shows the first few lines of the
document. With a medium display size, the item shows a
more detailed icon and additional information such as its
relevance.
4.2.2 Semantic zoom
The medium browsing level is intended for more detailed
exploration. To achieve this, we allow users to zoom in
on items of interest. Unlike the fisheye view, the
traditional zoom reduces the level of context but enables
the user to see a larger number of items in greater detail.
Here too we use the scaling mechanism that reveals
various levels of detail according to the display size of
each item. The display size of an item depends on its a
priori size and the current zoom factor.
4.2.3 Multiple windowing
The narrow browsing level is intended to provide fine-grained
views of individual items. To achieve this, we
use multiple windows to display the full details about any
item in the map. Unlike other browsing levels, the map is
left unchanged. This allows users to view a complete
document (for Documents IDMs) or the detailed
information about a descriptor (for Topic IDMs) while
still viewing the map itself.
Users can easily compare the contents of multiple
windows, leaving them open for further reading or closed
(i.e. represented by an icon) for further access. Most
often, users classify their windows and reflect this
classification in the spatial organization of windows and
icons on the screen. Foss [Foss89] reports an experiment
with Notecards in which spatial organization helped users
localize information on the screen and window location
often acted as a reminder. Our spatial interaction
paradigm should be of similar benefit to users.
4.3 Querying and customizing
Fox et al. [Fox91] have established that querying is
useful for navigation. SHADOCS treats it as a form of
navigation and differs from most other systems by
integrating querying and browsing in the same framework.
Queries can be issued by selecting items directly on
Topic IDMs and Document IDMs. The selected items
are translated into a real query that is sent to the web of
documents through the SHADOCS interpreter. This
results in a subset of documents for which a Document
IDM is computed and displayed. Both regions and cities
can be selected. A query is represented in the system by
a vector is the number of
descriptors known. Each x i is 1 if descriptor D i is among
the selected items of the map, 0 otherwise. For a Topic
IDM, the descriptors D i correspond exactly to the
selected items: cities represent descriptors and regions
represent sets of descriptors. For a Document IDM, the
descriptors D i correspond to the selected documents on
the map. This query technique corresponds to a
mechanism also known as query-by-example, which
provides a useful extension to query languages for
information retrieval [Stanfill91, Khale89].
We consider that customization, like querying, is an
integral part of navigation. Customization allows users to
suit the map to their needs and taste: the layout of a map
can be changed with traditional editing commands, and
annotations of various kinds can be added. Customization
helps users localize themselves: annotations act as
landmarks that users remember and recognize easily. For
example, readers mark their own paths, annotate items,
add post-it notes, etc. These annotations then serve as
clues during further navigation by the owner of the map
as well as other users. This latter aspect is emphasized
by the fact that IDMs can be shared among users.
SHADOCS also uses customization to implement active
maps. A document resulting from a query can be made
active. This means that the document is re-computed at
regular intervals from the initial query, therefore tracking
changes in the web and filtering them.
5 IMPLEMENTATION
This section describes the most important aspect of the
implementation of SHADOCS, namely the automatic
computation of the Interactive Dynamic Maps. This
computation is based on full-text analysis of documents
and is carried out by SHADOCS' engine.
5.1 Information retrieval techniques
The computation of IDMs is based on a set of information
retrieval techniques known as full-text analysis. Most of
these techniques consist of representing documents and
keywords by vectors. The coordinates of document
vectors are computed from the set of keywords and the
coordinates of keyword vectors are computed from the set
of documents, as follows: coordinate x i of document D is
was found in D and 0 otherwise.
Reciprocally, coordinate x i of the vector representing a
keyword T is 1 if the document D i contain T and 0
otherwise. More complex formulas for computing these
vectors can be used (see for example [Salton83] or
[Larson92]).
Correlations among documents, correlations among
keywords and the relevance of documents to keywords
can be computed from these vectors. The basic idea is
that if two documents are similar, their vectors are
similar. One measure of the similarity between two
vectors is the cosine of the angle between those two
vectors: collinear vectors have a zero angle and thus a
cosine of 1, while orthogonal vectors have a 90 degrees
angle and therefore a cosine of 0. The cosine in turn can
be computed from the scalar product. Various measures
and computation techniques exist [Salton83,Larson92].
5.2 Computing a Topic IDM from a web of
documents
In this section we briefly describe the algorithm that we
have developed for the automatic generation of Topic
IDMs (more details can be found in [Zizi94]). Topic
IDMs are generated in two steps: generating the
intermediate thesaurus structure and mapping the
structure of the thesaurus into an IDM.
5.2.1 Computing an intermediate thesaurus from the
web
The first step in generating a Topic IDM consists of
creating a thesaurus. The thesaurus is a set of topics or
ors (i.e. terms and expressions selected to
describe the subjects of the documents) that are
correlated and organized in classes. It is obtained
automatically by applying full-text analysis to a web of
documents and applying clustering techniques to the
resulting set of descriptors.
The SHADOCS clustering strategy is based on a dynamic
clustering technique [Diday82]. This requires the
computation of similarity between pairs of descriptors.
The similarity between two descriptors T k and T h is
computed as follows [Salton83]:
where t ik is the frequency of descriptor T k in document
D i and n is the number of documents in the web.
The dynamic clustering computes a set of classes A 1 ,
of the thesaurus that define a partition {A 1 ,
each A i contains a set of descriptors (p
is a user-settable parameter that defaults to 12). The
computation starts with an arbitrary partition {A 1 ,
improves it incrementally until it reaches
stability. At each step, the partition is improved by
computing the distance for each element of each class A i
(based on the correlation formula) between the document
and the centroid of its class and by comparing it with the
distance between the document and the centroids of the
other classes. If the element is found to be closer to the
centroid of another class, it is moved to that class and
the centroid of this class is re-computed.
Creating the thesaurus is computationally expensive.
However, the thesaurus need only be created from
scratch once. It can then be updated incrementally when
documents are added to the initial web. When the
number of documents is large, it is unlikely that a new
document changes the classes of the thesaurus. Hence
the cost of adding a new document can be reduced to the
cost of re-computing the correlations. A full re-computation
of the classes can be done when a larger
number of documents have been added. Experiments with
various bodies of documents show that, in most cases,
the dynamic clustering converges in a few iterations
(typically 5 or fewer).
5.2.2 Laying out items and areas in Topic IDM
The second step in generating a Topic IDM consists of
making the thesaurus and its structure visible. A Topic
IDM will then provide a graphical display of the
thesaurus, giving an overview of the semantic
information extracted from the web of documents and of
its structure.
A Topic IDM consists of regions corresponding to the
descriptor classes A i and cities corresponding to the
descriptors. Regions and cities are laid out to reflect the
importance of the topics they represent within the
collection. The size of a region is proportional to the
importance of the descriptors it contains and also
depends on its relative importance in the collection. The
importance of a descriptor is defined as the number of
documents that contain this descriptor.
The regions of a Topic IDM are rectangles {R 1 ,
that represent the classes {A 1 , A 2 ,.,A n } of
the thesaurus. Each class A i has an importance u i that is
the sum of the importance p k of the descriptors it
contains:
such that T k is in A i
Each rectangle R i is identified by the coordinates of its
its width and height (W i ,
The rectangle that represents the whole map is
referred to as R. X top and Y top are the coordinates of its
upper-left corner and W and H are its width and height.
Our algorithm successively lays out the rectangles R i in
the rectangle R. At each step the algorithm computes X i ,
. the area covered by R i , that is A (R i
proportional to its importance u i . In other words, we
have
. the aspect ratio of R i defined as
(R
is as close to 1 as possible, i.e. R i looks more like a
square than a thin strip. This is because we have to
lay out cities inside R i .
At each step, the part of the rectangle R that is still
uncovered is a rectangle R rest . The algorithm computes
the width, height and top-left coordinates for the
rectangle R i that represents the next class A i that has not
yet been processed. This layout is obtained by cutting
either the width or height of R rest proportionally to the
size of A i . If the aspect ratio of the resulting rectangle is
too different from 1, A i is gathered with A i+1 , A i+2 .
A i+k until the aspect ratio of the corresponding rectangle
is satisfying. In this case the algorithm is called
recursively on rectangle R i with classes {A i+1 , A i+2 .
A i+k }.
Once the regions are laid out, we can lay out icons
representing the cities in the regions. In a Topic IDM,
each city represents a descriptor of the thesaurus; the
importance of the city reflects the number of documents
to which the descriptor is assigned. A threshold value e
can be defined by the user in order to control the
importance of the descriptors to be displayed. The set V i
of icons representing descriptors T k that appear on the
map in a region A i is defined as follows:
{ T k in A i such that p k > e}
The icons representing descriptors in V i are laid out in
the rectangle R i such that the most important city is at
the center of the rectangle and other cities are laid out on
ellipses according to their importance. The coordinates of
the center of rectangle R i and hence the position of the
biggest city are:
The other cities are laid out on ellipses centered at (X
a
with such that v k is in V i
Hence the coordinates of city v k are:
with q k varying according to the number of cities so as to
obtain a spatial distribution.
Finally, the routes of the map represent pairs of
descriptors whose correlation is higher than a given
threshold.

Figure

2 is a hard-copy of a Topic IDM computed by the
algorithm outlined above. Each class corresponds to a
rectangle. The main descriptor of each class has been
highlighted. The figure clearly shows that descriptors in
the same class are more correlated than descriptors in
different classes, which demonstrates the effectiveness of
the dynamic clustering.
The layout of the IDM is computationally efficient.
Therefore, the overall cost of the generation of a Topic
IDM is the generation of the thesaurus and, more
precisely, the dynamic clustering part.
5.3 Computing a Document IDM
In a Document IDM, cities are documents that are
represented by icons. The documents may be the result of
a query or they may have been selected manually by the
users or the designers. The map is drawn according to the
following conventions:
. Roads between cities correspond to special
relationships between the documents represented by
the cities, e.g. "comment", "contains reference to", "to
be read before". In particular, they can be the links of
a traditional hypertext system.
. Cities representing similar documents are laid out
close to each other on the map while cities
representing very different documents are laid out far
away from each other.
. The size of the icon depicting a document reflects its
importance according to either its relevance to a
given query or its subjective importance as set by
users or designers (depending on the origin of the
map).
The main difficulty in achieving this layout is to reflect
the similarity between documents as distances on the
map. We have adapted a general algorithm for laying out
graphs [Kamada89]. This algorithm maps the graph into a
physical system made of particles and springs. Each node
is mapped to a particle and a spring is set between each
pair of particles. The strength and default length of each
spring depends on the length of the shortest path between
the two nodes corresponding to the particles it is attached
to. A spring corresponding to nodes that are directly
connected in the original graph has a unit length and a
strong strength. Springs corresponding to non-directly
connected nodes in the original graph have a longer
default length and a weaker strength. The layout of the
nodes correspond to the positions of the particles when
the spring system is in a stable state. The algorithm first
initializes the positions of the particles and then
computes the energy of the system. It then decreases the
energy step-by-step, by moving the particle with highest
energy to a stable position. When the energy of the
system reaches a minimum, the algorithm stops. We
have added an optional final pass that moves the nodes
so as to avoid or minimize the overlap of the icons
representing the cities.

Figure

3 shows a Document IDM computed with this
algorithm. While the layout of a Topic IDM is
computationally efficient, the algorithm used here to lay
out Document IDMs is expensive, especially for the first
layout. We have not focused yet on performance issues,
but we expect to improve performance by giving better
initial positions to the nodes, since this dramatically
improves the efficiency of the layout algorithm.
6 RESULTS AND LESSONS LEARNED
In order to evaluate the effectiveness of IDMs for
exploring document sets, we have put a set of Unix
manual pages in SHADOCS. We have taken 62 manual
pages for commands of the X Window System
[Scheifler86]. We used a relatively small set of
documents in order to better control, understand and
analyze the results.
The manual pages contain 70008 words of which 6055
are different. Full-text analysis of these documents
produced 131 descriptors and 398 links that were
gathered into seven classes by the dynamic clustering.
They were obtained by removing empty and small words
and words that are not significant with respect to the set
of documents.
The descriptors represent 0.18% of the total number of
words and 2.16% of the number of different words. The
links represent 4.67% of the links of a totally
connected graph. Figure 2 shows the global Topic IDM
representing this set of descriptors.
The first observation is the large number of descriptors,
especially when considering the number of documents.
This is actually an effect of using a small set of
documents. With a larger set, the proportion of different
words drops because an average vocabulary is limited to
a few thousand words. Still, too many descriptors presents
a potential problem, and we need to improve the quality
of the full-text analysis.
One important issue is descriptors that are compound
expressions instead of single words (e.g. "window
system", "user interface"). Techniques exist to identify
them [Salton83,Bourigault92], which we need to
integrate.
The second observation is the quality of the dynamic
clustering. The classes are quite significant with respect
to the contents of the documents. An important parameter
appears to be the number of classes of the partition. It
might be the case that this parameter is less important
when the number of descriptors grows. Figure 2 was
computed with seven classes because the default value
(12) resulted in classes that were not significant enough,
because of their small size.
The last observation is the importance of interaction. The
ability to edit and customize maps contributes to a better
understanding of the set of documents. For example,
moving items allows users to make the display more
pleasing and at the same time gives them a better sense
of the dependencies between items. This encourages
exploration by trial and error, which in turn is supported
by the navigation features. At the same time,
disorientation is reduced by the possibility to set
annotations and landmarks and by the fact that the
display is quite stable.
7 CONCLUSION AND FUTURE WORK
As more and more documents become available
electronically, the problem of accessing this information
becomes more and more crucial. Everyone who has used
a system such as the World-Wide Web has experienced
the frustration of knowing that so much information is
available and yet not being able to get a sense of it or
how to access it.
We believe that the solution to this problem will come
from a combination of computation, visualization, and
interaction: representations of the contents of documents
will be computed from the documents themselves,
visualized on the screen and used to navigate and query
interactively the system. As described in this article, we
have started to investigate this approach with SHADOCS
and have obtained encouraging results.
The first direction for future work is to improve and
extend the system: the computation of IDMs should use
more advanced techniques, especially for the
construction of the thesaurus; visualization could be
improved with better layout algorithms and maybe the
use of 3D; interaction requires faster response time.
The second direction for future work is to conduct user
testing in a real setting in order to evaluate the
effectiveness of the approach and tune various
parameters of the system.
The third direction for future work will expand this
approach to include multimedia as well as text
documents. The main problem here will be the automatic
identification of descriptors. As a starting point, image
analysis and signal processing techniques can be used to
identify meaningful components in audio and video
documents. Although this aspect is still a wide open
problem, we believe that it will deserve more and more
attention as electronic documents move from hypertext to
hypermedia.

Acknowledgments

This work is partially supported by CNET-CNRS project
Cesame. We also thank O2 Technology for their support
and Wendy Mackay for improving the readability of this
article.



--R

Kms: a distributed hypermedia system for managing knowledge in organizations.
The bookmark and the compass: orientation tools for hypertext users.
Tools for designing hyperdocuments.
Surface grammatical analysis for the extraction of terminological noun phrases.
Turning ideas into products: The guide system.
The use of cluster hierarchies in hypertext information retrieval.
Bases de donn-es : des syst-mes relationnels aux systemes - objets

Detecting lost users: Empirical studies on browsing hypertext.
Integrating search and retrieval with hypertext.
Generalized fisheye views.
Notecards in a nutshell.
An algorithm for drawing general indirect graphs.
area information server.
Evaluation of retrieval techniques in an experimental on-line catalog


O2 Reference Manual.
Navigation in hyperspace
Introduction to Modern Information Retrieval.
Graphical fisheye views of graphs.
The X Window System.
Treevisualization with tree-maps: 2-d space-filling approach
Massively parallel information retrieval for wide area information servers.
Intermedia: the concept and construction of a seamless information environment.
Shadocs, the sharing documents system.
--TR
Generalized fisheye views
The X window system
Notecards in a nutshell
KMS: a distributed hypermedia system for managing knowledge in organizations
The bookmark and the compass: orientation tools for hypertext users
An algorithm for drawing general undirected graphs
The use of cluster hierarchies in hypertext information retrieval
Hypertext and hypermedia
Tree visualization with tree-maps
Tools for designing hyperdocuments
Integrating search and retrieval with hypertext
Graphical fisheye views of graphs
Navigating in hyperspace
Turning ideas into products
Introduction to Modern Information Retrieval

--CTR
David Thevenin , Jolle Coutaz, Adaptation des IHM: taxonomies et archi. logicielle, Proceedings of the 14th French-speaking conference on Human-computer interaction (Confrence Francophone sur l'Interaction Homme-Machine), p.207-210, November 26-29, 2002, Poitiers, France
Peter Brusilovsky , Riccardo Rizzo, Using maps and landmarks for navigation between closed and open corpus hyperspace in Web-based education, The New Review of Hypermedia and Multimedia, v.8 n.1, p.59-82, January
Chaomei Chen , Mary Czerwinski, From latent semantics to spatial hypertextan integrated approach, Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems: links, objects, time and space---structure in hypermedia systems, p.77-86, June 20-24, 1998, Pittsburgh, Pennsylvania, United States
Nikos Pediotakis , Mountaz Hascot-Zizi, Visual relevance analysis, Proceedings of the first ACM international conference on Digital libraries, p.54-62, March 20-23, 1996, Bethesda, Maryland, United States
visualization;navigation;information retrieval;interaction paradigm