Figure 1: Strand map example showing the "Heat" and "Water Cycle" strands for grades K to 8. Arrows indicate how one benchmark supports the ideas in the next benchmark. Dotted lines show connections to other maps.
Keywords: Conceptual Browsing Interfaces, Web Services, Visualization, Digital Libraries
Biography
Qianyi Gu is a full-time Ph.D. student at the University of Colorado at Boulder, Department of Computer Science. His research topics are artificial intelligence, human-computer interaction and information retrieval and visualization. He received his M.S. degree from the Computer Science Department, State University of New York at Stony Brook. His thesis deals with the different technologies for information retrieval, web mining and presentation. Currently, he is involved in several Digital Libraries research projects: the Digital Library for Earth System Education (DLESE – www.dlese.org), and the National Science Digital Library (NSDL).
Biography
Faisal Ahmad is a full-time Ph.D. student at the University of Colorado at Boulder, Department of Computer Science. He obtained his Master's degree from the same university, His thesis investigated the core architectural components enabling concept space-based resource discovery for educational digital libraries.
Biography
Francis Molina holds a PhD in Botany from the University of British Columbia, Canada. He worked for 8 years as a research scientist at the American Type Culture Collection where he performed molecular characterization and computer-assisted image analysis and identification of microbial strains. His interest in computers led him to pursue a certificate in Interactive Multimedia and Web Development at the George Washington University. He is the technology director of Project 2061, a long-term education reform initiative of the AAAS (American Association for the Advancement of Science) where he introduced SVG as a key technology for developing interactive strand maps which depict students' progression of understanding of key science ideas.
Biography
Tamara Sumner is Assistant Professor the Department of Computer Science, University of Colorado at Boulder. Her research includes human-computer Interaction, user interface design, usability and education technology. She is Principal Investigator (PI) or co-PI on several NSDL projects and is the former chair of NSDL's Educational Impact and Evaluation Committee.
In this paper we present a system that supports the dynamic generation of conceptual browsing interfaces for digital libraries using SVG. This system is part of the Strand Map Service (SMS), a service being developed for the National Science Digital Library (NSDL). The SMS aims to provide educators and learners with conceptual browsing interfaces that help them to locate and use learning resources in educational digital libraries. These interfaces are comprised of interacting visual components that contain different views onto a concept space that can be modeled as nodes and links (Strand Maps). Rather than creating a static presentation of these interfaces, the system generates visualizations of these interfaces dynamically using SVG to represent information modeled in the data repository. Our approach builds on recent advances in visualization components and programmatic interfaces to knowledge organization systems.
1. Introduction
1.1 Conceptual Browsing Interface and Strand Maps
1.2 Strand Map Service
1.3 Visual Component Generator (VCG)
1.4 Service Impact
2. Components and Operation
2.1 System Features
2.2 System Architecture and Workflow
2.2.1 System Components
2.2.2 Workflow for Generating Conceptual Browsing Interfaces
2.3 CSIP
2.4 VCG
2.5 Visualization Algorithm
2.5.1 Related work in Graph Drawing
2.5.2 New Algorithm
2.5.3 Methodology
2.5.4 Algorithm
3. Evaluation
3.1 Visual Components Examples
3.2 Evaluation Results
3.3 Analysis
4. Example of Integration
Bibliography
Conceptual browsing interfaces, based on nationally recognized educational standards, can help educators and learners to locate, comprehend and use educational resources in digital libraries . These interfaces provide navigational and orientation cues that are typically lacking from traditional keyword or fielded search interfaces. Prior research indicates that concept map representations are useful cognitive scaffolds, helping users lacking domain expertise – such as learners, new teachers, or educators teaching out of area – to understand the macro-level structure of an information space . [1] [2]
We are creating a web service to support the construction of conceptual browsing interfaces based on the learning goals articulated in Benchmarks for Science Literacy. [3] These learning goals, or benchmarks, describe what learners should know, or be able to do, at key stages in their education across the natural sciences, mathematics, technology, and social science disciplines. Within the United States, the benchmarks provide a common framework for understanding relationships between national, state and local standards.
Strand maps provide a visual representation that emphasizes the coherence intended in the benchmarks and encourage both teachers and learners to make connections between ideas. The Atlas of Science Literacy [4] , published by American Association for the Advancement of Science (AAAS) and the National Science Teachers Association, features strand maps on topics important to science literacy (e.g., weather and climate, flow of energy in ecosystems, or conservation of matter). Each map consists of node-link representations illustrating a set of relationships between benchmarks organized around a topic (Figure 1). High-level descriptions of the benchmarks are provided in the nodes, while the links depict the interrelationships between benchmarks. Each map contains vertical strands reflecting key ideas in that topic (e.g., heat, water cycle, atmosphere, and climate change are strands within the weather and climate map). Each strand is cross-referenced by grade levels (K-2, 3-5, 6-8, 9-12) to illustrate how student understanding develops over time.
Figure 1: Strand map example showing the "Heat" and "Water Cycle" strands for grades K to 8. Arrows indicate how one benchmark supports the ideas in the next benchmark. Dotted lines show connections to other maps.
The conceptual browsing interfaces enable educators and learners to:
The Strand Map Service builds on and extends the significant knowledge base embodied in Benchmarks and the Atlas. The Service supports the needs of K-12 (primary and secondary school) educators and learners, and digital library developers through the provision of graphical conceptual browsing interfaces. It also supports the programmatic web service interface which enables digital library developers to easily construct conceptual browsing interfaces appropriate to the needs of their specific library audiences using dynamically generated visual components provided by the Service.
The Benchmarks Repository is a database housing the benchmarks, strand maps, and related information. The Service middleware uses query adapters, designed to search over different collections within NSDL, in order to locate resources that support learning goals articulated in the benchmarks. The Visual Component Generator is responsible for dynamically generating conceptual browsing interfaces. The Service supports a ‘spectrum of interoperability’ to maximize its utility for a broad range of digital library projects [5] . Specifically, library developers can create interfaces and services by making calls to our web service interface or by harvesting benchmark information using the OAI-PMH server.
Rather than creating static presentations of strand maps, the Visual Component Generator (VCG) dynamically generates visualizations of maps and map components in SVG from information modeled in the Benchmarks Repository. Our approach builds on recent advances in visualization components and programmatic interfaces to knowledge organization systems [6] . We describe the architecture of the VCG and the visualization algorithm used to generate the visual interfaces, as well as the results of the evaluation.
The Concept Space Interchange Protocol (CSIP) is the primary mode of interaction between digital libraries and the Strand Map Service. Its design is based on REpresentational State Transfer (REST) web architecture style. REST is a document-centric web service architecture where each service request has a unique URL and the response is considered to be a transfer of representation of the document. The REST architecture style was chosen for its low overhead and widespread use in the DL community. CSIP provides three services that can be used by digital libraries to access strand maps information: Service Description, Submit Resource and Query. The query service is used as the service middleware for generating the conceptual browsing interface. This service request is used to get AAAS concept maps information that can be used in DLs for resource discovery and navigation. This request can be made by using the HTTP Post method and the following URL: servername/Query.
Numerous types of information retrieval queries on strand maps are possible using CSIP. These queries are suitable for different learning contexts, concept map visualization aspects, and client user interface components. Examples of requests supported by CSIP include:
An example of a CSIP query request used to retrieve a graphical representation is:
<Query DetailLevel="Skeleton" Scope="Strand" Format="SVG">
<Content-Query>
<ObjectID>SMS-STD-0004</ObjectID>
</Content-Query>
</Query>
|
The above request retrieves an SVG representation of a map with an ObjectID of SMS-STD-0004.
Another example is:
<SMS-CSIP xmlns="http://sms.dlese.org" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://sms.dlese.org C:\Project\Protocol\SYNTAX~1.0\CSIP.xsd">
<Query DetailLevel="Detailed" Format="SVG" Scope="ALL">
<Navigational-Query>
<ObjectID>SMS-BMK-9022</ObjectID>
<Relation>
<is-referenced-by />
</Relation>
</Navigational-Query>
</Query>
</SMS-CSIP>
|
The above request retrieves an SVG representation of a benchmark with an ObjectID of SMS-BMK-9022 and all benchmarks which it references.
Graph Drawing and Visualization addresses the problem of constructing geometric representations of conceptual structures that are modeled by graphs [7] . Over the last ten years there has been significant growth in research in graph drawing theory, systems, and applications [8] . Various graphic standards have been proposed for drawing graphs on a plane, depending on the application [9] . The vertices are usually represented by circles or boxes, and the edges (=node connectors or links) are represented by a simple open curve between the vertices.
Prior research in graph drawing techniques can inform the development of the visualization algorithm since strand maps are a form of directed acyclic graphs (DAGS) [9] [10] . This research suggests that most techniques and algorithms are best suited for specific classes of graphs. Due to the rich variety of graph representations, there is no single graph layout algorithm that can effectively generate all representations. Variations in the semantic and aesthetic constraints of different types of graphs will affect the applicability of existing algorithms. Strand maps have unique features and aesthetics compared to other type of DAGS: they have a relatively small number of nodes compared to many DAGS, the node size is significantly larger in order to contain descriptions of the benchmarks whereas most DAGS typically have small node sizes, and the vertical and horizontal alignment of groups of nodes is an important semantic distinction that needs to be represented. Thus, it was necessary to develop a new algorithm to generate visual components for the NSDL Strand Map Service.
Our methodology combined expert knowledge acquisition activities, to inform algorithm design and evaluation, with rapid prototyping. Our knowledge acquisition activities involved analyzing the published strand maps and interviewing professional strand map developers. These activities enabled us to articulate the semantic constraints that needed to be preserved and the desirable aesthetic heuristics used by human experts who created the published maps. Two different algorithms were designed and prototyped that used different spatial information to constrain node placement. One algorithm used the placement information from the paper-based map to inform graph construction. The other algorithm used tree-based processing and a grid to inform the placement of nodes and graph construction. Preliminary evaluations indicated that the latter algorithm better satisfied the previously identified constraints and heuristics.
The visualization algorithm uses tree-based processing where a strand map is viewed as consisting of a tree with multiple roots. Breadth first search is used to compute the vertical depth level of each node relative to its nearest root. Depth first search is used to compute the horizontal relationships, across strands and within a strand, between nodes at the same vertical depth. The results of these two searches are combined to quantitatively identify internal relations between nodes. These quantitative relations are then used to allocate nodes to placements within a predefined grid that represents the available drawing space. Where pairs of nodes conflict; e.g., the link between two nodes may cross a third node and violate an aesthetic heuristic, local placement adjustments are made by moving the conflicting node to the next available placement in the grid.
The readability of conceptual browsing interfaces can be evaluated by graph-drawing conventions, aesthetics, rules and efficiency. The goal of our system is to generate a graph rendition in SVG whose readability closely approximates graph drawing with human heuristic effort. Another important requirement is that it preserves the semantics of the strand map in the graphical presentation.
We measured the evaluation metrics quantitatively on different visual components of stand maps. As in the service study, instead of just browsing the full map, the user will browse different visual components of strand maps to meet their various requirements. Different visual components have different complexity levels, providing a good way to evaluate the system's performance on different complexity requests. Four categories of visual components were identified in our evaluation process:
Map topologies resulting from a human expert and the SMS are shown in Figures 4 and 5, respectively. Despite minor variations in topology, the spatial relationships of benchmark objects are preserved. The system can also generate novel visualizations by responding to a request for a benchmark object and its nearest neighbors (Figure 6).
Figure 6: Novel visualization: Focus view of one node (colored red) and its children nodes from different maps (SVG).
Evaluation results are shown in Figures 7 and 8.
The following conclusions can be made from the results:
Figure 9 shows a demonstrator with the Strand Map Service embedded in a client digital library, the Digital Library for Earth System Education (DLESE – www.dlese.org). Users can browse strand maps in two ways: using the pull down menus (on the left) or by direct manipulation of map elements. The menus use the XML option supported by CSIP; information in the Service is used to populate this DLESE-specific interface element created by DLESE developers to mimic menus in the rest of the library. The interactive map visualizations use CSIP’s SVG option; the Service is dynamically generating map, strand, and benchmark ‘viewer’ components in response to user actions in the interface. Representing the information space in terms of maps and strands reflects the major visual representations published in the Atlas of Science Literacy [4] . However, the Service can also generate new visualizations, inherent in the Benchmarks Repository data model, that have never been published. An example of this capability in the DLESE demonstrator is the option to "view Related Benchmarks" on the benchmark description page. This option displays the pre-requisites and post-requisites of the selected benchmark (nearest neighbors) in a single map view. In the Atlas, these neighboring benchmarks are typically spread across several published maps. Users can elect to retrieve library resources that support the selected benchmark; in this demonstrator, resources are retrieved that are aligned with the benchmark’s corresponding National Science Education Standard.
XHTML rendition created by gcapaper Web Publisher v2.0, © 2001-3 Schema Software Inc.
