A formal description of zz-structures Antonina Dattolo Flaminia L. Luccio Dipartimento di Matematica e Informatica Dipartimento di Informatica Università degli Studi di Udine, Italy Università Ca’ Foscari, Venezia, Italy antonina.dattolo@uniud.it luccio@unive.it ABSTRACT structures. The focus of this paper is on particular and innovative struc- Year Domain Reference tures for storing, linking and manipulating information: the 1984-2004 zz-vims (Azz, Ezz, [23] zz-structures. Gzz and Zzz, and Lzz) In the last years, we worked at the formalization of these structures, retaining that the description of the formal as- 2001 Associative writing [24] pects can provide a better understanding of them, and can 2001 Various Demos [4] also stimulate new ideas, projects and research. 2002-2006 Bionformatics [16, 17] This work presents our contribution for a deeper discussion 2004 Cellular phones [17] on zz-structures. 2006-2007 Archival finding aids [1] 2007 Grid Systems [9] 2007-2009 Web-based Education [2, 10, 12] 1. INTRODUCTION 2007-2009 Audio Archives [3, 7] At the first Wearable Computer Conference [18], Ted Nel- 2008 Personal Information Space [5] son proposed “a prototype that implements some interesting 2008 Sentiment Classification [6] ideas, intended to lead to such a new kind of simple and 2008 Virtual Museums [11] unified world, possibly to permit the unification of every- 2009 Publication Sharing Systems [8] thing that non-computer people want to do with comput- TM ers”. The software was ZigZag 1 , a “principled system of Table 1: Models and applitudes interconnections” [19] and a new, graph-centric system of conventions for data and computing, based on the so-called zz-structures. Zz-structures are “a generalized representation for all data Nelson writes [19]: “The ZigZag system is very hard to ex- and a new set of mechanisms for all computing” [23]: inno- plain, especially since it resembles nothing else in the com- vative structures for storing, linking and manipulating in- puter field that we know of, except perhaps a spreadsheet cut formation. into strips and glued into loops”. Zz-structures are hyper- The intention of this work is to present our contribution to orthogonal, non-hierarchical structures for storing, linking the formalization of zz-structures and to encourage further and manipulating data. Intuitively, data are contained in discussion. In our opinion, the description of a formal model cells that are connected by crossing dimensions forming a can provide a deeper understanding of the model and can structure that resembles a spreadsheet but contains intri- stimulate new ideas, projects and research. cate connections [18, 19, 20, 21, 22, 23]. The paper is organized as follows: in Section 2, we give Zz-structures have been seen from many different perspec- an informal description of zz-structures, that prepares the tives: merely a large variety of implementations and appli- reader to the formal model presented in Section 3. We tudes, and some formal models have been proposed. We conclude in Section 4 with a brief discussion and future look. specify that we use the term “applitude” instead of “appli- cation”. Nelson states [23]: “Instead of “applications”, sep- 2. THE ZZ-STRUCTURES arated zones of function and usage connected by the nar- row channels of clipboard and file export/import, we have Zz-structures introduce a new, graph-centric system of “applitudes” which are deeply interconnected to the whole, conventions for data and computing [19]. A zz-structure amongst themselves, and amongst their parts”. The main can be thought of as a space filled with cells. Each cell may difference is that, unlike applications, applitudes exploit the have a content (such as integers, text, images, audio, etc.), dense and intricate connections among the information con- and it is called atomic if it contains only one unit of data of tained in a zz-structure. Applitudes can also be combined one type, or it is called referential if it represents a package with each other and are not “walled off” from the rest of of different cells [23]. the system. Table 1 collects a list of research contribu- Cells are connected together with links of the same color tions (applitudes and implementations), developed using zz- into linear sequences called dimensions. A single series of cells connected in the same dimension is called rank, i.e., 1 a rank is in a particular dimension and a dimension may ”ZigZag” is a registered trademark in the U.S.A. for the zzstructure-based software of Project Xanadu. contain many different ranks. The starting and the ending 7 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. Dimen- sions 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 Figure 1: An example of zz-structure. 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 di- to display neighbouring views (i.e., views centered in a cell mension. Among them the most common views are the two- at distance one from the previous one) [11]. dimensional rectangular views: The cells are placed, using The aim of this section is to summarize, analyze, and il- different rasters, on a Cartesian plane where the dimensions lustrate with new examples, discuss and relate all the above increase going down and to the right. The simplest raster proposals in order to provide a general overview of the formal is the row and column raster, i.e., two rasters which are the model, at least for the original concepts defined by Nelson same but rotated of 90 degrees from each other. A cell is in [18]. chosen and placed at the center of the plane (cursor centric view). The chosen cell, called focus, may be changed by Zz-structure. moving the cursor horizontally and vertically. In a row view In [14, 15] the authors define a zz-structure as a directed I, a rank is chosen and placed vertically. Then the ranks multigraph with colored edges (i.e., a graph where pair of related to the cells in the vertical rank are placed horizon- nodes may have multiple colored edges connecting them), tally. Vice versa, in the column view H, a rank is chosen and where each node has at most one outcoming edge and one placed horizontally and the related ranks are placed verti- outgoing edge for each color. In [9] the authors further for- cally. All the cells are denoted by different numbers. Note malize these concepts (choosing however bidirectional links) that in a view the same cell may appear in different positions as follows. as it may represent the intersection of different dimensions. Consider an edge-colored multigraph ECM G = (M G, C, c) where: M G = (V, E, f ) is a multigraph composed of a set 3. FORMALIZING ZZ-STRUCTURES of vertices V , a set of edges E and a surjective function As we have mentioned in the introduction, zz-structures f : E → {{u, v} | u, v ∈ V, u = v}. C is a set of colors, have been studied from many perspectives, and many imple- and c : E → C is an assignment of colors to edges of the mentations and applitudes have been proposed in different multigraph. Finally, deg(x) (respectively, degk (x)) denotes fields. Some research has also been provided towards a for- the number of edges incident to x, (respectively, of color ck ). mal definition of these structures. In the seminal work of Definition 1. : Zz-structure - A zz-structure is an edge- [14], we find the first proposal of formalizing these struc- colored multigraph S = (M G, C, c), where M G = (V, E, f ), tures in terms of graphs; this work has been extended and and ∀x ∈ V, ∀k = 1, 2, ..., |C|, degk (x) = 0, 1, 2. Each vertex motivated in [15], where the authors use this formalization of a zz-structure is called zz-cell and each edge a zz-link. The in order to compare these structures with mSpaces and Pol- set of isolated vertices is V0 = {x ∈ V : deg(x) = 0}. yarchies. This comparison is done building a taxonomy as a subsumption diagram, a subsumption being a generaliza- An example of a zz-structure is shown in Figure 1. Normal, tion of something. The general result is that zz-structures dotted and thick lines represent different colors. subsume lists, 2D arrays, trees and also polyarchies; pol- yarchies subsume mSpace polyarchies. Finally zz-structures Dimension. and edge-colored multigraph subsume each other. In [15] the authors state that “each of the edge colors Later, in [9, 10, 11, 12] we have revisited and redefined correspond to a different spatial dimension”. This concept, into more precise mathematical terms, the definitions of zz- together with all the following definitions, is further formal- structures provided in [14, 15], and have also introduced ized in [9] where the authors state that an alternative way of new notions such as the one of local orientation, borrowed viewing a zz-structure is a union of subgraphs, each of them from the field of distributed computing, and required to pro- containing edges of a unique color. vide a formal definition of local posward and negward direc- tions. The formal model is a requirement in [9] for the con- Proposition 1. Consider a set of colors C = {c1 , c2 , ..., c|C| } struction of an actor-based model where actors can add new and a family of indirect edge-colored graphs {D1 , D2 , ..., connections between cells of the zz-structure, i.e., dynami- D|C| }, where Dk = (V, E k , f, {ck }, c), with k = 1, ..., |C|, is cally modifying its structure. Moreover, this formalization a graph such that: 1) E k = ∅; 2) ∀x ∈ V , degk (x) = 0, 1, 2. S|C| has provided interesting tools for the introduction of new Then, S = k=1 Dk is a zz-structure. formal concepts, such as the extension of the standard no- tion of view to higher dimensional views (e.g., n-dimensions Definition 2. : Dimension - Given a zz-structure S = S|C| k k=1 D , then each graph D , k = 1, . . . , |C|, is a distinct k H and I views, 3-dimensions extended H and I views, etc.) [10, 12], and for the definition of techniques that allow users dimension of S. 8 The zz-structure of Figure 1 contains three dimensions Dthick , Head and tail cells. Dnormal and Ddotted , respectively represented by thick, nor- If we focus on a vertex x, Rik = . . . x−2 x−1 xx+1 x+2 . . . is mal, and dotted lines and shown in Figure 2. In turn, each 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 . Figure 2: The dimensions Dthick , Dnormal and Ddotted . Views. dimension is composed by a set of connected components In the following, we denote with x ∈ R(x) a a the rank R(x) and a set (eventually empty) of isolated vertices. As an related to vertex x, of color ca . example, Dnormal is composed of a cycle {v1 , v2 , v4 , v1 }, a |C| path {v3 , v5 }, and one isolated vertex v6 , while Dthick is Definition 8. : H-view - Given a zz-structure S = ∪k=1 Dk , composed of two distinct paths {v3 , v1 }, {v2 , v4 , v5 , v6 }, and where Dk = ∪i=1 lk (Rik ∪V0k ), and where Rik = (Vik , Eik , f, {ck }, no isolated vertex. c), the H-view of size l = 2m + 1 and of focus x ∈ V = ∪li=0 k Vik , on main vertical dimension Da and secondary hor- Rank. izontal dimension Db (a, b ∈ {1, ..., lk }), is defined as a tree Each “series of cells connected sequentially in any dimen- whose embedding in the plane is a partially connected col- sion” identifies a rank [23]. ored l × l mesh in which: Definition 3. : Rank - Consider a dimension Dk = (V, • the central node, in position ((m + 1), (m + 1)), is the |C| focus x; E , f, {ck }, c), k = 1, . . . , |C| of a zz-structure S = ∪k=1 Dk . k Then, each of the lk (lk ≥ 1) connected components of Dk • the horizontal central path (the m + 1-th row) from is called a rank. left to right, focused in vertex x ∈ R(x) b is: −g −1 +1 +p Thus a rank is an indirect graph Rik = (Vik , Eik , f, {ck }, c) x . . . x xx . . . x where x ∈ R(x) s b , for s = (i = 1, 2, . . . , lk ) such that 1) Eik ∈ E k and Eik = ∅; 2) −g, . . . , +p (g, p ≤ m). ∀x ∈ Vik , Vik ∈ V , degk (x) = 1, 2. • for each cell xs , s = −g, . . . , +p, the related vertical path, from top to bottom, is: Definition 4. : Ringrank - A ringrank is a rank Rik , (xs )−gs . . . (xs )−1 xs (xs )+1 . . . (xs )+ps , where (xs )t ∈ where ∀x ∈ Vik , degk (x) = 2. a R(x s ) , for t = −gs , . . . , +ps (gs , ps ≤ m). In Figure 2, the dimension Dthick has two ranks: {v3 , v1 } Intuitively, the H-view extracts ranks along the two chosen and {v2 , v4 , v5 , v6 }; the dimension Dnormal has one rank dimensions. Note that, the name H-view comes from the {v3 , v5 }, and one ringrank {v1 , v2 , v4 , v1 }. 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 Cells and their orientation. row) is the headcell of R(x)b if g < m and the cell x+p (in A vertex [9] has local orientation on a rank if each of its the same row) is the tailcell of R(x) b if p < m. Analogously, (1 or 2) incident edges has assigned a distinct label (1 or -1). −gs a the cell x is the headcell of R(xs ) if gs < m and the cell More formally (see also [13]): x+ps is the tailcell of R(x a s ) if ps < m. Intuitively, the view Definition 5. : Local orientation - Consider a rank is composed of l × l cells unless some of the displayed ranks |C| have their headcell or tailcell very close (less than m steps) Rik = (Vik , Eik , f, {ck }, c) of a zz-structure S = ∪k=1 Dk . to the chosen focus. Then, ∃ a function gx : Ei → {−1, 1}, such that, ∀x ∈ Vik , i k As an example consider Figure 3 left that refers to the if ∃y, z ∈ Vik : {x, y}, {x, z} ∈ Eik , then gxi ({x, y}) = zz-structure of Figure 1. The main vertical dimension is gxi ({x, z}). Thus, we say that each vertex x ∈ Vik has a Ddotted and the secondary horizontal dimension is Dthick . local orientation in Rik . 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 Definition 6. : Posward and negward directions - path related to v4 is {v3 , v5 , v4 , v6 }, that is v6 is the tailcell Given an edge {a, b} ∈ Eik , we say that {a, b} is in a posward of the rank as ps = 1 < m = 2. direction from a in Rik , and that b is its posward cell iff The I-view can be defined analogously to the H-view gai ({a, b}) = 1, else {a, b} is in a negward direction and a [9]. An example of I-view with main horizontal dimension is its negward cell. Moreover, a path in rank Rik follows a Ddotted , secondary vertical dimension Dthick , size l = 5 and posward (negward) direction if it is composed of a sequence focus v5 is shown in Figure 3 right. of edges of value 1 (respectively, -1). We can now extend the known definition of H and I views to a number n > 2 of dimensions [10]. Intuitively, we will 9   central vertex x and neighborhood N (x) = {y ∈ V : y =       x+1 , x+1 ∈ R(x) i , i ∈ {1, . . . , n}}.        The m-extended star view extends the number of cells di- rectly 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- S|C| Sk      ture S = k=1 Dk , where Dk = li=1 Rik ∪ V0k , and where Ri = (Vi , Ei , f, {ck }, c), the m-extended star view is a star k k k Sk view of focus x ∈ V = li=0 Vik , dimensions D1 , D2 , . . . , Dn , Figure 3: An example of H-view and I-view. and each extension constituted, ∀y ∈ N (x) and ∀i ∈ {1, . . . , n}, by the paths (y +1 , . . . , y +p ) ⊆ R(x) i (p ≤ m). build n − 1 different H-views (respectively, I-views), cen- Fig. 5 shows an schematic example of 5-extended star view. tered in the same focus, with a fixed main dimension and a secondary dimension chosen among the other n − 1 dimen-  sions. Formally:  Definition 9. n-dimensions H-view - Given a zz-struc- |C| ture S = ∪k=1 Dk , where Dk = ∪li=1 k (Rik ∪ V0k ), and where    Ri = (Vi , Eik , f, {ck }, c), the n-dimensions H-view of size k k  l = 2m + 1 and of focus x, x ∈ V = ∪li=0 k Vik , on dimensions 1 2 D , D , . . . , D is composed of n − 1 rectangular H-views, n  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. Figure 5: A 5-extended star view.  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 ex-  tensions to multidimensional views, the algorithms for the     additions of new connections and the displaying of neigh-  bouring 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 represent-  ing 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 docu- ments on a given topic in a concept space, and to create semantic interconnections and personalized maps. Finally, Figure 4: An example of a 3-dimensions H-view. in [11] the authors propose a multi-agent adaptive system to support tours of virtual museums. In particular, the agents This view has focus on v4 , size l = 5, main dimension collaborate in order to help users visualizing their personal- Ddotted , and secondary dimensions Dthick and Dnormal . ized views and choosing their navigational path inside the A star view [12] visualizes information related to a focus virtual museum. vertex and a set of n chosen dimensions. There are two typologies of star views: the star view and the m-extended star view. 4. DISCUSSION AND CONCLUSIONS In this paper we have concentrated our attention on the Definition 10. Star view - Given a zz-structure S = S|C| k Sk formal models for representing zz-structures. Besides the k=1 D , where D k = li=1 Rik ∪ V0k , and where Rik = motivations, above provided, in our opinion a formal model Sk (Vi , Ei , f, {ck }, c), the star view of focus x ∈ V = li=0 k k Vik can help the navigation of a user by providing extra informa- 1 2 n and dimensions D , D , . . . , D is a star graph n+1 -star on tion, such as, e.g., the distances between the cell where (s)he 10 is located and one where (s)he wants to move. Defining zz- 339–346. Funchal, Madeira, Portugal, 4-7 May 2008. structures as graphs allows, e.g., the application of known al- [11] A. Dattolo and F. L. Luccio. Visualizing personalized gorithms for the (dynamical) computation of shortest paths, views in virtual museum tours. In International or of paths with small stretch factor (i.e., ratio between the Conference on Human System Interaction (HSI08), best path connecting two nodes and the shortest path). A pages 109–114. Krakow, Poland, 25-27 May 2008. user may thus compute a general shortest path, or, e.g., a [12] A. Dattolo and F. L. Luccio. A new concept map shortest path (given that the two nodes are connected) in the model for e-learning environment. In Lecture Notes in subgraph induced by a particular color, meaning that (s)he Business Information Processing 18, pages 404–417, wants to move following a unique dimension, i.e., concept. April 2009. Currently we are extending the formal model and prepar- [13] P. Flocchini, B. Mans, and N. Santoro. Sense of ing a survey of current literature on zz-structures, in order direction: Definitions, properties and classes. to analyze and synthesize it, and to stimulate new reflec- Networks, 32(3):165–180, 1998. tions and studies on this innovative way of conceiving the [14] M. McGuffin. A graph-theoretic introduction to Ted organization of information and knowledge. Nelson’s Zzstructures. January 2004. http://www.dgp. toronto.edu/∼mjmcguff/research/zigzag/. 5. REFERENCES [15] M. McGuffin and m. c. schraefel. A comparison of [1] I. Anderson. From ZigZagT M to BigBag: Seeing the Hyperstructures: Zzstructures, mSpaces, and wood and the trees in online archive finding aids. In Polyarchies. In Proceedings of the 15th ACM Proceedings of the Workshop on New Forms of Conference on Hypertext and Hypermedia (HT’04), Xanalogical Storage and Function. Turin, Italy, 29 pages 153–162. Santa Cruz, California, USA, 9-13 June 2009. August 2004. [2] M. Andric, V. Devedzic, W. Hall, and L. Carr. [16] A. Moore and T. Brailsford. Unified hyperstructures Keywords linking method for selecting educational for bioinformatics: escaping the application prison. web resources à la ZigZag. International Journal of Journal of Digital Information, 5(1):Article No.254, Knowledge and Learning, 3(1):30–45, 2007. 2004. [3] S. Canazza and A. Dattolo. Open, dynamic electronic [17] A. Moore, J. Goulding, T. Brailsford, and H. Ashman. editions of multidimensional documents. In IASTED Practical applitudes: Case studies of applications. In Proceedings of European Conference on Internet and Proceedings of the 15th ACM Conference on Hypertext Multimedia Systems and Applications, pages 230–235. and Hypermedia (HT’04), pages 143–152. Santa Cruz, Chamonix (France), 14-16 March 2007. California, USA, 9-13 August 2004. [4] L. Carr. ZigZag for web browsers, 2001. [18] T. H. Nelson. What’s on my mind. In Invited talk at http://www.ecs.soton.ac.uk/∼lac/zigzag. the first Wearable Computer Conference. Fairfax VA, [5] P. Casoto, A. Dattolo, F. Ferrara, N. Pudota, 12-13 May 1998. P. Omero, and C. Tasso. Toward making agent uml http://www.xanadu.com.au/ted/zigzag/xybrap.html. practical: a textual notation and a tool. In Proceedings [19] T. H. Nelson. Welcome to ZigZag. 1999. of the Workshop on Adaptation for the Social Web, http://xanadu.com/zigzag/tutorial/ZZwelcome.html. 5th ACM Int. Conf. on Adaptive Hypermedia and [20] T. H. Nelson. Xanalogical structure, needed now more Adaptive Web-Based Systems, pages 14–23. Germany, than ever: parallel documents, deep links to content, 29 July - 1 August 2008. deep versioning, and deep re-use. ACM Computing [6] P. Casoto, A. Dattolo, and C. Tasso. Sentiment Surveys, 31(4:33), 1999. classification for the italian language: A case study on [21] T. H. Nelson. ZigZag (tech briefing): Deeper movie reviews. Journal of Internet Technology, Special cosmology, deeper documents. In Proceedings of the issue on Intelligent Agent and Knowledge Mining, 12-th ACM conference on Hypertext and Hypermedia 9(4):365–373, 2008. (HT’01), pages 261–262. University of Aarhus, [7] A. Dattolo. Authoring and navigating ethnic music Aarhus, Denmark, 14-18 August 2001. audio archives. Signal Processing, 2009 (to appear). [22] T. H. Nelson. Structure, tradition and possibility. In [8] A. Dattolo, F. Ferrara, and C. Tasso. Supporting Proceedings of 14th ACM Conference on Hypertext personalized user concept spaces and recommendations and Hypermedia (HT’03). Nottingham, United for a publication sharing system. In UMAP ’09: Kingdom, 26-30 August 2003. Proceedings of the 1th and 17th international http://www.ht03.org/keynote-ted.html. conference on User Modeling, Adaptation, and [23] T. H. Nelson. A cosmology for a different computer Personalization. Trento, Italy, 22-29 June 2009. universe: data model mechanism, virtual machine [9] A. Dattolo and F. L. Luccio. A new actor-based and visualization infrastructure. Journal of Digital structure for distributed systems. In International Information: Special Issue on Future Visions of Conference on Hypermedia and Grid Systems Common-Use Hypertext, 5(1):298, 2004. (HGS07), pages 195–201. Opatija, Adriatic Coast [24] K. Wideroos. Awt (associative writing tool): (Croatia), 21-25 May 2007. supporting writing process with a ZigZag based [10] A. Dattolo and F. L. Luccio. Formalizing a model to writing tool - work in progress. In Proceedings of the represent and visualize concept spaces in e-learning 12-th ACM conference on Hypertext and Hypermedia environments. In Proceedings of the 4th Webist (HT’01), pages 35–36. University of Aarhus, Aarhus, International Conference (WEBIST08), pages Denmark, 14-18 August 2001. 11