Information Visualization and knowledge visualization
Information visualization (InfoVis) tools function as intermediaries between information (such as recorded knowledge) and the users of it, like teachers, whose role is to interpret an area of knowledge to the student. In order to fulfill this function, InfoVis techniques are aiming at supporting the cognitive system of their users. Researchers in Visualization are trying to develop and use tools that foster the access to information resources. They want their visualization tools to help users in their information tasks, such as searching, browsing, learning, and exploration.
The term InfoVis and Visualization can be referenced in a variety of contexts, the most definition was given by Card , Shneiderman, and Mackinlay , they defined InfoVis as “the use of computer-supported, interactive, visual representations of abstract non-physically based data to amplify cognition”. In 2009, Friendly and Denis  provided a graphic overview of the events in the history of visualization, they illustrated the milestones (important works and events in the domain of visualization) within a timeline (chronology of innovations) from 1600 to 2009.
There are numerous attempts to define the two basic concepts of Information and Knowledge. For example, Keller and Tergan give a definition: “Information is data that has been given meaning through interpretation by the way of relational connection and pragmatic context. Knowledge is information, which has been cognitively processed and integrated into an existing human knowledge structure”  (another wildly-used definition by Chen et al can be found in ). Schank and Abelson have defined the concept knowledge structures in . In 2012, Van Biljon has given a summary of the similarities and differences between these two types of Visualizations on the existed visualization works .
Nowadays, some InfoVis works handle with the abstract data structures have been introduced to visualize knowledge structures, most of InfoVis and knowledge visualization researchers see no more obvious differences between knowledge visualization and InfoVis. For this reason, in the rest of thesis, I no longer intentionally distinguish the terms InfoVis and knowledge visualization.
InfoVis Toolkit and InfoVis Tools
The visualization toolkit also becomes an indispensable part of many AI tools. For example, in the ontological engineering tool Protégé , there are many InfoVis plug-ins providing the Memory Island: Visualizing Hierarchical Knowledge as Insightful Islands visual representation to help the users to build their ontology. In addition, with the famous (in data mining) Orange Software, users can select different visualizations to visualize the results of data/text mining. Some other well-known visualization tools for graph and network are PHYLOViZ4  , Gephi5  and Tulip6 . Gephi is an InfoVis tool, which provides different existed spatialization algorithms for visualizing network and other datasets. With the semantic plug-in SemanticWebImport developed by Erwan Demairy of Inria DREAM team, Gephi can be used for visualizing ontologies. In Figure 2.1, two visualizations created with Gephi for InPhO and Rock ontologies are presented.
Design and Evaluation Visualization Systems
How effectively design, valid visualization systems, and evaluation evaluate the different InfoVis techniques is one of the most important part of the InfoVis research. Munzner  proposed the four-level nested design model about the design and validation of visualization systems. They suggest that for designing a visualization system, the visualization researchers need to first design the domain problem characterization, then do the data/task abstraction design and encoding/interaction technique design, and at last design the algorithms of the visualization technique. Meyer et al. then extends this works and they proposed a four-level nested model which contains the blocks and guidelines at each level..
Tree and Hierarchic Knowledge Visualizations
In this section, we begin with the definition of hierarchic knowledge and its skeleton – tree structure, and then we review the different hierarchic knowledge visualization techniques and the graph-drawing algorithms and theories behind these visualizations.
Tree, Hierarchic knowledge and Skeleton
A Tree is a hierarchical data set (HDS); it organizes data or knowledge (information records) into a hierarchy. Although hierarchical knowledge is a data type richer than a tree, its information records are organized around a hierarchy, such as, the taxonomy of an ontology. As this hierarchy is the most important knowledge structure, we call it as the skeleton of the knowledge. To visualize a hierarchical knowledge, representing knowledge’s information contents with this knowledge skeleton is necessary and it is still an challenge.
Classical Tree Visualization Techniques
Visualizing the tree structure is one of the most essential and important task, a network can be also abstracted as a tree-structure by using the Spanning tree algorithm (e.g., Minimal Spanning tree algorithms [23, 24]) or based on a clustering technique (e.g., the hierarchical clustering technique of networks, such as the technique proposed in ).
Tree hierarchies or tree structures are collections of items (e.g., information contents or concepts) with each item having a link (relation) to one parent item (except the root). The items of a tree structure are also called as tree nodes. Items and the links between parent and child can have multiple attributes (see basic tree structure in Figure 2.4).
To create a visual representations of tree structure dataset , we can use an outline style of indented labels likes the tables of contents of a book , a node-link diagram, or a Treemap (the space slit into nested regions). In this section, we discuss the basic approach for tree visualization: the indented List and Node-link diagram. We discuss the Treemap (tilling algorithms) later within the map-like visualization approaches in section 2.8.1.
Cartography and Knowledge Cartography
Many cartographic principle and technique have been introduced to create the knowledge map; these cartographic InfoVis approaches are also called Map-like visualizations, as they created a knowledge map as the visual representation of the dataset. In this section, we briefly review the basic concepts of Cartography, the Knowledge Cartographic and the existing maplike visualization techniques.
Cartography, as its name, is the study on making maps. It is combining science, aesthetics, and technique. The main topic of cartography is how reality can be effectively modeled.
The fundamental problems of traditional cartography are to:
Set the map’s agenda and select traits of the object to be mapped. This is the concern of map editing. Traits may be physical, such as roads or landmasses, or may be abstract, such as the (political) boundaries.
Map projections: Represent the terrain of the mapped object on flat media (a 2D plane).
Map generalization: The concern of generalization, how to make the map. o Eliminate characteristics of the mapped object that are not relevant to the map’s purpose. o Reduce the complexity of the characteristics that will be mapped.
Map design: Orchestrate the elements of the map to convey best its message to its audience.
Memory Island technique creates a knowledge island (map) as the visual representation of the given knowledge. Visualizing a tree structure has been studied for many years, before we discuss our Memory Island technique; we review some important works on creating a map from the hierarchic data including the Tree-Maps, the approaches based on the spatialization, and the map-like approaches.
Tree mapping approaches apply the space-filling algorithms for creating maps. They display hierarchical data as a map of nested regions (rectangles or non- rectangular regions). For example, the famous classic Tree-Map uses a space-filling algorithm to create the maps. In the beginning of 90s, the existing tree-drawing algorithms have problem for display a large treestructure in a limited display space. This type of space filling algorithms also been considered as tiling algorithms, which try to fill the display space. The first treemapping approach was proposed by Johnson and Shneiderman . They proposed a space-filling algorithm inspired by the idea of mosaic for tree-structure data. As this visualization technique creates a map (e.g., Figure 2.12) for the hierarchical data set (tree-structure dataset), Johnson and Shneiderman named their InfoVis technique as Treemaps.
Table of contents :
PART I. BACKGROUND AND LITERATURE REVIEW
CHAPTER 1 GENERAL INTRODUCTION
1.1 Overview and Research Context
1.2 Industrial Context
1.3 Contributions and Related Research Areas
CHAPTER 2 REVIEW OF LITERATURE
2.1 Information Visualization and knowledge visualization
2.2 InfoVis Toolkit and InfoVis Tools
2.3 Design and Evaluation Visualization Systems
2.4 Tree and Hierarchic Knowledge Visualizations
2.4.1 Tree, Hierarchic knowledge and Skeleton
2.4.2 Classical Tree Visualization Techniques
2.5 Ontology and Ontology Visualization
2.6 Knowledge Maps
2.7 Cartography and Knowledge Cartography
2.7.2 Knowledge Cartography
2.8 Cartographic Visualization
2.8.1 Treemapping Approaches
2.8.2 Spatialization (Layout) and Tree drawing algorithms
2.8.3 Map‐like Visualization Approaches
2.10 Spatial Cognition
PART II. MEMORY ISLAND TECHNIQUE
CHAPTER 3 MEMORY ISLAND IDEA AND DESIGN METHODOLOGY
3.1 The arts of Memory technique and the notion of Memory Islands
3.2 The Objectives of Memory Island technique
3.2.1 Recognition (truthful)
3.2.2 Discovery (functional and beautiful)
3.2.3 Surprise (insightful and enlightening)
3.3 The idea of Memory Island
3.4 Map (Landscape) Metaphor
3.5 Why do we choose 2D traditional map representation
3.6 Geographic Metaphors and Cartographic Means
3.6.1 Proportion Metaphor
3.6.2 Distance/centrality Metaphor
3.6.3 Font Attributes and Point Attributes
3.6.5 Paths and Gaps
3.7 Memory Island Prototype Algorithm
CHAPTER 4 HIERARCHICAL REORGANIZATION BY SEMANTIC SIMILARITY
4.1.1 Related works
4.1.2 Hierarchical Reorganization by Semantic Similarity
CHAPTER 5 VISUALIZING HIERARCHICAL DATA AS ISLANDS
5.1 Island Generation
5.1.1 Polyle II Algorithm
5.1.2 Memory Island Algorithm
5.1.3 Discussion on Memory Island Algorithm
5.2 Reshaping the Resulting Island
CHAPTER 6 LABELLING AND MAP GENERATION
6.1 Related Works
6.1.1 PFLP Problem
6.1.2 PFLP Algorithms
6.1.3 Google Map Mechanism
6.2 Labeling and Map Generation in Memory Island
6.3.1 Improvement of the Label placement algorithm
6.3.2 Apply Area‐features label placement algorithm
CHAPTER 7 MEMORY ISLAND INTERFACE
7.1 Overview+Detail interactive interface
7.1.1 Map‐like Focus + Context and Element highlighting technique:
7.1.2 Map interactive functions
7.1.3 Design of Memory Island Interface
PART III. IMPLEMENTATION AND APPLICATIONS
CHAPTER 8 MEMORY ISLAND IMPLEMENTATION
8.1 Memory Island Application’s sub‐system components
8.1.1 Knowledge Extraction
8.1.2 Island Generation
8.1.3 Label Placement and Map Generation
8.1.4 Memory Island Interface Generation
8.2 The run‐time of Memory Island Application
CHAPTER 9 CREATING KNOWLEDGE MAPS USING MEMORY ISLAND
9.1.1 Text and Document Data
9.1.3 Hierarchical Dataset
9.1.4 Project OBVIL – Digital Humanities Dataset
PART IV. VALIDATION AND EVALUATION OF MEMORY ISLAND
CHAPTER 10 VALIDATING MEMORY ISLAND
10.1 Visualization mantras
10.2 User Study
10.2.1 Methods and Visualization Set‐up
CHAPTER 11 PSYCHOLOGICAL EVALUATION
11.1 Related work
11.1.1 Users’ requirements analysis
11.1.2 Evaluations of Ontology Visualization tools
11.1.3 Evaluations of Tree Visualization tools
11.1.4 Evaluations of Map‐like Visualization tools
11.2 Psychological experimental protocol
11.2.1 Ontology Browsing Task
11.2.2 Ontology Understanding Task
11.2.3 Ontology Remembering Task
11.2.4 The Subjective Task
11.2.5 Suggested Evaluation Procedure
11.3 A Preliminary Users Study
11.3.1 Methods and Experiment Set‐up
11.4 Discussion with the past evaluation experiment
PART VI. CONCLUSION AND PERSPECTIVES
CHAPTER 12 CONCLUSIONS
CHAPTER 13 FUTURE WORKS
13.1 Develop the Visualization Tools for Digital Humanities
13.2 Improve the Usage of space
13.3 Evaluation of the long‐term memorization
13.4 User Interface and interactive functions
13.5 Integrate Memory Islands to platforms of DH and DL