A formal description of zz-structures

Abstract

The focus of this paper is on particular and innovative structures for storing, linking and manipulating information: the zz-structures. In the last years, we worked at the formalization of these structures, retaining that the description of the formal aspects can provide a better understanding of them, and can also stimulate new ideas, projects and research. This work presents our contribution for a deeper discussion on zz-structures.

1. INTRODUCTION

At the first Wearable Computer Conference [ 18 ], Ted Nelson proposed “a prototype that implements some interesting ideas, intended to lead to such a new kind of simple and unified world, possibly to permit the unification of everything that non-computer people want to do with computTM 1 ers”. The software was ZigZag , a “principled system of interconnections” [ 19 ] and a new, graph-centric system of conventions for data and computing, based on the so-called zz-structures.

Nelson writes [ 19 ]: “The ZigZag system is very hard to explain, especially since it resembles nothing else in the computer field that we know of, except perhaps a spreadsheet cut into strips and glued into loops”. Zz-structures are hyperorthogonal, non-hierarchical structures for storing, linking and manipulating data. Intuitively, data are contained in cells that are connected by crossing dimensions forming a structure that resembles a spreadsheet but contains intricate connections [ 18, 19, 20, 21, 22, 23 ].

Zz-structures have been seen from many different perspectives: merely a large variety of implementations and applitudes, and some formal models have been proposed. We specify that we use the term “applitude” instead of “application”. Nelson states [ 23 ]: “Instead of “applications”, separated zones of function and usage connected by the narrow channels of clipboard and file export/import, we have “applitudes” which are deeply interconnected to the whole, amongst themselves, and amongst their parts”. The main difference is that, unlike applications, applitudes exploit the dense and intricate connections among the information contained in a zz-structure. Applitudes can also be combined with each other and are not “walled off” from the rest of the system. Table 1 collects a list of research contributions (applitudes and implementations), developed using zz1”ZigZag” is a registered trademark in the U.S.A. for the zzstructure-based software of Project Xanadu. structures.

Year 1984-2004

Domain

[ 23 ] [ 24 ] [ 4 ] [ 16, 17 ] [ 17 ] [ 1 ] [ 9 ] [ 2, 10, 12 ] [ 3, 7 ] [ 5 ] [ 6 ] [ 11 ] [ 8 ]

Zz-structures are “a generalized representation for all data and a new set of mechanisms for all computing” [ 23 ]: innovative structures for storing, linking and manipulating information.

The intention of this work is to present our contribution to the formalization of zz-structures and to encourage further discussion. In our opinion, the description of a formal model can provide a deeper understanding of the model and can stimulate new ideas, projects and research.

The paper is organized as follows: in Section 2, we give an informal description of zz-structures, that prepares the reader to the formal model presented in Section 3. We conclude in Section 4 with a brief discussion and future look. 2.

THE ZZ-STRUCTURES

Zz-structures introduce a new, graph-centric system of conventions for data and computing [ 19 ]. A zz-structure can be thought of as a space filled with cells. Each cell may have a content (such as integers, text, images, audio, etc.), and it is called atomic if it contains only one unit of data of one type, or it is called referential if it represents a package of different cells [ 23 ].

Cells are connected together with links of the same color into linear sequences called dimensions. A single series of cells connected in the same dimension is called rank, i.e., a rank is in a particular dimension and a dimension may contain many different ranks. The starting and the ending cells of a rank are called, headcell and tailcell, respectively, and the direction from the starting (ending) to the ending (starting) cell is called posward (respectively, negward). For any dimension, a cell can only have one connection in the posward direction, and one in the negward direction. This ensures that all paths are non-branching, and thus embodies the simplest possible mechanism for traversing links. Dimensions are used to project different structures: Ordinary lists are viewed in one dimension; spreadsheets and hierarchical directories in many dimensions.

There are many different ways to view these structures: A raster is a way of selecting the cells from a structure, while a view is a way of placing the cells on a screen. Generic views are designed to be used in a big variety of cases and usually show only few dimensions or few steps in each dimension. Among them the most common views are the twodimensional rectangular views: The cells are placed, using different rasters, on a Cartesian plane where the dimensions increase going down and to the right. The simplest raster is the row and column raster, i.e., two rasters which are the same but rotated of 90 degrees from each other. A cell is chosen and placed at the center of the plane (cursor centric view). The chosen cell, called focus, may be changed by moving the cursor horizontally and vertically. In a row view I, a rank is chosen and placed vertically. Then the ranks related to the cells in the vertical rank are placed horizontally. Vice versa, in the column view H, a rank is chosen and placed horizontally and the related ranks are placed vertically. All the cells are denoted by different numbers. Note that in a view the same cell may appear in different positions as it may represent the intersection of different dimensions. 3.

FORMALIZING ZZ-STRUCTURES

As we have mentioned in the introduction, zz-structures have been studied from many perspectives, and many implementations and applitudes have been proposed in different fields. Some research has also been provided towards a formal definition of these structures. In the seminal work of [ 14 ], we find the first proposal of formalizing these structures in terms of graphs; this work has been extended and motivated in [ 15 ], where the authors use this formalization in order to compare these structures with mSpaces and Polyarchies. This comparison is done building a taxonomy as a subsumption diagram, a subsumption being a generalization of something. The general result is that zz-structures subsume lists, 2D arrays, trees and also polyarchies; polyarchies subsume mSpace polyarchies. Finally zz-structures and edge-colored multigraph subsume each other.

Later, in [ 9, 10, 11, 12 ] we have revisited and redefined into more precise mathematical terms, the definitions of zzstructures provided in [ 14, 15 ], and have also introduced new notions such as the one of local orientation, borrowed from the field of distributed computing, and required to provide a formal definition of local posward and negward directions. The formal model is a requirement in [ 9 ] for the construction of an actor-based model where actors can add new connections between cells of the zz-structure, i.e., dynamically modifying its structure. Moreover, this formalization has provided interesting tools for the introduction of new formal concepts, such as the extension of the standard notion of view to higher dimensional views (e.g., n-dimensions H and I views, 3-dimensions extended H and I views, etc.) [ 10, 12 ], and for the definition of techniques that allow users to display neighbouring views (i.e., views centered in a cell at distance one from the previous one) [ 11 ].

The aim of this section is to summarize, analyze, and illustrate with new examples, discuss and relate all the above proposals in order to provide a general overview of the formal model, at least for the original concepts defined by Nelson in [ 18 ].

Zz-structure.

In [ 14, 15 ] the authors define a zz-structure as a directed multigraph with colored edges (i.e., a graph where pair of nodes may have multiple colored edges connecting them), where each node has at most one outcoming edge and one outgoing edge for each color. In [ 9 ] the authors further formalize these concepts (choosing however bidirectional links) as follows.

Consider an edge-colored multigraph ECM G = (M G, C, c) where: M G = (V, E, f ) is a multigraph composed of a set of vertices V , a set of edges E and a surjective function f : E → {{u, v} | u, v ∈ V, u = v}. C is a set of colors, and c : E → C is an assignment of colors to edges of the multigraph. Finally, deg(x) (respectively, degk(x)) denotes the number of edges incident to x, (respectively, of color ck).

Definition 1. : Zz-structure - A zz-structure is an edgecolored multigraph S = (M G, C, c), where M G = (V, E, f ), and ∀x ∈ V, ∀k = 1, 2, ..., |C|, degk(x) = 0, 1, 2. Each vertex of a zz-structure is called zz-cell and each edge a zz-link. The set of isolated vertices is V0 = {x ∈ V : deg(x) = 0}. An example of a zz-structure is shown in Figure 1. Normal, dotted and thick lines represent different colors.

Dimension.

In [ 15 ] the authors state that “each of the edge colors correspond to a different spatial dimension”. This concept, together with all the following definitions, is further formalized in [ 9 ] where the authors state that an alternative way of viewing a zz-structure is a union of subgraphs, each of them containing edges of a unique color.

Proposition 1. Consider a set of colors C = {c1, c2, ..., c|C|} and a family of indirect edge-colored graphs {D1, D2, ..., D|C|}, where Dk = (V, Ek, f, {ck}, c), with k = 1, ..., |C|, is a graph such that: 1) Ek = ∅; 2) ∀x ∈ V , degk(x) = 0, 1, 2. Then, S = S|kC=|1 Dk is a zz-structure.

Definition 2. : Dimension - Given a zz-structure S = S|kC=|1 Dk, then each graph Dk, k = 1, . . . , |C|, is a distinct dimension of S. The zz-structure of Figure 1 contains three dimensions Dthick, Dnormal and Ddotted, respectively represented by thick, normal, and dotted lines and shown in Figure 2. In turn, each dimension is composed by a set of connected components and a set (eventually empty) of isolated vertices. As an example, Dnormal is composed of a cycle {v1, v2, v4, v1}, a path {v3, v5}, and one isolated vertex v6, while Dthick is composed of two distinct paths {v3, v1}, {v2, v4, v5, v6}, and no isolated vertex.

Rank.

Each “series of cells connected sequentially in any dimension” identifies a rank [ 23 ].

Definition 3. : Rank - Consider a dimension Dk = (V, Ek, f, {ck}, c), k = 1, . . . , |C| of a zz-structure S = ∪|kC=|1Dk. Then, each of the lk (lk ≥ 1) connected components of Dk is called a rank. ∀x ∈ Vik, Vik ∈ V , degk(x) = 1, 2. (Tih=us 1a, 2ra,n..k. ,islka)nsuinchdirtehcatt g1r)apEhikR∈ik =Ek(Vaink,dEEik,ikf,={ck∅}, c) ; 2)

Definition 4. : Ringrank - A ringrank is a rank Rik, where ∀x ∈ Vik, degk(x) = 2.

In Figure 2, the dimension Dthick has two ranks: {v3, v1} and {v2, v4, v5, v6}; the dimension Dnormal has one rank {v3, v5}, and one ringrank {v1, v2, v4, v1}.

Cells and their orientation.

A vertex [ 9 ] has local orientation on a rank if each of its (1 or 2) incident edges has assigned a distinct label (1 or -1). More formally (see also [ 13 ]):

Definition 5. : Local orientation - Consider a rank

Rik = (Vik, Eik, f, {ck}, c) of a zz-structure S = ∪|kC=|1Dk. Then, ∃ a function gxi : Eik → {−1, 1}, such that, ∀x ∈ Vik, if ∃y, z ∈ Vik : {x, y}, {x, z} ∈ Eik, then gxi({x, y}) = gxi({x, z}). Thus, we say that each vertex x ∈ Vik has a local orientation in Rik.

Definition 6. : Posward and negward directions

Given an edge {a, b} ∈ Eik, we say that {a, b} is in a posward direction from a in Rik, and that b is its posward cell iff ga({a, b}) = 1, else {a, b} is in a negward direction and a i is its negward cell. Moreover, a path in rank Rik follows a posward (negward) direction if it is composed of a sequence of edges of value 1 (respectively, -1).

Head and tail cells.

If we focus on a vertex x, Rik = . . . x−2x−1xx+1x+2 . . . is expressed in terms of negward and posward cells of x: x−1 is the negward cell of x and x+1 the posward cell. We also assume x0 = x. In general x−i (x+i) is a cell at distance i in the negward (posward) direction.

Definition 7. : Headcell and tailcell - Given a rank

Rik = (Vik, Eik, f, {ck}, c), a cell x is the headcell of Rik iff ∃ its posward cell x+1 and ∃ its negward cell x−1. Analogously, a cell x is the tailcell of Rik iff ∃ its negward cell x−1 and ∃ its posward cell x+1.

Views.

In the following, we denote with x ∈ R(ax) the rank R(ax) related to vertex x, of color ca.

Definition 8. : H-view - Given a zz-structure S = ∪|kC=|1Dk, where Dk = ∪lik=1(Rik∪V0k), and where Rik = (Vik, Eik, f, {ck}, c), the H-view of size l = 2m + 1 and of focus x ∈ V = ∪lik=0Vik, on main vertical dimension Da and secondary horizontal dimension Db (a, b ∈ {1, ..., lk}), is defined as a tree whose embedding in the plane is a partially connected colored l × l mesh in which: • the central node, in position ((m + 1), (m + 1)), is the focus x; • the horizontal central path (the m + 1-th row) from left to right, focused in vertex x ∈ R(bx) is: x−g . . . x−1xx+1 . . . x+p where xs ∈ R(bx), for s = −g, . . . , +p (g, p ≤ m). • for each cell xs, s = −g, . . . , +p, the related vertical path, from top to bottom, is: (xs)−gs . . . (xs)−1xs(xs)+1 . . . (xs)+ps , where (xs)t ∈ R(axs), for t = −gs, . . . , +ps (gs, ps ≤ m).

Intuitively, the H-view extracts ranks along the two chosen dimensions. Note that, the name H-view comes from the fact that the columns remind the vertical bars in a capital letter H. Observe also that the cell x−g (in the m + 1-th row) is the headcell of R(bx) if g < m and the cell x+p (in the same row) is the tailcell of R(bx) if p < m. Analogously, the cell x−gs is the headcell of R(axs) if gs < m and the cell x+ps is the tailcell of R(axs) if ps < m. Intuitively, the view is composed of l × l cells unless some of the displayed ranks have their headcell or tailcell very close (less than m steps) to the chosen focus.

As an example consider Figure 3 left that refers to the zz-structure of Figure 1. The main vertical dimension is Ddotted and the secondary horizontal dimension is Dthick. The view has size l = 2m + 1 = 5, the focus is the node v5, the horizontal central path is {v2, v4, v5, v6}. The vertical path related to v4 is {v3, v5, v4, v6}, that is v6 is the tailcell of the rank as ps = 1 < m = 2.

The I-view can be defined analogously to the H-view [ 9 ]. An example of I-view with main horizontal dimension Ddotted, secondary vertical dimension Dthick, size l = 5 and focus v5 is shown in Figure 3 right.

We can now extend the known definition of H and I views to a number n > 2 of dimensions [ 10 ]. Intuitively, we will build n − 1 different H-views (respectively, I-views), centered in the same focus, with a fixed main dimension and a secondary dimension chosen among the other n − 1 dimensions. Formally:

Definition 9. n-dimensions H-view - Given a zz-struc

ture S = ∪|kC=|1Dk, where Dk = ∪lik=1(Rik ∪ V0k), and where Rik = (Vik, Eik, f, {ck}, c), the n-dimensions H-view of size l = 2m + 1 and of focus x, x ∈ V = ∪lik=0Vik, on dimensions D1, D2, . . . , Dn is composed of n − 1 rectangular H-views, of main dimension D1 and secondary dimensions Di, i = 2, . . . , n, all centered in the same focus x.

Analogously, we can define an n-dimensions I-view. An example of a 3-dimensions H-view is provided in Figure 4. This view has focus on v4, size l = 5, main dimension Ddotted, and secondary dimensions Dthick and Dnormal.

A star view [ 12 ] visualizes information related to a focus vertex and a set of n chosen dimensions. There are two typologies of star views: the star view and the m-extended star view.

Definition 10. Star view - Given a zz-structure S = S|kC=|1 Dk, where Dk = Slik=1 Rik ∪ V0k, and where Rik = (Vik, Eik, f, {ck}, c), the star view of focus x ∈ V = Slik=0 Vik and dimensions D1, D2, . . . , Dn is a star graph n+1-star on central vertex x and neighborhood N (x) = {y ∈ V : y = x+1, x+1 ∈ R(ix), i ∈ {1, . . . , n}}.

The m-extended star view extends the number of cells directly accessible from a view; it is based on a star view, but, for each vertex y in the neighborhood N (x), adds the set of the p (p ≤ m) posward cells related to the given dimensions.

Definition 11. m-extended star view - Given a zz-struc

ture S = S|kC=|1 Dk, where Dk = Slik=1 Rik ∪ V0k, and where Rik = (Vik, Eik, f, {ck}, c), the m-extended star view is a star view of focus x ∈ V = Slik=0 Vik, dimensions D1, D2, . . . , Dn, and each extension constituted, ∀y ∈ N (x) and ∀i ∈ {1, . . . , n}, by the paths (y+1, . . . , y+p) ⊆ R(ix) (p ≤ m).

The view has focus v3 and shows the connections along six dimensions. Note that cells v1 and v5 have, e.g., extension p = 0, while the maximum extension (p = m = 5) is reached only by the connection along the dashed and double lines.

For lack of space, we cannot provide all the formal extensions to multidimensional views, the algorithms for the additions of new connections and the displaying of neighbouring views and we refer interested readers to [ 9, 10, 11, 12 ]. Just note that the above formal models have found interesting real world applications. Very briefly, in [ 9 ] the authors present an actor-based model, capable of representing both hypermedia distribution and collaborative schemes among different and heterogeneous entities which are part of a particular grid infrastructure and cooperate in order to achieve common goals and solve problems. In [ 10, 12 ], the authors propose the use zz-structures in order to help an author of an e-learning environment, to organize documents on a given topic in a concept space, and to create semantic interconnections and personalized maps. Finally, in [ 11 ] the authors propose a multi-agent adaptive system to support tours of virtual museums. In particular, the agents collaborate in order to help users visualizing their personalized views and choosing their navigational path inside the virtual museum.

DISCUSSION AND CONCLUSIONS

In this paper we have concentrated our attention on the formal models for representing zz-structures. Besides the motivations, above provided, in our opinion a formal model can help the navigation of a user by providing extra information, such as, e.g., the distances between the cell where (s)he is located and one where (s)he wants to move. Defining zzstructures as graphs allows, e.g., the application of known algorithms for the (dynamical) computation of shortest paths, or of paths with small stretch factor (i.e., ratio between the best path connecting two nodes and the shortest path). A user may thus compute a general shortest path, or, e.g., a shortest path (given that the two nodes are connected) in the subgraph induced by a particular color, meaning that (s)he wants to move following a unique dimension, i.e., concept.

Currently we are extending the formal model and preparing a survey of current literature on zz-structures, in order to analyze and synthesize it, and to stimulate new reflections and studies on this innovative way of conceiving the organization of information and knowledge.

References

[1] I. Anderson. From ZigZagT M to BigBag : Seeing the wood and the trees in online archive finding aids . In Proceedings of the Workshop on New Forms of Xanalogical Storage and Function . Turin, Italy, 29 June 2009.

[2] M. Andric , V. Devedzic , W. Hall, and L. Carr . Keywords linking method for selecting educational web resources a` la ZigZag . International Journal of Knowledge and Learning , 3 ( 1 ): 30 - 45 , 2007 .

[3] S. Canazza and A. Dattolo . Open, dynamic electronic editions of multidimensional documents . In IASTED Proceedings of European Conference on Internet and Multimedia Systems and Applications , pages 230 - 235 . Chamonix (France), 14 - 16 March 2007 .

[4] L. Carr . ZigZag for web browsers , 2001 . http://www.ecs.soton.ac.uk/∼lac/zigzag.

[5] P. Casoto , A. Dattolo , F. Ferrara , N. Pudota , P. Omero , and C. Tasso . Toward making agent uml practical: a textual notation and a tool . In Proceedings of the Workshop on Adaptation for the Social Web, 5th ACM Int. Conf. on Adaptive Hypermedia and Adaptive Web-Based Systems , pages 14 - 23 . Germany, 29 July - 1 August 2008 .

[6] P. Casoto , A. Dattolo , and C. Tasso . Sentiment classification for the italian language: A case study on movie reviews . Journal of Internet Technology, Special issue on Intelligent Agent and Knowledge Mining , 9 ( 4 ): 365 - 373 , 2008 .

[7] A. Dattolo . Authoring and navigating ethnic music audio archives . Signal Processing , 2009 (to appear).

[8] A. Dattolo , F. Ferrara , and C. Tasso . Supporting personalized user concept spaces and recommendations for a publication sharing system . In UMAP '09: Proceedings of the 1th and 17th international conference on User Modeling , Adaptation, and Personalization . Trento, Italy, 22 - 29 June 2009.

[9] A. Dattolo and F. L. Luccio . A new actor-based structure for distributed systems . In International Conference on Hypermedia and Grid Systems (HGS07) , pages 195 - 201 . Opatija, Adriatic Coast (Croatia), 21 - 25 May 2007 .

[10] A. Dattolo and F. L. Luccio . Formalizing a model to represent and visualize concept spaces in e-learning environments . In Proceedings of the 4th Webist International Conference (WEBIST08) , pages 339 - 346 . Funchal, Madeira, Portugal, 4 -7 May 2008 .

[11] A. Dattolo and F. L. Luccio . Visualizing personalized views in virtual museum tours . In International Conference on Human System Interaction (HSI08) , pages 109 - 114 . Krakow, Poland, 25 - 27 May 2008 .

[12] A. Dattolo and F. L. Luccio . A new concept map model for e-learning environment . In Lecture Notes in Business Information Processing 18 , pages 404 - 417 , April 2009 .

[13] P. Flocchini , B. Mans , and N. Santoro . Sense of direction: Definitions, properties and classes . Networks , 32 ( 3 ): 165 - 180 , 1998 .

[14] M. McGuffin . A graph-theoretic introduction to Ted Nelson's Zzstructures . January 2004 . http://www.dgp. toronto.edu/∼mjmcguff/research/zigzag/.

[15] M. McGuffin and m. c. schraefel. A comparison of Hyperstructures: Zzstructures, mSpaces, and Polyarchies . In Proceedings of the 15th ACM Conference on Hypertext and Hypermedia (HT'04) , pages 153 - 162 . Santa Cruz, California, USA, 9 - 13 August 2004 .

[16] A. Moore and T. Brailsford . Unified hyperstructures for bioinformatics: escaping the application prison . Journal of Digital Information , 5 ( 1 ):Article No. 254 , 2004 .

[17] A. Moore , J. Goulding , T. Brailsford , and H. Ashman . Practical applitudes: Case studies of applications . In Proceedings of the 15th ACM Conference on Hypertext and Hypermedia (HT'04) , pages 143 - 152 . Santa Cruz, California, USA, 9 - 13 August 2004 .

[18] T. H. Nelson . What's on my mind . In Invited talk at the first Wearable Computer Conference. Fairfax VA , 12 - 13 May 1998 . http://www.xanadu.com.au/ted/zigzag/xybrap.html.

[19] T. H. Nelson . Welcome to ZigZag. 1999 . http://xanadu.com/zigzag/tutorial/ZZwelcome.html.

[20] T. H. Nelson . Xanalogical structure, needed now more than ever: parallel documents, deep links to content, deep versioning, and deep re-use . ACM Computing Surveys , 31 ( 4 :33), 1999 .

[21] T. H. Nelson. ZigZag (tech briefing): Deeper cosmology, deeper documents . In Proceedings of the 12-th ACM conference on Hypertext and Hypermedia (HT'01) , pages 261 - 262 . University of Aarhus, Aarhus, Denmark, 14 - 18 August 2001 .

[22] T. H. Nelson . Structure, tradition and possibility . In Proceedings of 14th ACM Conference on Hypertext and Hypermedia (HT'03) . Nottingham, United Kingdom, 26 - 30 August 2003 . http://www.ht03.org/keynote-ted.html.

[23] T. H. Nelson . A cosmology for a different computer universe: data model mechanism, virtual machine and visualization infrastructure . Journal of Digital Information: Special Issue on Future Visions of Common-Use Hypertext , 5 ( 1 ): 298 , 2004 .

[24] K. Wideroos. Awt (associative writing tool): supporting writing process with a ZigZag based writing tool - work in progress . In Proceedings of the 12-th ACM conference on Hypertext and Hypermedia (HT'01) , pages 35 - 36 . University of Aarhus, Aarhus, Denmark, 14 - 18 August 2001 .