Using XML-Topic Map on a PDA

1. Knowledge Index Management (KIM) and XML - Topic Maps (XTM)

1.1. Mondeca's solution

Mondeca [MON01] provides Topic Maps-based Software Components and Solutions for Knowledge Index Management enabling companies to organize, navigate, visualize and access a large and rich collection of information

Mondeca's mission is to transform the way we all access and navigate content on the Web. Based on the principles that govern the way humans organize and interact with information, Mondeca allows Internet users to visualize information and its whole environment on an intelligent intuitive scale.

Mondeca's technology, referred to as Dynamic Content Navigation, is made of up two fundamental concepts: structuring content as a Topic Network, and allowing intuitive access to the content with Spatial Maps. The Topic Network organization allows users to access content through a topic-to-topic navigation, providing a clear and efficient content browsing tool (Figure 1). Mondeca has also developped Spatial Maps ( Figure 2) to enable users to access content as a whole by "flying over" these Topic Networks, similar to a zoom-in and zoom-out feature on a camera.

1.2. Topic Maps

Topic Maps [XTM01] is an ISO Standard (ISO/IEC 13250, January 2000) that enables vast information resources to be classified and navigated consistently. We have long understood the idea of creating style sheets to control the formatting and layout of information. Topic Maps introduces the concept of creating style sheets to control knowledge-based information access and navigation.

From a technical sense, Topic Maps describes what an information set is about, by formally declaring topics, and linking the relevant information sets to the appropriate topics (Figure 3). Topic Maps can be applied from "above" the information set, rather than from "inside" them. They are superimposed views. A Topic Map expresses an opinion about what the topics are and their relevant relationships. There is no limit to the number of Topic Maps that can be created above the same information set.

2. Topic Maps and PDA

2.1. Palm Navigator

Mondeca would like to provide XTM users a shareware software for using Topic Maps on their PDA. This shareware, called Palm Navigator, is developped for Palm OS with the help of MSc students from the University of Bordeaux 1, coordinated by Pascal Auillans and Oliver Baudon. A first version has been available since March 2001. A second is planned for March 2002. This paper will present the current version, as well as the improvements planned for the second version.

Programming for a PDA presents three major difficulties :

• small capacity of RAM

• slow processor

• archaical file system

To solve these limitations, we used an efficient data structure issued from graph manipulations. Moreover, the parsing and analysis of the topic map is deported to a PC (Figure 4 and Figure 5).

2.2. From Topic Maps to Bipartite Graphs

From a mathematical point of view, a topic map may be considered as a hypergraph and thus, as a bipartite graph [AB01].

2.2.1. Graph

A graph G is a couple (V,E), where V is the set of vertices and E the set of edges. An edge e is a pair of vertices {x,y}. We usually say that x and y are incident with e, or that they are the endpoints of e. x and y are said to be adjacent or neighbors.

In this paper we will consider that all the graphs are simple, meaning there exist neither multiple edges nor self-loops, ie each pair {x,y} in E is unique and with x different of y.

The order of a graph, that we will note n, is its number of vertices, and its size, that we usually note m, is its number of edges. The degree of a vertex v, denoted by deg(v), is the number of edges that are incident with it.

2.2.2. Example

The simple graph in Figure 6 is of order 6, and size 8. The degree of the vertex labeled 1 is 2, while its neighbors are the vertices 2 and 6 and its incident edges are a = {1,2}and f = {1,6}.

2.2.3. Hypergraphs

Hypergraphs are a generalization of graph concepts, where an edge is incident with an unspecified number of vertices. In this case, we will use the term hyperedges. The representing graph of a hypergraph, is a graph G where the set of vertices is the union of the set of vertices and the edges of the hypergraph, and there exists an edge between two vertices if and only if one of the vertices is a hyperedge incident with the other vertex : .

An important property of the representative graph of hypergraph is that the vertices can be decomposed into two sets such that there exist no edges between any couple of vertices belonging to the same set. These types of graphs are therefore named bipartite graphs.

2.2.4. Graph Coding

To represent the Topic Map on the PDA, we use its graph representation. A graph is mainly represented using two arrays of integers. Each vertex is represented by an integer from 0 to n - 1. Because the graph is simple, we only have to code the list of neighbors for each vertex. This is done in a first array a1, of size 2m where the adjacency lists are given in a contiguous order. The second array a2 is of size n+1 and contains at each index v the starting index of the neighborhood of vertex v. The last index n contains 2m. In that way, the degree of each vertex v may be easily obtained because it is equal to a2[v+1] - a2[v].

Note that if each neighborhood is sorted, knowing if two vertices are adjacent or not may be obtained in a logarithmic time, using dichotomy.

Example The graph in Figure 6 is coded by the two following arrays:

i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
a1[i]	1	5	0	2	3	4	1	3	5	1	2	4	1	3	5	0	2	4
a2[i]	0	2	6	9	12	15	18

3. Palm Navigator

3.1. Using Palm Navigator

The Figure 9 presents the sequence of screens in Palm Navigator. An example of each screen is given in Figure 10, Figure 11, Figure 12, Figure 13 and Figure 14

3.1.1. Technical specifications

Both PC's XML parser and Palm navigator were written using Java.

The XML parser uses the Sun's Java APIs for XML processing : JAXP 1.1 [JAX01]. It is implemented as a HotSync Manager's plug-in, using CDKJ 4.0 [CDK01]. Our DTD for the Topic Map on the Palm is a subset of the ISO DTD, which is itself a subset of the DTD used by Mondeca Navigator ().

Palm Navigator were written using WabaSDK [WAB01] and runs using the Waba virtual machine WabaVM. The IHM was written using Waba Extras v1.30.

The software was tested on a Palm emulator and on a Palm V with 3Mo of RAM, and a processor at 20Mhz. It runs well on the emulator. On the Palm, the number of topics and associations available is too small to have a real use. Moreover, drawing a screen takes too much time.

3.1.2. Furtherwork

A new version of Palm Navigator is planned for February 2002. The following improvements have been defined for this version :

• specify screens more similar than those proposed in Mondeca Navigator;

• rewrite Palm Navigator in C or C++ to improve the number of topics and associations and the speed;

• improve the XTM Parser.

4. DTD

<!-- XML Topic Map DTD  for Palm Navigator........................ -->
<!-- XML Topic Map (XTM) DTD for Palm Navigator, Version 1.0

     This DTD is a subset of the XTM DTD version 1.0
     XML Topic Map (XTM)
       Copyright 2000 TopicMaps.Org, All Rights Reserved.

        Authors:    Group Mondeca (DESS GL Université Bordeaux I)
        Version:    v1.0
-->
<!-- Use this URI to identify the default XTM namespace:

         "http://www.topicMaps.org/xtm/1.0/"

     Used to identify the XLink namespace:

         "http://www.w3.org/1999/xlink"
-->

<!-- topicMap: Topic Map document element ........................ -->

<!ELEMENT topicMap
   ( topic | association )*
>
<!ATTLIST topicMap
   id              ID        #IMPLIED
   xmlns           CDATA     #FIXED 'http://www.topicmaps.org/xtm/1.0/'
   xmlns:xlink     CDATA     #FIXED 'http://www.w3.org/1999/xlink'
   xml:base        CDATA     #IMPLIED
>

<!-- topic: Topic element ....................................... -->

<!ELEMENT topic
   ( instanceOf*, ( baseName | occurrence )* )
>
<!ATTLIST topic
   id              ID        #REQUIRED
>

<!-- instanceOf: Points To a Topic Representing a Class .......... -->

<!ELEMENT instanceOf  topicRef >
<!ATTLIST instanceOf EMPTY >

<!-- topicRef: Reference to a Topic Element ...................... -->

<!ELEMENT topicRef  EMPTY >
<!ATTLIST topicRef
   xlink:href      CDATA     #REQUIRED
>

<!-- baseName: Topic or Occurrence Base Name ..................... -->

<!ELEMENT baseName  baseNameString >
<!ATTLIST baseName EMPTY >

<!-- baseNameString: Base Name String Container .................. -->

<!ELEMENT baseNameString  ( #PCDATA ) >
<!ATTLIST baseNameString EMPTY >

<!-- occurrence: Resources Regarded as an Occurrence ............. -->

<!ELEMENT occurrence
   ( instanceOf?, baseName?, resourceData )
>
<!ATTLIST occurrence EMPTY >

<!-- resourceData: Container for Resource String ................. -->

<!ELEMENT resourceData  ( #PCDATA ) >
<!ATTLIST resourceData EMPTY >

<!-- association: Topic Association  ............................. -->

<!ELEMENT association
   ( instanceOf?, member+ )
>
<!ATTLIST association
   id              ID        #REQUIRED
>

<!-- member: Member in Topic Association ......................... -->

<!ELEMENT member
   ( roleSpec?, topicRef+ )
>
<!ATTLIST member EMPTY >

<!-- roleSpec: Points to a Topic Serving as an Association Role .. -->

<!ELEMENT roleSpec topicRef >
<!ATTLIST roleSpec EMPTY >

<!-- end of DTD XML Topic Map (XTM) for Palm Navigator -->

		

Design and Development by deepX Ltd.