ARROW SYMBOLS: THEORY FOR INTERPRETATION
By
Yohei Kurata
B.Eng. University of Tokyo, Japan, 2000
M.Eng. University of Tokyo, Japan, 2002

A THESIS
Submitted in Partial Fulfillment of theRequirements for the Degree ofDoctor of Philosophy(in Spatial Information Science and Engineering)

The Graduate School
The University of Maine
May, 2007

Advisory Committee:
Max. J. Egenhofer, Professor in Spatial Information Science and Engineering, Advisor
M. Kate Beard-Tisdale, Professor in Spatial Information Science and Engineering
Werner Kuhn, Professor in Geoinformatics, Universität Münster
Kathleen Stewart Hornsby, Assistant Research Professor in National Center for
Geographic Information and Analysis
Michael F. Worboys, Professor in Spatial Information Science and Engineering© 2007 Yohei Kurata
All Rights Reservedii

LIBRARY RIGHTS STATEMENT
In presenting this thesis in partial fulfillment of the requirements for an advanced degree
at The University of Maine, I agree that the Library shall make it freely available forinspection. I further agree that permission for “fair use” copying of this thesis forscholarly purposes may be granted by the Librarian. It is understood that any copying or
publication of this thesis for financial gain shall not be allowed without my written
permission.

Signature:
Date:

ARROW SYMBOLS: THEORY FOR INTERPRETATION
By Yohei Kurata
Thesis Advisor: Dr. Max J. Egenhofer
An Abstract of the Thesis Presented
in Partial Fulfillment of the Requirements for the
Degree of Doctor of Philosophy(in Spatial Information Science and Engineering)
May, 2007
People often sketch diagrams when they communicate successfully among each other.
Such an intuitive collaboration would also be possible with computers if the machines
understood the meanings of the sketches. Arrow symbols are a frequent ingredient ofsuch sketched diagrams. Due to the arrows’ versatility, however, it remains a challenging
problem to make computers distinguish the various semantic roles of arrow symbols. The
solution to this problem is highly desirable for more effective and user-friendly pen-based
systems. This thesis, therefore, develops an algorithm for deducing the semantic roles ofarrow symbols, called the arrow semantic interpreter (ASI).
The ASI emphasizes the structural patterns of arrow-containing diagrams,
which have a strong influence on their semantics. Since the semantic roles of arrowsymbols are assigned to individual arrow symbols and sometimes to the groups of arrowsymbols, two types of the corresponding structures are introduced: the individual
structure models the spatial arrangement of components around each arrow symbol andthe inter-arrow structure captures the spatial arrangement of multiple arrow symbols.
The semantic roles assigned to individual arrow symbols are classified into orientation,

behavioral description, annotation, and association, and the formats of individual
structures that correspond to these four classes are identified. The result enables thederivation of the possible semantic roles of individual arrow symbols from theirindividual structures. In addition, for the diagrams with multiple arrow symbols, thepatterns of their inter-arrow structures are exploited to detect the groups of arrowsymbols that jointly have certain semantic roles, as well as the nesting relations between
the arrow symbols.
The assessment shows that for 79% of sample arrow symbols the ASI
successfully detects their correct semantic roles, even though the average number of the
ASI’s interpretations is only 1.31 per arrow symbol. This result indicates that thestructural information is highly useful for deriving the reliable interpretations of arrowsymbols.

ACKNOWLEDGMENTSFirst, I would like to thank all my family in Japan, who respected my decision to study
abroad and supported me from the other side of the Earth. My deepest thanks also go to
my advisor, Dr. Max Egenhofer, who has always cheered me up, given me insightfuladvice, and kept stimulating my academic interest. Other committee members, Dr. Kate
Beard, Dr. Mike Worboys, Dr. Kathleen Hornsby, and Dr. Werner Kuhn, also helped me
considerably to complete this work. My former advisor, Dr. Atsuyuki Okabe, strongly
encouraged me to study abroad. Without his push I would have missed the exciting
experience in working academically with international people. Dr. Christian Claramunt,
Dr. Lars Kulik, Dr. Richard Lowe, Dr. Atushi Shimojima, Dr. Barbara Tversky gave me
great advice on my work and presentations. Makiko Matsuoka helped my life in Maine
and also gave me some useful suggestions on this work. Finally, I'd like to thank myfriends, Cindy and Maurice Brown, Taichi Godo, Michael Hendricks, Hae-kyong Kang,
Inga Mau, Errol Millios, Tomokazu Miyakozawa, Yuri Uesaka, Caixia Wang, Markus
Wersch, Dominik Wilmsen, and Teruyoshi Yoshida, who gave warm comments on mywork and cheered me a lot.
Dr. Ronald Ferguson from the Georgia Institute of Technology was the external
reader on my dissertation. My special thanks go to him for his advice and encouragement.
This work was partially supported by the National Geospatial-Intelligence
Agency under grant numbers NMA201-01-1-2003 and NMA401-02-1-2009, a Universityof Maine International Tuition Scholarship, and a University of Maine Graduate Summer
Research Award.
iii

TABLE OF CONTENTSACKNOWLEDGMENTS ................................................................................................. iii
LIST OF TABLES ............................................................................................................. ix
LIST OF FIGURES .......................................................................................................... xii
Chapter 1 INTRODUCTION...............................................................................................1
1.1. Difficulty in Deriving Interpretations of Arrow Symbols................................... 4
1.2. Research Approach.............................................................................................. 6
1.3. Hypothesis........................................................................................................... 7
1.4. Major Results ...................................................................................................... 8
1.5. Intended Audience............................................................................................... 9
1.6. Thesis Organization........................................................................................... 10
Chapter 2 RELATED WORK ............................................................................................132.1. Definition of Arrow Symbols............................................................................ 14
2.2. Semantic Roles of Arrow Symbols ................................................................... 16
2.2.1. Specifying a Directional Property .......................................................... 17
2.2.2. Illustrating a Spatial Movement ............................................................. 19
2.2.3. Illustrating Communication.................................................................... 21
2.2.4. Illustrating Continuous Existence........................................................... 22
2.2.5. Indicating a Temporal Order................................................................... 23
2.2.6. Labeling .................................................................................................. 25
2.2.7. Indicating Ordered Binary Relations ...................................................... 25
2.3. Characteristics of Arrow Symbols and Diagrams ............................................. 26iv

2.4. Computational Understanding of Diagrams...................................................... 29
2.4.1. Current Diagram-Understanding Systems.............................................. 29
2.4.2. What is Diagram Understanding?........................................................... 32
2.4.3. Diagram-Understanding Systems and Arrow Symbols .......................... 34
2.5. Spatial Relations between Line Segments ........................................................ 35
2.6. Summary ........................................................................................................... 39
Chapter 3 STRUCTURES OF ARROW DIAGRAMS .....................................................40
3.1. Terminology ...................................................................................................... 41
3.2. Individual Structures ......................................................................................... 42
3.2.1. Three Component Slots .......................................................................... 42
3.2.2. Definition of Individual Structures......................................................... 43
3.2.3. Pattern of Individual Structures .............................................................. 45
3.3. Inter-Arrow Structures ...................................................................................... 49
3.3.1. Definition of Inter-Arrow Structures ...................................................... 50
3.3.2. Topological Relations between Two Arrow Symbols............................. 50
3.3.3. Analysis of Topological Relations Established by Direct Links ............ 55
3.4. Demonstration ................................................................................................... 60
3.4.1. Example 1: Wolves’ Attack Scenario...................................................... 61
3.4.2. Example 2: Industrial Revolution Scenario............................................ 63
3.5. Summary ........................................................................................................... 64
Chapter 4 INTERPRETATIONS OF ARROW SYMBOLS IN 1-ARROWDIAGRAMS .................................................................................................65
4.1. Classification of Semantic Roles ...................................................................... 66v

4.2. Basic formats of Individual Structures.............................................................. 68
4.2.1. Basic Formats for Orientation ................................................................ 68
4.2.2. Basic Formats for Behavioral Description ............................................. 70
4.2.3. Basic Formats for Annotation................................................................. 74
4.2.4. Basic Formats for Association ................................................................ 75
4.3. Rules for Optional Components........................................................................ 77
4.3.1. Adjective Components ........................................................................... 77
4.3.2. Adverbial Components ........................................................................... 78
4.4. Interpretations of Arrow Symbols in Simple 1-Arrow Diagrams ..................... 79
4.4.1. Patterns of Simple 1-Arrow Diagrams for Orientation .......................... 80
4.4.2. Patterns of Simple 1-Arrow Diagrams for Behavioral Description ....... 81
4.4.3. Patterns of Simple 1-Arrow Diagrams for Annotation ........................... 82
4.4.4. Patterns of Simple 1-Arrow Diagrams for Association .......................... 83
4.4.5. Comparison of Patterns .......................................................................... 84
4.5. Interpretation of Arrow Symbols in General 1-Arrow Diagrams ..................... 85
4.6. Summary ........................................................................................................... 87
Chapter 5 INTERPRETATIONS OF ARROW SYMBOLS IN MULTI-ARROWDIAGRAMS .................................................................................................89
5.1. Terminology ...................................................................................................... 90
5.2. Group Roles of Arrow Symbols........................................................................ 91
5.2.1. Indicating Element-Sharing .................................................................... 91
5.2.2. Formulating a Branching Process........................................................... 92
5.2.3. Indicating Interactions during Transition ............................................... 93vi

5.2.4. Illustrating an Extent Change ................................................................. 95
5.2.5. Specifying an Interval............................................................................. 96
5.3. Nesting of Arrow Diagrams .............................................................................. 97
5.4. Interpretation of Arrow Symbols in Multi-Arrow Diagrams ............................ 98
5.4.1. Detection of Subordinate Arrow Diagrams .......................................... 100
5.4.2. Tentative Deduction of Group Roles .................................................... 100
5.4.3. Deduction of Individual Roles.............................................................. 103
5.4.4. Validation of Tentative Group Roles .................................................... 103
5.5. Demonstration ................................................................................................. 104
5.5.1. Example 1: Wolves’ Attack Scenario.................................................... 104
5.5.2. Example 2: Industrial Revolution Scenario.......................................... 105
5.6. Summary ......................................................................................................... 107
Chapter 6 EVALUATION................................................................................................108
6.1. Method ............................................................................................................ 108
6.2. Statistical Overview .........................................................................................115
6.3. Validity of the Hypothesis................................................................................116
6.4. Statistical Analysis in Terms of Each Class of Semantic Roles .......................117
6.5. Analysis of Misinterpretations ........................................................................ 120
6.5.1. Oversight .............................................................................................. 120
6.5.2. Partial Match......................................................................................... 122
6.5.3. No-Answer............................................................................................ 124
6.6. Summary ......................................................................................................... 126
Chapter 7 CONCLUSIONS.............................................................................................127vii

7.1. Summary of Thesis ......................................................................................... 127
7.2. Results and Major Findings ............................................................................ 128
7.2.1. Classification of Individual Roles ........................................................ 128
7.2.2. Investigation of Group Roles................................................................ 129
7.2.3. Two Syntactic Structures of Arrow Diagrams ...................................... 129
7.2.4. An Algorithm for Deducing Individual Roles of Arrow Symbols........ 130
7.2.5. The Arrow Symbol Interpreter (ASI) .................................................... 130
7.3. Future Work..................................................................................................... 131
7.3.1. Remediation.......................................................................................... 131
7.3.1.1. Reclassification of Individual Roles ............................................ 131
7.3.1.2. Detection of Impractical Interpretations ...................................... 133
7.3.1.3. Detection of Omitted Components .............................................. 136
7.3.2. Automation ........................................................................................... 137
7.3.3. Detail Enrichment................................................................................. 138
7.3.4. Applications.......................................................................................... 139
GLOSSARY ....................................................................................................................140
BIBLIOGRAPHY............................................................................................................146
BIOGRAPHY OF THE AUTHOR ..................................................................................161

viii

LIST OF TABLES
Table 3.1: Number of patterns of the 9-link matrices satisfying the constraint.................55
Table 3.2: 68 topological relations between two arrow symbols, which have no
indirect links..................................................................................................56
Table 4.1: Nine prescriptive patterns that individual structures must satisfy whenarrow symbols are used for orientation (s: subject, PCL|O|E: PCL, PCO,
or PCE). .........................................................................................................70
Table 4.2: Fifteen basic formats of individual structures that correspond tobehavioral description (s: subject, e: entity involved in the transition,
p: position related to the transition, e|p: either e or p, [e|p]n: one ormore e|p). ......................................................................................................72
Table 4.3: 104 prescriptive patterns that individual structures must satisfy whenarrow symbols are used for behavioral description (s: subject, e:
entity involved in the transition, p: position related to the transition). .........73
Table 4.4: Four prescriptive patterns that individual structures must satisfy whenarrow symbols are used for annotation (l: label, s: subject). ........................74
Table 4.5: Associated subjects and effective relations between them, which may
naturally determine the order of the associated subjects. .............................76
Table 4.6: Sixteen prescriptive patterns that individual structures must satisfy
when arrow symbols are used for association (s1, s2: associatedsubjects). .......................................................................................................76
Table 4.7: Information provided by adverbial components. ..............................................79ix

Table 4.8: Five formats and fifteen patterns of simple individual structures that
correspond to orientation (s: subject, cav: adverbial component) .................80
Table 4.9: Eighteen formats and 104 patterns of simple individual structures that
correspond to behavioral description (s: subject, e: entity involved in
the transition, p: position related to the transition). The patterns may
overlap between the rows..............................................................................82
Table 4.10: One format and four patterns of simple individual structures that
correspond to annotation (l: label, s: subject)...............................................83
Table 4.11: Two formats and 32 patterns of simple individual structures that
correspond to association (s1, s2: associated subjects, cav: adverbial
component). ..................................................................................................83
Table 5.1: Individual roles of arrow symbols presumed by their group role. ....................99
Table 5.2: Spatial arrangements required for the arrow symbols with the grouproles in Section 5.2......................................................................................101
Table 5.3: Components required for the arrow symbols with the group roles in
Section 5.2...................................................................................................102
Table 5.4: Indirect reference of arrow symbols specified by the group roles in
Section 5.2...................................................................................................103
Table 6.1: Four types of interpretation result with regard to a semantic role ri............... 114
Table 6.2: The interpretation results of the 94 arrow symbols with regard toorientation................................................................................................... 118
Table 6.3: The interpretation results of the 94 arrow symbols with regard to withregard to behavioral description................................................................. 118
xTable 6.4: The interpretation results of the 94 arrow symbols with regard to withregard to annotation.................................................................................... 118
Table 6.5: Number of the four types of interpretation results with regard toassociation. ................................................................................................. 119
Table 6.6: Probability that each interpretation result with regard to a semantic roleri occurs if two nominal variables are independent. ................................... 119
Table 6.7: Individual structures of the 33 arrow symbol which yielded partial
match ([MC]*: arbitrary number of MC).....................................................123xi

LIST OF FIGURES
Figure 1.1: Diagrams with arrow symbols which describe dynamic spatial
information: (a) a process that the El Niño effect indirectly influences
the price of tofu in Japan and (b) how to build a LEGO model......................2
Figure 1.2: Two arrow-containing diagrams where a group of arrow symbols has
its own semantic role: (a) representing expansion and (b) indicating
multiple possibilities. ......................................................................................5
Figure 2.1: Examples of non-simple arrow symbols. ........................................................15
Figure 2.2: A collection of semantic roles of arrow symbols (Horn 1998)........................16
Figure 2.3: The presumably earliest diagram with an arrow symbol used forspecifying a directional property other than map’s North, drawn in
1737 (Gombrich 1990)..................................................................................17
Figure 2.4: Two arrow-containing diagrams, in which each arrow symbol
metaphorically indicates increase or stability of a value. .............................18
Figure 2.5: Two arrow plots, capturing a vector field (Garcke et al. 2000). .....................19
Figure 2.6: (a) A diagram in Galilei’s manuscript showing arrow symbols that
illustrates the course of movement of Jupiter’s moon (Westendorp
2006). (b) The pictorial message mounted to Pioneer 10 spacecraft inwhich an arrow symbol illustrates the course of movement of thespacecraft (Sagan and Sagan 1972). .............................................................20
Figure 2.7: Arrow symbol capture a typical immigration route in the New YorkState (Monmonier 1990). ..............................................................................20xii

Figure 2.8: Two arrow-containing diagrams in which each arrow symbol illustrates
a spatial interaction and its scale between two locations: (a) Gradel
and Crutzen (1995) and (b) Tobler (1987). ...................................................22
Figure 2.9: An arrow symbol illustrating a communication between two objects(Worboys and Duckham 2004). ....................................................................22
Figure 2.10: A timetable in which each arrow symbol captures continuous
existence of a job phase over a time interval (Horn 1998). ..........................23
Figure 2.11: Two flowcharts in which each arrow symbol indicates a temporalorder: (a) Horn (1998) and (b) Hornsby and Egenhofer (2000). ..................24
Figure 2.12: An illustration of a computer’s hard drive, in which each arrowsymbols attaches a text label to a mechanical component of the drive(Worboys and Duckham 2004). ....................................................................25
Figure 2.13: A directed graph, in which each arrow symbol captures an orderedbinary relation between two elements (Lipschutz and Lipson, 1997). .........26
Figure 2.14: ASSIST (Alvarado and Davis 2001b; 2001a; Davis 2002)...........................30
Figure 2.15: A sketch-based system that supports GUI designs (Landay and Myers
2001). ............................................................................................................30
Figure 2.16: sKEA (Ferguson and Forbus 2002; Forbus and Usher 2002). ......................31
Figure 2.17: QuickSet (Cohen et al. 1997; Johnston 1998; Cohen et al. 2000;
Oviatt and Cohen 2000). ...............................................................................32
Figure 2.18: nuSketch COA creator (Forbus et al. 2001; Ferguson and Forbus
2002). ............................................................................................................32
Figure 3.1: Three component slots associated with an arrow symbol. ..............................42xiii

Figure 3.2: An arrow symbol with multiple components in each component slot. ...........43
Figure 3.3: The label “WATER” is attached to only one of the dashed arrowsymbols, but is conceptually assigned to the body slot of all dashedarrow symbols...............................................................................................43
Figure 3.4: Two pairs of 1-arrow diagrams, each with the same components indifferent component slots, illustrate different semantics. .............................44
Figure 3.5: A 1-arrow diagram with two primary components (a tourist icon and afirework icon) and three modifier components (“Mr. K”, “July 4”,
and “Boston”)................................................................................................45
Figure 3.6: Two 1-arrow diagrams, whose head components are apparently same,
but belong to different component types: (a) object (a broken car) and(b) event (a car accident)...............................................................................47
Figure 3.7: Arrow symbols with the same tail components and different types ofhead components: (a) object, (b) an event, and (c-d) a location. ..................48
Figure 3.8: Four 1-arrow diagrams with the patterns of their individual structures. .........49
Figure 3.9: Six 2-arrow diagrams where arrow symbols are connected by (a) ahead-head intersection, (b) references to the same “Inspection” label,(c) both a head-tail intersection and references to the same landing
strip icon, (d) a body-tail intersection, (e) references to the same cell
phone and database icons, and (f) both a tail-tail intersection andreferences to the same “Inspection” label.....................................................51
Figure 3.10: The 9-link matrices that capture the topological relations between thepairs of arrow symbols in Figures 3.9a-f. .....................................................53xiv

Figure 3.11: The conceptual neighborhood graph of the relations #1 through #34,
illustrated on a plane. ....................................................................................58
Figure 3.12: Characteristics of the conceptual neighborhood graph in Figure 3.11:(a) symmetric and converse relations and (b) the four subgraphs thatare obtained by reversing the direction of an arrow symbol whenmirroring the relation along the graph’s horizontal or vertical axis..............59
Figure 3.13: The transition from (a) the flat conceptual neighborhood graph of therelations #1 through #34 with repeated columns and rows to (b) agraph displayed on the surface of a torus, which is obtained by gluing
together the repeated rows and columns along the fringes of the flatgraph .............................................................................................................59
Figure 3.14: Two structures of the conceptual neighborhood graph of the relations#1 through #68, where nodes are aligned on (a) two parallel planesand (b) the surfaces of two nested tori. .........................................................60
Figure 3.15: Two 2-arrow diagrams that capture that (a) a pack of wolves splits
into two packs, which approach a sheep from front and behind, andthat (b) the industrial revolution leads to the population drift fromrural area to urban area. ................................................................................61
Figure 3.16: The process of deriving the individual structures and the inter-arrow
structure of the multi-arrow diagram in Figure 3.15a...................................62
Figure 4.1: Classification of semantics roles of arrow symbols. .......................................66
Figure 4.2: Diagrams with arrow symbols for orientation, specifying (a) themoving direction of a vehicle, (b) a wind direction of a point inxv

Maine, and (c) the direction of an external force by which a board
cracks. ...........................................................................................................68
Figure 4.3: Three basic formats of individual structures that correspond toorientation (s: subject). .................................................................................69
Figure 4.4: An arrow diagram with five arrow symbols, all used for annotation..............74
Figure 4.5: Only one basic format of the individual structures that correspond toannotation (l: label, s: subject)......................................................................74
Figure 4.6: Only one basic format of the individual structures that correspond toassociation (s1, s2: associated subjects) ........................................................75
Figure 4.7: A 1-arrow diagram with two adjective components, “Mr. K” and“Maine,” each of which specifies the name of an entity illustrated
nearby............................................................................................................77
Figure 4.8: The number of patterns of simple individual structures that correspondto each class of semantic roles. .....................................................................84
Figure 4.9: Simple 1-arrow diagrams whose individual structures have the patterns(a) (PCL, PCO, PCL), (b) (MC, –, PCO), (c) (MC, PCO, PCL), whichcorresponds to one, two, and no classes of semantic roles,
respectively. ..................................................................................................85
Figure 5.1: Synthesis of two 1-arrow diagrams yields a multi-arrow diagram,which captures additional semantics: the pack of wolves splits into
two packs. .....................................................................................................89xvi

Figure 5.2: Three 2-arrow diagrams capturing pairs of element-sharing individual
semantics. In addition, (b) and (c) imply that the pairs are mutually
exclusive and synchronized, respectively. ....................................................92
Figure 5.3: The same branching processes are captured by (a) a pair of arrowsymbols with a direct body-tail link and (b) a pair of arrow symbols
with an indirect tail-tail link..........................................................................93
Figure 5.4: Six 2-arrow diagrams with different types of direct links between
arrow symbols, which indicate different interactions between thesubjects: (a) separation, (b) meeting, (c) contact, (d) drop-by, (e)diversion, and (f) confluence.........................................................................95
Figure 5.5: Two multi-arrow diagrams in which a group of arrow symbols is used
for illustrating (a) the diffusion of balloons and (b) the expansion of aballoon...........................................................................................................96
Figure 5.6: Two multi-arrow diagrams in which a pair of reversely directed arrowsymbols is used for specifying the interval of (a) wavelength ofelectric waves assigned to televisions and radios and (b) a pulse(1997)............................................................................................................96
Figure 5.7: (a) The central arrow symbol points to “Fish catch,” but conceptuallyrefers to the subordinate arrow diagram “ Fish catch ↓ ”; and (b) the
central arrow symbol points to the horizontal arrow symbol, butconceptuallyreferstothesubordinate

arrow

diagram“ Rural area → Urban area .”.......................................................................97
population

xvii

Figure 5.8: Two 2-arrow diagrams which capture (a) a pack of wolves splits into
two packs, which approach a sheep from front and behind and (b) theindustrial revolution leads to the population drift from rural area tourban area....................................................................................................104
Figure 6.1: A prototype of the ASI. ..................................................................................109
Figure 6.2: Semantic roles of 304 sample arrow symbols found in a GIS textbook(Jones 1997). ............................................................................................... 110
Figure 6.3: Semantic roles of (a) 745 arrow symbols found in a biology textbook(Comins and Kaufmann III 2003), Part I and II, and (b) 956 arrowsymbols found in an astronomy textbook (Avila 1992).............................. 111
Figure 6.4: Two arrow-containing diagrams with a set of similar arrow symbols. ......... 112
Figure 6.5: Semantic roles of the 94 representative arrow symbols. ............................... 112
Figure 6.6: The number of interpretations that the ASI deduced for the 94
representative arrow symbols. .................................................................... 115
Figure 6.7: The interpretation results of the 94 representative arrow symbols................ 116
Figure 6.8: Two arrow-containing diagrams in which arrow symbols are used fororientation in irregular formats: (a) the arrow symbol points to an
adverbial component “Azimuth direction” and (b) each arrow symbolrefers to two locations.................................................................................121
Figure 6.9: An arrow-containing diagram in which arrow symbols are used for
behavioral descriptions, although the subjects are not illustrated in
the diagrams. ...............................................................................................121xviii

Figure 6.10: An arrow-containing diagram where the white arrow symbol
indirectly refers to the empty table in the previous line..............................122
Figure 6.11: Two arrow-containing diagrams, each with an arrow symbol whose
individual structure has the pattern of (PCO[MC]*, [MC]*, PCO[MC]*).
.....................................................................................................................124
Figure 6.12: Two arrow-containing, in which two arrow symbols are used forinterval specification (a) by themselves or (b) in combination. .................125
Figure 6.13: Two arrow-containing, each with an arrow symbol used for (a)pointing and (b) gradation. .........................................................................125
Figure 7.1: A model of evolutions of arrow symbols’ semantic roles. ............................133
Figure 7.2: Three arrow diagrams whose individual structures has the same
patterns,(PCO, –, PCLMC), illustrating (a) behavioral description,(b) no behavioral description due to the immobility of the broken car,and (c) no behavioral description due to the (immobile) Brandenburg
Gate. ............................................................................................................134
Figure 7.3: (a) Hierarchy of an operation move and its subclasses and (b) hierarchyof animal and its super/subclasses with inheritance of mobility.................135
Figure 7.4: An arrow diagram that may illustrate two different scenarios dependingon the context: a vehicle approaches a person (encounter) or aperson leaves a vehicle (division). ..............................................................138xix

Chapter 1
INTRODUCTION

People often sketch diagrams to facilitate their communication. Diagrams clarify mental
shapes and structures, which are difficult to communicate verbally. If computers would
understand such diagrams, people could operate information systems more intuitively, forinstance, by sketching diagrams to explain their ideas and knowledge. Indeed, a numberof pen-based computer systems that understand diagrams have been developed, and theirusefulness has been reported repeatedly (Oviatt 1996; Egenhofer 1997; Landay andMyers 2001; Davis 2002; Ferguson and Forbus 2002). These pioneering systems havedemonstrated that computational diagram understanding is a highly promising technologythat will enrich human-computer interactions.
Arrow symbols are used in a variety of diagrams, such as pictorial instructions,route maps, traffic signs, guideboards, route maps, and flowcharts (Horn 1998; Wildbur
and Burke 1998). Tversky and Lee (1999) observed that arrow symbols were used inabout a half of the sketch maps that they analyzed. One reason for the popularity of arrowsymbols is that they are convenient—even though their shapes are extremely simple, theycapture a large variety of semantics, such as directions, movements, interactions,transitions, orders, and relations. In addition, arrow symbols enable us to communicate
dynamic spatial information even in a static diagram. For instance, Figure 1.1a contains
only a few words and arrow symbols over a background map, but people easily read thecomplicated mechanism where the El Niño effect (i.e., sea temperature rise in the1Southeastern Pacific Ocean) indirectly influences the rise of the price of tofu in Japan.
Similarly, arrow symbols are particularly useful for illustrating such dynamic spatial
processes as spatial diffusion of ideas, migrations of tribes and refugees, advances ofarmies, and so forth (Monmonier 1990). Interestingly, people can communicate such
dynamic spatial information more intuitively by arrow-containing diagrams than byverbal expressions. Even small children, who have not yet learnt a written language, canunderstand the pictorial instructions of toys, which typically use arrow symbols (Figure1.1b). In this way, the convenience and expressive power of arrow symbols leads to thefrequent use of arrow symbols in people’s daily communication.

Feeding Protein
Fish flour Soybeans

Tofu Price

Fish CatchEl Niño

(a)(b)

Figure 1.1: Diagrams with arrow symbols which describe dynamic spatial
information: (a) a process that the El Niño effect indirectly influences the price of
tofu in Japan and (b) how to build a LEGO model.
An important feature of arrow symbols is that they do not describe any
meaning by themselves—they provide the information about the other elements to which
the arrow symbols refer. This function of arrow symbols is called their semantic role.
Arrow symbols may have a large variety of semantic roles, such as specifying the moving
2direction of an object and indicating a causal relation between two events. Semantic roles
are slightly different from meanings, because, for instance, annotation (attaching a label
to an element) is a semantic role that an arrow symbol may have (Section 2.2.6), but not
the meaning that the arrow symbol expresses. On the other hand, to express a certain
meaning (for instance, increase) is considered as a semantic role of an arrow symbol.
In order to understand an arrow-containing diagram correctly, the diagram
readers have to figure out the semantic roles of arrow symbols in the diagram. For
instance, to understand Figure 1.1b, the diagram readers (probably small children andtheir parents) have to figure out that most arrow symbols instruct the readers to attach one
Lego block to another. Unfortunately, it is not always easy, especially for computers, tofigure out such semantic roles of arrow symbols. For example, in Figure 1.1a, people who
do not know the El Niño effect may consider that the arrow symbol departing from “ElNiño” illustrates the spatial movement of “Fish Catch” to South America, or attaches alabel “El Niño” to “Fish.” To avoid such misinterpretations, current pen-based systems
restrict the semantic roles of arrow symbols to a small set (Alvarado and Davis 2001b;
Landay and Myers 2001; Kurtoglu and Stahovich 2002), or require their users to specify
the semantic role of every arrow symbol by speech (Oviatt and Cohen 2000), use ofdifferent-shaped arrow symbols (Forbus et al. 2001), text input, or selection from a menu
(Forbus and Usher 2002). Consequently, the current pen-based systems prevent theirusers from making full use of arrow symbols in human-computer interactions.
To overcome this blockage, this thesis aims at enabling computers to derive thesemantic roles of arrow symbols in sketched diagrams. To this goal, this thesis develops3an algorithm for deducing the semantic roles of arrow symbols. Such deduced semanticroles are called the interpretations of arrow symbols. With a capability of deriving
interpretations of arrow symbols, pen-based information systems will understandhand-drawn diagrams with less human aid. Consequently, people will be able to operatethese systems more intuitively and effectively as if they collaborate with other people.

1.1. Difficulty in Deriving Interpretations of Arrow Symbols
Deriving interpretations of arrow symbols requires an intricate reasoning process. For
instance, in Figure 1.1a, a typical interpretation of the downward arrow symbol next to“Fish Catch” is a representation of the decrease of the fish catch. Most people agree withthis interpretation, as they know that fish catch is a quantitative variable and also that ashort downward arrow symbol, attached to a quantitative variable, may represent thedecrease of its value. Other interpretations, such as a specification of the moving
direction of Fish Catch, may be possible, but this case lacks the evidence to support suchalternative interpretations. Similarly, in Figure 1.1a, a typical interpretation of the arrowsymbol connecting “El Niño” with “Fish Catch↓” is an indication of the causal relation
between the El Niño effect and the decrease of fish catch. The reader may come up withthis interpretation if the reader knows that both “El Niño” and the decrease of fish catchare events and also that an arrow symbol connecting two events may indicates a causal
relation. Also, this interpretation is persuasive if the reader knows that the El Niño effecttypically influences fishing. In this way, the interpretations of arrow symbols depend4partly on the reader’s background knowledge about both the illustrated elements andwhat semantic roles arrow symbols may have in each situation. It is not clear, however,what range of knowledge is actually necessary (and sufficient) for deriving theinterpretations of arrow symbols.
Another difficulty associated with the interpretations arises when the semanticroles of arrow symbols are assigned to a group of arrow symbols instead of individualarrow symbols. For example, the arrow symbols in Figure 1.2a jointly represent an
expansion of a balloon and those in Figure 1.2b jointly indicate that the “inspection”
event is followed by the “shipping” or “disposal” event, but not both. In this way, arrowsymbols may form a group and jointly have an additional semantic role; however, it is not
obvious which set of arrow symbols in the diagram organizes a group and what semanticroles these arrow symbols jointly have.

Inspection

pass

fail

Shipping Disposal
(a)

(b)

Figure 1.2: Two arrow-containing diagrams where a group of arrow symbols has its
own semantic role: (a) representing expansion and (b) indicating multiple
possibilities.

5

1.2. Research Approach
It is impossible to derive the interpretation of an arrow symbol from the arrow symbol
alone. As observed in the previous examples, the semantic role of an arrow symbol
depends on what elements the arrow symbol refers to and how (being attached to one
element, connecting two elements, and so forth). Therefore, this thesis emphasizes theinfluence of these arrow-related elements and their spatial arrangement.
The combination of arrow symbols with the elements to which the arrowsymbols refer is considered a syntactic unit, called an arrow diagram (Kurata andEgenhofer 2005a; 2006c). An arrow diagram with one arrow symbol is called a 1-arrow
diagram, whereas an arrow diagram with more than one arrow symbol is called amulti-arrow diagram (Figure 1.1a). The elements to which the arrow symbols refer are
called the components of the arrow diagram. A component may be specified as an icon, atext label, a small diagram embedded in the diagram, or a specific position of a picture, amap, or an image.
In order to systematically study the influence of components and their spatial
arrangement, this thesis develops a model of components’ arrangement and distinguishes
the patterns of such arrangement based on the classification of the components. This
thesis also considers the arrangement of multiple arrow symbols, because such properties
as symmetry (Figure 1.2a) and connection (Figure 1.2b) contribute to the organization ofarrow symbols and, accordingly, influence their semantic roles. For this purpose, spatial

6

relations between two arrow symbols, which form the basis of the arrangement ofmultiple arrow symbols, are analyzed.
In addition to the arrangement of components and arrow symbols, the visualappearance of arrow symbols (for instance, color and width) and context may also
influence their semantic roles. Tversky et al. (2007) demonstrates that carefully crafted
context can disambiguate meanings of depictive symbols, including arrow symbols, justas they can disambiguate meanings of words. This thesis, however, ignores the arrowsymbols’ appearance and underlying context, because these are considered here asadditional clues that narrow down the candidates for the correct semantic roles, but would
not contribute directly to deriving those candidates.

1.3. Hypothesis
The goal of this research is to develop an algorithm for interpreting arrow symbols, withwhich computers can understand appropriately what their users want to represent by eacharrow symbol in sketched diagrams. The interpretation method makes use of the spatial
arrangement of arrow symbols and components, assuming that such arrangement is themost important factor for the interpretations of arrow symbols. A key question is how
reliable the interpretations deduced by this method are. Thus, this thesis examines thefollowing hypothesis:
The interpretation method, which deduces interpretations from the spatial
arrangement of arrow symbols and components in arrow diagrams, detects the7correct semantic roles of arrow symbols at a significantly higher rate thanrandom choices.
To assess this hypothesis, a prototype system, which implements the developed
interpretation method, deduces the interpretations of sample arrow symbols. Then, thecorrectness of these interpretations is statistically evaluated.

1.4. Major Results
The primary achievement of this thesis is the determination of an algorithm for deducing
semantic roles of arrow symbols in arrow diagrams. This method is called the arrowsymbol interpreter (ASI), since it works as an interpreter of arrow symbols to pen-based
computer systems. In addition, this thesis accomplishes:•recognition and classification of major semantic roles that arrow symbols may
individually or jointly have,•models of the spatial arrangement of components and arrow symbols in arrow
diagrams,•

identification of the relation between the semantic roles of arrow symbols and thestructural patterns associated with these arrow symbols, and•finding of background knowledge necessary for the interpretation of arrow symbols.
The ASI provides computers a capability of deriving the interpretations ofarrow symbols with little human aid. Thus, pen-based information systems equipped with8

the ASI will be able to understand arrow-containing diagrams more intelligently. As aresult, people will be able to operate these systems more intuitively and efficiently bysketching a diagram to explain their knowledge and ideas.
Another expected use of the ASI is to analyze any potential ambiguity of arrowsymbols when designing a diagram. If an arrow symbol is fundamentally ambiguous, the
ASI will give multiple interpretations, including the interpretations that differ from thepresenter’s original intention. Thanks to this feature, diagram designers can test theirdiagrams with the ASI, examining whether the diagram has a risk of misinterpretations.
This implies that there are two types of the correct semantic roles: (1) the intended
semantic roles of an arrow symbol, which corresponds to the semantic role that the
diagram drawer has originally intended, and (2) the consistent semantic roles with which
the diagram captures the semantics consistent with a common-sense world. The ASI aims
at deriving the consistent interpretations of arrow symbols.

1.5. Intended Audience
Although this thesis is originally motivated by an interest in the diagrammatic
representations of spatio-temporal information at cartographic scales, the concepts
discussed in this thesis are not restricted to spatial information studies, but apply to amuch larger variety of domains where arrow-containing diagrams are used forcommunication. The primary audience of this thesis is researchers and practitioners fromthe fields of spatial information science, computer science, artificial intelligence,9

diagrammatic communication studies, cartography, and geography. Particularly, thisthesis should be of interest to system designers who aim at developing intuitive
human-machine interfaces. At the same time, since arrow symbols are commonly used ina large variety of scientific and non-scientific domains, this thesis should also be ofinterest to anyone who has an interest in how arrow-containing diagrams arecommunicated and how such diagrams should be drawn.

1.6. Thesis Organization
This thesis is organized into seven chapters. Chapter 2 reviews related work, starting withthe discussion about the definition of arrow symbols and an investigation of major
semantic roles of arrow symbols. Then, current pen-based information systems arereviewed, through which the necessity of an algorithm for interpreting arrow symbols is
confirmed. Also, this chapter reviews the studies of spatial line-line relations, which
provide a foundation for modeling the spatial arrangement of arrow symbols in
multi-arrow diagrams.
Chapter 3 formalizes the structures of arrow diagrams from two viewpoints.
The individual structure models the spatial arrangement of components around eacharrow symbol, while the inter-arrow structure models the spatial arrangement of multiple
arrow symbols in the diagram. These two structures work complementarily, as theycapture the configuration of arrow diagrams from local and global perspectives,
respectively.
10

Chapters 4 and 5 develop an algorithm for deducing the interpretation of arrowsymbols. First, Chapter 4 considers 1-arrow diagrams, where the interpretation of thearrow symbol is derived from its individual structure alone. This chapter distinguishes
four classes of the semantic roles of arrow symbols. Then, the prescriptive patterns that
individual structures must satisfy when arrow symbols have each class of semantic roles,
as well as the rules for adding optional components, are identified. The obtained
knowledge makes it possible to determine all classes of semantic roles that correspond toa given individual structure, which is essential to derive the interpretations of individualarrow symbols.
Chapter 5 considers multi-arrow diagrams, where arrow symbols may organizea group and jointly have a certain semantic role. Also, in a multi-arrow diagram, an arrowsymbol may refer to an inner arrow diagram, thereby forming a nested structure. This
chapter analyzes how the spatial arrangement of arrow symbols corresponds to theorganization of arrow symbol groups and nested structures, and exploits thosecorrespondences to the interpretations of arrow symbols in multi-arrow diagrams.
Chapter 6 conducts an experiment to examine the hypothesis. In thisexperiment, an ASI’s prototype makes interpretations of sample arrow symbols in the
figures of a GIS textbook and the correctness of ASI’s interpretations is statisticallyevaluated. From this result and the detailed analysis of misinterpreted samples thischapter addresses problems in the current ASI that have led to misinterpretations of arrowsymbols11

Chapter 7 concludes this thesis with a summary of major results and a
discussion of future research problems.

12Chapter 2
RELATED WORKAs one of the most fundamental elements in diagrams, arrow symbols are widely used
across domains, generations, cultures, and languages. Naturally, arrow symbols are
discussed and investigated in a large variety of contexts. Sections 2.1-2.5 review therelevant work with the following five fundamental questions: (1) what are arrow symbols,(2) how do people use arrow symbols, (3) why do people frequently use arrow symbols,(4) what problems happen when arrow symbols are used in human-machine interactions,and (5) what models are available for structuring arrow diagrams. The answers to thesequestions contribute to the interpretation of arrow symbols.
The review starts with definitions of arrow symbols (Section 2.1) and major
semantic roles that arrow symbols have (Section 2.2). Section 2.3 discusses thecharacteristics of both arrow symbols and diagrams that motivate people to use arrowsymbols. Section 2.4 reviews major pen-based computer systems, discusses the goal ofdiagram understanding technologies, and identifies the necessity of an algorithm forinterpreting arrow symbols in such pen-based systems. Section 2.5 reviews the studies ofspatial relations between line segments, which form a foundation for modeling the spatial
arrangement of arrow symbols in arrow diagrams.

13

2.1. Definition of Arrow Symbols
What are arrow symbols? Arrow symbols are often called arrows in short. The termarrow symbol emphasizes that it refers to a symbol instead of a flying weapon calledarrow. The symbol is a mark or character used as a conventional representation ofsomething (The Concise Oxford Dictionary, 10th edition). Arrow symbols are polysemic
symbols, representing a large variety of things depending on the context (Section 2.2).
Dictionaries define the arrow (symbol) as follows:•

Something, such as a directional symbol, that is similar to an arrow in form orfunction (The American Heritage Dictionary of the English Language, 4th Edition).

•

A sign consisting of a straight line with an upside down V shape at one end of it,which points in a particular direction, and is used to show where something is(Cambridge Advanced Learner’s Dictionary).

•

Something shaped like an arrow; especially a mark (as on a map or signboard) toindicate a direction (Merriam-Webster Online Dictionary).

•

A mark or sign like an arrow, used to show direction or position (Oxford Advanced
Lerner’s Dictionary).

These definitions commonly point out that the shape of an arrow symbol is similar to anarrow (in the sense of the flying weapon), and that an arrow symbol typically shows a
direction or a position of something.

14

Tversky (2001) defined an arrow symbol as “a special kind of line, with one
end marked, inducing an asymmetry.” This definition highlights two essential features ofarrow symbols: linearity and asymmetry. With these two features, an arrow symbol
establishes an affordance (Gibson 1979) to prompt the diagram readers to move theirattention from the tail along the body to the head of the arrow symbol. Accordingly, if thearrow symbol connects two elements, these elements are naturally ordered. Also, if the
diagram space is mapped onto a physical space, the arrow symbol naturally makes people
imagine the movement of something (typically illustrated around the arrow symbol) in
this space. Naturally, arrow symbols are related to such image schemata as LINKS andPATHS (Johnson 1987), which are recurring imaginative patterns with which people
comprehend and structures their experiences while moving through and interacting.
This thesis basically follows the Tversky’s definition of arrow symbols. Thisdefinition, however, implicitly assumes simple arrow symbols, not allowing branchingarrow symbols, bidirectional arrow symbols, looped arrow symbols, and lines with∆-shaped marks on them (Figure 2.1). This thesis considers a branching arrow symbol asa pair of partly coexisting arrow symbols and a bi-directional arrow symbol as a pair offully coexisting arrow symbols with reverse direction. On the other hand, the looped
arrow symbols and the lines with ∆-shaped marks along them are considered not as arrowsymbols, but other type of symbols that consist of a linear body and a directional mark.

(a)

(b)

(c)

Figure 2.1: Examples of non-simple arrow symbols.
15(d)2.2. Semantic Roles of Arrow Symbols
How do people use arrow symbols? Van der Waarde and Westendorp (2000) found thatarrow symbols in user instructions have the following seven usages: direction of amovement, physical change or transformation, indication of a dimension (distance),labeling, focusing the attention, indication of a sequence (order), and a part of designed
symbols. Horn (1998) also collected various semantic roles of arrow symbols (Figure 2.2),
although his collection looks not exhaustive (for instance, labeling is missing), while itcontains such an unfamiliar role as arrow as object moving.

Figure 2.2: A collection of semantic roles of arrow symbols (Horn 1998).
The remainder of this section reviews various usages of arrow symbols in
literature. Each usage corresponds to different semantic role. The collected semantic roles
are later classified (Section 4.1) and used as a foundation for the interpretation.

16

2.2.1. Specifying a Directional Property
An arrow symbol may be attached to a single element in a diagram. In this case, all visualvariables of the arrow symbol, such as length, width, shape, color, direction, and pattern(Bertin 1983), can be controlled by its designer. Among these variables, the length anddirection are predominant because of the linearity and asymmetry peculiar to arrowsymbols. Accordingly, arrow symbols are potentially suitable for representing properties
related to a length, a direction, or both. A length-related property, however, can be more
simply represented by a line segment or a bar. Consequently, arrow symbols are
preferably used to specify a direction-related property or a property related to both adirection and a length (i.e., vector).
Maps with arrow symbols pointing North are found as early as the beginning of
the 15th century (Westendorp 2006). As for the directional properties other than the
map’s North, Gombrich (1990) found the diagram with an arrow symbol specifying thedirection of water flow in a channel, dating back to 1737 (Figure 2.3).

Figure 2.3: The presumably earliest diagram with an arrow symbol used forspecifying a directional property other than map’s North, drawn in 1737 (Gombrich1990).
17

Directions sometimes have metaphorical meanings. Typically, the upward
direction is associated with increase or improvement, whereas the downward direction isassociated with decrease or debasement (Lakoff and Johnson 1980). Accordingly, upwardand downward arrow symbols are used to metaphorically indicate those semantics,
respectively. For instance, in Figure 1.1, an upward arrow symbol next to “Tofu Price”
indicates the rise of tofu price. Figure 2.4 shows two examples in which arrow symbols
metaphorically indicate the trend of the tourist numbers and that of a market index,
respectively, by their directions. Similarly, major contemporary Internet web browsers,
such as Internet Explorer, Firefox, and Opera, adopt the icons of rightward and leftward
arrow symbols, which metaphorically indicate the forward and back operations (i.e.,switching to the next and previous pages), respectively.

(a)

(b)

Figure 2.4: Two arrow-containing diagrams, in which each arrow symbol
metaphorically indicates increase or stability of a value.
Both directions and vectors can be seen from an object-based view or afield-based view (Chrisman 1978; Peuquet 1984). For example, the direction of waterflow can be seen as a property of water (an object) or a property of a certain location in
the channel (Figure 2.3). A vector field is a field where a property related to a direction
and a length varies from place to place. Traditionally, a vector field is visualized by a18

diagram with many arrow symbols, called an arrow plot (Sanna et al. 2000). Garcke et al.
(2000) developed a visualization technique for simplifying arrow plots by clusteringvector fields and assigning only one arrow symbol for each cluster (Figure 2.5).

(a)

(b)

Figure 2.5: Two arrow plots, capturing a vector field (Garcke et al. 2000).

2.2.2. Illustrating a Spatial Movement
Another traditional semantic role of arrow symbols is to illustrate a spatial movement(and its route). The linearity and asymmetry of arrow symbols are appropriate features forillustrating both route and direction of the spatial movement, respectively. Bertin (1983)
claimed that arrow symbols are the most efficient (and often the only) formula forillustrating a complex movement. Westendorp (2006) found that Galileo Galilei’s
manuscript for his book, Sidereus Nuncius, published in 1610, has arrow symbols
illustrating the course of movement of Jupiter’s moons (Figure 2.6a). Interestingly, thepictorial message mounted to the Pioneer 10 spacecraft (Figure 2.6b) contains a similararrow symbol illustrating the route of the spacecraft in the solar system, assuming thataliens would understand that the arrow symbol illustrates the route of the spacecraft(Sagan and Sagan 1972).
19

(a)

(b)

Figure 2.6: (a) A diagram in Galilei’s manuscript showing arrow symbols that
illustrates the course of movement of Jupiter’s moon (Westendorp 2006). (b) The
pictorial message mounted to Pioneer 10 spacecraft in which an arrow symbol
illustrates the course of movement of the spacecraft (Sagan and Sagan 1972).
An arrow symbol may illustrate not only an individual spatial movement, butalso a typical pattern of repeated spatial movements. Monmonier (1990) showed an
example where a set of linearly linked arrow symbols captures a typical immigrationroute of the first settlements in the New York State (Figure 2.7). In a similar way,architects annotate a floor plan with what patterns they anticipate for people or vehicles(Do and Gross 2001).

Figure 2.7: Arrow symbol capture a typical immigration route in the New York State(Monmonier 1990).

20

2.2.3. Illustrating Communication
In geography, the flow of people, goods, or services between two locations is typicallymodeled as the spatial interaction of the locations (Bailey and Gatrell 1995). Spatial
interactions have attracted much attention from economic geographers, because modelingthe scale of spatial interactions contributes to the demand projection of new facilities,
such as shopping centers and parking lots. A spatial interaction is essentially anaggregation of spatial movements between two locations. Consequently, an arrow symbol
can illustrate a spatial interaction just like a spatial movement, although the route is often
abbreviated due to the lack of the drawer’s concern. The scale of a spatial interaction isreasonably expressed by the width of the arrow symbol’s linear part (Figure 2.8a), sincepeople typically perceive the width of lines without a bias (Robinson et al. 1995).
The diagram illustrating spatial interactions easily becomes messy as thenumber of interacting locations increases (Figure 2.8b). Thus, the cartographic
community has made a considerable efforts to visualize spatial interactions effectively(Tobler 1981; 1987; Becker et al. 1995). Tobler (1981) visualized a large number ofspatial interactions simply by arrow plots (Section 2.2.1), assuming a potential vector
field that implies the imbalance of the original data.

21

(a)

(b)

Figure 2.8: Two arrow-containing diagrams in which each arrow symbol illustrates aspatial interaction and its scale between two locations: (a) Gradel and Crutzen(1995) and (b) Tobler (1987).
An arrow symbol may illustrate an interaction between two locations, as well
as between two remote entities. This usage is called communication, since the interactionis achieved by the communication of a certain item, such as message and data, from one
entity to another entity (Figure 2.9).

Figure 2.9: An arrow symbol illustrating a communication between two objects(Worboys and Duckham 2004).

2.2.4. Illustrating Continuous Existence
Timetables and chronological tables often contain arrow symbols, which illustrate thatsomething (for instance, a project or a dynasty) persists over a certain time interval
22

(Figure 2.10). Arrow symbols illustrating such continuous existence are probablytransformed from those illustrating a spatial movement (Section 2.2.2), since persistenceover a time interval is considered a travel in time instead of space. Such transformation ofa spatial concept into a temporal concept naturally occurs, since people often understandthe concept of time with the aid of spatial metaphors (Lakoff and Johnson 1980).

Figure 2.10: A timetable in which each arrow symbol captures continuous existenceof a job phase over a time interval (Horn 1998).

2.2.5. Indicating a Temporal Order
Flowcharts often contain arrow symbols, each of which indicates a temporal order
between two components. The connected components may represent:•

two different elements (Figure 2.11a), or•

two different states of the same element (Figure 2.11b).
In the former case, the arrow diagram may imply a conditional relation or acausal relation between the elements, such that the proceeding element works as aprecondition or a cause of the subsequent element. For example, in Figure 1.1, the arrow23

symbol connecting “El Niño” and “Fish Catch ↓” illustrates a causal relation between the
El Niño effect (cause) and the decrease of fish catch (result).
In the latter case, the arrow symbol captures a change of the element. A change
is an event where an element transforms its property, such as identity, appearance, name,and structure. The studies of event modeling frequently use arrow diagrams forvisualizing changes (Claramunt and Theriault 1995; Hornsby and Egenhofer 1997;
Claramunt et al. 1998; Hornsby and Egenhofer 1998; 2000). For instance, Figure 2.11b
illustrates the historical transitions of territories in New England, where each horizontal
arrow symbol captures a change of a territory with regard to its presence or absence,
while each diagonal arrow symbol captures a change of a land with regard to its theterritorial attribution.

(a)

(b)

Figure 2.11: Two flowcharts in which each arrow symbol indicates a temporal order:(a) Horn (1998) and (b) Hornsby and Egenhofer (2000).

24

2.2.6. Labeling
A complicated illustration often contains several arrow symbols, each of which assigns atext label to another element. For instance, Figure 2.12 illustrates a computer’s hard drive,
where arrow symbols are used for labeling its mechanical parts. Alternatively, the labels
may be placed directly onto the labeled elements, but such direct placement of labels may
mess up the diagram. Line segments also can be used for labeling, but the use of arrowsymbols promotes a clear distinction between labels and labeled elements.

Figure 2.12: An illustration of a computer’s hard drive, in which each arrow symbols
attaches a text label to a mechanical component of the drive (Worboys and Duckham
2004).

2.2.7. Indicating Ordered Binary Relations
The use of arrow symbols to indicate relations is a widespread convention in sketches(Forbus and Usher 2002). Especially, arrow symbols distinctively indicate ordered binary
relations (i.e., asymmetric relations between two elements). Ordered binary relations area broad concept that includes spatial interactions, communications, temporal orders,conditional/causal relations, changes, and labeling. In mathematics, a set of ordered25

binary relations within a domain is modeled as a directed graph (Lipschutz and Lipson,1997), which is often visualized as a multi-arrow diagram (Figure 2.13).

Figure 2.13: A directed graph, in which each arrow symbol captures an orderedbinary relation between two elements (Lipschutz and Lipson, 1997).

2.3. Characteristics of Arrow Symbols and Diagrams
Why do people use arrow symbols? One obvious reason is that arrow symbols have alarge variety of semantic roles, regardless of their extremely simple shapes (Section 2.2).
This characteristic of arrow symbols enables people to use arrow symbol conveniently
and casually. The second reason is that the presence of arrow symbols encourages causal,
functional interpretations of a diagram (Tversky et al. 2000). Thanks to this characteristic,
people can communicate a complicated process or mechanism even in a static diagram.
The third reason is that people frequently use diagrams to assist in communication, which
naturally leads to the frequent use of arrow symbols.
Why do people frequently use diagrams? A well-known answer is, as seen in a
proverb, “a picture is worth a thousand words” (Tufte 1990)—that is, graphic
representations, including diagrams, convey certain types of information more effectively
than verbal expressions. For instance, people often draw a rough map to explain a route,26

because rough maps are easier than verbal route descriptions (Agrawala and Stolte 2001).
Larkin and Simon (1987) and Cheng et al. (1999), however, pointed out that diagrams
work effectively only if the diagrams’ advantages are appropriately exploited; otherwise,
diagrams are rather tortuous. Larkin and Simon (1987) further insisted that such anadvantage of diagrams lies in the adjacency of elements (i.e., the diagrams’ characteristicthat related elements are typically located nearby), which reduces the amount of searchthat is necessary for problem solving.
Larkin and Simon (1987) also highlighted the effect of perceptual inference.
People intuitively make inference about parallelism/perpendicular lines, relative positions,similarity under translation, scaling and/or rotation, approximate equivalence of lengths,
sizes, and angles, relative size, and proportionality and, therefore, diagrams may reduce
cognitive efforts for problem solving by making use of people’s outstanding ability ofsuch perceptual inference (Novak 1995).
Another benefit of diagrams is that they can serve as short-term memories forintermediate results (Novak 1995). People progressively annotate a diagram withintermediate results, making those results available when necessary for problem solving.
Tversky (2001) demonstrated that externalizing a diagrammatic representation reduces
the demand on memory, thereby facilitating information processing.
Stenning and Oberlander (1995) pointed out specificity as another advantage ofdiagrams. They showed that diagrams are less abstract representations than verbal
descriptions, reducing the mental load for problem solving and, thereby, enhancing theability of information processing. Meanwhile, diagrams are used also for illustrating27

abstract concepts. People often understand such abstract concepts in terms of spatial
metaphors (Lakoff and Johnson 1980). Therefore, diagrams, which bootstrap abstract
thought onto spatial thought, facilitate people’s understanding of abstract concepts(Tversky 2000).
Pinker (1990) tried to model how people understand diagrams (or graphs in his
terminology), considering diagrams as a communication medium that conveys conceptual
messages. Diagram readers have their own graph schema, which is developed througheducation and experiences. If a diagram suits their graph schema, the readers understandthe conceptual message of the diagram almost automatically. Even if the diagram does
not suit their graph schema, the readers try to understand the diagram by reasoning. This
process, however, requires a heavy mental load, and accordingly people sometimes take along time or even fail to understand a diagram. In this way, Pinker’s model explains thedifference of people’s abilities to understand diagrams.
These studies pointed out many benefits of diagrams, which explain why
people frequently use diagrams. Diagrams are a beneficial and effective tool for humancommunication; therefore, it is highly desirable for information systems to allow theirusers to interact with the systems through diagrammatic communications. Actually, many
researchers have tried to develop such systems, some of which are reviewed in the next
section.

28

2.4. Computational Understanding of Diagrams
Diagram-understanding systems are computer systems with a capability of understanding
diagrams that the user draws. Through the review of current diagram-understanding
systems, this section identifies the goal of diagram understanding technologies and thenecessity of a method for interpreting arrow symbol.

2.4.1. Current Diagram-Understanding Systems
Over the last ten years, a variety of diagram-understanding systems have been developed,
aiming at more natural and effective human-computer interaction. For instance, Aoki etal. (1996) developed a system that transforms hand-drawn floor plans into CAD data.
Egenhofer and Blaser developed Spatial-Query-by-Sketch, which enabled its users toquery spatial data by sketching a rough map of a place of interest (Egenhofer 1997;
Blaser and Egenhofer 2000). SketchIT (Stahovich 1997; Kurtoglu and Stahovich 2002)
interprets hand-drawn mechanical drawings and recreates new designs that realize thesame functions. Similarly, ASSIST (Alvarado and Davis 2001b; 2001a; Davis 2002)
interprets hand-drawn mechanical drawings and predicts how the illustrated mechanism
would behave (Figure 2.14). Landay and Myers (2001) developed a computer system that
supports GUI designs, which interprets hand-drawn screen layouts and generates a
prototype program (Figure 2.15). Skubic (2002) built a self-propelled robot, which moves
in the real world following a route in a sketch map.

29

Figure 2.14: ASSIST (Alvarado and Davis 2001b; 2001a; Davis 2002).

Figure 2.15: A sketch-based system that supports GUI designs (Landay and Myers
2001).
While these systems were designed for specific tasks, GeoRep (Ferguson andForbus 2000) was designed for the understanding of diagrams in various domains,
distinguishing the domain-independent lower-level process and the higher-level processusing domain-specific rules. Ferguson et al. (2000) applied GeoRep for the understandingof well-standardized diagrams used in military operations, called Course of Action (COA)
diagrams. Furthermore, sKEA (Ferguson and Forbus 2002; Forbus and Usher 2002) is
totally free from the application domains. In this system, the user teaches the computerhis or her knowledge of any domain by sketching diagrams (Figure 2.16).

30

Figure 2.16: sKEA (Ferguson and Forbus 2002; Forbus and Usher 2002).
In addition to the diagram-understanding systems based on sketching interfaces,
some researchers combine a sketching interface with a speech interface, aiming at moreuser-friendly and effective user interaction. For instance, Egenhofer (1996) developed theframework of Sketch-and-Talk in GIS, which enables its user to query spatial data byindicating a place of interest by the combination of sketch and speech, which partiallyoverlap with each other and work complementarily (Schlaisich and Egenhofer 2001).
QuickSet (Cohen et al. 1997; Johnston 1998; Cohen et al. 2000; Oviatt and Cohen 2000)
is a multi-modal system for map-based tasks, which is operated by speech and pen input(Figure 2.17). Based on the experiments with QuickSet, Oviatt (1999) pointed out thatspeech and pen input work complementarily rather than independently and, accordingly,
the combination of these two modes improves both input efficiency and recognition rate.
Similarly, nuSketch (Forbus et al. 2001; Ferguson and Forbus 2002) is a multi-modal
system operated by sketch and speech. This system is based on GeoRep (Ferguson andForbus 2000) and also applied to the COA diagrams (Figure 2.18). With speech input,
nuSketch avoids the problems in recognizing objects (glyphs), which may be rapidly
31

drawn and then classified via a few quick verbal comments rather than carefully drawn indetail (Ferguson and Forbus 2002). ASSISTANCE (Davis 2002) is another multi-modal
system that facilitates mechanical designs with sketch and verbal input.

Figure 2.17: QuickSet (Cohen et al. 1997; Johnston 1998; Cohen et al. 2000; Oviattand Cohen 2000).

Figure 2.18: nuSketch COA creator (Forbus et al. 2001; Ferguson and Forbus 2002).

2.4.2. What is Diagram Understanding?
A comparison of these diagram-understanding systems reveals three different levels ofcomputational diagram understanding. At the most primitive level, diagram
understanding is equivalent to a set of symbol recognition processes. For example, the32floor plan interpreter (Aoki et al. 1996) recognizes such architectural symbols as walls,
doors, and windows individually, using a collection of templates for those architecturalsymbols. This level of diagram understanding is relatively easy, as it is achieved by
preparing a sufficient set of templates for the target domain (Davis 2002).
The difficulty of such symbol recognition arises when the system has to handle
polysemic symbols, such as zigzag symbols in mechanical drawings, which may
represent a spring or an electrical resistor (Kurtoglu and Stahovich 2002). Interpretationof such ambiguous symbols requires the consideration of plausible relations between theentities represented by the symbols (Davis 2002; Kurtoglu and Stahovich 2002). For
instance, a zigzag symbol that connects to a battery symbol probably represents anelectrical resister, because a battery can be connected to an electrical resister, but rarely toa spring. In this way, background knowledge about plausible relations among theelements in the target domain is necessary for the diagram understanding in the middle
level.
The highest level of diagram understanding further requires the understandingof the overall mechanism or process that the diagram illustrates. At this level, diagram
understanding is no longer a passive process of absorbing what is in the diagram, but anactive process of model construction and inference, using the diagram as an outline of themodel to be constructed (Novak 1995). If a diagram-understanding system achieves thislevel, the system can predict how each element in the diagram would behave in the realworld (Funt 1980; Davis 2002) or even redesign the mechanism that satisfies the samefunctions (Stahovich 1997).
33

Interpretation of arrow-containing diagrams corresponds to the middle-level
diagram understanding, because arrow symbols are polysemic. Like zigzag symbols, theinterpretation of arrow symbols may have to consider the plausible relations between thecomponents. In addition, the interpretation of arrow symbols is critical for thehighest-level diagram understanding, since arrow symbols are often used for theillustration of complicated processes or mechanisms.

2.4.3. Diagram-Understanding Systems and Arrow Symbols
Many of the diagram-understanding systems accept the use of arrow symbols. In somesystems, however, the use of arrow symbols is restricted to a single or a few
predetermined semantic roles. For instance, in the GUI design support system (Landay
and Myers 2001) arrow symbols are used only for specifying which window emerges orgets focus when each GUI component is operated (Figure 2.15). In SketchIT (Stahovich
1997; Kurtoglu and Stahovich 2002), arrow symbols are used only for specifying thedirections in which mechanical components can move. In ASSIST (Alvarado and Davis
2001b; 2001a; Davis 2002) the user can use an arrow symbol to specify the gravity
direction (Figure 2.14). In nuSketch COA creator (Forbus et al. 2001; Ferguson andForbus 2002) arrow symbols with different semantic roles are distinguished by theirdifferent shapes. Such restriction of arrow symbols to a few semantic roles works
effectively for specific tasks, since the ambiguity of arrow symbols are excluded. As adrawback, the users of these systems are forced to get used to the restriction of arrowsymbols, which sacrifices the intuitiveness of sketching interfaces.
34QuickSet (Cohen et al. 1997; Johnston 1998; Cohen et al. 2000; Oviatt andCohen 2000) accepts arrow symbols with a variety of semantic roles, such as specifying a
direction, illustrating a route, and indicating relations (Figure 2.17). Furthermore, sKEA
(Ferguson and Forbus 2002; Forbus and Usher 2002) allows its users to express arbitrary
binary relations using arrow symbols (Figure 2.16). These systems, however, still haveroom for improvement, because the users have to specify the semantic role of everyarrow symbol by speech (QuickSet), text input, or selection from a menu (sKEA). Suchspecification disturbs human-computer interactions, because in human communications
arrow symbols are communicated smoothly without specification.
Overall, most current diagram-understanding systems do not allow the naturaluse of arrow symbols, due to the lack of a human-like ability to understand the semanticroles of arrow symbols. One exception is ASSISTANCE (Davis 2002), which
automatically distinguishes the arrow symbols representing causality and those
representing external force. Such distinction, however, depends on the domain-specificrules, which cannot be applied to other sketch-based tasks. The remainder of this thesis,
therefore, develops a general-purpose algorithm for deriving the interpretations of arrowsymbols in diagrams, aiming at the improvement of sketching interfaces.

2.5. Spatial Relations between Line Segments
In multi-arrow diagrams, a set of arrow symbols in a specific formation may organize agroup and jointly capture certain semantics, such as expansion and multiple choices35

(Figure 1.2). This motivates us to model the spatial arrangement of arrow symbols in
multi-arrow diagrams (Section 3.3). As the foundation of this model, this section reviews
the studies of spatial relations between (directed) line segments.
Topological relations are spatial relations invariant under topologicaltransformations, such as translation, rotation, and scaling (Egenhofer 1989). Topologicalrelations between line segments in R2 (and their lower-dimensional relatives, temporalintervals in R1) have been studied extensively in artificial intelligence andspatio-temporal databases communities.
The 4-intersection (Egenhofer and Franzosa 1991) captures topologicalrelations between two spatial objects, including line segments, based on the presence orabsence of geometric intersections of the objects’ interiors and boundaries. The
topological relations between two objects1 A and B are characterized by the patterns of
the 4-intersection matrix (Equation 1) with regard to the emptiness or non-emptiness ofeach entry, where X ° and ∂X refer to the interior and boundary of an object X,
respectively.

 A° ∩ B° A° ∩ ∂B 
M ( A, B ) =  ∂A ∩ B° ∂A ∩ ∂B 

(1)

The 4-intersection distinguishes eight topological relations between two line
segments embedded in R1 (Pullar and Egenhofer 1988) and sixteen relations between two

1

Capitalized letters are used for representing individual spatial objects, since these objects are originallydefined as point sets Alexandroff, P. (1961) Elementary Concepts of Topology. Dover, Mineola, NY.

36

line segments embedded in R2 (Hadzilacos and Tryfona 1992). The dimension-extended
method of the 4-intersection (Clementini et al. 1993) finds eighteen relations between
two line segments embedded in R2.
The 9-intersection (Egenhofer and Herring 1991) extends the 4-intersection byconsidering also the intersections with respect to the objects’ exteriors, which gives rise
to distinguishing 33 topological relations between two line segments embedded in R2(Egenhofer 1994). Another variation of the 4-intersection distinguishes explicitly the two
distinct elements of line segments’ boundaries—the start point and the end point—andidentifies 16 relations between uni-directed line segments embedded in a cyclic
one-dimensional space (Hornsby et al. 1999) and 68 relations between two directed line
segments embedded in R2 (Kurata and Egenhofer 2006a). In this model, the topologicalrelations between two line segments1 L1 and L2 are characterized by the patterns of a 3×3
matrix (Equation 2) with regard to the emptiness or non-emptiness of each entry, where∂ s L , L ° and ∂ e L refer to the start point, interior, and end point of a directed line
segment L, respectively.

 ∂ s L1 ∩ ∂ s L2

M (L1 , L2 ) =  L1 ° ∩ ∂ s L2
∂ L ∩ ∂ L
s 2
 e 1

∂ s L1 ° ∩ L2 ° ∂ s L1 ∩ ∂ e L2 
L1 ° ∩ L2 °L1 ° ∩ ∂ e L2 
∂ e L1 ∩ L2 ° ∂ e L1 ∩ ∂ e L2 (2)Models for more detailed topological relations, capturing such properties ofnon-empty intersections as the number of intersections and the dimension of common
parts, have been developed for topological relations between two regions (Egenhofer andFranzosa 1995) and two line segments (Clementini and Di Felice 1998), yielding a set of37

topological invariants. Such additional invariants have been known to be tightly related
to distinguishing even basic relations between line segments, such as touching andcrossing (Herring 1991). Furthermore, Nedas et al. (2007) captured more details of
topological relations between line segments by incorporating two metric measures,
splitting ratios and closeness measures, into the 9-intersection matrix.
Other approaches categorize spatial relations between line segments based on
the order of the line segments. Allen (1983) identified thirteen order relations between
two temporal intervals (essentially uni-directed line segments in R1). Schlieder (1995)
extended the concept of order into a two-dimensional space and identified 63
two-dimensional order relations (essentially directional relations) between two straightdirected line segments embedded in R2. The dipole calculus (Moratz et al. 2000)
distinguished 24 directional relations between two straight directed line segments
embedded in R2, which fulfill the constraints of a relation algebra. Likewise, a set of 26
order relations between two directed line segments in R1 forms the directed interval
algebra (Renz 2001). The direction-relation matrix provides an overall framework fordescribing directional relations between any pair of extended objects in R2, including
arbitrarily shaped line segments (Goyal and Egenhofer 2000).

38

2.6. Summary
This section reviewed the related studies about the characteristics and semantic roles ofarrow symbols, diagram-understanding computer systems, and spatial relations between
line segments. The major findings are summarized as follows:•

An arrow symbol is defined as a special kind of line, with one end marked, inducing
an asymmetry.

•

Arrow symbols are used multi-purposely for specifying a directional property,
illustrating a spatial movement, communication, and continuous existence, indicating
an ordered binary relation (including temporal orders, changes, causal relations, andconditional relations), and labeling.

•

Diagrams facilitate the communication of information as well as enhance people’sability for problem solving. To make use of such diagrams’ strength, a number of
pen-based systems that understand human-sketched diagrams have been developed,
aiming at more user-friendly and effective computer interfaces.

•

To realize more intelligent interfaces, diagram-understanding systems should beequipped with a capability to interpret the arrow symbols in the diagrams.

•

Topological relations between two directed line segments, which forms a foundation
for modeling the spatial arrangement of arrow symbols, are modeled systematically
based on the presence or absence of geometric intersections of the three parts (startpoint, interior, and end point) of the two segments.

39

Chapter 3
STRUCTURES OF ARROW DIAGRAMS

Pen-based systems should be able to distinguish the semantic roles of arrow symbols,
since people use arrow symbols multi-purposely without specification (Section 2.2). Thus,
this thesis develops an algorithm for deducing the semantic roles of arrow symbols,
which is called the ASI (arrow symbol interpreter). This method emphasizes the structural
patterns of arrow diagrams, which apparently have a strong influence on the diagrams’
semantics (Section 1.1). As the foundation, this chapter introduces two types of structuresof arrow diagrams, called individual structures and inter-arrow structures (Kurata andEgenhofer 2005a; 2005b; 2006c). Individual structures model the spatial arrangement ofcomponents around individual arrow symbols, while the inter-arrow structures model the
spatial arrangement of multiple arrow symbols in arrow diagrams. These two types ofstructures work complementarily, because they capture the configurations of arrow
diagrams from local and global perspectives.
This chapter first introduces relevant terminology (Section 3.1). Then, Section
3.2 and Section 3.3 define the individual structures and the inter-arrow structures,
respectively. Section 3.4 demonstrates through two examples how these two types ofstructures work complimentarily.

40

3.1. Terminology
An arrow diagram is a syntactic unit in a diagram, which consists of arrow symbols andthe elements to which the arrow symbols refer, called the components of the arrow
diagram (Section 1.2). Each component is considered an independent semantic unit that
contributes to the diagram’s semantics. Components are typically illustrated around thearrow symbols by an icon, text, a small diagram embedded in the arrow diagram, or a
specific point or region in the background picture, map, or image. Sometimes
components are separate from the arrow symbols or even not illustrated in the diagram(Section 6.5.1).
A 1-arrow diagram contains a single arrow symbol, while a multi-arrow
diagram contains more than one arrow symbol. The semantics of the 1-arrow diagram isestablished by an arrow symbol and its components (Chapter 4). Thus, this thesis
considers the spatial arrangement of the components around the arrow symbol, which ismodeled as an individual structure (Section 3.2). In a multi-arrow diagram, suchindividual structure is associated with every arrow symbol in the diagram. In addition, a
set of arrow symbols, typically forming a certain spatial arrangement, may organize agroup and jointly capture certain semantics (Section 5.2). Thus, this thesis also considers
the spatial arrangement of multiple arrow symbols, which is modeled as an inter-arrow
structure (Section 3.3).

41

3.2. Individual Structures
The individual structure of an arrow symbol models the spatial arrangement ofcomponents related to this arrow symbol. This section defines the individual structure
and its patterns, introducing the notion of three component slots and the categorization ofcomponents.

3.2.1. Three Component Slots

When an arrow symbol refers to a component around the arrow symbol, this component
is located in front of, behind, or along the arrow symbols to which the component refers.
This thesis, therefore, considers that an arrow symbol is a deictic reference frame(Retz-Schmidt 1988), which identifies three different conceptual areas where thecomponents related to this arrow symbol can be located (Figure 3.1). These three areas
are called the component slots of an arrow symbol and the component slots behind, along,and in front of the arrow symbol are called the tail slot, body slot, and head slot,
respectively (Kurata and Egenhofer 2005a).
Tail slot

Body slot

Head slot

Figure 3.1: Three component slots associated with an arrow symbol.
Each component slot may contain zero, one, or multiple components (Figure3.2). Every component, if illustrated around an arrow symbol, is assigned uniquely to one42

of the three component slots, thereby making the distinction of tail components, bodycomponents, and head components.

Mr. K
5:50pm
5:30pmFigure 3.2: An arrow symbol with multiple components in each component slot.
In addition, it is assumed that even if an arrow symbol implicitly refers to acomponent without pointing to, originating from, or passing by or through it, thiscomponent is assigned to one of the arrow symbol’s three component slots (Figure 3.3).

Figure 3.3: The label “WATER” is attached to only one of the dashed arrow symbols,
but is conceptually assigned to the body slot of all dashed arrow symbols.

3.2.2. Definition of Individual Structures

The individual structure associated with an arrow symbol a (or simply called a’s
individual structure), s ind (a ) , is defined as a list of the components in a’s threecomponent slots. It is denoted by a 3-tuple in Equation 3, where C tail (a ) , C body (a ) , andC head (a ) are the respective non-ordered sets of components in a’s tail, body, and head43

slots. For instance, the individual structure associated with the arrow symbol in Figure
3.2 is ({“Mr. K”, traveler, “5:30pm”}, {parking lot, gas station}, {house, “5:50pm”}).

sind (a ) = (C tail (a ), C body (a ), C head (a ))(3)

An individual structure captures the spatial arrangement of components in aprimitive way, but such arrangement is critical for the diagram’s semantics (Kurata andEgenhofer 2005a). For example, Figure 3.4a shows two 1-arrow diagrams in which thetail component and the head component have been exchanged, essentially reversing thesemantics from “mounting a wheel to a car” to “removing a wheel from a car.” Figure
3.4b shows another pair of 1-arrow diagrams where the head component has been moved
to the body slot, such that the semantics changes from “a tourist goes to Maine” to “atourist passes through Maine.”

(a)

(b)

Figure 3.4: Two pairs of 1-arrow diagrams, each with the same components indifferent component slots, illustrate different semantics.

44

3.2.3. Pattern of Individual Structures

The individual structures have countless configurations, since arrow symbols may refer toarbitrary components. Thus, this thesis extracts fundamental patterns of the individual
structures by categorizing the components.
First, components are dichotomized into primary component (PC) and modifiercomponents (MC). A primary component represents an independent concept, while a
modifier component modifies something else, such as a primary component and an arrowsymbol. For instance, in Figure 3.5, the icons for traveler and firework are primary
components that represent a traveler and a firework show, while the labels “Mr. K”, “July4”, and “Boston” are modifier components, which modify the traveler icon, the arrowsymbol, and the firework icon, respectively.
Mr. K
July 4
BostonFigure 3.5: A 1-arrow diagram with two primary components (a tourist icon and afirework icon) and three modifier components (“Mr. K”, “July 4”, and “Boston”).
A component has such a representation style as an icon, a text label, a small
diagram embedded in the diagram, or a point or region in the background picture, map, or
image. The dichotomization of components is, however, purely conceptual and not
determined by the representation style of components alone. Therefore, both primary
components and modifier components may be expressed by any representation style.

45

There are, however, the following diagrammatic conventions and rules, which are usefulfor distinguishing the primary and modifier components in a visual domain:•

Icons are usually primary components;•

Text labels attached to icons are usually modifier components;•

If an arrow symbol refers to only one component, it is always the primary
component; and•Any representation style of a component, if used alone at the head slot, is always aprimary component, because the modifier component can be used alone in the tailslot as a label in annotation (Section 4.2.3) or in the body slot as an adverbial
component (Section 4.3.2), but not in the head slot.
In addition to the distinction of primary and modifier components, the primary

components are further categorized into the following four types:•

A location is a position in space. It is a point or a homogeneous area that is
considered as a unit of space (e.g., the parking lot, the gas station, and the house in
Figure 3.2). A modifier component may also represent a position in space (e.g.,“Boston” in Figure 3.5), but it is not included in the location.

•

A moment is a position in time. It is an instant or a homogeneous interval that is
considered a unit of time (e.g., “5:50pm” in Figure 3.2). A modifier component may
also represent a position in time (e.g., “July 4” in Figure 3.5), but it is not included in
the location.

46

•An object is an entity or its unit, which exists in physical or conceptual space, andtakes an action (e.g., a traveler in Figure 3.5) or gets manipulated (e.g., a wheel and avehicle without a wheel in Figure 3.4b). Objects are continuants, which endure
through some extended interval of time (Worboys and Hornsby 2004).

•

An event occurs in time. It is characterized by a set of changes that the event triggers.
An event occurs at an instant or over an interval (e.g., a firework show in Figure 3.5).
Events are occurents, which happen and are then gone (Worboys and Hornsby 2004).

Location, moment, object, and event are symbolically expressed by PCL, PCM, PCO, andPCE, respectively, emphasizing that they are subcategories of primary components (PC).
The component types may depend on the context. For instance, in Figures
3.6a-b the same icons pointed by the arrow symbols refer to an object (a broken car) andan event (a car accident), respectively. This implies that a method for determining thecomponent types is necessary for fully automated interpretation, but at this stage weassume that the type of every component is given.

(a)

(b)

Figure 3.6: Two 1-arrow diagrams, whose head components are apparently same,
but belong to different component types: (a) object (a broken car) and (b) event (acar accident).
The influence of the component types on the diagram’s semantics ishighlighted in the following example (Kurata and Egenhofer 2005a). The arrow symbols

47

in Figures 3.7a-c originate from the same tourist, but point to different components: (a) abag (an object), (b) a symposium (an event), and (c) the State of Maine (a location).
These different types of components lead to different semantics: (a) the tourist holds out
his bag, (b) the tourist attends the symposium, and (c) the tourist goes to Maine. On theother hand, arrow diagrams with the same patterns of component types often lead tosimilar type of semantics. For example, both Figures 3.7c and 3.7d illustrate a spatial
movement of the tail component (an object) to the head component (a location).

Symposium

(a)

(b)

(c)

(d)

Figure 3.7: Arrow symbols with the same tail components and different types ofhead components: (a) object, (b) an event, and (c-d) a location.
With the distinction of primary and modifier components (PC and MC), andfurther distinction of four subclasses of the primary components (PCL, PCM, PCO, andPCE), the pattern of the individual structure is defined as follows:
pattern_of_individual_structure ::=“(” tail_components “,” body_components “,”head_components “)”
tail_components ::= [components]
body_components ::= [components]
head_components ::= [components]
components::= component [components]

component::= PCL|PCM|PCO|PCE|MC48

For instance, the patterns of the individual structures in Figures 3.8a-d are (-, -, -),(PCO, -, PCL), (PCLPCO, -, -)2, and (MC, PCO, PCL), respectively. The three elementsin each 3-tuple indicate the type of all components in the tail, body, and head slots.

You arehere(a) (-, -, -)(b) (PCO, -, PCL)(c) (PCL PCO, -, -)2(d) (MC, PCO, PCL)

Figure 3.8: Four 1-arrow diagrams with the patterns of their individual structures.

3.3. Inter-Arrow Structures
Inter-arrow structure models the spatial arrangement of arrow symbols in a multi-arrow
diagram. Such arrangement is captured as a set of spatial relations between all pairs of thearrow symbols. Among several types of spatial relations, this thesis focuses on the
topological relations, since topological information is highly influential in people’s
conceptualizations of space (Egenhofer and Mark 1995) and accordingly is expected toplay an important role for the diagrams’ semantics.

2

This pattern may be described as (PCO PCL, -, -) as well, since the notation of the individual structure isnot concerned with the order of components within a slot.

493.3.1. Definition of Inter-Arrow Structures

The inter-arrow structure of an arrow diagram d, sint (d ) , is defined as the set of
topological relations between all pairs of arrow symbols in d (Equation 4), where
M L (ai , a j ) is the 9-link matrices (Section 3.3.2) of two arrow symbols ai and aj, which
captures their topological relations, and A(d ) is the set of all arrow symbols in d.

{sint (d ) = M L (ai , a j ) ai , a j ∈ A(d ), ai ≠ a j}(4)

3.3.2. Topological Relations between Two Arrow Symbols

Topological relations between two arrow symbols are established by the geometricintersections of the arrow symbols (Figures 3.9a and 3.9d), as well as the arrow symbols’references to the same component(s) (Figures 3.9b and 3.9e). To contrast these two typesof connections between arrow symbols, a geometric intersection of two arrow symbols iscalled a direct link, while a connection intermediated by a component to which botharrow symbols refer is called an indirect link (Kurata and Egenhofer 2006c). Two arrowsymbols may be connected by direct links (Figures 3.9a and 3.9d), indirect links (Figures
3.9b and 3.9e), or both direct and indirect links (Figures 3.9c and 3.9f).

50

Inspection

pass

fail

Shipping(a)Main Gate
Temporary Gate(d)

Disposal(b)
query
result(e)(c)
Inspection

DB

pass

fail

Shipping

Disposal(f)Figure 3.9: Six 2-arrow diagrams where arrow symbols are connected by (a) ahead-head intersection, (b) references to the same “Inspection” label, (c) both ahead-tail intersection and references to the same landing strip icon, (d) a body-tailintersection, (e) references to the same cell phone and database icons, and (f) both atail-tail intersection and references to the same “Inspection” label.
From a geometric viewpoint, topological relations between arrow symbols
established by their direct links are equivalent to topological relations between two
directed line segments (Section 2.5). The topological relations between two directed line
segments are captured based on the presence or absence of geometric intersections of
their three parts—tail (start point), body (interior), and head (end point) (Kurata andEgenhofer 2006a). Similarly, this thesis distinguishes three parts of arrow symbols—back
end, interior, front end—which are called the tail, the body, and the head of the arrowsymbol, respectively. The tail and head are treated as points, while the body is consideredan open-ended line segment. Depending on the combination of the intersecting parts, 3×3= 9 types of direct links between two arrow symbols are distinguished: direct tail-tail,tail-body, tail-head, body-tail, body-body, body-head, head-tail, head-body, andhead-head links. These nine types of direct links between two arrow symbols a1 and a2
are concisely represented by a 3×3 matrix (Equation 5), where ∂ tail a k , ak ° , and ∂ head a k51

are the tail, body, and head of an arrow symbol a k , respectively. This matrix corresponds
to the hbt-matrix (Kurata and Egenhofer 2006a), which distinguishes 68 topologicalrelations between two directed line segments.

 ∂ tail a1 ∩ ∂ tail a 2

M DL (a1 , a2 ) =  a1 ° ∩ ∂ tail a2
∂ a ∩ ∂ atail 2
 head 1∂ tail a1 ° ∩ a2 ° ∂ tail a1 ∩ ∂ head a 2 
a1 ° ∩ a2 °a1 ° ∩ ∂ head a2 ∂ head a1 ∩ a2 ° ∂ head a1 ∩ ∂ head a2 (5)Similarly, 3×3 = 9 types of indirect links are distinguished by the combinationof the component slots that contain the component to which both arrow symbols refer.
These nine types of indirect links are called indirect tail-tail, tail-body, tail-head,body-tail, body-body, body-head, head-tail, head-body, and head-head links. The nine
types of indirect links between two arrow symbols a1 and a2 are concisely represented byanother 3×3 matrix (Equation 6), where C tail (ak ) , C body (a k ) , and C head (a k ) are therespective sets of all components in the tail, body, and head slot of an arrow symbol a k .

M IL (a1 , a 2 ) = C tail (a1 ) ∩ C tail (a 2 ) C tail (a1 ) ∩ C body (a 2 ) C tail (a1 ) ∩ C head (a 2 )  C body (a1 ) ∩ C tail (a 2 ) C body (a1 ) ∩ C body (a 2 ) C body (a1 ) ∩ C head (a 2 )
 C (a ) ∩ C (a ) C (a ) ∩ C (a ) C (a ) ∩ C (a ) 
tail
2
head
1
body
2
head
1
head
2 
 head 1(6)Topological relations between arrow symbols are established by direct links,
indirect links, and their combinations. Direct links and indirect links are analogous in thesense that both associate two arrow symbols by connecting the tail, body, or head of one
arrow symbol with the tail, body, or head of another arrow symbol. Due to this analogy,
the presence or absence of the nine types of direct links and the nine types of indirect52

links between two arrow symbols a1 and a2 is concisely represented by a single 3×3
matrix called the 9-link matrix M L (a1 , a 2 ) (Equation 7), where m DL ij and m IL ij are
the (i, j) elements of M DL ij (a1 , a 2 ) (Equation 5) and M IL ij (a1 , a 2 ) (Equation 6) ,respectively.

[

M L (a1 , a 2 ) = mL ij

]

φ
D

mL ij = ID & I

if mDL ij = φ
if mDL ij = ¬φ
if mDL ij = φ
if mDL ij = ¬φmIL ij = φmIL ij = φmIL ij = ¬φmIL ij = ¬φ

∧
∧
∧
∧

(7)

(i, j = {1,2,3})

The first, second, and third row of the 9-link matrix correspond to a1’s tail,body, and head, while the first, second, and third columns correspond to a2’s tail, body,and head, respectively. Each cell specifies the presence of direct (D), indirect (I), or
mixed (D & I) links. Figure 3.10 shows the 9-link matrices for the topological relations
between the pairs of arrow symbols in Figure 3.9.
φ φ
φ φ

φ φ

(a)

φ
φ 

D 

φ φ φ D φ φ  φ φ φ I φ φ 
φ φ φ φ φ φ 

φ φ I φ φ φ  I φ φ 

(b)

(c)

(d)

φ φ
φ φ

φ I

(e)

D
φ 
φ 

B φ φ 
φ φ φ φ φ φ 

(f)Figure 3.10: The 9-link matrices that capture the topological relations between thepairs of arrow symbols in Figures 3.9a-f.
The 9-link matrix distinguishes 49 = 262,144 patterns, since its nine entries are
four-valued (φ, D, I, D & I). Not all of these patterns, however, correspond to actual
topological relations between two arrow symbols, due to the following conditions on the
topological relations:53•The head of an arrow symbol cannot intersect with more than one part of anotherarrow symbol, because the head is a single point. Similarly, the tail of an arrowsymbol cannot intersect with more than one part of another arrow symbol.

•

If the head slot of an arrow symbol contains multiple components, these components
cannot be contained in different component slots of another arrow symbol, because
these components are located at a single (or undistinguishable) position to which thearrow symbol points. Similarly, if the tail slot of an arrow symbol contains multiple
components, these components cannot be contained in different component slots ofanother arrow symbol•

The head of an arrow symbol cannot simultaneously have a direct link and an
indirect link with two different parts of another arrow symbol, because the head is asingle point. Similarly, the tail of an arrow symbol cannot simultaneously have a
direct link and an indirect link with two different parts of another arrow symbol.

These three conditions on the topological relations yield the following constraints on the
9-link matrix, respectively:•

The first column, third column, first row, and third row may have at most one direct(D) or mixed (D & I) link.

•

The first column, third column, first row, and third row may have at most one
indirect (I) or mixed (D & I) link.

•

The first column, third column, first row, and third row may not have both indirect(I) and direct (D) link at the same time.
54

These three constraints compile the following single constraint:•

The first column, third column, first row, and third row have at most one non-empty
element.

Among the 262,144 patterns of the 9-link matrix, only 1,864 patterns satisfy thisconstraint (Table 3.1). This indicates that the 9-link matrix distinguishes 1,864
topological relations between two arrow symbols. Among the 1,864 topological relations,
184 relations are symmetric, while the rest form 840 pairs of converse relations.

Table 3.1: Number of patterns of the 9-link matrices satisfying the constraint.

m L 22empty
non-empty

Number of non-empty cells except m L 22
0
1
2
3
4
1
2
3
1
8×3
16×3
8×3
1×34
1×31
8×32
16×33
8×34
1×35
4
96
576
864
324

466
1,374
1,864

3.3.3. Analysis of Topological Relations Established by Direct Links

If the entries of the 9-link matrix are limited to φ and D, the 9-link matrix has 29 = 512
patterns, among which 68 patterns satisfy the previous constraint. This indicates that for
two arrow symbols the 9-link matrix distinguishes 68 topological relations that are
established by direct links alone (Table 3.2). These 68 topological relations between two
arrow symbols exactly match with the 68 topological relations between two directed line
segments embedded in R2 (Kurata and Egenhofer 2006a).

55

D

φ
D

φ
φ 

D 

φ
φ

 D

D

φ
φ

φ
φ

φ
D 
φ 

φ
D

 φ

φ
D 
φ 

D φ
φ φ 
D φ 

φ
D

 φ

φ
D 
φ 

φ
D

 φ

D φ
φ φ 
φ φ 

φ

D
φ 
φ 

φ
D

 φ

φ
φ

φ

D

φ
D

φ
D

φ

D

φ
φ

φ
D 
φ 

φ
D 
φ 

φ
φ

φ

D
D

φ

D
φ

 φ

D
D

φ

φ
D 
φ 

φ
D 
φ 

φ
D 
φ 

56

φ
D

 φ

D
D

φ
φ 

φ φ
D φ 
D φ 

φ
D

 φ

D
D

φ

D 

φ
D

 φ

D
D
D

φ
D 
φ 

φ
φ

 D

D
D

φ

φ
D 
φ 

φ φ
D φ 
D φ 

φ
D

 φ

D

φ
φ

D
φ 
φ 

φ
φ

φ

D
D

φ
D

 φ

D
D

φ

φ

#43

φ
φ

 D

D φ
D φ 
φ φ 

φ
φ 
D 

φ
D

 φ

φ
φ

φ

φ
D

 φ

φ
D

φ

φ
D
D

D
φ 
φ 

D
φ 
φ 

↑↓

φ
φ 
D 

φ
D 
φ 

φ
φ

 D

φ
D

 φ

↑↓

φ
D 
φ 

φ
D 
φ 

↑↓

D
φ

 φ

↑↓

φ
D 
φ 

φ

φ

φ φ
D φ 
D φ 

↑↓

φ
D

 φ

φ

#42

#40
#53

φ

#54

D

#49

φ
φ

 D

↑↓

φ
φ

φ

D

φ

φ
D

φ
φ

φ

↑↓

#55

φ
D 
φ 

D

D
φ

 φ

↑↓

φ φ
φ φ

 D φφφ

φ φ
D φ 
φ φ 

#56D φ
D φ 
D φ 

#41

φ
φ

φ

φ
D

 φ

#57

D 

φ φ
D φ 
φ φ 

#58

φ

φ
φ

φ

↑↓

#59

φ
φ 

D φ
D φ 
φ φ 

#66

φ

φ
φ

 D

↑↓

φ
φ 
D 

φ
φ

φ

↑↓

#52

D 

#39

D

φ

#48

#37
#44

D
φ

 φ

φ
φ 

#50

D
φ 
φ 

#45

φ
φ

φ

φ
φ

D
φ 
φ 

D φ
D φ 
D φ 

φ
D

φ

φ
D
D

φ
D 
φ 

φ
D 
φ 

↑↓
#67

φ
D

 φ

φ
φ

D
φ 
φ 

D

φ

↑↓

φ φ
D φ

 φ φ

↑↓
#31

D

#29

#27

φ
D

 φ

φ
φ 
D 

φ
D

#64

D

φ
φ

φ

#65

φ
D

 φ

φ
φ

φ

#51

D

↑↓

#34

4

D
φ 
φ 

φ
φ

φ

D

#62

φ
φ

#21

φ
D

 φ

#30

#17

φ φ
φ φ 
D φ Dφφ 
D φ 

↑↓

φ
D

 φ

φ
φ

φ

#63

D

φ
D 
φ 

#28

#13
#26

φ
φ

φ
D 
φ 

3

D
φ

 φ

φ
φ
D

φ
φ

φ φ
D φ

 φ φφ φ
D φ 
φ φ 

↑↓

#46

D
φ

 φ

↑↓

φ
φ

φ

D φ
φ φ 
φ φ 

#47

φ
D 
φ 

φ
φ

φ
φ

 D

#60

φ
φ

φ

D

φ
φ 
D φ 

#61

φ
D 
φ 

#19

φ φ
D φ

 φ φ

φ
φ

#68

D φ
φ φ 
φ φ 

φ
D 
φ 

φ
φ

φ

↑↓

#20

φ
D

 φ

D
φ 
φ 

#15

φ φ
φ φ

 D φ

#16

#11
#12

Number of Links
2

↑↓

D
φ

 φ

↑↓

#9
D φ
φ φ

 φ φ#22

D φ
φ φ 
D φ 

#23

D 

φ
φ

φ

#24

φ
φ 

φ φ φ D φ φ  φ φ φ 

#25

D 

φ
D 
φ 

φ φ
D φ 
φ φ 

↑↓#7
φ φ φ 
φ φ φ  D φ φ 

#18

D φ
φ φ

 φ φ

φ
φ 

#14

#10

φ φ
φ φ

φ φ

φ φ
φ φ

φ φ

↑↓

#5

#3

1

↑↓

D φ
φ φ 
φ φ 

φ
φ

φ

#38

#35
#8
φ
φ

φ

D
φ 
φ 

#32

φ φ
φ φ

φ φ

#33

D φ φ 
φ φ φ  φ φ φ 

#6#4

φ φ φ 
φ φ φ φ φ φ 

#36With Direct Body-Body Link
Symmetric
Asymmetric#20Without Direct Body-Body Link
Symmetric
Asymmetric#1

Table 3.2: 68 topological relations between two arrow symbols, which have no
indirect links.

φ
φ

φ

D
D
D

φ
D 
φ 

These 68 relations are schematized by a conceptual neighborhood graph(Egenhofer and Al-Taha 1992; Freksa 1992). In the conceptual neighborhood graph, eachnode corresponds to a relation, and each link indicates that two relations corresponding to
the linked two nodes are conceptual neighbors (Freksa 1992), which are topologicallysimilar relations between which a continuous transformation can be performed without
having to go through a third relation. For example, the relations #2 and #18 areconceptual neighbors, because #18 is derived from #2 by moving the head of one arrowsymbol from another’s exterior to its body. The conceptual neighborhood graph of the 68
relations is derived computationally by linking all pairs of relations with a single
difference across their 9-link matrices. Such pairs are always conceptual neighbors,
equivalent to type-A neighbors for 1-dimensional intervals (Freksa 1992), because achange of one entry in the 9-link matrix reflects an atomic change, dissolving either anintersection of two boundary elements, or an intersection between a boundary element
and a body, or an intersection between two bodies.
Figure 3.11 shows the conceptual neighborhood graph of the relations #1
through #34, which is homeomorphic to the conceptual neighborhood graph of therelations #35 through #68. It displays more than 34 nodes to highlight some of theregularities of the neighborhoods by repeating the nodes in the front and back row as wellas in the left and right column. The graph reveals the special status of the relations #10
and #11 as the only relations with two conceptual neighbors among their 34 companions
without body-body intersections.

57

#1
#11

#10
#33

#34
#26
#32

#19
#13

#18

#34

#33

#14

#32

#23
#7

#3

#15

#20
#12

#21

#22

#17

#1

#6

#34

#28

#4

#5
#16

#29

#24

#2

#25

#31

#9

#8

#15

#30

#14

#30
#27

#31

#34

Figure 3.11: The conceptual neighborhood graph of the relations #1 through #34,
illustrated on a plane.
The conceptual neighborhood graphs in Figure 3.11 have the following uniquecharacteristics:•

Relations with fewer direct links are located closer to the center.

•

Relations located on the diagonal from top-left to bottom-right are symmetric (Figure
3.12a).

•

Pairs of relations that are located symmetrically across the diagonal from top-left tobottom-right are converse, that is, the same matrices are obtained by transposing thematrices along their main diagonals (Figure 3.12a).

•

The conceptual neighborhood graph can be decomposed into four subgraphs with ahorizontal and vertical mirror axis such that the same matrices are obtained byreversing the direction of one arrow symbol (Figure 3.12b).

58

#7

#2

#4

r se
ve
n
co

#6

#5

#3

symmetric relation

(a)

(b)

Figure 3.12: Characteristics of the conceptual neighborhood graph in Figure 3.11:(a) symmetric and converse relations and (b) the four subgraphs that are obtained byreversing the direction of an arrow symbol when mirroring the relation along thegraph’s horizontal or vertical axis.
Gluing the front and back rows of the conceptual neighborhood graph in Figure
3.11, and then the leftmost and rightmost columns, yields a non-redundant configuration,in which the graph extends over the surface of a torus Figure 3.13b. Relations #10 and#11, which are placed irregularly above the flat graph in Figure 3.11, are now outside thetorus (Figure 3.13b).
identical

identical

(a)

(b)

Figure 3.13: The transition from (a) the flat conceptual neighborhood graph of therelations #1 through #34 with repeated columns and rows to (b) a graph displayed on
the surface of a torus, which is obtained by gluing together the repeated rows andcolumns along the fringes of the flat graph
59

The integrated conceptual neighborhood graph of the relations #1 through #68
has a two-layered structure, where each layer contains a homeomorphic conceptual
neighborhood graph of #1 through #34 or #35 through #68, and each node in one layer islinked uniquely to one node in another layer, thereby representing the neighbor relation
between #n and #(n+34) with 1≤n≤34. Consequently, the conceptual neighborhood graphof the relations #1 through #68 can be represented in a 3-dimensional space where nodes
are aligned on two parallel planes (Figure 3.14a) or on the surfaces of two nested tori
(Figure 3.14b), with links across the two planes or surfaces to represent the neighbor
relations between #n and #(n+34).
#35-#68#35-#68#1-#34#1-#34(a)(b)

Figure 3.14: Two structures of the conceptual neighborhood graph of the relations #1
through #68, where nodes are aligned on (a) two parallel planes and (b) the surfacesof two nested tori.

3.4. Demonstration
This chapter has introduced two types of structures in arrow diagram, which capture theconfiguration of arrow diagrams from two different perspectives. To demonstrate howthese two types of structures work complimentarily, this section considers the structures
60

of two examples in Figure 3.15. These two examples are revisited in Section 5.4.3, where
we demonstrate the process of deriving the interpretation of arrow symbols making use
ofn the patterns of the two structures.

Industrial Revolution

a1
a2

a3

a4 Urban
Rural
Area population Area

(a)

(b)

Figure 3.15: Two 2-arrow diagrams that capture that (a) a pack of wolves splits into
two packs, which approach a sheep from front and behind, and that (b) the industrial
revolution leads to the population drift from rural area to urban area.

3.4.1. Example 1: Wolves’ Attack Scenario

Figure 3.16 is a flowchart of the process of deriving the individual structures and theinter-arrow structure of the multi-arrow diagram in Figure 3.15a.

61

a1
a2

a1

a1

a2

+

Individual Structuressind (a1 ) = (wolves,−, sheep )sind (a 2 ) = ( part of wolves,−, sheep )Patterns of Individual Structures

a2

Inter-Arrow Structure
sint (d a ) = {M L (a1 , a 2 )}
φ φ φ 
M L (a1 , a 2 ) =  D φ φ  φ φ I pind (a1 ) = pind (a2 ) = ( PCO ,−, PCO )Figure 3.16: The process of deriving the individual structures and the inter-arrow
structure of the multi-arrow diagram in Figure 3.15a.
Figure 3.15a has two arrow symbols a1 and a2, which are associated with theindividual structures in Equation 8. The a2’s tail component is a part of the wolves,
although it is not explicitly illustrated in the diagram.
sind (a1 ) = (wolves,−, sheep )sind (a 2 ) = ( part of wolves,−, sheep )(8)

These two individual structures have the same patterns (Equation 9)

pind (a1 ) = pind (a 2 ) = (PCO ,−, PCO )(9)Since Figure 3.15a has only one pair of arrow symbols, the inter-arrow
structure consists of a single 9-link matrix M L (a1 , a2 ) , which captures the topological62

relation between a1 and a2. This topological relation is established by a direct body-taillink and an indirect head-head link (Equation 10).
s int (d a ) = {M L (a1 , a 2 )}
φ φ φ 
M L (a1 , a 2 ) =  D φ φ  φ φ I 

(10)

3.4.2. Example 2: Industrial Revolution Scenario

The arrow symbols a3 and a4 in Figure 3.15b are associated with the individual structures
in Equation 11. The arrow diagram is nested, since a3’s head component is an arrow
diagram “ Rural Area → Urban Area .”populationsind (a3 ) =  " Industrial Re volution" ,−, " Rural Area → Urban Area"populationsind (a 4 ) = (" Rural Area" , " population" , "Urban Area")(11)

These two individual structures have the patterns in Equation 12. The
subordinate diagram “ Rural Area → Urban Area ,” which refers to a spatial movement,
populationis considered as an ongoing event.

pind (a3 ) = (PCE ,−, PCE )pind (a 4 ) = (PCL , PCO , PC L )(12)

The inter-arrow structure of the 2-arrow diagram in Figure 3.15b consists of asingle 9-link matrix, which captures the topological relation between a3 and a4
established by their direct head-body link (Equation 13).
63

s int (d a ) = {M L (a 3 , a 4 )}φ
M L (a 3 , a 4 ) = φ
φ

φ
φ

φ
φ 
D φ 

(13)

3.5. Summary
This chapter introduced two types of structures in arrow diagrams. These structures
capture the configurations of arrow diagrams complementarily. The individual structuresmodel the spatial arrangement of components around individual arrow symbols, while theinter-arrow structures model the spatial arrangement of multiple arrow symbols in arrow
diagrams. The individual structure is represented as a 3-tuple, whose elements show thecomponents in the arrow symbol’s three component slots. Based on the distinction of two
component categories, primary and modifier components, and further distinction of four
sub-categories of primary components (location, moment, object, and event), the patternof such an individual structure is captured as a 3-tuple which shows the type of allcomponents in the three component slots. The inter-arrow structure is the set of
topological relations between all pairs of arrow symbols in a multi-arrow diagram. The
topological relation between two arrow symbols is characterized by the presence orabsence of nine types of direct links and nine types of indirect links between the arrowsymbols. To concisely represent such topological relation the 9-link matrix is introduced.
The two structures of arrow diagrams form the foundation for the interpretation of arrowsymbols.

64

Chapter 4
INTERPRETATIONS OF ARROW SYMBOLS IN 1-ARROWDIAGRAMSThis chapter develops a method for deriving the interpretation of arrow symbols in
1-arrow diagrams. We consider four classes of semantic roles—orientation, behavioral
description, annotation, and association—from which the interpretation of each arrowsymbol is made. A 1-arrow diagram has one individual structure and no inter-arrow
structure. The configuration of the individual structure is tightly related to the semanticrole of the arrow symbol, since in order to use an arrow symbol for a semantic roles theindividual structure must satisfies one of the basic formats peculiar to the semantic role
(Kurata and Egenhofer 2005b). This chapter, therefore, identifies for each class ofsemantic roles the basic formats of individual structures, as well as rules for adding
optional components to the basic formats.
This chapter starts with the classification of the semantic roles of arrowsymbols (Section 4.1). Section 4.2 identifies a set of basic formats, which individual
structures must satisfy when arrow symbols are used for each class of semantic roles.
Meanwhile, Section 4.3 identifies a set of rules for adding optional components to theindividual structures. The combination of the basic formats and the optional components
determines all patterns of individual structures that correspond to each class of semanticroles, which are essential for the interpretation of arrow symbols. Thus, first, with a focus
on simple 1-arrow diagrams (i.e., arrow diagrams with at most one component in each65

slot), Section 4.4 derives all patterns of individual structures that correspond to each classof semantic roles, and demonstrates that the patterns of individual structures are certainly
helpful for deriving the interpretations of arrow symbols. Finally, Section 4.5 develops analgorithm for deriving all possible interpretations of arrow symbols from the patterns ofgiven individual structures.

4.1. Classification of Semantic Roles
Arrow symbols have a large variety of semantic roles (Section 2.2), which make theinterpretation difficult. To simplify the discussion, the semantic roles of arrow symbols
are classified into four classes (Figure 4.1).

Semantic Roles of Arrow Symbols
requires only one component

requires at least two components

Orientation
assumes a transition

does not assume a transition

Behavioral Description
features one subject

Annotation

associates multiple subjects

Association

Figure 4.1: Classification of semantics roles of arrow symbols.
First, the semantic roles are dichotomized into those that require only one
component and those that require at least two components. In the group with a single
requisite component, the arrow symbol is attached to a component and specifies a
directional property of this component (Section 2.2.1). This semantic role is called66

orientation. Although an arrow symbol for orientation may refer to more than one
component, only one of them is essential for assigning the semantic role to the arrowsymbol, while the others are optional (Section 4.2.1).
The group with two or more requisite components is further dichotomized into
behavioral description and others, depending on whether a transition of certain subject isprojected upon the arrow symbol. Spatial movement is a spatial transition and continuous
existence is a temporal transition. Therefore, illustrations of spatial movement (Section
2.2.2) and continuous existence (Section 2.2.4) are categorized into behavioral
description. In addition, a transition may yield interactions with other components on theroute (Section 2.2.3) and a transition may yield the change of the subject (Section 2.2.5).
The shape of an arrow symbol is often meaningful for this category, as it may capture theroute of the transition.
Arrow symbols with the remaining semantic roles connect multiple
components without implying a transition. Among those semantic roles labeling (Section
2.2.6) is an exception, because the connected components refer to the same single subject,while the other semantic roles always associate different subjects. Thus, labeling isdistinguished from the other semantic roles and referred to as an independent class, called
annotation.
The remaining semantic roles are categorized into a single class, calledassociation, since the arrow symbols associate different subjects. Conventionally one
arrow symbol associates two subjects, due to its linearity. Such association usuallyindicates the presence of an asymmetric relation between these two subjects. These67

relations do not include interactions, since an interaction assumes a transition of one
entity approaching another and, therefore, the illustration of interaction is categorized
into behavioral description rather than association.

4.2. Basic formats of Individual Structures
When an arrow symbol is used for a certain semantic role, its individual structure
satisfies one of the formats specific to the semantic role. Among such formats, thissection identifies basic formats, which refer to the minimum set of components that arenecessary for establishing the semantic roles of arrow symbols.

4.2.1. Basic Formats for Orientation

An arrow symbol for orientation refers to a single component (subject), specifying its
directional property. The arrow symbol points to, originates from, or passes through or by
the subject, typically implying that the directional property is related to an outgoingaction, a passing action, or an incoming action, respectively (Figure 4.2). Accordingly,
orientation corresponds to the three basic formats in Figure 4.3.

(a)

(b)

(c)

Figure 4.2: Diagrams with arrow symbols for orientation, specifying (a) the moving
direction of a vehicle, (b) a wind direction of a point in Maine, and (c) the directionof an external force by which a board cracks.
68

s
s

s

(a)

(b)

(c)

Figure 4.3: Three basic formats of individual structures that correspond toorientation (s: subject).
The subject must be a primary component, which represents an independent
concept. Among the four subcategories of primary components (i.e., location, moment,
object, and event), the subject cannot be a moment, since the moment, which is azero-dimensional concept, does not have a directional property. On the other hand, the1-arrow diagrams in Figure 4.2a-c, whose subjects are a vehicle, a point in Maine, and acracking event, indicate that the subject may be an object, a location, and an event,respectively. Consequently, when an arrow symbol is used for orientation, its individual
structure must satisfy one of the prescriptive patterns in Table 4.1; that is, there must be
at least one combination of the tail, body, and head components such that theircomponent types correspond to one of the nine prescriptive patterns in Table 4.1. For
instance, the patterns (PCL, –, –), (PCL, MC, –) and (PCLMC, MC, –) satisfy theprescriptive pattern (PCL,,). The blanks in prescriptive patterns mean that thecorresponding component slots may be empty or filled by optional components (Section
4.3.2). In Table 4.1, (PCL|O|E, , ), which represents (PCL, , ), (PCO, , ), and (PCE, , ),is counted as three patterns. Table 4.1, therefore, indicates that there are 3 × 3 = 9
prescriptive patterns that correspond to orientation.

69

Table 4.1: Nine prescriptive patterns that individual structures must satisfy whenarrow symbols are used for orientation (s: subject, PCL|O|E: PCL, PCO, or PCE).
Basic Format Prescriptive Patterns(s, , )

(PCL|O|E, , )( , s, )( , PCL|O|E, )( , , s)( , , PCL|O|E)

4.2.2. Basic Formats for Behavioral Description

An arrow symbol for behavioral description illustrates the transition of a single subject3.
A spatial transition refers to the subject’s movement, while a temporal transition refers to
the subject’s persistence over a temporal period. The transition may refer to a set of
positions in space and time. If a component representing a spatial position is located in
the tail, body, and head slot, this component specifies the origin, intermediate points, anddestination of the transition, respectively. Similarly, if a component representing the
temporal position is located in the tail, body, and head slot, this component specifies thestart time, intermediate times, and end time of the transition, respectively. The transition
may also refer to entities on the route, with which the subject interacts. If such an entity isdrawn in the arrow symbol’s tail, body, and head slots, the interaction takes place before,
during, and after the transition, respectively.

3

An arrow symbol may illustrate the transition of multiple entities (e.g., people in a queue in Figure 3.9d),but these entities are regarded as a single group subject, whose members have the common roles in theillustrated scenario.

70

When an arrow symbol is used for behavioral description, its individual
structure must satisfy the following four constraints:•

The subject (s) is located in any component slot, except when the diagram highlights
the change of the subject by illustrating the subject before and after the transition in
the tail and head slots, respectively.

•

In addition to the subject, the arrow symbol refers at least one component
representing the transition-related position or the entity involved in the transition;otherwise the arrow symbol refers to the subject alone and, accordingly, the arrowsymbol specifies a directional property rather than illustrates a transition.

•

Each involved entity (e) cannot coexist at the same place with the subject; otherwise
the diagram no longer implies that the interaction between the subject and e istriggering or triggered by the subject’s transition. In addition, it is assumed that morethan one involved entity cannot coexist at the same place 4 . Accordingly, eachinvolved entity cannot be located in the tail or head slot that already contains the
subject or another involved entity.

•

Each transition-related position (p) cannot coexist at the same location with thesubject and the involved entities; otherwise such a component specifying a position
is regarded an adjective component (Section 4.3.1), which is attached to the nearby

4

A set of entities involved in the transition, located at the same place, are treated as a single group entity,

whose members share the same role in the illustrated scenario.

71

component (i.e., a subject or an involved entity) and specifies its spatial or temporal
position. Accordingly, each transition-related position cannot be located in the tail orhead slot that already contains the subject, involved entity, or anothertransition-related position.
•

The body slot, which has length, may contain the subject, one or more involved
entities, and one or more transition-related positions at the same time.

These five constraints determine the fifteen basic formats under which an arrow symbol
is used for behavioral description (Table 4.2).

Table 4.2: Fifteen basic formats of individual structures that correspond tobehavioral description (s: subject, e: entity involved in the transition, p: position
related to the transition, e|p: either e or p, [e|p]n: one or more e|p).
Basic Formats
in HeadSlotin TailSlot
SingleSubject[e|p]nse|ps[e|p]ne|pss[e|p]n

e|p

e|p

s

e|p

e|p

e|p

s

[e|p]ne|p

Two Subjectse|p[e|p]n

s

e|p

e|p

s

s

s

[e|p]ne|pss[e|p]nss

in BodySlot[e|p]n

s

s

72

s

[e|p]nThe subject s must be either an object or an event, considering that objects andevents may actively change their spatial and temporal positions, but locations andmoments do not. Each involved entity e must be an object, an event, or a location,
considering that it is possible to interact with objects, events, and locations, but not with
moments. Each transition-related position is obviously a location or a moment. As aconsequence, when an arrow symbol is used for behavioral description, its individual
structure must satisfy one of the prescriptive patterns in Table 4.3.

Two
Subjects

in Body Slot

Single Subject

in Tail Slotin Head Slot

Table 4.3: 104 prescriptive patterns that individual structures must satisfy whenarrow symbols are used for behavioral description (s: subject, e: entity involved in
the transition, p: position related to the transition).
FormatPrescriptive Patterns(s, [e|p]n, e|p)

(PCO|E, [PCL|M|O|E]n, PCL|M|O|E)(s, [e|p]n, )(PCO|E, [PCL|M|O|E]n, )(s, , e|p)

(PCO|E, , PCL|M|O|E)(e|p, [e|p]n, s)(PCL|M|O|E [PCL|M|O|E]n, PCO|E)( , [e|p]n, s)( , [PCL|M|O|E]n, PCO|E)(e|p, , s)

(PCL|M|O|E, , PCO|E)(e|p, s[e|p]n, e|p)

(PCL|M|O|E, PCO|E[PCL|M|O|E]n, PCL|M|O|E)( , s[e|p]n, )( , PCO|E[PCL|M|O|E]n, )(e|p, s, e|p)

(PCL|M|O|E, PCO|E, PCL|M|O|E)(e|p, s[e|p]n, )(PCL|M|O|E, PCO|E[PCL|M|O|E]n, )(e|p, s, )(PCL|M|O|E, PCO|E, )( , s[e|p]n, e|p)

( , PCO|E[PCL|M|O|E]n, PCL|M|O|E)( , s, e|p)

( , PCO|E, PCL|M|O|E)(s, [e|p]n, s)(PCO|E, [PCL|M|O|E]n, PCO|E)(s, , s)

(PCO|E, , PCO|E)73

4.2.3. Basic Formats for Annotation

An arrow symbol for annotation attaches a label to a subject, thereby specifying such aproperty of the subject as name, type, status, spatial position, and temporal position(Figure 4.4). Conventionally, annotation corresponds to only one format of individual
structures in Figure 4.5, where an arrow symbol originates from the label and points tothe subject, implying an asymmetric relation that the label is assigned to the subject.
Mr. K

airporttraveler
9:00pmgoing to Boston

Figure 4.4: An arrow diagram with five arrow symbols, all used for annotation.

slFigure 4.5: Only one basic format of the individual structures that correspond toannotation (l: label, s: subject).
The label must be a modifying component, since it modifies the subject, while
the subject must be a primary component. Consequently, when an arrow symbol is used
for annotation, its individual structure must satisfy one of the four prescriptive patterns inTable 4.4.

Table 4.4: Four prescriptive patterns that individual structures must satisfy whenarrow symbols are used for annotation (l: label, s: subject).
Basic Format

Prescriptive Patterns(l, , s)(MC, , PCL|M|O|E)74

4.2.4. Basic Formats for Association

An arrow symbol for association associates two different subjects, indicating thepresence of an asymmetric relation between them. These subjects are placed in the tailslot and the head slot of the arrow symbols (Figure 4.6), such that these two subjects lookequally emphasized while their order is highlighted.

s1

s2

Figure 4.6: Only one basic format of the individual structures that correspond toassociation (s1, s2: associated subjects)
The asymmetric relation that holds between the two subjects is called theeffective relation. For instance, in the arrow diagram “El Niño

Fish Catch↓,” a typicaleffective relation between “El Niño” and “Fish Catch↓” is causality. Such effective
relation may be specified by an adverbial component in the body slot (Section 4.3.2), or
described in the caption or the legend; otherwise, the diagram reader has to infer anappropriate effective relation from the context or the reader’s knowledge about theplausible relations between the subjects. The effective relation may provide an ordering
rationale, which naturally determines the order of the associated subjects; otherwise, theorder is arbitrarily determined (Table 4.5).

75

Table 4.5: Associated subjects and effective relations between them, which may
naturally determine the order of the associated subjects.
Associated Subjects

Effective
Relation

Ordering
Rationale

Representation

El Niño, Fish Catch ↓Causality

logical order

El Niño Fish Catch↓Plan, Do, Seework process

temporal order

Plan Do See

Niagara Falls,
Lake Ontario

water flow

spatial order(high to low)

Niagara Falls Lake Ontario

Maine, New England

geographicalattribution

spatial order(part to whole)

Maine New England

Lobster, Maine

local product-

Lobster Maine
Maine Lobster

Each subject must be a primary component, since it represents an independent
concept. Any subcategory of a primary component (i.e., a location, a moment, an object
or an event) can be the subject, as long as an appropriate effective relation can be foundbetween the pair of subjects. Accordingly, when an arrow symbol is used for association,
its individual structure must satisfy one of the 4 × 4 = 16 prescriptive patterns in Table
4.6.

Table 4.6: Sixteen prescriptive patterns that individual structures must satisfy whenarrow symbols are used for association (s1, s2: associated subjects).
Basic Format

Prescriptive Pattern(s1, , s2)(PCL|M|O|E, , PCL|M|O|E)76

4.3. Rules for Optional Components
Individual structures may have optional components, which enrich the diagram’s
semantics, but are not requested by the previous basic formats. This section distinguishes
two types of such optional components—adjective components and adverbial
components—and identifies a set of rules for adding such optional components to theindividual structures.

4.3.1. Adjective Components

Adjective components correspond to adjectives in natural language. Like an adjective thatmodifies a single noun, an adjective component modifies a component nearby, andspecifies a property of this component such as name, spatial position, and temporal
position (Figure 4.7). Naturally, each adjective component is a modifier component,
which coexists with the modified component in the same component slot.

Mr. K

Maine

Figure 4.7: A 1-arrow diagram with two adjective components, “Mr. K” and“Maine,” each of which specifies the name of an entity illustrated nearby.

774.3.2. Adverbial Components

Adverbial components correspond to adverbial phrases in natural language. Similar to an
adverbial phrase that modifies a verb, an adverbial component modifies the semantic roleof an arrow symbol. Four different scenarios arise:•

When an arrow symbol is used for orientation, the adverbial components provide
information about the directional property specified by the arrow symbol, such as
type, name, and scale (Table 4.7a1-a3).

•

When an arrow symbol is used for behavioral description, the adverbial components
provide information about the illustrated transition, such as type of the transition andaccompanying interactions, scale, cause of the transition, overall spatial or temporal
position where and when the transition and accompanying interactions take place(Table 4.7b1-b4).

•

When an arrow symbols is used for annotation, the arrow symbol does not refer toadverbial components, because they are simply unnecessary.

•

When an arrow symbol is used for association, the adverbial components provide
information about the illustrated relation, such as effective relation (Section 4.2.4)
and overall spatial or temporal position where and when the relation is effective(Table 4.7c1-c3).

Adverbial components are placed in the body slot, normally in its center, implying thatthe adverbial component is assigned to the entire arrow symbol. Naturally, each adverbial
component is a modifier component.
78

Table 4.7: Information provided by adverbial components.

orientation

Semantic
Role

Provided Information(a1) property type(a2) property nameassociation

behavioral description

installheat(a3) property scale
10 mph(b1) type of the transition andaccompanying interactions

liquid

50 kgm/s2

f1

external force(b2) transition scale
noon

gas
(b4) overall spatial / temporal position
where and when the transition andaccompanying interactions take place(b3) cause of transition

2006
Germany

belong toW-cup
tourist ↑(c2) overall spatial / temporal position
where and when the relation is effective(c1) effective relation

4.4. Interpretations of Arrow Symbols in Simple 1-Arrow Diagrams
The combination of the prescriptive patterns of individual structures (Section 4.2) and theoptional components (Section 4.3) determines the patterns of the individual structuresthat correspond to each class of semantic roles. However, the number of such patterns istheoretically countless, since the individual structures may have an arbitrary number of
optional components. To focus the discussion, this section considers only simple 1-arrow
diagrams, which contain at most one component in each component slot. The individual79structure of a simple arrow diagram, called the simple individual structure, distinguishes
63 = 216 patterns, since each of the three component slots may contain one out of six
choices: an object, an event, a location, a moment, a modifier component, or nothing.
Consequently, for each class of semantic roles, all corresponding patterns of simple
individual structures can be determined from the 216 patterns.

4.4.1. Patterns of Simple 1-Arrow Diagrams for Orientation

When an arrow symbol is used for orientation, its simple individual structure satisfies
one of the three basic formats in Figure 4.3 and may have an adverbial component in the
body slot if empty (Section 4.3.2). Thus, orientation corresponds to five formats in Table
4.8. In each format, the subject must be a location, an object, or an event (Section 4.2.1),
while the adverbial component, if it exists, is a modifier component (Section 4.3.2).
Consequently, 5 × 3 = 15 patterns of simple individual structures in Table 4.8 correspondto orientation.

Table 4.8: Five formats and fifteen patterns of simple individual structures that
correspond to orientation (s: subject, cav: adverbial component)
FormatPatterns(s, -, -)(PCL|O|E, -, -)(s, cav, -)(PCL|O|E, MC, -)(- , s, -)(-,PCL|O|E, -)(-, -, s)(-, -, PCL|O|E)(-, cav, s)(-, MC, PCL|O|E)
80

4.4.2. Patterns of Simple 1-Arrow Diagrams for Behavioral Description

When an arrow symbol is used for behavioral description, its individual structure
satisfies one of the fifteen basic formats in Table 4.2 and may have one adverbial
component in the body slot if empty (Section 4.3.2). Thus, behavioral description
corresponds to 18 formats in Table 4.9. In each format, the subject must be an object oran event, each entity involved in the transition must be an object, an event, or a location,and each position related to the transition must be a location or a moment (Section 4.2.2),
while the adverbial component, if it exists, is a modifier component. (Section 4.3.2).
Consequently, 104 patterns of simple individual structures in Table 4.8 correspond tobehavioral description.

81

Table 4.9: Eighteen formats and 104 patterns of simple individual structures that
correspond to behavioral description (s: subject, e: entity involved in the transition,
p: position related to the transition). The patterns may overlap between the rows.
Formatin Tail Slot

Single Subject

in Head SlotnPatterns(s, [e|p] , e|p)

(PCO|E, PCL|M|O|E, PCL|M|O|E)(s, [e|p]n, -)(PCO|E, PCL|M|O|E, -)(s, -, e|p)

(PCO|E, -, PCL|M|O|E)(s, cav, e|p)

(PCO|E, MC, PCL|M|O|E)(e|p, [e|p]n, s)(PCL|M|O|E, PCL|M|O|E, PCO|E)(-,[e|p]n, s)(-, PCL|M|O|E, PCO|E)(e|p, -, s)(PCL|M|O|E, -, PCO|E)(e|p, cav, s)(PCL|M|O|E, MC, PCO|E)(e|p, s[e|p]n, e|p)-Two
Subjects

in Body Slotn(-, s[e|p] , -)-(e|p, s, e|p)

(PCL|M|O|E, PCO|E, PCL|M|O|E)(e|p, s[e|p]n, -)-(e|p, s, -)(PCL|M|O|E, PCO|E, -)(-, s[e|p]n, e|p)-(-, s, e|p)(-, PCO|E, PCL|M|O|E)(s, [e|p]n, s)(PCO|E, PCL|M|O|E, PCO|E)(s, -, s)(PCO|E, -, PCO|E)(s, cav, s)(PCO|E, MC, PCO|E)

4.4.3. Patterns of Simple 1-Arrow Diagrams for Annotation

When an arrow symbol is used for annotation, its individual structure satisfies the format
in Figure 4.5 and may have no adverbial component (Section 4.3.2). In this format, thelabel must be a modifier component, while the subject is any category of primary82

component (Section 4.2.3). Consequently, four patterns of simple individual structures inTable 4.10 correspond to annotation.

Table 4.10: One format and four patterns of simple individual structures that
correspond to annotation (l: label, s: subject).
FormatPatterns(l, -, s)(MC, -, PCL|M|O|E)

4.4.4. Patterns of Simple 1-Arrow Diagrams for Association

When an arrow symbol is used for association, its individual structure satisfies one of thesixteen formats in Figure 4.6 and may have an adverbial component in the body slot, if
empty (Section 4.3.2). Thus, two formats correspond to association. In each format, theassociated subjects are any type of primary components (Section 4.2.4), while theadverbial component, if it exists, is a modifier component (Section 4.3.2). Consequently,
16 × 2 = 32 patterns of simple individual structures correspond to association.

Table 4.11: Two formats and 32 patterns of simple individual structures that
correspond to association (s1, s2: associated subjects, cav: adverbial component).
FormatPatterns(s1, , s2)(PCL|M|O|E, -, PCL|M|O|E)(s1, cav, s2)(PCL|M|O|E, MC, PCL|M|O|E)83

4.4.5. Comparison of Patterns

Sections 4.4.1-4.4.4 identified all patterns of simple individual structure that correspondto the four classes of semantic roles. Figure 4.8 summarizes the number of patterns that
correspond to each class of semantic roles. Among the 216 patterns of simple individual
structures, 15 + 4 + 8 + 80 = 107 patterns correspond to exactly one class, 24 patterns
correspond to two classes, and the remaining 85 patterns correspond to no class.
Orientation

Association
15

8
24

Annotation

480

Behavioral Description

85

Figure 4.8: The number of patterns of simple individual structures that correspond toeach class of semantic roles.
This result indicates:•

An arrow symbol, whose individual structure has one of the 107 patterns, is uniquelyinterpreted within the four classes of semantic roles (Figure 4.9a).

•

An arrow symbol, whose individual structure has one of the 24 patterns, yields
multiple interpretations: behavioral description and annotation (Figure 4.9b)•

An arrow symbol has no interpretation within the four classes of semantic roles if its
individual structure has one of the remaining 83 patterns (Figure 4.9).

84

Figure 4.8 also indicates that arrow symbols for orientation and annotation are always
uniquely interpreted, while arrow symbols for behavioral description and association
may be ambiguous.

New York City

SeattleBoston(a)

You are
here

(b)

(c)

Figure 4.9: Simple 1-arrow diagrams whose individual structures have the patterns(a) (PCL, PCO, PCL), (b) (MC, –, PCO), (c) (MC, PCO, PCL), which corresponds toone, two, and no classes of semantic roles, respectively.

4.5. Interpretation of Arrow Symbols in General 1-Arrow Diagrams
This section develops an algorithm that deduces all classes of semantic roles that
correspond to the given individual structure. This algorithm enables computers to derive
the possible interpretations of an arrow symbol if its structural information is available.
The target is expanded to general individual structures, which may have more than one
component in each component slot.
The individual structure of an arrow symbol a, sind (a ) , corresponds to asemantic role σ i if and only if sind (a ) satisfies one of σ i ’s prescriptive patterns (Tables
4.1, 4.3, 4.4, and 4.6) and every extra component in sind (a ) is considered as either anadverbial component or an adjective component. The individual structure sind (a ) was
denoted by a 3-tuple(C (a ), C (a ), C (a )) , where
tail

body

head

Ctail (a ) ,C body (a ) ,and C head (a ) be the respective sets of all components in a’s tail, body, and head slot
85

(Section 3.2). Let σ 1 - σ 4 are the four classes of semantic roles (orientation, behavioral()

description, annotation, and association), respectively, and C tail ij , Cbody ij , Chead ij is thejth prescriptive pattern that correspond to the class σ i (Tables 4.1, 4.3, 4.4, and 4.6).
The number of elements in C tail ij and Chead ij are one or zero, while that of Cbody ij may
be two or more. Let the function type(c ) give the type of a component c. With this setting,all classes of semantic roles that correspond to sind (a ) are deduced computationally by
the following algorithm:
1:

results  {}2:

(T , B, H )  ({type(c ) c ∈ C tail (a )}, {type(c ) c ∈ Cbody (a )}, {type(c ) c ∈ Chead (a )})3: For every semantic class σi(

4:For σi’s every template C tail ij , C body , C head ij

5:

If C tail ij ∈ T ∧ C body ∈ B ∧ C head ij ∈ H
ij

ij

(
) (
) (
(T , B , H )  (T \ C , B \ C(T , B , H )  (T , B , H )

6:
7:

+

+

*

*

+

tail ij+*+

body ij)) then, H \ Chead ij

)

+

8:

IF σi <> “ANNOTATION” then remove all M from B

9:

S = T * ∪ B* ∪ H *10:

If ¬ {PL ∈ S } ∨ {PM ∈ S } ∨ {PO ∈ S } ∨ {PE ∈ S }[{(] and _) (

 M ∈ T * ∧ Ctail ij = φ¬)} ∨ {(M ∈ B ) ∧ (C
∨ {(M ∈ H ) ∧ (C=φhead ij=φ*

add σi to results
End If11:

body ij*

Next

12: Next

86*)}∨ then _)} (T , B, H ) is sind (a ) ’s pattern (line 2). (T + , B + , H + ) is the component type of all extra
components in s ind (a ) (line 6), each of which must be either an adverbial or adjective
component if the prescriptive pattern currently under inspection is valid. (T * , B * , H * ) is
the type of the components that must be adjective components (lines7-8). Since theadjective components must be modifier components (MC), T*, B*, and H* cannot be PCL,
PCM, PCO, PCE (line 10). In addition, if T*, B*, and H* contain MC, there must be at least

one element in C tail ij , Cbody ij , and Chead ij , respectively, since any adjective component
needs an entity to be attached with (line 10).

4.6. Summary
This chapter developed an algorithm for deriving the interpretations of the arrow symbolin 1-arrow diagrams. The semantic roles of arrow symbols are classified into four classes:
orientation, behavioral description, annotation, and association. For each class ofsemantic roles, a set of prescriptive patterns of individual structures, as well as rules foradding optional components are identified. The combination of these prescriptive patterns
and optional components determine all patterns of individual structures that correspond toeach class of semantic roles. Accordingly, it becomes possible to deduce all classes ofsemantic roles that may correspond to a given individual structure, which is essentially toderive the interpretation of arrow symbols from the four choices. This chapter developed87

an algorithm for such deduction of interpretations. The validity of this algorithm isevaluated in Chapter 6.

88Chapter 5
INTERPRETATIONS OF ARROW SYMBOLS IN MULTI-ARROWDIAGRAMS

A remarkable property of multi-arrow diagrams is that arrow symbols are spatiallyarranged in a meaningful way. Due to this property, a multi-arrow diagram capturesricher semantics than a set of 1-arrow diagrams whose synthesis forms the same
multi-arrow diagram (Figure 5.1). This chapter, therefore, studies the meanings of spatial
arrangements of arrow symbols and then exploits such meanings for the interpretation ofarrow symbols in multi-arrow diagrams.

+
Figure 5.1: Synthesis of two 1-arrow diagrams yields a multi-arrow diagram, which
captures additional semantics: the pack of wolves splits into two packs.
According to the previous observations, arrow symbols form a meaningfularrangement when they jointly capture certain semantics (Section 1.1) or when arrow
diagrams are nested (Section 3.4.2). Thus, after introducing basic terminology (Section5.1), this chapter explores several cases where arrow symbols jointly capture semantics,
essentially studying the semantic roles assigned to groups of arrow symbols (Section 5.2).
Then, Section 5.3 discusses the meanings and structural characteristics of nested arrow
diagrams. Based on the correspondence between the spatial arrangement and thesemantics found in Sections 5.2 and 5.3, Section 5.4 develops a sequential method for89

deducing semantic roles of both individual arrow symbols and arrow symbol groups in a
multi-arrow diagram. Finally, Section 5.5 demonstrates with two examples how thismethod works.

5.1. Terminology
The semantic roles of arrow symbols are assigned not only to individual arrow symbols,
but also to groups of arrow symbols. The semantic role assigned to an individual arrowsymbol is called the individual role, while the semantic role assigned to a group of arrowsymbols is called the group roles.
In a multi-arrow diagram, each arrow symbol may individually capture certain
semantics together with its components, just like the arrow symbol in a 1-arrow diagram
does. The semantics captured by an arrow symbol a and the components referred by a iscalled a’s individual semantics. The individual semantics of an arrow symbol a is tightly
related to a’s individual role, since the individual role determines the type of theindividual semantics. For instance, if a’s individual role is association, then a and its
components capture a certain relation between two of these components.
Similarly, if an arrow symbol group A has a group role, the arrow symbols in A
and their components capture certain semantics, which is called A’s group semantics.

905.2. Group Roles of Arrow Symbols
This section introduce several kinds of semantic roles that are assigned to groups ofarrow symbols. Each group role corresponds to specific spatial arrangements of arrowsymbols, which are later exploited for the interpretation of arrow symbols (Section 5.4).

5.2.1. Indicating Element-Sharing

When multiple arrow symbols refer to the same component c, the individual semantics
associated with these arrow symbols may be related to each other in the sense that thesesemantics refer to the same elements represented by c. For example, in Figure 5.2a thepair of the individual semantics—the traveler is Mr. K and the traveler goes to
Hawaii—are mutually related in the sense that they refer to the same traveler. In addition,a set of individual semantics that shares an element may be mutually-exclusive (i.e., only
one of these individual semantics can be true) or synchronized (i.e., whenever one is true
all others are also true). For example, in Figure 5.2b the pair of the individual
semantics—an exam results in pass and an exam results in failure—shares the same
exam and the group members are mutually-exclusive (i.e., an exam results in pass or fail,but not both). On the other hand, in Figure 5.2c the pair of the individual semantics—acell phone sends a query to a database and the database returns a result to the cell
phone—are synchronized (i.e., whenever the cell phone sends a query the database
returns a result). Background knowledge that two events typically occur simultaneously(e.g., send and return) or never occur together (e.g., pass and fail) is helpful for judging
91

whether the element-sharing between the individual semantics further implies theirmutually-exclusiveness or synchronization. Empirically, the symmetry of the 9-link
matrix (Section 3.3) is also useful, since arrow symbols are typically arranged
symmetrically when illustrating the mutually-exclusive or synchronized scenarios(Figures 5.2b-c).
Mr. K

Hawaii

Exam

Pass

query

Fail

resultφ φ φ 
φ φ φ  I φ φ I φ φ 
φ φ φ φ φ φ 

φ φ I φ φ φ  I φ φ 

(a)

(b)

(c)

DB

Figure 5.2: Three 2-arrow diagrams capturing pairs of element-sharing individual
semantics. In addition, (b) and (c) imply that the pairs are mutually exclusive andsynchronized, respectively.

5.2.2. Formulating a Branching Process

A branching process is a temporal process in which a precedent element p is followed byonly one of multiple subsequent elements{s1 ,L, s n } . The branching process isconventionally represented by a multi-arrow diagram in which one arrow symbol (a*)
directly connects p to s * ∈ {s1 ,L , s n } , while the other arrow symbols connect a*’s bodyto s i ∈ {s1 ,L, s n } \ s * (Figure 5.3a). Although only a* originates from p, every arrowsymbol conceptually refers to p as its tail component. This spatial arrangement may
imply that p is normally followed by s * , while the other subsequent elements refer to
exceptional scenarios. For instance, in Figure 5.3a, the operation “Search the address
92

book for the given name” is normally followed by the operation “Show the map aroundthe found address,” while “Show an error message” occurs only in an exceptional

scenario.
A branching process is essentially a set of temporal orders with a common
precedent element, which are mutually-exclusive. Consequently, the branching process
can be also captured by a set of arrow symbols sharing a tail component (Figure 5.3b).
This alternative spatial arrangement, however, cannot guarantee that the two subsequentelements are mutually exclusive.
Search the address bookfor the given namenot foundSearch the address bookfor the given nameShow an error
message

not found

Show the map aroundthe found addressShow the map aroundthe found address

(a)

(b)

Show an error
message

Figure 5.3: The same branching processes are captured by (a) a pair of arrowsymbols with a direct body-tail link and (b) a pair of arrow symbols with an indirect
tail-tail link.

5.2.3. Indicating Interactions during Transition

If two arrow symbols are used for behavioral description and they have a direct link (i.e.,they intersect with each other), their intersections may indicate that the two subjects,
associated with these arrow symbols, are located at the same position at the same time,
having a certain interaction with each other. Since the tail, body, and head of an arrowsymbol correspond to the origin, intermediate path, and destination of the subject’s

93spatial transition, respectively, the nine types of direct links (Section 3.3) may naturallyindicate the following interactions:•

A direct tail-tail link may indicate that the subjects get separated, possibly as a resultof a precedent event (Figure 5.4a). This interaction is called separation.

•

A direct head-head link may indicate that the subjects get together, possibly leading
to a certain reaction (Figure 5.4b). This interaction is called meeting.

•A direct body-body link may indicate that the two subjects have a contact with eachother during their transitions (Figure 5.4c). This interaction is called contact.

•

A direct head-tail/tail-head link may indicate that the arrival of one subject leads tothe departure of another subject or, if both arrow symbols refer to the same subject,
the subject drops by the location at the link (Figure 5.4d). These two interactions arecalled push-out and drop-by, respectively.

•

A direct body-tail/tail-body link may indicate that a certain event that involves a
subject already in transition, such as splitting, leads to the departure of anothersubject (Figure 5.4e). This interaction is called diversion.

•

A direct head-body/body-head link may indicate that one subject finishes its
transition when the subject encounters another subject and possibly has a certain
reaction, such as merger (Figure 5.4f). This interaction is called confluence.

Multiple direct links between two arrow symbols indicate a combination of theseinteractions.

94

(a)

(b)
Main Gate
Temporary Gate

(d)

(e)

(c)

YogurtMilk(f)

Figure 5.4: Six 2-arrow diagrams with different types of direct links between arrowsymbols, which indicate different interactions between the subjects: (a) separation,(b) meeting, (c) contact, (d) drop-by, (e) diversion, and (f) confluence.

5.2.4. Illustrating an Extent Change

A set of arrow symbols that originate from the same component and point in various
directions may jointly capture the diffusion or expansion of this component (Figure 5.5).
Conversely, a set of arrow symbols that point to the same component from various
directions may jointly capture the concentration or shrinking of this component.
Diffusion and expansion are different concepts, although they correspond to the sameformats. Diffusion refers to the mass of spatial movements of subsets or copies of thesame subject (Figure 5.5a). Naturally, the common component must be a collective or
replicable entity. On the other hand, expansion refers to a subject’s change with regard toits shape and, therefore, the common component must be a transformable entity (Figure5.5b). Similarly, concentration and shrinking are not equivalent, although theycorrespond to the identical formats.

95

(a)

(b)

Figure 5.5: Two multi-arrow diagrams in which a group of arrow symbols is used forillustrating (a) the diffusion of balloons and (b) the expansion of a balloon.

5.2.5. Specifying an Interval

A pair of arrow symbols, which faces away from each other, may be used for illustrating
an interval (Figure 5.6a). In this case, the two arrow symbols originate from the samelabel that represents something to which the interval is assigned (Figure 5.6a), intervalname (Figure 5.6b), or the scale of the interval. Bi-directional arrow symbols are used forthe same purpose (Figure 5.6a). In addition, if the interval is too narrow to put two arrowsymbols and a label between them, arrow symbols are arranged to sandwich the intervalfrom both sides (Figure 5.6b).

(a)

(b)

Figure 5.6: Two multi-arrow diagrams in which a pair of reversely directed arrowsymbols is used for specifying the interval of (a) wavelength of electric waves
assigned to televisions and radios and (b) a pulse (1997).
965.3. Nesting of Arrow Diagrams
The spatial arrangement of arrow symbols is exploited not only for organizing a group ofarrow symbols, but also for nesting arrow diagrams. In a nested arrow diagram, somearrow symbols refer to its sub-diagrams, each of which forms an arrow diagram by itself(Figure 5.7). Such sub-diagrams are called the subordinate arrow diagram in the nested
arrow diagrams.
Just like an icon or a text label, a subordinate arrow diagram serves as acomponent for the arrow symbol that refers to this subordinate arrow diagram. Thus, themiddle arrow symbol in Figure 5.7a, for instance, organizes an individual structure(" El Nin~o",−, " Fish catch ↓") . Since the subordinate arrow diagram “ Fish catch ↓ ”
captures an event where the fish catch decreases, the individual structure has a pattern of(PCO, –, PCE). This pattern corresponds to behavioral description and association(Section 4.4). Thus, the middle arrow symbol may capture the (spatial) transition of “ElNiño” to get involved into “ Fish catch ↓ ” or associates “El Niño” and “ Fish catch ↓ .” In

this way, an arrow diagram may capture a complicated scenario by nesting the diagram.
Industrial Revolution

El Niño

a3

Fish catch

a4 Urban
Rural
Area population Area

(a)

(b)

Figure 5.7: (a) The central arrow symbol points to “Fish catch,” but conceptuallyrefers to the subordinate arrow diagram “ Fish catch ↓ ”; and (b) the central arrowsymbol points to the horizontal arrow symbol, but conceptually refers to thesubordinate arrow diagram “ Rural area → Urban area .”population97

If a multi-arrow diagram is nested, the arrow symbol a*, which refers to a
subordinate arrow diagram dsub, either originates from or points to the center of dsub, suchthat the diagram reader would notice that a* refers to entire dsub instead of a part of dsub.
Accordingly, a* apparently has an indirect link (Figure 5.7a) or a direct link (Figure 5.7b)with the arrow symbol in dsub.

5.4. Interpretation of Arrow Symbols in Multi-Arrow Diagrams
In a multi-arrow diagram, interpreting arrow symbols means deducing both semanticroles of individual arrow symbols (i.e., individual roles) and those of arrow symbolgroups (i.e., group roles). Different orders of these two deduction processes yield thefollowing two approaches:•in the bottom-up approach the deduction of individual roles proceeds the deductionof group roles, and•in the top-down approach the deduction of individual roles follows the deduction ofgroup roles.

Some group roles presume that arrow symbols in the group also have a specificindividual role (Table 5.1). Thus, it is straightforward to deduce individual roles before
deducing group roles (i.e., the bottom-up approach). The bottom-up approach is, however,inefficient in the diagram where some arrow symbols refer to components indirectly andsuch indirect reference becomes evident after the deduction of group roles. For instance,in Figure 5.3a, the horizontal arrow symbol indirectly refers to the process “Search the98address book for the given name.” This indirect reference is detected after figuring outthat the arrow symbols jointly formulate a branching process. In the bottom-up approach
the individual roles of arrow symbols are deduced without the information about suchindirect reference and, accordingly, may yield incorrect interpretations at first. Since suchincorrect interpretations must be corrected afterwards, the bottom-up approach becomesinefficient.

Table 5.1: Individual roles of arrow symbols presumed by their group role.
Group Role

Assumed Individual Roles

formulating a branching process

association (illustrating a temporal order)

indicating interactions of subjects
during their transitions

behavioral description

illustrating diffusion/ expansion /concentration / shrinking

behavioral description

The top-down process avoids such inefficient interpretation process. A
top-down approach is possible by deducing the group roles tentatively, assuming ahypothetical individual role on each arrow symbol, if necessary. The actual interpretation
process proceeds as follows:
Step 1: Subordinate arrow diagrams (Section 5.3) are detected.
Step 2: The group roles of arrow symbols, except those in the subordinate diagrams, arededuced tentatively, assuming that each arrow symbol has a specific individual
role, if necessary.
99

Step 3: Individual role of each arrow symbol is deduced, considering the indirectreferences of arrow symbols specified by the tentative group roles.
Step 4: The tentative group roles are rejected if the individual roles assumed in Step 2
are inconsistent with the individual roles deduced in Step 3.
The following four sections explain each of these four steps.

5.4.1. Detection of Subordinate Arrow Diagrams

Let a given multi-arrow diagram be d. In Step 1, the candidates for d’s subordinate arrow
diagrams are detected as d’s sub-diagrams, which satisfy the following conditions:
C1: The sub-diagram consists of a subset of the arrow symbols in d and all components
to which these arrow symbols refer, thereby forming an arrow diagram by itself.
C2: The sub-diagram is connected (i.e., it cannot be divided into two sub-diagrams, eachof which satisfies C1).
C3: The sub-diagram has a valid interpretation as an arrow diagram.
C4: One of d’s arrow symbols, except those in the sub-diagram, either points to or
originates from the sub-diagram’s center.

5.4.2. Tentative Deduction of Group Roles

In Step 2, the group roles of arrow symbols are tentatively deduced. The deduction is
primarily based on the spatial arrangement of arrow symbols, since such arrangement100contributes to the group organizations of arrow symbols (Section 5.2). Table 5.2 shows
the spatial arrangements of arrow symbols that correspond to the group roles introducedin Section 5.2. Each arrangement in Table 5.2 essentially works as the requirement for aset of arrow symbols to have each group role. The presence or absence of eacharrangement in the given arrow diagram is judged mostly from the diagram’s inter-arrow
structure, which captures the links between the arrow symbols in the diagram (Section
3.3). Some arrangements may correspond to more than one group role and, accordingly,
yield multiple candidates for the group roles. For instance, two arrow symbols with adirect body-tail link correspond to both formulating a branching process and illustratinginteractions of subjects.

Table 5.2: Spatial arrangements required for the arrow symbols with the group roles
in Section 5.2.
Group Role

Required Spatial Arrangement

indicating element-sharing

arrow symbols with indirect link(s)formulating a branching process

an arrow symbol a* and other arrow symbols, eachwith a direct tail-body link with a* and no other links

indicating interactions ofsubjects during their transitions

arrow symbols with direct link(s)illustrating diffusion / expansion

many arrow symbols with indirect tail-tail links

illustrating concentration /shrinkingmany arrow symbols with indirect head-head links

specifying an interval(a) Two arrow symbol, facing away from each other,with an indirect tail-tail link and no other links(b) Two arrow symbols, facing each other, with nolinks and a short distance between them101In addition, some group roles have additional requirements for the component
to which all arrow symbols in the group refer (Table 5.3). Such requirements may be
useful for narrowing down the candidates for the group roles.

Table 5.3: Components required for the arrow symbols with the group roles in
Section 5.2.
Group Role

Required Components

illustrating diffusiona collective or replicable entity

illustrating concentrationa collective entity

illustrating expansion / shrinking

a transformable entity

specifying an intervala label showing the interval’s owner or scale

In the actual process, the tentative group roles are deduced as follows. For eachgroup role, every pair of arrow symbols, except the arrow symbols in subordinate arrow
diagrams, is examined for satisfaction of the requirements in Tables 5.2 and 5.3. If so,
this role is adopted as the candidate for the group role of this pair. Afterwards, it isexamined whether there is any set of mutually-linked arrow symbols for which every pairhas the same group role. If so, this group role is reassigned to the set of these arrowsymbols.

102

5.4.3. Deduction of Individual Roles

In Step 3, the individual role of each arrow symbol is deduced by the same process as theinterpretation of arrow symbols in 1-arrow diagrams (Section 4.5), because even in
multi-arrow diagrams the semantic role of each arrow symbol is established by its
individual structure. This deduction process, however, must consider the components towhich the arrow symbol indirectly refers. Some group roles specify such indirectreference of arrow symbols (Table 5.4).

Table 5.4: Indirect reference of arrow symbols specified by the group roles in
Section 5.2.
Group Role

Indirect Reference

formulating a branching process

all arrow symbols indirectly refer to the same tailcomponent, to which only one arrow symbol (a*)
directly refer by its tailindicating drop-by(a subclass of indicating interactions both arrow symbols refer to the same subjectof subjects during their transitions)indicating diversion
one arrow symbol refer to the part of the subject(a subclass of indicating interactions
assigned to another arrow symbolof subjects during their transitions)5.4.4. Validation of Tentative Group Roles

Step 2 may have assumed that each arrow symbol has a certain individual role, which is
specified by the tentative group role (Table 5.1). If the individual role of each arrowsymbol assumed in Step 2 is inconsistent with the individual role deduced in Step 3, the103

tentative group role is incorrect and, accordingly, rejected. Otherwise, the tentative grouprole is adopted as the valid interpretation.

5.5. Demonstration
This section demonstrates with two examples (Figure 5.8) how the developed method forinterpreting arrow symbols in multi-arrow diagrams (Section 5.4) works. These examples
are identical to those used in Section 3.4 for demonstrating two complementary structuresof arrow diagrams.

Industrial Revolution

a1

a3

a2

a4 Urban
Rural
Area population Area

(a)

(b)

Figure 5.8: Two 2-arrow diagrams which capture (a) a pack of wolves splits into two
packs, which approach a sheep from front and behind and (b) the industrial
revolution leads to the population drift from rural area to urban area.

5.5.1. Example 1: Wolves’ Attack Scenario

The 2-arrow diagram in Figure 5.8a has two sub-diagrams, “wolves sheep” and“sheep,” which are associated with the arrow symbols a1 and a2, respectively. The
sub-diagram “wolves sheep” cannot be a subordinate arrow diagram, since a2 points not
the center of “wolves sheep.” Similarly, “sheep” cannot be a subordinate arrow104diagram, since a1 points not to the center of “sheep.” Consequently, the 2-arrow
diagram is not nested.
Since a1 and a2 have a direct body-tail link and an indirect head-head link, a1
and a2 may have a group role of indicating element-sharing (of the sheep) and indicating
diversion (of the wolves) (Table 5.2). If indicating diversion is the correct interpretation,

the individual roles of a1 and a2 should be behavioral description (Table 5.1) and thesubject associated with a1 should be succeeded to a2 (Table 5.3). Consequently, theindividual structures of a1 and a2 are (wolves, –, sheep) and (a part of wolves, –, sheep),
respectively. The patterns of these two structures are both (PCO, –, PCO), whichcorrespond to behavioral description (Table 4.3) and association (Table 4.6).
Consequently, indicating diversion is not rejected and it is deduced that both a1 and a2
have the individual role of behavioral description and they jointly have group roles ofindicating diversion and indicating element-sharing.

5.5.2. Example 2: Industrial Revolution Scenario

The 2-arrow diagram in Figure 5.8b has two sub-diagrams, “ Industrial revolution ” and↓“ Rural area → Urban area ,” which are associated with the arrow symbols a3 and a4,
population

respectively. “ Rural area → Urban area ” satisfies all requirements for a subordinate
population

arrow diagram.

105

Assume “ Rural area → Urban area ” is not a subordinate arrow diagram. Then,
population

since a3 and a4 have a direct head-body link, a3 and a4 may have a group role ofindicating confluence. If indicating confluence is the correct interpretation, the individual

roles of a3 and a4 should be behavioral description (Table 5.1), but it is impossible,
because“Industrial Revolution” cannot get together with the “population.”

Consequently, indicating confluence is an invalid interpretation. On the other hand, if a3
and a4 are not jointly used for indicating confluence, their direct head-body link cannot
be explained. Consequently, “ Rural area → Urban area ” must be a subordinate arrow
population

diagram.
The individual structure of a4, (“Rural Area”, “population”, “Urban Area”),
has a pattern of (PCL, PCO, PCL), which corresponds to behavioral description (Table
4.3). Accordingly,

 " Industrial revolution" ,−, " Rural area → Urban area" , has apopulationpattern of (PCE, –, PCE), which corresponds to behavioral description (Table 4.3) andassociation (Table 4.6). Behavioral description is an impossible interpretation, however,since “Industrial Revolution” is not something that approaches the population drift eventor changes into this event. Consequently, a3 is used for association—implying that theindustrial revolution causes or contributes to the population drift from the rural area to theurban area.

1065.6. Summary
In multi-arrow diagrams, an arrow symbol may refer to subordinate arrow diagrams,
which are subsets of the multi-arrow diagrams. In addition, arrow symbols in multi-arrow
diagrams may organize a group under a specific spatial arrangement and jointly have thefollowing group roles:•

to indicate that a set of individual semantics refers to the same component,•

to formulate a branching process,•to indicate interactions of subjects during their transitions,•to illustrate an entity’s extent change, and•to specify an interval.

Thanks to such nesting and the group roles of arrow symbols, multi-arrow diagrams
capture richer semantics than a set of 1-arrow diagrams. This chapter developed a method
for interpreting arrow symbols in such multi-arrow diagrams, which consisted of the four
steps: (1) detection of subordinate arrow diagrams, (2) tentative deduction of group roles,(3) deduction of group roles, and (4) validation of the tentative group roles. The spatial
arrangements of arrow symbols were exploited for detecting subordinate arrow diagrams,
as well as for deducing group roles of arrow symbols.

107Chapter 6
EVALUATIONThis thesis has developed an algorithm for deriving the interpretations of arrow symbols,
which is called the Arrow Symbol Interpreter (ASI). This method emphasizes structural
patterns of arrow diagrams under the hypothesis that the interpretation method, which
deduces interpretations from the spatial arrangement of arrow symbols and components
in arrow diagrams, detects the correct semantic roles of arrow symbols at a significantly
higher rate than random choices (Section 1.3). To examine this hypothesis this chapter
conducts an experiment, in which a prototype system, which implements the algorithm in
Section 4.5, deduces the semantic roles of individual arrow symbols in the sample
arrow-containing

diagrams.

Then,

the

correctness

of

the

computer-generated

interpretations is statistically evaluated. The detailed design of the experiment is
described in Section 6.1. Section 6.2 shows the result of this experiment, from which
Section 6.3 evaluates the hypothesis. Section 6.4 further analyzes the result of thisexperiment with a focus on each class of semantic roles. Finally, Section 6.5 analyzes the
misinterpreted arrow symbols in order to find out problems in the current ASI.

6.1. Method
The purpose of this experiment is to examine the correctness of the interpretations ofarrow symbols deduced by the ASI. The experiment features the algorithm for deducing
108

possible semantic roles of individual arrow symbols (i.e., individual roles) from thepattern of their individual structures, because this algorithm is well-formalized (Section
4.5) and commonly used in the interpretations of arrow symbols in 1-arrow diagrams andthose in multi-arrow diagrams.
Figure 6.1 shows a screenshot of the prototype system, which has beendeveloped for the experiment. The prototype deduces the set of all semantic roles(orientation, behavioral description, annotation, association, or their combinations) that
corresponds to a given individual structure. At this time, the user of this prototype has tospecify the pattern of the individual structure associated to the arrow symbol. The
automation of this process is a subject for future research (Section 7.3.2).

Figure 6.1: A prototype of the ASI.
Sample arrow symbols for the experiment were collected from an introductory
GIS textbook, “Geographical Information Systems and Computer Cartography” (Jones
1997), because this material satisfies the following conditions:•the material contains a sufficient number of arrow-containing diagrams;•

the semantic roles of arrow symbols in these diagrams are not biased (Figure 6.2);
109•

the material is expected to be read by people without special education or training in
diagram reading; and•the material matches the interest of the readers whom this thesis targets.
Other
5%

Orientation
25%

Association
22%

Annotation
21%

Behavioral description
27%

Figure 6.2: Semantic roles of 304 sample arrow symbols found in a GIS textbook(Jones 1997).
We also examined two introductory textbooks in biology and astronomy, but
the semantic roles of the arrow symbols used in these two textbooks are considerably
biased, because the biology textbook predominantly uses arrow symbols for illustratingchemical reactions or movement of organisms, both of which belong to behavioral
description (Figure 6.3a), while the astronomy textbook often uses arrow symbols forillustrating an interval, which cannot be categorized into the four classes of semanticroles (Figure 6.3b). From these two examples, we considered that the materials in
traditional domains, which may follow the diagrammatic conventions in those domains,are not preferable for the source of sample arrow symbols. Also, newspapers andmagazines were avoided, since their diagrams are typically drawn by few designers andadhere to in-house standards.
110Other
Association 4%
8%
Annotation
5%

Orientation
1%

Other
29%

Orientation
30%

Association
2%
Annotation
11%

Behavioral
description
82%

(a)

Behavioral
description
28%

(b)

Figure 6.3: Semantic roles of (a) 745 arrow symbols found in a biology textbook(Comins and Kaufmann III 2003), Part I and II, and (b) 956 arrow symbols found in
an astronomy textbook (Avila 1992).
The correct semantic role of each arrow symbol in the textbook figures was
assigned based on the figures plus context, sometimes drawn from the caption and the
body text. We confirmed that the assignment of the correct semantic roles to the arrowsymbols correspond to the result of votes by human subjects.
From the figures in the GIS textbook 64 arrow-containing diagrams with 304
arrow symbols were collected. Among the 64 diagrams, 53 diagrams contain multiple
arrow symbols. Some diagrams contain a large number of similar arrow symbols, whichhave the same semantic roles and the same patterns of individual structures (Figure 6.4).
These similar arrow symbols, if counted individually, may distort the statistic result. Thus,
for every set of similar arrow symbols in each diagram one representative is selected.
Finally, 94 representative arrow symbols were prepared for the experiment.

111

Figure 6.4: Two arrow-containing diagrams with a set of similar arrow symbols.
Figure 6.5 shows the semantic roles of the 94 representative arrow symbols.
The selection of representatives did not bias the proportion of the four classes of semantic
roles
Other
10%

Orientation
27%

Association
12%

Annotation
22%
Behavioral
description
29%

Figure 6.5: Semantic roles of the 94 representative arrow symbols.
The evaluation starts with counting the number of interpretations that the ASI
deduced. Then, for every arrow symbol, the correctness of the deduced interpretations is
examined, based on the distinction of the following four categories of correctness:•exact match, where the ASI deduced only one interpretation that is exactly the correct

semantic role;

112

•

partial match, where the ASI deduced multiple interpretations one of which is thecorrect semantic role;•oversight, where the ASI deduced zero, one, or multiple interpretations, but theseinterpretations do not include the correct semantic role, which belongs to one of thefour classes of semantic roles (i.e., orientation, behavioral description, annotation,or association); and•no-answer, where the ASI deduced zero, one, or multiple interpretations, but theseinterpretations do not include the correct semantic role, because the correct semanticrole belongs to none of the four classes of semantic roles.
Then, the numbers of sample arrow symbols whose interpretations yield these four
categories are counted. This thesis considers that ASI successfully detects the correct
semantic role of an arrow symbol if the arrow symbol yields an exact match or a partial
match. Accordingly, the sum of exact match and partial match cases, divided by the

number of all sample arrow symbols, is called the detection rate. This thesis calculates
the ASI’s detection rate and examines if it is significantly larger than the detection rate
under random choices.
The experiment results are also analyzed statistically with a focus on each classof semantic roles. For each class of semantic roles (say, ri) the interpretation results are
categorized into true-positive, true-negative, false-positive, and false-negative results,
depending on (1) whether ri is the correct semantic role and (2) whether the ASI’s

113

interpretation includes ri (Table 6.1). These four categories of results have the following
meanings:•

the true-positive result means that the ASI successfully deduced ri, which is thecorrect semantic role;•

the true-negative result means that the ASI successfully excluded ri, which is not thecorrect semantic role;•

the false-positive result means that the ASI unnecessarily deduced ri, which is not thecorrect semantic role; and•the false-negative result means that the ASI failed to detect the correct semantic roleri, thereby yielding oversight.

Then, the numbers of sample arrow symbols whose interpretation yields these four
categories of results are counted. The results are summarized into four 2×2 contingency
tables, which are then evaluated with Fisher’s exact test to examine a hypothesis that the
ASI’s conclusion on whether a semantic role ri may be the correct semantic role or not isrelated to whether ri is actually the correct semantic role or not.

Table 6.1: Four types of interpretation result with regard to a semantic role ri.
Whether the ASI’s interpretations include ri
YesNo
Whether correct
semantic role is ri

Yestrue-positive

false-negativeNo

false-positivetrue-negative

114

Finally, the misinterpreted arrow symbols (i.e., arrow symbols whose
interpretation yields partial match, oversight, or no-answer) are analyzed in order to findout problems in the current ASI.

6.2. Statistical Overview
Figure 6.6 shows the number of interpretations that the ASI deduced for the 94 arrowsymbols. In most cases the ASI deduces one or two interpretations. This result indicatesthat ASI certainly removes the ambiguity of arrow symbols, since initially there are fourinterpretation choices (i.e., orientation, behavioral description, annotation, andassociation). For 6% of the arrow symbols the ASI was unable to deduce interpretations,due to the use of irregular formats (Section 6.5.1) or new formats that correspond to theunexpected semantic roles (Section 6.5.3). On average, 1.31 interpretations are deduced
per arrow symbol.
Nointerpretation
6%
Twointerpretatons37%

One
interpretaton
57%

Figure 6.6: The number of interpretations that the ASI deduced for the 94
representative arrow symbols.
Figure 6.7 shows the correctness of the ASI’s interpretations. For 44% + 35% =79% of the 94 arrow symbols, the ASI successfully detected the correct semantic role.
115Especially, 44% of the 94 arrow symbols yielded a unique interpretation, which requires
no further process for narrowing down the interpretations. For 11% + 10% = 21% of the
94 arrow symbols, the ASI failed to detect the correct semantic roles. The 10% of the 94
arrow symbols failed the detection because their correct semantic roles are not amongorientation, behavioral description, annotation, and association.
No-answer
10%
Oversight
11%
Exact Match
44%

Partial Match
35%

Figure 6.7: The interpretation results of the 94 representative arrow symbols.

6.3. Validity of the Hypothesis
The hypothesis of this thesis is that the interpretation method, which deduces
interpretations from the spatial arrangement of arrow symbols and components in arrow
diagrams, detects the correct semantic roles of arrow symbols at a significantly higher
rate than random choices (Section 1.3). The interpretation method used for theexperiment is the ASI. According to the previous statistical result, the ASI detected thecorrect semantic roles (i.e., the ASI’s interpretations include the correct semantic roles)
for 79% of sample arrow symbols, even though the average number of the interpretations
is only 1.31 per arrow symbol. If zero, one, or two interpretations are randomly selectedfrom four choices at the probability of 6%, 57%, and 37%, respectively (Figure 6.6), the116expected detection rate (i.e., the probability that the randomly-selected interpretations foran arrow symbol include its correct semantic role) is only 30%, which is much smallerthat the ASI’s detection rate. In addition, the probability that such randomly-selectedinterpretations include the correct semantic roles for 79% of 94 arrow symbols is only
9.7×10-24. This result clearly supports the hypothesis that the ASI detects the correct
semantic roles at a significantly higher rate than random choices. This result indicatesthat the ASI’s interpretation is reliable, at least more than randomly-selectedinterpretations.

6.4. Statistical Analysis in Terms of Each Class of Semantic Roles
Tables 6.2-6.5 summarize the interpretation results of the 94 arrow symbols with regard
to each class of semantic role. The comparison of these tables reveals that:•

The interpretations with regard to annotation are highly accurate (Table 6.4);•

Interpretations with regard to orientation and behavioral description are slightly
error-prone; that is, they are occasionally deduced unnecessarily and occasionally
undetected (Tables 6.2 and 6.3); and•Association is detected with few omissions, but at the same time often deduced

unnecessarily (Table 6.5).

117

Table 6.2: The interpretation results of the 94 arrow symbols with regard toorientation.

Whether the correct
semantic role isorientation

Yes
No

Total

Whether the ASI’s interpretations
include orientation
Yes
No
19
6

Total
25

6

63

69

25

69

94

Table 6.3: The interpretation results of the 94 arrow symbols with regard to withregard to behavioral description.

Whether the correct
semantic role isbehavioral description

Yes
No

Total

Whether the ASI’s interpretations
include behavioral description
Yes
No
25
3

Total
28

10

56

66

35

59

94

Table 6.4: The interpretation results of the 94 arrow symbols with regard to withregard to annotation.

Whether the correct
semantic role isannotation
Total

Yes
No

Whether the ASI’s interpretations
include annotation
Yes
No
21
0

Total
21

2

71

73

23

71

94

118

Table 6.5: Number of the four types of interpretation results with regard toassociation.

Whether the correct
semantic role isassociation

Yes
No

Total

Whether the ASI’s interpretations
include association
Yes
No
10
1

Total
11

30

53

83

40

54

94

These four tables are evaluated with Fisher’s exact test, which statisticallyexamines the significance of the dependence between two nominal variables in a 2×2
contingency table (Fisher 1922). Under the null hypothesis that two variables are
independent, products of the marginal probabilities determine the probabilities that eachtype of interpretation result occurs (Table 6.6). Consequently, we can accurately calculate
the probability p that the frequency in a certain cell becomes less than or equal to theobserved frequency under the condition of fixed marginal frequencies. If p issignificantly small, the null hypothesis is rejected and, accordingly, the alternative
hypothesis that two variables are dependent is supported.

Table 6.6: Probability that each interpretation result with regard to a semantic role ri
occurs if two nominal variables are independent.

Whether the correct
semantic role is ri
Total

Yes
No

Whether the ASI’s interpretations
include ri
YesNox(1-y)xy

Totalx(1-x)y(1-x)(1-y)(1- x)

y

(1-y)

1

119

The calculated p that the frequency of the false-negative results is less than orequal to the observed frequency is 5.2×10-10, 9.1×10-12, 5.3×10-19, and 6.6×10-4 for Tables
6.2-6.5, respectively. Thus, for all four tables the null hypothesis is rejected at the 1%
level of significance. This result indicates that the ASI’s conclusion on whether asemantic role ri may be the correct semantic role or not is significantly related to whether
ri is actually the correct semantic role or not. Interestingly, p for Table 6.6 is much larger

than others, indicating the ASI’s weak detection power with regard to association.

6.5. Analysis of Misinterpretations
In order to achieve a practical level of the interpretations, however, higher detection rateand smaller number of unnecessary interpretations are still desirable. In order to find the
directions for improving the ASI, this section analyzes the sample arrow symbols whose
interpretation yields oversight, partial match, or no-answer.

6.5.1. OversightOversight occurred for eleven arrow symbols out of the 94 samples. Among these elevenarrow symbols, six, four, and one corresponded to the failure to detect orientation,
behavioral description, and association, respectively.

The common reason why the ASI failed to detect orientation was the use of
unexpected formats. For instance, in Figure 6.8a, an adverbial component “Azimuth

120

direction” is placed in front of the arrow symbol, even though this thesis has assumed

that adverbial components are located in the arrow symbol’s body slot (Section 4.3.2).
Similarly, in Figure 6.8b, each arrow symbol refers to two locations, even though thisthesis has assumed that an arrow symbol for orientation refers to at most one location(Section 4.2.1). Incorporating such additional formats into the current set of basic formats
for orientation (Figure 4.3) will improve the ASI’s ability to detect orientation.

(a)

(b)

Figure 6.8: Two arrow-containing diagrams in which arrow symbols are used fororientation in irregular formats: (a) the arrow symbol points to an adverbial
component “Azimuth direction” and (b) each arrow symbol refers to two locations.
The common reason why the ASI failed to detect behavioral description was
the omission of the subject (Figure 6.9). The subject of behavioral description is omitted
typically when it is obvious from the context. In such case, the diagram caption may be
useful for detecting the omitted subject.

Figure 6.9: An arrow-containing diagram in which arrow symbols are used for
behavioral descriptions, although the subjects are not illustrated in the diagrams.
121

Figure 6.10 shows the case where the ASI failed to detect association. The
white arrow symbol indirectly refers to the empty table in the previous line, thereby
associating the empty table with the subsequent table of settlements. Like this example,
an arrow symbol may be placed at a line head and associate an element in the previous
line with the subsequent element. This spatial arrangement is also seen in the descriptionsof mathematical deductions. The knowledge of such diagram conventions would help us
to identify the components to which arrow symbols may indirectly refer.

Figure 6.10: An arrow-containing diagram where the white arrow symbol indirectly
refers to the empty table in the previous line.

6.5.2. Partial Match

Thirty-three arrow symbols out of the 94 samples yielded a partial match. For 25 cases
the ASI deduced the correct interpretation, behavioral description, together with anunnecessary interpretation, association. For the remaining eight cases the ASI deduced
the correct interpretation, association, together with an unnecessary interpretation,
behavioral description. Table 6.7 shows the patterns of the individual structures of the 33

arrow symbols, highlighting the large portion of the pattern (PCO[MC]*, [MC]*,122

PCO[MC]*) (24 out of 33 cases). Thus, to resolve the ambiguity of arrow symbols withthis pattern is a key for reducing partial match results.

Table 6.7: Individual structures of the 33 arrow symbol which yielded partial match([MC]*: arbitrary number of MC).
Pattern of
Individual Structure(PCO[MC]*, [MC]*, PCO[MC]*)(PCO[MC]*, [MC]*, PCE[MC]*)(PCO[MC]*, [MC]*, PCO[MC]*)(PCE[MC]*, [MC]*, PCL[MC]*)(PCO[MC]*, [MC]*, PCO[MC]*)(PCO[MC]*, [MC]*, PCL[MC]*)

Correct
Interpretations

Unnecessary
Interpretations

behavioral
description

association

association

behavioral
description

Number of
Samples
17
3
3
2
7
1

Arrow symbols, whose individual structure has the pattern (PCO[MC]*, [MC]*,PCO[MC]*) are used fro capturing the change of a subject, indicating an interaction

between a subject and an involved entity (Section 4.2.2), or associating two subjects(Section 4.2.4). The first two correspond to behavioral description, while the last one
corresponds to association. The following three facts are useful for distinguishing thesethree scenarios:•

An arrow symbol captures the change of a subject only if two objects refer to two
different states of the same subject (Figure 6.11a).

•

An arrow symbol associates two subjects if both of the two subjects are immovable(Figure 6.11b).

123

•

An arrow symbol typically captures the interaction between a subject and an
involved entity if the shape of the arrow symbol is not simple, implying the course of
spatial transition.

(a)

(b)

Figure 6.11: Two arrow-containing diagrams, each with an arrow symbol whose
individual structure has the pattern of (PCO[MC]*, [MC]*, PCO[MC]*).

6.5.3. No-Answer

For nine arrow symbols out of the 94 samples the ASI failed interpretations simply
because their semantic roles did not belong to the four classes of semantic roles. These
unexpected semantic roles are categorized into the following three types:•

to illustrate an interval, either by itself (Figure 6.12a) or in combination with anotherreversely directed arrow symbol (Figure 6.12b)—seven cases;•

to highlight a certain point in the space (Figure 6.13a)—one case; and.

•to imply a series of elements ordered by the value of their certain property, such as
brightness (Figure 6.13b)—one case;

124

These additional semantic roles are called interval specification, pointing, and gradation,
respectively. Arrow symbols for pointing are familiar in computers’ graphical userinterfaces. Interval specification is considered also as a group role when the interval isspecified by two arrow symbols (Section 5.2.5).

(a)

(b)

Figure 6.12: Two arrow-containing, in which two arrow symbols are used forinterval specification (a) by themselves or (b) in combination.

(a)

(b)

Figure 6.13: Two arrow-containing, each with an arrow symbol used for (a) pointing
and (b) gradation.
It is an open question whether the ASI should support these additional semanticroles, because it may be of little merit, while it would increase the risk of partial match.

125

Instead, it might be a better solution to expand the coverage of the current four classes ofsemantic roles to include those additional semantic roles. For instance, pointing can be
included in annotation by considering that arrow symbols for annotation may attach an
empty label to a subject.

6.6. Summary
This chapter conducted an experiment in which the ASI’s prototype interpreted 94 sample
arrow symbols. For 79% of the samples the ASI successfully detected the correct
semantic roles, even though the average number of interpretations was only 1.31. This
result supports that the interpretation method, which deduces interpretations from thespatial arrangement of arrow symbols and components in arrow diagrams, detects thecorrect semantic roles of the arrow symbols at a significantly higher rate than random
choices. For 35% of the sample arrow symbols, however, the ASI deduced unnecessaryinterpretations in addition to the correct semantic roles. Background knowledge about,for instance, the components’ immobility seems useful for removing such unnecessaryinterpretations. For 11% of the samples the ASI failed to detect the correct semantic roles
due to the use of unexpected formats and the omission of subjects. 10% of the samples
had semantic roles that the current ASI did not support, which are interval specification,
pointing, and gradation.

126

Chapter 7
CONCLUSIONS

People often sketch diagrams for communication. If computers understand such diagrams,
we can interact with computers more intuitively. Arrow symbols are a fundamental
element of such diagrams. They capture a large variety of semantics, as well as enable us
to describe dynamic processes and mechanisms in static diagrams. Due to the arrows’
versatility, however, it remains a challenging problem to make computers distinguish thevarious semantic roles of arrow symbols. The solution to this problem is highly desirable
for more effective and user-friendly computer systems with sketching interfaces.

7.1. Summary of Thesis
This thesis developed an algorithm for deducing the semantic roles of arrow symbols,
called the Arrow Symbol Interpreter (ASI). The ASI emphasized the structural patterns ofarrow-containing diagrams, since the diagram follows a specific spatial arrangement tocapture certain semantics. Since the semantic roles of arrow symbols are assigned toindividual arrow symbols and sometimes to the groups of arrow symbols, two types of
the corresponding structures were introduced: the individual structure models the spatial
arrangement of components around each arrow symbol and the inter-arrow structure
models the spatial arrangement of multiple arrow symbols. The semantic roles assigned
to individual arrow symbols were classified into four types, and for each class the127corresponding formats of individual structures were identified. The result enabled thederivation of the possible semantic roles of individual arrow symbols. In addition, for the
diagrams with multiple arrow symbols, the patterns of their inter-arrow structures were
exploited to detect the groups of arrow symbols that jointly have certain semantic roles,
as well as the nesting relations between the arrow symbols. The assessment showed thatfor 79% of the sample arrow symbols the ASI successfully detected their correct semanticroles, even though the average number of interpretations was only 1.31. This result
indicated that the structural information is highly useful for deriving the reliableinterpretations of arrow symbols.

7.2. Results and Major Findings

7.2.1. Classification of Individual Roles

Based on the survey of various arrow-containing diagrams, semantic roles assigned toindividual arrow symbols (i.e., individual roles) were classified into orientation,
behavioral description, annotation, and association. The ASI was built on thisclassification. The experiment, however, revealed such additional semantic roles asinterval specification, pointing, and gradation.

1287.2.2. Investigation of Group Roles

This thesis also investigated the following semantic roles which are assigned to groups ofarrow symbols (i.e., group roles): indicating element-sharing, formulating a branchingprocess, indicating interactions of subjects during their transitions, illustrating an extent
change, and specifying an interval.

7.2.3. Two Syntactic Structures of Arrow Diagrams

An arrow symbol aligns the components as well as makes a formation with other arrowsymbols, thereby establishing a syntactic structure within the diagram. The patterns ofsuch syntactic structures are important for the interpretation, since arrow diagrams follow
a specific spatial arrangement to capture the semantics. This thesis, therefore, introduced
two types of syntactic structures; individual structures modeled the spatial arrangementof components around the individual arrow symbols based on the distinction of threecomponent slots, while the inter-arrow structures modeled the spatial arrangement ofarrow symbols based on the topological relations between every pair of these arrowsymbols. These two structures work complimentarily, as they captured the configurationsof arrow diagrams from local and global perspectives.

1297.2.4. An Algorithm for Deducing Individual Roles of Arrow Symbols

This thesis identified the correspondence between the individual roles of arrow symbols
and the pattern of individual structures, which are determined by both the basic formats
that the individual structure must follow and the optional components. Making use of thiscorrespondence, an algorithm for deducing the possible individual roles of arrow symbols
was developed. The assessment showed that this method successfully detected the correct
individual roles for 79% of sample arrow symbols.

7.2.5. The Arrow Symbol Interpreter (ASI)

Based on the correspondences between the group roles and the spatial arrangement ofarrow symbols, a method for deducing the possible groups of arrow symbols and theirgroup role was developed. In addition, an algorithm for detecting subordinate arrow
diagrams in multi-arrow diagrams, which also made use of the spatial arrangement ofarrow symbols, was developed. By combining the methods for detecting subordinate
arrow diagrams, deducing the individual roles, and deducing the group roles, this thesis
finally invented an algorithm for deriving both individual roles and group roles of arrowsymbols in a multi-arrow diagrams, which consisted of four sequential steps.

1307.3. Future Work
This section discusses future work in the four areas: remediation, automation, detailenrichment, and applications.

7.3.1. Remediation

The analysis of misinterpreted sample arrow symbols revealed some problems in thecurrent ASI (Section 6.5). In order to reduce misinterpretations and ambiguousinterpretations, this section proposes the following guidelines for the remediation:

7.3.1.1. Reclassification of Individual RolesThe experiment found that the current four classes of individual roles did not fully cover
the individual roles that arrow symbols may have (Section 6.5.3). The classification ofindividual semantics (Section 4.1) might have emphasized too much the categorization of
the semantic roles found in the preliminary reviews (Sections 2.2.1-2.2.7) and lacked aconvincing rationale for classifying the entire range of individual roles that arrowsymbols potentially have.
An alternative approach would be to reclassify the individual roles of arrowsymbols from a viewpoint of semantic extension (Langacker 1999). The semantic
extension is a cognitive process that people assign a new meaning to a vocabulary byextending its original meaning. There are three mechanisms that trigger the semantic
extensions:131•

Metaphor (Lakoff and Johnson 1980; Lakoff 1987), where a concept succeeds thename of a similar concept. For example, firewalls in computer networks succeed its
name from firewalls in buildings based on the analogy that both firewalls prevent the
intrusion of threats. Metaphor is considered a mapping from a source domain to atarget domain, such that the target domain is effectively understood by analogy of
the well-understood source domain. For example, “life is a journey” explains a life
(target domain) by a metaphor of journey based on their similarity.
•

Metonymy (Kovecses and Radden 1998), where a concept succeeds the name ofcontiguous concept. Usually contiguity is such a physical property as spatial

proximity and temporal concurrency. For example, in the sentence “the kettle isboiling,” the kettle is a metonymy of hot water in the kettle based on their spatial

proximity. Metonymy is seen as a cognitive process to access a target by way of
another easily-referable source in the same domain.
•

Synecdoche (Seto 1999), where a concept succeeds the name of either more generalor special concept. For example, in the sentence “click your mouse,” a mouse button
is called mouse, which is a more general concept. Conversely, in the sentence “manshall not live by bread alone,” food is called bread, which is more special concept.

These three types of semantic extensions are driven by people’s cognitive motivations to
reduce the memory load for naming a new concept by applying the name of an existing
concept (Gyori 2002).

132

A vocabulary becomes polysemic through iterative semantic extensions.
Probably the polysemy of arrow symbols is also explained by such iterative semantic
extensions, starting from their most primitive meaning—a flying weapon with a sharphead and a linear body. By tracing this evolution process, the semantic roles (bothindividual and group roles) of arrow symbols should be schematized as a tree. This tree
should rationalize the classification of the semantic roles of arrow symbols. The tree in
Figure 7.1 shows a model of evolutions of arrow symbols’ semantic roles, superimposedby the current classification of semantic roles. This tree indicates that pointing isfundamentally different from the other classes of semantic roles.
Orientation
Direction

Metaphorical Direction
VectorMoving Receiving Sending
Direction Direction Direction

Space Regulation

Association
LinkageArrow
WeaponMapping

Behavioral Description
Spatial Movement

Motion Path

Encounter Division

Continuous
Existence

Communication

ChangePointing

SpatialLinkage

Temporal
Order

Attribution/
Assignment

Causal Relation
Interval Specification
Gradation

Annotation

Schemacity (Synechdoche)
Extension (Metaphor / Menetomy)

Figure 7.1: A model of evolutions of arrow symbols’ semantic roles.
7.3.1.2. Detection of Impractical Interpretations

The ASI sometimes deduces an unnecessary interpretation, behavioral description, whenassociation is the correct semantic role of a given arrow symbol (Section 6.5.2). Such133

unnecessary behavioral description can be removed making use of backgroundknowledge about the component’s immobility. For instance, the three arrow diagrams in
Figure 7.2 have the same pattern of individual structures, (PCO, –, PCLMC), whichcorrespond to both behavioral description and association. The arrow symbols in Figures
7.2b-c are, however, not used for behavioral description due to the immobility of thebroken car and the Brandenburg Gate, respectively.

Berlin(a)

Berlin(b)

Berlin(c)Figure 7.2: Three arrow diagrams whose individual structures has the same patterns,(PCO, –, PCLMC), illustrating (a) behavioral description, (b) no behavioral
description due to the immobility of the broken car, and (c) no behavioral
description due to the (immobile) Brandenburg Gate.
Kurata and Egenhofer (2006b) demonstrated that the component’s mobility andimmobility can be computationally derived from a general-purpose ontology (Guarino1998), such as WordNet (Fellbaum 1998). First, mobility is often employed already in thedefinition of an entity class as one of its essential characteristics. For instance, WordNet
defines animal as “living organism characterized by voluntary movement,” which clearly
indicates the mobility of animals. Second, the mobility of a class may be determined fromthe operations associated with this class. For instance, ball, which WordNet defines as “around object that is hit or thrown or kicked in games,” is associated with such operations

as hit, throw, and kick. Since hit, throw, and kick are subclasses of the transitive verb
move (Figure 7.3a), it is considered that the ball has mobility. Finally, mobility isinherited from upper classes to lower classes. Consequently, any subclasses of animal,
134

such as cat and dog, and any subclasses of ball, such as soccer ball and tennis ball, arealso considered movable (Figure 7b).

characterized byits mobility

move

hit

propel, impel

…

throw

…

kick

organism, being
plant

animalchordate

…

…

…
cat

(a)

dog

…

: movable entity class(b)

Figure 7.3: (a) Hierarchy of an operation move and its subclasses and (b) hierarchyof animal and its super/subclasses with inheritance of mobility.
A difficulty arises when determining the lack of mobility (i.e., immobility),
since immobility is less recognized as an essential characteristic of an entity class thanmobility. A realistic solution is to adopt the closed world assumption (Reiter 1987), thatis, to assume that lack of knowledge about its mobility indicates its immobility. For
instance, the Brandenburg Gate is considered immovable, because the Brandenburg Gate
and its super classes (memorial/monument, structure/construction, artifact/artifact, and soforth) are not characterized by their mobility and have no operation related to move. Suchinferences rely on the completeness of the ontology and have a risk of unexpectedconsequences. For example, from WordNet one would misjudge a cloud in the sky to be
immovable due to the lack of knowledge about its mobility. Because this problem arises
from the incompleteness of WordNet, the use of another ontology may actually reveal themobility of a cloud. Indeed, Dictionary.com defines cloud as “a large moving body ofthings in the air or on the ground,” which clearly indicates the cloud’s mobility. Such135

discrepancies among ontologies imply the merit to employ and mine multiple ontologies
concurrently.
In general, the four classes of individual roles require some elements with thefollowing characteristics:•

Behavioral description requires a subject to move.

•

Orientation requires a subject that may have a directional property.

•

Annotation requires a subject whose property can be specified by the given label.

•

Association requires two subjects that can be associated under the effective relation.

Thus, if an interpretation requires an element to carry the characteristics that the element
actually cannot carry, the interpretation is considered impractical. To realize such
judgment of impractical interpretations, the ASI should be equipped with a database about
the possible characteristics of components or a capability of deducing possible
characteristics of components from existing knowledge bases. It is left for future researchwhether the components’ characteristics other than mobility can be computationallydetermined making use of existing knowledge bases.

7.3.1.3. Detection of Omitted Components

An arrow symbol may refer to the components which are not drawn around the arrowsymbol, especially when they are obvious from the context (Section 6.5.1). Thus, ideally,
the ASI should exploit the information from captions and legends in addition to diagrams,136

in order to model the context that influences the interpretations of arrow symbols. This
problem is a common long-term research goal for the study of diagram understanding.

7.3.2. Automation

This thesis has aimed at the contribution to the development of more intelligent computer
systems with sketching interfaces, in which users can naturally explain their ideas andknowledge by sketching a diagram. To facilitate natural interactions in such systems, theprocess of diagram understanding should be automated as fully as possible. The current
ASI, however, still requires much of the user’s assistance due to the lack of the following

abilities:•

Detection of components in diagrams, which requires symbol and text recognition
techniques.

•

Identification of the component type of the detected components. Some
diagrammatic conventions help to make the distinction between primary andmodifier components (Section 3.2.3), but further distinction of four subtypes ofprimary components require a new database about the component type of various
components or a technique for deducing such component types from existingknowledge bases.

•

Judgment on whether each arrow symbol refers to each component and, if yes, which
component slot of the arrow symbol contains this component. The distance between

137

the arrow symbol and the component should be a key for such detection, but it
depends on the diagram.
•

Identification of the component types that subordinate arrow diagrams (Section 5.3)
play. The component type of the subordinate arrow diagram is event if thesubordinate diagram illustrates a dynamic process; otherwise, its component typeshould be classified into object, as it represents a certain static concept.

The development of these techniques is highly desirable for the practical application of
the ASI. Also, these techniques are necessary for more comprehensive evaluation of the
ASI, including the deduction of group roles.

7.3.3. Detail Enrichment

Another direction of future research is to furnish details to the current interpretations ofarrow symbols. The current ASI distinguishes only four classes of semantic roles, whichmight be too coarse for some applications. For instance, the current ASI deduces simply
that the arrow symbol in Figure 7.4 is used for behavioral description, but the illustrated
scenario is significantly different depending on whether the car or the traveler is the
subject (i.e., which component moves).

Figure 7.4: An arrow diagram that may illustrate two different scenarios dependingon the context: a vehicle approaches a person (encounter) or a person leaves a
vehicle (division).
138

In general, depending on the relative positions of the subject and the involved
entities, subtypes of behavioral description, such as encounter and division, can be
distinguished. Similarly, depending on the type of the effective relation, such subtypes ofassociation as temporal order, causal relation, and mapping can be distinguished.

7.3.4. Applications

Applying the ASI to actual pen-based systems has two goals. The first goal is to remove
the restriction on the use of arrow symbols in the current pen-based systems and improvetheir usability and effectiveness. The second goal, which is more ambitious, is tocontribute to the creation of innovative computer systems with sketching interfaces (andpossibly speech interfaces as well), where people may collaborate with computer systems
as naturally as people often do in face-to-face communications. Since arrow symbols arefundamentals to paper-based communication that people have enjoyed for hundreds ofyears, the computer’s ability to understand arrow-containing diagrams surely expands thepotential of the collaboration by people and computers.

139

GLOSSARY
1-Arrow Diagram

An arrow diagram that contains a single arrow symbol.

Adjective Component

An optional component of an arrow diagram that is attached to a component and modifies
it.

Adverbial Component

An optional component of an arrow diagram that is attached to an arrow symbol andmodifies its semantic role.

Annotation

A semantic role of an arrow symbol to attach a label to a subject.

Arrow Diagram

A combination of arrow symbols and the elements to which the arrow symbols refer.
Unlike an arrow-containing diagram, every component of an arrow diagram must be
referred by at least one of the arrow symbols in the arrow diagram.

140

Arrow Semantic Interpreter (ASI)

A set of algorithms for deducing the semantic roles of arrow symbols in an arrow
diagram, which is developed in this thesis.

Arrow Symbol

A symbol with a linear part and a mark on it, which induces both linearity andasymmetry.

Association

A semantic role of an arrow symbol to associate two different subjects, illustrating theirasymmetric relation.

Behavioral description

A semantic role of an arrow symbol to illustrate a spatial or temporal transition of a
subject, possibly involving other entities on the course of transition.

Component

An element in a diagram, such as an icon, a text label, a small diagram embedded in the
diagram, or a specific position of a picture, a map, or an image, to which an arrowsymbol refers. Components are categorized into primary components and modifiercomponents.

141

Component Slot

A conceptual area that may contain components, identified by an arrow symbol. Eacharrow symbol identifies three component slots in front of, along, or behind the arrowsymbol, which are called the tail slot, body slot, and head slot, respectively.

Direct Link

A link between two arrow symbols established by their geometrical intersections.

Event (PCE)

A primary component that represents something that occurs in time and is characterized
by a set of changes that it triggers.

Group Role

The semantic role associated with a group of arrow symbols.

Indirect Link

A link between two arrow symbols established when these arrow symbols refer to thesame component.

Individual Role

The semantic role associated with a single arrow symbol. This thesis distinguishes fourtypes of individual roles: orientation, behavioral description, annotation, andassociation.

142

Individual Structure

A model of the spatial arrangement of components referred by an arrow symbol, which is
captured as a 3-turple whose three elements are the respective component sets in thearrow symbol’s three component slots.

Inter-Arrow Structure

A model of the spatial arrangement of multiple arrow symbols, which is captured as theset of topological relations between all pairs of the arrow symbols.

Interpretation of an Arrow Symbol (or a Group of Arrow Symbols)

The semantic role of an arrow symbol (or a group of arrow symbols) of arrow symbols
deduced by people or a computer.

Link

A spatial connection of multiple arrow symbols, usually representing certain relevance
between the semantics associated with these arrow symbols. Links establish topologicalrelations between arrow symbols. Direct links and Indirect links are distinguished.

Location (PCL)

A primary component that represents a position in space.

Modifier Component (MC)A component that modifies something else.
143

Moment (PCM)

A primary component that represents a position in time.

Multi-Arrow Diagram

An arrow diagram that contains two or more arrow symbols.

Nested Arrow Diagram

A multi-arrow diagram that contains a subordinate arrow diagram.

Object (PCO)

A primary component that represents an entity or its unit, which exists in physical orconceptual space and takes an action or gets manipulated.

Orientation

A semantic role of an arrow symbol, where the arrow symbol is attached to a subject,specifying its directional property.

Pattern of an Individual Structure

3-tuples, such as (MC, –, PCL), whose three elements show the types of all components inthe arrow symbol’s three component slots.

Primary Component (PC)A component that represents an independent concept.
144

Semantic RoleThe function of an arrow symbol or a group of arrow symbols to provide the information
about the components to which the arrow symbol refers.

Subordinate Arrow Diagram

A sub-diagram of an arrow diagram which forms an arrow diagram by itself and isreferred by an arrow symbol from outside.

145

BIBLIOGRAPHY
Agrawala, M. and Stolte, C. (2001) Rendering Effective Route Maps: Improving
Usability through Generalization. in: Fiume, E. (Ed.) 28th Annual Conference on
Computer Graphics and Interactive Techniques (SIGGRAPH 2001), Los Angeles, CA,

241-249, ACM Press.
Alexandroff, P. (1961) Elementary Concepts of Topology. Dover, Mineola, NY.
Allen, J. (1983) Maintaining Knowledge About Temporal Intervals. Communications of
the ACM, 26(11): 832-843.

Alvarado, C. and Davis, R. (2001a) Preserving the Freedom of Paper in a
Computer-Based Sketch Tool. in: Smith, M., Koubek, R., Salvendy, G., and Harris, D.
(Eds.) HCI International, New Orleans, LA, 687-691, Lawrence Erlbaum Associates.
Alvarado, C. and Davis, R. (2001b) Resolving Ambiguities to Create a Natural Sketch
Based Interface. in: Nebel, B. (Ed.) 17th International Joint Conference on Artificial
Intelligence (IJCAI-01), Seattle, WA, 1365-1374, Morgan Kaufmann.

Aoki, Y., Shio, A., Arai, H., and Odaka, K. (1996) A Prototype System for Interpreting
Hand-Sketched Floor Plans. in: International Conference on Pattern Recognition,
Vienna, Austria, 3, 747-751, IEEE Computer Society.
Avila, V. (1992) Biology: A Human Endeavor. Bookmark Publishers, Chula Vista, CA.
Bailey, T. and Gatrell, A. (1995) Interactive Spatial Data Analysis. Longman, Essex, UK.
146

Becker, R., Eick, S., and Wilks, A. (1995) Visualizing Network Data. IEEE Transactions
on Visualization and Computer Graphics, 1(1): 16-21.

Bertin, J. (1983) Semiology of Graphics: Diagrams, Networks, Maps. University of
Wisconsin Press, Madison, WI.
Blaser, A. and Egenhofer, M. (2000) A Visual Tool for Querying Geographic Databases.
in: Gesù, V., Levialdi, S., and Tarantini, L. (Eds.) AVI2000 - Advanced VisualDatabases, Salerno, Italy, 211-216.

Cheng, O., Lowe, R., and Scaife, M. (1999) Cognitive Science Approaches toUnderstanding Diagrammatic Representations. in: Blackwell, A. F. (Ed.) Thinking with
Diagrams, Kluwer Academic Publishers.

Chrisman, N. R. (1978) Concepts of Space as a Guide to Cartographic Data Structures.
in: Dutton, G. (Ed.) The First International Advanced Study Symposium on
Topological Data Structures for Geographic Information Systems, Cambridge, MA,

1-19, Harvard Laboratory for Computer Graphics and Spatial Analysis.
Claramunt, C. and Theriault, M. (1995) Managing Time in GIS: An Event-Oriented
Approach. in: Clifford, J. and Tuzhilin, A. (Eds.) Recent Advances in Temporal
Databases, Zurich, Switzerland, 23-42, Springer.

Claramunt, C., Theriault, M., and Parent, C. (1998) A Qualitative Representation of
Evolving Spatial Entities in Two-Dimensional Topological Spaces. in: Carver, S. (Ed.)
Innovations in GIS V. Taylor & Francis, 119-129.

147

Clementini, E. and Di Felice, P. (1998) Topological Invariants for Lines. IEEE
Transactions on Knowledge and Data Engineering, 10(1): 38-54.

Clementini, E., Di Felice, P., and van Oosterom, P. (1993) A Small Set of Formal
Topological Relationships Suitable for End-User Interaction. in: Abel, D. and Ooi, B.
C. (Eds.) 3rd International Symposium on Advances in Spatial Databases, Singapore,
Lecture Notes in Computer Science, 692, 277-295, Springer.
Cohen, P., McGee, D., and Clow, J. (2000) The Efficiency of Multimodal Interaction for a
Map-Based Task. in: 6th Applied Natural Language Processing Conference(ANLP2000), Seattle, WA, 331-338, Morgan Kaufmann.

Cohen, P. R., Johnston, M., McGee, D. R., Oviatt, S. L., Pittman, J. A., Chen, L., andClow, J. (1997) QuickSet: Multimodal Interaction for Distributed Applications. in: 5thInternational Multimedia Conference (Multimedia '97), Seattle, WA, 31-40, ACM

Press.
Comins, N. and Kaufmann III, W. (2003) Discovering the Universe. W. H. Freeman andCompany, New York, NY.
Davis, R. (2002) Sketch Understanding in Design: Overview of Work at the MIT AI Lab.
in: Davis, R., Landay, J., and Stahovich, T. (Eds.) AAAI Spring Symposium on Sketch
Understanding, Stanford, CA, 24-31, AAAI Press.

Do, E. and Gross, M. (2001) Thinking with Diagrams in Architectural Design. Artificial
Inteligence Review, 15: 135-149.

148

Egenhofer, M. (1989) A Formal Definition of Binary Topological Relationships. in:
Litwin, W. and Schek, H.-J. (Eds.) 3rd International Conference on Foundations of
Data Organization and Algorithms (FODO), Paris, France, Lecture Notes in Computer

Science, 367, 457-472, Springer.
Egenhofer, M. (1994) Definitions of Line-Line Relations for Geographic Databases.
IEEE Data Engineering Bulletin, 16(3): 40-45.

Egenhofer, M. (1996) Multi-Modal Spatial Querying. in: 7th International Symposium on
Spatial Data Handling, Delft, Netherlands, 785-799, Talyor & Francis.

Egenhofer, M. (1997) Query Processing in Spatial-Query-by-Sketch. Journal of Visual
Languages and Computing, 8(4): 403-424.

Egenhofer, M. and Al-Taha, K. (1992) Reasoning About Gradual Changes of Topological
Relationships. in: Frank, A., Campari, I., and Formentini, U. (Eds.) Theories andmethods of spatio-temporal reasoning in geographic space, Pisa, Italy, Lecture Notes

in Computer Science, 639, 196-219, Springer.
Egenhofer, M. and Franzosa, R. (1991) Point-Set Topological Spatial Relations.
International Journal of Geographical Information Systems, 5(2): 161-174.

Egenhofer, M. and Franzosa, R. (1995) On the Equivalence of Topological Relations
International Journal of Geographical Information Systems, 9(2): 133-152.

149

Egenhofer, M. and Herring, J. (1991) Categorizing Binary Topological Relationships
between Regions, Lines and Points in Geographic Databases. in: Egenhofer, M.,
Herring, J., Smith, T., and Park, K. (Eds.) A Framework for the Definitions ofTopological Relationships and an Algebraic Approach to Spatial Reasoning within
This Framework, NCGIA Technical Reports 91-7. National Center for Geographic

Information and Analysis, Santa Barbara, CA.
Egenhofer, M. and Mark, D. (1995) Modeling Conceptual Neighborhoods of TopologicalLine-Region Relations. International Journal of Geographical Information Systems, 9:555-565.
Fellbaum, C., (Ed.) (1998) WordNet: An Electronic Lexical Database, Cambridge, MA,
MIT Press.
Ferguson, R. and Forbus, K. (2000) GeoRep: A Flexible Tool for Spatial Representationof Line Drawings. in: 17th National Conference on Artificial Intelligence, Austin, TX,
510-516, AAAI Press.
Ferguson, R. and Forbus, K. (2002) A Cognitive Approach to Sketch Understanding. in:Davis, R., Landay, J., and Stahovich, T. (Eds.) AAAI Spring Symposium on Sketch
Understanding, Stanford, CA, 67-72, AAAI Press.

Ferguson, R., Rasch, R., Turmel, W., and Forbus, K. (2000) Qualitative Spatial
Interpretation of Course-of-Action Diagrams. in: Proceedings of the 14th International
Workshop on Qualitative Reasoning, Morelia, Mexico, 47-52.

150

Fisher, R. A. (1922) On the Interpretation of χ2 from Contingency Tables, and the
Calculation of P. Journal of the Royal Statistical Society, 85(1): 87-94.
Forbus, K., Ferguson, R., and Usher, J. (2001) Towards a Computational Model of
Sketching. in: 6th International Conference on Intelligent User Interfaces, Santa Fe,
NM, 77-83, ACM Press.
Forbus, K. and Usher, J. (2002) Sketching for Knowledge Capture: A Progress Report. in:
7th International Conference on Intelligent User Interfaces, San Francisco, CA, 71-77,

ACM Press.
Freksa, C. (1992) Temporal Reasoning Based on Semi-Intervals. Artificial Inteligence,
54: 199-227.
Funt, B. (1980) Problem-Solving with Diagrammatic Representations. Artificial
Intelligence, 13: 201-230.

Garcke, H., Preuber, T., Rumpf, M., Telea, A., Weikard, U., and van Wijk, J. (2000) A
Continuous Clustering Method for Vector Fields. in: Hansen, C., Johnson, C., andBryson, S. (Eds.) Visualization 2000, Los Alamitos, CA, 351-358, IEEE Computer
Society Press.
Gibson, J. (1979) The Ecological Approach to Visual Perception. Houghton Mifflin,
Boston.

151

Gombrich, E. (1990) Pictorial Instructions. in: Barlow, H., Blakemore, C., andWeston-Smith, M. (Eds.) Images and Understanding: Thoughts About Images, Ideas
About Understanding. Cambridge University Press, Cambridge, UK, 26-45.

Goyal, R. and Egenhofer, M. (2000) Consistent Queries over Cardinal Directions acrossDifferent Levels of Detail. in: Tjoa, A. M., Wagner, R., and Al-Zobaidie, A. (Eds.) 11th
International Workshop on Database and Expert Systems Applications, Greenwich,

U.K, 876-880.
Graedel, T. and Crutzen, P. (1995) Atmosphere, Climate, and Change. W. H. Freeman andCompany, New York, NY.
Guarino, N. (1998) Formal Ontology in Information Systems. in: Guarino, N. (Ed.)
FOIS'98, Trento, Italy, 3-15, IOS Press.

Gyori, G. (2002) Semantic Change and Cognition. Cognitive Linguistics, 13(2): 123-166.
Hadzilacos, T. and Tryfona, N. (1992) Model for Expressing Topological Integrity
Constraints in Geographic Databases. in: Frank, A., Campari, I., and Formentini, U.
(Eds.) The International Conference GIS—From Space to Territory: Theories andMethods of Spatio-Temporal Reasoning in Geographic Space, New York, NY, Lecture

Notes in Computer Science, 639, 252-268, Springer.
Herring, J. (1991) The Mathematical Modeling of Spatial and Non-Spatial Information in
Geographic Information Systems. in: Mark, D. and Frank, A. (Eds.) Cognitive andLinguistic Aspects of Geographic Space. Kluwer, Dordrecht, Netherlands, 313-350.

152

Horn, R. (1998) Visual Language: Global Communication for the 21st Century. MacroVu,
Inc., Bainbridge Island, WA.
Hornsby, K. and Egenhofer, M. (1997) Qualitative Representation of Change. in: Hirtle, S.
and Frank, A. (Eds.) COSIT '97, Laurel Highlands, PA, Lecture Notes in Computer
Science, 1329, 15-33, Springer.
Hornsby, K. and Egenhofer, M. (1998) Identity-Based Change Operations for Composite
Objects. in: Poiker, T. and Chrisman, N. (Eds.) 8th International Symposium on
Spatial Data Handling, Vancouver, Canada, 202-213.

Hornsby, K. and Egenhofer, M. (2000) Identity-Based Change: A Foundation for
Spatio-Temporal Knowledge Representation. International Journal of Geographical
Information Science, 14(3): 207-224.

Hornsby, K., Egenhofer, M., and Hayes, P. (1999) Modeling Cyclic Change. in: Chen, P.,
Embley, D., Kouloumdjian, J., Liddle, S., and Roddick, J. (Eds.) Advances inConceptual Modeling, Paris, France, Lecture Notes in Computer Science, 1227,

98-109, Springer.
Johnson, M. (1987) The Body in the Mind: The Bodily Basis of Meaning, Imagination,
and Reason. The University of Chicago Press, Chicago.

153

Johnston, M. (1998) Unification-Based Multimodal Parsing. in: 17th International
Conference on Computational Linguistics and 36th Annual Meeting of the Association
for Computational Linguistics, Montréal, Canada, 624-630, Morgan Kaufmann

Publishers.
Jones, C. (1997) Geographical Information Systems and Computer Cartography.
Longman, Harlow, UK.
Kovecses, Z. and Radden, G. (1998) Metonymy: Developing a Cognitive Linguistic View.
Cognitive Linguistics, 9(1): 37-77.

Kurata, Y. and Egenhofer, M. (2005a) Semantics of Simple Arrow Diagrams. in:Barkowsky, T., Freksa, C., Hegarty, M., and Lowe, R. (Eds.) AAAI Spring Symposium
on Reasoning with Mental and External Diagram: Computational Modeling andSpatial Assistance, Stanford, CA, 101-104, AAAI Press.

Kurata, Y. and Egenhofer, M. (2005b) Structure and Semantics of Arrow Diagrams. in:
Cohn, A. and Mark, D. (Eds.) COSIT '05, Ellicottville, NY, Lecture Notes in Computer
Science, 3693, 232-250, Springer.
Kurata, Y. and Egenhofer, M. (2006a) The Head-Body-Tail Intersection for Spatial
Relation between Directed Line Segments. in: GIScience'06, Münster, Germany,
Lecture Notes in Computer Science, 4197, 269-286, Springer.

154

Kurata, Y. and Egenhofer, M. (2006b) Ontology-Based Interpretation of Arrow Symbols
for Visual Communication. in: Andrienko, G., Andrienko, N., Jankowski, P., andMacEachren, A. (Eds.) GIScience 2006 Workshop on Visualization, Analytics &Spatial Decision Support, Münster, Germany, CD-ROM.

Kurata, Y. and Egenhofer, M. (2006c) Topological Relations of Arrow Symbols in
Complex Diagrams. in: Barker-Plummer, D., Cox, R., and Swoboda, N. (Eds.)
Diagrams'06, Stanford, CA, Lecture Notes in Artificial Intelligence, 4045, 112-126,

Springer.
Kurtoglu, T. and Stahovich, T. (2002) Interpreting Schematic Sketches Using PhysicalReasoning. in: Davis, R., Landay, J., and Stahovich, T. (Eds.) AAAI Spring Symposium
on Sketch Understanding, Stanford, CA, 78-85, AAAI Press.

Lakoff, G. (1987) Women, Fire, and Dangerous Things: What Categories Reveal About
the Mind. University of Chicago Press, Chicago, IL.

Lakoff, G. and Johnson, M. (1980) Metaphors We Live By. University of Chicago Press,
Chicago, IL.
Landay, J. and Myers, B. (2001) Sketching Interfaces: Toward More Human Interface
Design. IEEE Computer, 34(3): 56-64.
Langacker, R. (1999) Grammer and Conceptualization. Mouton de Gruyter, Berlin,
Germany / New York, NY.

155

Larkin, J. and Simon, H. (1987) Why a Diagram Is (Sometimes) Worth Ten Thousand
Words. Cognitive Science, 11(1): 65-99.
Monmonier, M. (1990) Strategies for the Visualization of Geographic Time-Series Data.
Cartographica, 27(1): 30-45.

Moratz, R., Renz, J., and Wolter, D. (2000) Qualitative Spatial Reasoning About Line
Segments. in: Horn, W. (Ed.) 14th European Conference on Artificial Intelligence,
Berlin, Germany, 234-238, IOS Press.
Nedas, K., Egenhofer, M., and Wilmsen, D. (2007) Metric Details of TopologicalLine-Line Relations. International Journal of Geographical Information Science,21(1): 21-48.
Novak, G. (1995) Diagrams for Solving Physical Problems. in: Glasgow, J., Narayanan, N.
H., and Chandrasekaran, B. (Eds.) Diagrammatic Reasoning: Cognitive andComputational Perspective. AAAI Press, Stanford, CA, 753-774.

Oviatt, S. (1996) Multimodal Interfaces for Dynamic Interactive Maps. in: Conference on
Human Factors in Computing Systems (CHI '96), New York, NY, 95-102, ACM Press.

Oviatt, S. (1999) Mutual Disambiguation of Recognition Errors in a Multimodal
Architecture. in: Conference on Human Factors in Computing Systems (CHI '99),
Pittsburgh, PA, 576-583, AAAI Press.

156

Oviatt, S. and Cohen, P. (2000) Multimodal Interfaces That Process What Comes
Naturally. Communications of the ACM, 43(3): 45-53.
Peuquet, D. (1984) A Conceptual Framework and Comparison of Spatial Data Models.
Cartographica, 21(4): 66-113.

Pinker, S. (1990) A Theory of Graph Comprehension. in: Freedle, R. (Ed.) Artificial
Intelligence and the Future of Testing. Lawrence Erlbaum, 73-126.

Pullar, D. and Egenhofer, M. (1988) Towards Formal Definitions of Topological
Relations among Spatial Objects. in: 3rd International Symposium on Spatial Data
Handling, Sydney, Australia, 225-241.

Reiter, R. (1987) On Closed World Data Bases. in: Gallaire, H. and Minker, J. (Eds.)
Logic and Data Bases. Plenum Press, New York, NY, 55-76.

Renz, J. (2001) A Spatial Odyssey of the Interval Algebra: 1. Directed Intervals. in: Nebel,
B. (Ed.) International Joint Conference on Artificial Intelligence 2001, Seattle, WA,
51-56, Morgan Kaufmann.
Retz-Schmidt, G. (1988) Various Views on Spatial Prepositions. AI Magazine, 9(2):95-105.
Robinson, A., Morrison, J., Muehrcke, P., Kimerling, A., and Guptill, S. (1995) Elementsof Cartography. John Wiley & Sons Inc., New York, NY.

Sagan, C. and Sagan, L. (1972) A Message from Earth. Science, 175(4024): 881-884.
157

Sanna, A., Montrucchio, B., and Montuschi, P. (2000) A Survey on Visualization of
Vector Fields by Texture-Based Methods. Research Developments in Pattern
Recognition, 1(1): 13-27.

Schlaisich, I. and Egenhofer, M. (2001) Multimodal Spatial Querying: What People
Sketch and Talk About. in: 1st International Conference on Universal Access in
Human-Computer Interaction, New Orleans, LA, 732-736.

Schlieder, C. (1995) Reasoning About Ordering. in: Frank, A. and Kuhn, W. (Eds.)
COSIT '95, Lecture Notes in Computer Science, 988, 341-349, Springer.

Seto, K. (1999) Distinguishing Metonymy from Synecdoche. in: Panther, K.-U. andRadden, G. (Eds.) Metonymy in Language and Thought. John Benjamins, Amsterdam,
Netherland, 91-120.
Skubic, M., Blisard, S., Carle, A., and Matsakis, P. (2002) Hand-Drawn Maps for Robot
Navigation. in: Davis, R., Landay, J., and Stahovich, T. (Eds.) AAAI Spring
Symposium Technical Report, Stanford, CA, 140-147, AAAI Press.

Stahovich, T. (1997) Interpreting the Engineer's Sketch: A Picture Is Worth a Thousand
Constraints. in: Anderson, M. (Ed.) AAAI Fall Symposium on Reasoning withdiagrammatic Representations II, Stanford, CA, 31-38, AAAI Press.

Stenning, K. and Oberlander, J. (1995) A Cognitive Theory of Graphical and Linguistic
Reasoning: Logic and Implementation. Cognitive Science, 19(1): 97-140.

158

Tobler, W. (1981) Depicting Federal Fiscal Transfers. Professional Geographer, 33(4):419-422.
Tobler, W. (1987) Experiments in Migration Mapping by Computer. The American
Cartographer, 14(2): 155-163.

Tufte, E. (1990) Envisioning Information. Graphics Press, Cheshire, CT.
Tversky, B. (2000) Some Ways That Maps and Diagrams Communicate. in: Freksa, C.,
Brauer, W., Habel, C., and Wender, K. (Eds.) Spatial Cognition II: Integrating
Abstract Theories, Empirical Studies, Formal Methods, and Practical Applications,Lecture Notes in Computer Science, 1849, 72-79, Springer.
Tversky, B. (2001) Spatial Schemas in Depictions. in: Gattis, M. (Ed.) Spatial Schemas
and Abstract Thought. MIT Press, Cambridge, MA, 79-111.

Tversky, B., Heiser, J., Lozano, S., Mackenzie, R., and Morrison, J. (2007) Enriching
Animations. in: Lowe, R. and Schnotz, W. (Eds.) Learning with Animation: Researchand Implications for Design. Cambridge University Press, Cambridge, UK.

Tversky, B. and Lee, P. (1999) Pictorial and Verbal Tools for Conveying Route. in: Freksa,
C. and Mark, D. (Eds.) Spatial Information Theory, COSIT '99, Stade, Germany,
Lecture Note in Computer Sceince, 1661, 51-64, Springer.

159

Tversky, B., Zacks, J., Lee, P., and Heiser, J. (2000) Lines, Blobs, Crosses and Arrows:
Diagrammatic Communication with Schematic Figures. in: Anderson, M., Cheng, P.,
and Haarslev, V. (Eds.) Theory and Application of Diagrams (Diagrams 2000),
Edinburgh, UK, Lecture Notes in Artificial Intelligence, 1889, 221-230, Springer.
Van der Waarde, K. and Westendorp, P. (2000) The Functions of Arrows in User
Instructions. in: The IIID Expert Forum on Manual Design, Eskilstuna, Sweden.
Westendorp, P. (2006) Design & Evolution of the Symbolic Arrow. in: Design &Evolution Conference, Delft, Netherlands, Design History Society.

Wildbur, P. and Burke, M. (1998) Information Graphics: Innovative Solutions inContemporary Design. Thames & Hudson, New York, NY.

Worboys, M. and Duckham, M. (2004) GIS: A Computing Perspectinve. CRC Press,
Boca Raton, FL.
Worboys, M. and Hornsby, K. (2004) From Objects to Events: GEM, the Geospatial
Event Model. in: GIScience 2005.

160

BIOGRAPHY OF THE AUTHOR
Yohei Kurata was born in Yokohama, Japan, on December 28, 1977. He studied at the
University of Tokyo with a major of city planning and obtained a Gakushi-Kogaku(Bachelor of Engineering) in Urban Engineering from the University of Tokyo in 2000.
Around that time he developed his interest in spatial information systems, especiallythose for ordinary people, and wrote a bachelor’s thesis entitled “Development of aPreference-Based Tour Planning System.” He then began his master’s study in the

Department of Urban Engineering and obtained a Shushi-Kogaku (Master ofEngineering) in Urban Engineering from the University of Tokyo in 2002. His master’s
thesis, entitled “Methods for Modeling and Automatic Matching of Rough Maps,” evoked
his interest in sketching interfaces of spatial information systems. After attending thedoctoral course at the University of Tokyo for one semester, he moved to the Universityof Maine in 2002, where he began his doctoral study in spatial information science andengineering. Since 2005 he has served as a Graduate Research Assistant with the
National Center for Geographic Information and Analysis and was awarded the College
of Engineering’s Graduate Research Assistant Award in 2006. As the first author he has
published five papers in referred conference proceedings and one paper in Japanese
research journal.
Yohei Kurata is a candidate for the Doctor of Philosophy degree in Spatial
Information Science and Engineering from the University of Maine in May, 2007.

161