Dynamically Generating Conceptual Browsing Interfaces for Digital Libraries Using SVG

Keywords: Conceptual Browsing Interfaces, Web Services, Visualization, Digital Libraries

Qianyi Gu
Ph.D Candidate
Department of Computer Science - University of Colorado at Boulder
Boulder
Colorado
USA
qianyi.gu@colorado.edu

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).

Faisal Ahmad
Ph.D Candidate
Department of Computer Science - University of Colorado at Boulder
Boulder
Colorado
USA
fahmad@colorado.edu

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.

Francis Molina, Ph.D
Technology Director
Project 2061, American Association for the Advancement of Science
Washington D.C.
USA
fmolina@aaas.org

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.

Tamara Sumner, Ph.D
Assistant Professor
Department of Computer Science - University of Colorado at Boulder
Boulder
Colorado
USA
sumner@colorado.edu

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.


Abstract


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.


Table of Contents


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

1. Introduction

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]

1.1 Conceptual Browsing Interface and Strand Maps

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.

Weather_and_Climate.jpg

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:

  1. Discover educational resources that support nationally-recognized learning goals (benchmarks)
  2. Browse learning goals and their interconnections by exploring interactive, concept map visualizations
  3. Enhance their own content knowledge by using the Service to examine important background information on learning goals, such as related prior research on student conceptions and student learning, related educational standards, and assessment strategies to check student understanding

1.2 Strand Map Service

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.

1.3 Visual Component Generator (VCG)

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.

1.4 Service Impact

  1. Digital Libraries' Perspective: By dynamically generating conceptual browsing interfaces in SVG, the Strand Map Service will enable digital libraries to organize their content around science content standards. This novel application of webmapping demonstrates the real-time generation of progression-of-understanding maps through SVG-database connectivity.
  2. End User's Perspective: By generating interactive SVG components based on the web services described below, the conceptual browsing interface provides users the gateway for information discovery in distributed digital libraries. The query language we developed can be used by different digital libraries to request the generation of SVG visual interfaces linked to their individual on-line resources. Through these interactive SVG interfaces provided by Strand Map Service, the user is able to retrieve useful information from on-line resources in distributed digital libraries.

2. Components and Operation

2.1 System Features

Client-Server Architecture
The server is based on the struts architecture. It consists of a client request handler to analyze user requests and generate a service call; an application logic to dynamically generate visual interfaces in SVG; and a data resources component to connect to a Relational Database (Microsoft SQL Server 2000) at the backend and generate as well as execute SQL queries.
Web Services as Communication Media
We developed a web services based protocol, the Concept Space Interchange Protocol (CSIP), to enable communications between client and server. The protocol design is based on the REpresentational State Transfer (REST) web architecture style. CSIP is implemented in XML. The protocol defines a query language which is used by the client to initiate the request to generate SVG components. When the CSIP query is sent to the server, it dynamically generates SVG as the front end of this web services and sends back the SVG as a query result to the client through CSIP.
Server-Side Dynamic Generation of the Visual Interface in SVG
In order to present the visual interfaces in response to a user's request, the server generates SVG dynamically by retrieving data from the backend database instead of storing static visual interfaces.

2.2 System Architecture and Workflow

whole_arc.jpg

Figure 2: Overall service architecture

2.2.1 System Components

Stand-alone Strand Map Interface
Graphical conceptual browsing interface that is presented to the end-user
Service Middleware
The interpreter that allows communication between client interfaces (including the stand-alone Strand Map Interface and NSDL clients), the back-end database, and the query adapters based on the Concept Space Interchange Protocol
Metadata Repository
Database housing the benchmarks, strand maps, and related information
Query Adapters
Translators that let queries from the NSDL Strand Map Service and client interfaces be understood by NSDL discovery systems

2.2.2 Workflow for Generating Conceptual Browsing Interfaces

2.3 CSIP

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.

2.4 VCG

system_arc.gif

Figure 3: VCG architecture

  1. User Request Analyzer Component
    • Receives queries from the client through CSIP
    • Analyzes and translates these requests to a graphical query (XML)
    • Sends graphical query to the Data Resource Component
  2. Data Resource Component
    • Parses the graphical query using XSLT and generates the corresponding SQL query
    • Executes SQL query
    • Gets the result set from the database
    • Creates the data structure used by the Graph Layout Component
  3. Graph Layout Component
    • Implements the visualization algorithm in Java
    • Uses the Rules and Aesthetics Component to create the requested conceptual browsing interface
    • Encodes the result in SVG format
  4. Rules and Aesthetics Component
    • Defines graph drawing rules
    • Applies semantic constraints and aesthetic heuristics
    • Defines the priorities guiding rule application

2.5 Visualization Algorithm

2.5.1 Related work in Graph Drawing

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.

2.5.2 New Algorithm

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.

2.5.3 Methodology

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.

2.5.4 Algorithm

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.

3. Evaluation

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:

3.1 Visual Components Examples

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).

vc1.svg

Figure 4: Human-generated strand map (SVG).

vc2.svg

Figure 5: System-generated strand map (SVG).

vc3.svg

Figure 6: Novel visualization: Focus view of one node (colored red) and its children nodes from different maps (SVG).

3.2 Evaluation Results

Evaluation results are shown in Figures 7 and 8.

evaluation1.gif

Figure 7: Values obtained for various metrics elements.

evaluation2.jpg

Figure 8: Occupancy efficiency of different components.

3.3 Analysis

The following conclusions can be made from the results:

4. Example of Integration

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.

integration.jpg

Figure 9: DLESE integration example

Bibliography

[1]
Hall, R.H., Hall, M.A. and Saling, C.B. The effects of graphical postorganization strategies on learning from knowledge maps. Journal of Experimental Education, 67 (2). 101-112.
[2]
O'donnell, A.M. Donald F. Dansereau, and Richard H. Hall, "Knowledge maps as scaffolds for cognitive processing," Educational Psychology Review, vol. 14, 2002.
[3]
AAAS Benchmarks for Science Literacy. Project 2061, American Association for the Advancement of Science, Oxford University Press, New York, 1993.
[4]
AAAS Atlas of Science Literacy. Project 2061, American Association for the Advancement of Science, and the National Science Teachers Association, Washington, DC, 2001.
[5]
Arms, W., Hillmann, D., Lagoze, C., Kraft, D., Marisa, R., Saylor, J., Terrizzi, C. and Van ed Sompel, H. A Spectrum of Interoperability: The Site for Science Prototype for the NSDL D-Lib Magazine, 2002, http://www.dlib.org/dlib/january02/arms/01arms.html.
[6]
Binding, C. and Tudhope, D. KOS at your Service: Programmatic Access to Knowledge Organisation Systems. Journal of Digital Information, 4 (4, Article No. 265, 2004-02-05). http://jodi.ecs.soton.ac.uk/Articles/v04/i04/Binding/.
[7]
Battista, G. and P. Eades, Graph Drawing: Algorithms for Visualization of Graphs. 1998: Prentice Hall.
[8]
Tollis, I., Graph Drawing and Information Visualization. ACM Computer Surveys, 1996. 28A(4).
[9]
Sugiyama, K. and S. Tagawa, Methods for Visual Understanding of Hierarchical Systems Structures. IEEE Trans. on Systems, Man, and Cybernetics, 1989: p. 109-125.
[10]
Miriyala, K. An Incremental Approach to Aesthetic Graph Layout. in Six International Workshop on Computer-Aided Software Engineering. 1993.

XHTML rendition created by gcapaper Web Publisher v2.0, © 2001-3 Schema Software Inc.