A comparison of hyperstructures: zzstructures, mSpaces, and polyarchies

ABSTRACT

Hypermedia applications tend to use simple representations for navigation: most commonly, nodes are organized within an unconstrained graph, and users are presented with embedded links or lists of links. Recently, new data structures have emerged which may serve as alternative models for both the organization, and presentation, of hypertextual nodes and links. In this paper, we consider zzstructures, mSpaces, and polyarchies from the perspective of graph theory, and compare these models formally. The novel aspects of this work include: providing a sound, graph-theoretic analysis of zzstructures; the identification of a new class of polyarchies associated with mSpaces; and the comparison and classification of these and other structures within a taxonomy. The taxonomy that results from our comparison allows us to consider, first; what the distinct characteristics of each model are at a fundamental level, and second; what model or attributes of a model may be most appropriate for the design goals of a given hypermedia application.

REFERENCES

• 1: Christopher Bailey , Samhaa R. El-Beltagy , Wendy Hall, Link Augmentation: A Context-Based Approach to Support Adaptive Hypermedia, Revised Papers from the nternational Workshops OHS-7, SC-3, and AH-3 on Hypermedia: Openness, Structural Awareness, and Adaptivity, p.239-251, August 14-18, 2001
• 2: Deborah Barreau , Bonnie A. Nardi, Finding and reminding: file organization from the desktop, ACM SIGCHI Bulletin, v.27 n.3, p.39-43, July 1995 [doi>10.1145/221296.221307]
• 3: L. Bartram. Can motion increase user interface bandwidth? In Proc. IEEE Conference on Systems, Man and Cybernetics, pages 1686--1692, 1997.
• 4: T. Berners-Lee, J. Hendler, and O. Lassila. The semantic web. Scientific American, May 2001.
• 5: Chaomei Chen , Mary Czerwinski, From latent semantics to spatial hypertext—an integrated approach, Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems: links, objects, time and space---structure in hypermedia systems, p.77-86, June 20-24, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276627.276636]
• 6: Nathan Conklin , Sandeep Prabhakar , Chris North, Multiple Foci Drill-Down through Tuple and Attribute Aggregation Polyarchies in Tabular Data, Proceedings of the IEEE Symposium on Information Visualization (InfoVis'02), p.131, October 28-29, 2002
• 7: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 8: Pratik Dave , Unmil P. Karadkar , Richard Furuta , Luis Francisco-Revilla , Frank Shipman , Suvendu Dash , Zubin Dalal, Browsing intricately interconnected paths, Proceedings of the fourteenth ACM conference on Hypertext and hypermedia, August 26-30, 2003, Nottingham, UK [doi>10.1145/900051.900071]
• 9: George W. Furnas , Jeff Zacks, Multitrees: enriching and reusing hierarchical structure, Proceedings of the SIGCHI conference on Human factors in computing systems: celebrating interdependence, p.330-336, April 24-28, 1994, Boston, Massachusetts, United States [doi>10.1145/191666.191778]
• 10: Dominic Giampaolo, Practical File System Design with the Be File System, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 11: N. Gibbins, S. Harris, and m. c. schraefel. Applying mSpace interfaces to the semantic web, 2003. http://eprints.ecs.soton.ac.uk/archive/00008639/.
• 12: T. Lukka. A gentle introduction to Ted Nelson's ZigZag structure. (An incomplete work in progress) http://www.nongnu.org/gzz/gi/gi.html.
• 13: M. J. McGuffin. A graph-theoretic introduction to Ted Nelson's zzstructures, January 2004. http://www.dgp.toronto.edu/~mjmcguff/research/zigzag/.
• 14: T. Nelson. ZigZag tutorial. 1999. http://xanadu.com/zigzag/tutorial/ZZwelcome.html.
• 15: T. Nelson. ZZ cell programming. http://xanadu.com/zigzag/fw99/ZZcellProg.html.
• 16: T. H. Nelson. What's on my mind. Invited talk at the first Wearable Computer Conference, 1998. http://www.xanadu.com.au/ted/zigzag/xybrap.html.
• 17: Theodor Holm Nelson, Xanalogical structure, needed now more than ever: parallel documents, deep links to content, deep versioning, and deep re-use, ACM Computing Surveys (CSUR), v.31 n.4es, Dec. 1999 [doi>10.1145/345966.346033]
• 18: Theodor Holm Nelson, ZigZag (Tech briefing), Proceedings of the twelfth ACM conference on Hypertext and Hypermedia, August 14-18, 2001, Århus, none, Denmark [doi>10.1145/504216.504281]
• 19: George Robertson , Kim Cameron , Mary Czerwinski , Daniel Robbins, Polyarchy visualization: visualizing multiple intersecting hierarchies, Proceedings of the SIGCHI conference on Human factors in computing systems: Changing our world, changing ourselves, April 20-25, 2002, Minneapolis, Minnesota, USA [doi>10.1145/503376.503452]
• 20: m. c. schraefel, ConTexts: Adaptable Hypermedia, Proceedings of the International Conference on Adaptive Hypermedia and Adaptive Web-Based Systems, p.369-374, August 28-30, 2000
• 21: m. c. schraefel, M. Karam, and S. Zhao. mSpace: interaction design for user-determined, adaptable domain exploration in hypermedia. In Proceedings of AH2003 Workshop on Adaptive Hypermedia and Adaptive Web-Based Systems, pages 217--234, 2003.
• 22: M. Spenke and C. Beilken. Visualization of trees as highly compressed tables with InfoZoom, 2003. Unpublished entry in InfoVis 2003 Contest, held at IEEE Symposium on Information Visualization. http://www.cs.umd.edu/hcil/InfovisRepository/.
• 23: Michael Spenke , Christian Beilken , Thomas Berlage, FOCUS: the interactive table for product comparison and selection, Proceedings of the 9th annual ACM symposium on User interface software and technology, p.41-50, November 06-08, 1996, Seattle, Washington, United States [doi>10.1145/237091.237097]
• 24: P. David Stotts , Richard Furuta , Cyrano Ruiz Cabarrus, Hyperdocuments as automata: verification of trace-based browsing properties by model checking, ACM Transactions on Information Systems (TOIS), v.16 n.1, p.1-30, Jan. 1998 [doi>10.1145/267954.267955]
• 25: H. Van Dyke Parunak, Don't link me in: set based hypermedia for taxonomic reasoning, Proceedings of the third annual ACM conference on Hypertext, p.233-242, December 15-18, 1991, San Antonio, Texas, United States [doi>10.1145/122974.122998]
• 26: David D. Woods, Visual momentum: a concept to improve the cognitive coupling of person and computer, International Journal of Man-Machine Studies, v.21 n.3, p.229-244, Sept. 1984 [doi>10.1016/S0020-7373(84)80043-7]
• 27: Polle T. Zellweger , Bay-Wei Chang , Jock D. Mackinlay, Fluid links for informed and incremental link transitions, Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems: links, objects, time and space---structure in hypermedia systems, p.50-57, June 20-24, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276627.276633]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.4 Hypertext/Hypermedia
          Subjects: Navigation

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.4 Hypertext/Hypermedia
          Subjects: Theory

General Terms:
Human Factors, Theory

Keywords:
ZigZag, connective structures, edge-coloured graphs, mSpace, multitrees, polyarchies, zzstructures