XML 2001 - December 11, 2001

Using XML-Topic Map on a PDA

Speaker:	Steven Heckler, Olivier Baudon
Track:	Wireless
Day:	Tuesday December 11, 2001
Time:	11:45am - 12:30pm

Using XML-Topic Map on a PDAPalm Navigator is a shareware program that is designed to helpimport a XML/Topic-Map onto a PDA (Personal Digital Assistant), andto enable navigation, jumping from one topic to another as simplyas web surfing. Palm Navigator is fully compliant with the ISO TopicMaps standard (ISO/IEC 13250) which enables exchanges between Websites.Due to the lack of power, both in terms of memory and processingcapicities, topic maps cannot be manipulated (parsing, navigating,querying) directly on the PDA. Moreover, the only way to stock data ona Palm Pilot is by using Palm Pilot Database files (PDB), which arearchaical indexed files of fixed-length strings. In Palm Navigator, wepropose an efficient, yet complex architecture based on a datastructure issued from graph theory. A prototype in Java has been availablesince March 2001 and a C version is planned for March 2002.Palm Navigator is separated into two components. The first, locatedon the user's Personal Computer, is in charge of parsing andconverting the XML-Topic Map file to a PDB file format andtransferring it to the PDA, using the usual craddle. The secondallows navigation and querying on the PDA.Representation on the PDA is based on a graph structure, which allowsefficient search and navigation on the topic map. As explained in ourprevious presentation at XML-Europe 2001 %22Graph Clustering for Very LargeTopic Maps%22, a topic map may be considered from a mathematical point onview, as a hypergraph and then represented by the bipartite graphrepresentative of the hypergraph.The graph structure is implemented with fixed size arrays which allowvery fast navigation and search. If the maximum degree of the verticesis bounded, any basic operation can be done in a constant time. Interms of topic maps, this means that our structure is efficient if themaximum number of roles for any association does not depend on the sumnumber of topics plus the number of associations.In a future version, Palm Navigator will integrate new features such asthe ability to attach Palm's standard objects to the topic map, inorder to make it self-sufficient.In our presentation, we will outline the Palm Navigator'sarchitecture and give results in terms of capacity and efficiency. Wewill also presents the remaining difficulties such as how to synchronize a topic map with modifications done on the PDA.