Adrijana Car
Department of Geomatics
University of Newcastle
Newcastle upon Tyne
Email: Adrijana.Car@ncl.ac.uk
Keywords: Hierarchical Spatial Reasoning, Spatial Information Theory, GIS
The main objective of the GeoComputation conference is to "…provide a forum for the discussion of emergent computer-based tools and techniques, and their application to spatial computation" (GeoComputation’98, Main Objectives, http://www.ggy.bris.ac.uk/geocomp). But, should every neural network application or cellular automata simulation be considered for GeoComputation? Catherine Dibble (personal communication) suggests to adopt computational Geographic Science as "…a much-needed conceptual framework for distinguishing advances in GeoComputation-methodologies from yet another application in computationally intensive techniques." In this paper we argue that Hierarchical Spatial Reasoning can be used as a GeoComputation-methodology to design conceptual spatial models using hierarchy as organizational principle. Moreover, we offer a method and tool to derive a formal model, and in turn, the computational one to study the problem(s) of interest.
Hierarchy is one of the most common forms of organizing and structuring complex systems. Spatial Information Science deals with spatial systems which are complex in nature. Research in Spatial Information Theory focuses on conceptualization of space, particularly on conceptual hierarchization of space and spatial phenomena. We understand spatial concepts as spatial objects and spatial relations arranged according to our experience and cognition (Couclelis and Gale 1986). Two issues related to the research on hierarchies and their use for spatial inference can be identified (Stephen Hirtle, personal communication):
The major part of the author’s research refers to the empirical issues. This paper offers a framework for research on hierarchies of space based on the general hierarchy theory (section 2), and how to use the gained knowledge to improve current spatial reasoning models in GIS or to design more appropriate ones. In particular, it examines the concepts of spatial hierarchies attempting to define their common structure and behavior (i.e., their ontology), and to identify methods for forming such hierarchies. The major outcome of this research is a common underlying theory of hierarchical spatial reasoning (section 3) together with a set of requirements on how to do such a reasoning. The term theory is used here in the natural scientist’s sense explaining observed regularities that are empirically testable.
One of the outcomes of this research, however, refers to the computational issues, i.e., to implement a conceptual model of hierarchical reasoning in a GIS. Formalization of conceptual spatial models bridges the gap between conceptual models and their successful implementation for the following reasons: (1) it helps to understand the underlying theory and structure, i.e., to describe the meaning of the data and the model (Dibble 1996), and (2) it provides a basis for comparison of similar models (Mark and Frank 1989; Egenhofer and Mark 1995; Mark and Frank 1996). An example illustrates an application of the hierarchical spatial reasoning to model wayfinding. It shows how a particular type of hierarchy is used for spatial reasoning (section 4). We discuss the formalization method and tool briefly, as sufficient background information is available in the cited literature (e.g. for formal specification written in a functional language Gofer is extensively described in a series of papers compiled by Frank et al. (1997)). In section 5 we give conclusions and suggest directions for future work.
Hierarchy is one of the most common forms of organizing and structuring complex systems where a system is subdivided in smaller subsystems, and further subdivision of subsystems can be recursively repeated as long as the subdivision makes sense (Koestler 1967). Such a hierarchical structure can be represented as a tree whose leaves represent the system components. A hierarchy consists of levels each representing a subset of objects selected from the initial set according to some criteria. The number of levels determines the depth of the hierarchy. The number of objects on each level determines its span, and in turn, the span of the hierarchy tree.
Each of these components has local and global properties. Local properties are properties of a level per se, determining objects which belong to a particular hierarchical level. A local property depends on a context in which a hierarchy is introduced (e.g., population size is useful as a criterion for introducing hierarchy of cities, countries or regional centers, but it is less useful when dealing with road classification). Global properties are independent of the system’s nature. They describe general structure of a hierarchy such as:
Koestler further suggests a rough classification of hierarchies into structural and functional hierarchies. The first emphasizes the spatial aspect of a system (a structure of the spatial domain) whereas the second focuses more on a process as another aspect. These classes tend to overlap even though the aspects are complementary aspects of an indivisible spatio-temporal process. Therefore, it is often useful and necessary to focus on just one of these aspects in order to successfully solve a task at hand.
Hierarchical Spatial Reasoning (HRS) is a method of spatial problem solving that uses hierarchy to infer spatial information and draw conclusions (Car 1997). Hierarchy, as an abstraction mechanism, is used to decrease the cognitive load in two major ways: to reduce the complexity of the problem domain by cutting down the problem space, or it can be used as a divide and conquer method where a problem is divided in smaller parts and then solved. Both strategies result in an efficient problem solving because only the necessary data is processed, usually in a shorter period of time.
One of the outcomes of this research is the requirements for hierarchical spatial reasoning, which state how to perform such a reasoning. The following must be given (Car and Frank 1994):
The method of hierarchization may provide non-optimal and/or incorrect results, or even generate these slower. For example, Shapiro, Weixman and Nir (1992) proposed a graph with an imposed hierarchical structure, and an adequate, simple heuristic shortest path search. The calculated paths were 40-50% longer than the optimal paths, thus suboptimal solutions have been produced. Therefore, the last two requirements have been added to the set, and can be understood as quality control of hierarchical reasoning.
A number of cognitive studies have shown the evidence that people may reason hierarchically in geographic space (Hirtle and Jonides 1985; McNamara, J. K. Hardy and Hirtle 1989). People often use approximate reasoning either to compensate for missing information or to simplify reasoning by using only information that is needed (Fotheringam 1992). To account for such reasoning, hierarchical algorithms, which approximate the strict results, are also of interest. Thus, we can say that hierarchical spatial reasoning follows patterns of human cognition, as it computes approximations. The rising question then is What is a good enough solution? rather than What is the optimal or strict result? This is similar to the economics term satisficing which is used when something is "good enough". The idea in economics is that people might look around for alternatives until they are (merely) satisfied, which is not quite the same as looking harder for the "optimal" alternative (Simon 1979). Thus, we can talk about satisficing versus optimizing solutions. An example addressing this issue is found in (Timpf and Frank 1997) showing that HSR can compute increasingly better results and stops the computation when the good enough result is achieved.
Classification. Considering the classification of hierarchies suggested by Koestler, we distinguish 2 types of spatial hierarchies (Table 1): functional spatial hierarchies are based on a task-subtask division and are useful for modeling spatial processes (e.g., Kuipers’ semantic hierarchy of robot’s movement or landscape modeling (Lavers and Haines-Young 1993)); structural spatial hierarchies consider subdivision of a spatial domain resulting in hierarchies of points, lines and areas.
| Functional
hierarchies (process: task - subtask) |
Structural
hierarchies (subdivision of spatial domain) |
| a subtask ˜ one level of hierarchy | a subset of data ˜ one level of hierarchy |
| different levels => different ontologies | different
levels => the same ontology but different amount of detail |
Table 1: Classification of Spatial Hierarchies
Hierarchization methods. At least two different methods to derive a spatial hierarchy emerged from analysis of hierarchies for spatial reasoning:
In both cases operations have been defined, describing criteria for selecting spatial objects into subsets, each of which represents different hierarchical levels.
Structural Hierarchies. In a structural hierarchy spatial objects are usually organized in levels such that each level contains the same type of objects interacting in the same way among themselves. That is, ontology is the same for each level. The levels differ only in the degree of detail. It is meaningful to consider hierarchies of geometric primitives, i.e., points, lines and areas (Coffey 1981), as many spatial concepts like Euclidean geometry, cell topology or graphs are based on their structure, properties and relationships. Typical examples for such hierarchies are quadtrees (Samet 1984), HTINs (De Floriani and Puppo 1992), triacons or quaternary triangular meshes (Dutton 1996), graph-subgraph subdivisions, or fractals (Batty and Longley 1994).
Structural hierarchy often refers to the granularity of the representation. Hernandez (1991), for example, discusses a model for qualitative spatial reasoning using levels with different granularity for projection and orientation (e.g.: level 0 = no orientation information; level 1 = (a) back, (b) left, right, front; level 2 = back, front, left, right; level 3 = back, front, left, right, left-back, right-back, left-front, right-front). Cohn (1995) considers the problem of representing the shape of a region, qualitatively, within a logical theory of space. He uses just two primitive notions, that of two regions connecting, and the convex hull of a region, to distinguish various concave shapes. By applying the technique recursively to the inside of a region, Cohn achieves a hierarchical representation at varying levels of granularity. Glasgow (1995) uses hierarchization in spatial planning. In these examples reasoning becomes simpler on levels with fewer details.
Research on HSR involves also formal description of functions or operations that form a hierarchy, that is, methods to transform a nonhierarchical structure into a hierarchical one (see section 3.1). For example, Frank and Timpf (1994) examine the idea of the intelligent zoom which implies that more details about objects become visible with the increasing scale and restricted display view. To achieve this zoom operation ability, they employ a hierarchical tree-like structure to store scale-dependent representations of objects from cartographic maps. Timpf further investigates how to link map objects at different levels of detail that represent the same real-world objects (1998) and proposes a hierarchical data structure that supports and describes the behavior of map objects at multiple levels. The hierarchical structure is a composition of three different types of hierarchies defined according to the functions of generalization, aggregation and filtering. The formal specification is available as the Gofer code.
Another example comes from cognitive linguistics and is given by Habel (1991; 1994; 1995). Habel proposes a hierarchical system of granularity levels as an adequate means of mental representations of space and time. He suggests that different levels of granularity of spatial memory are connected by specific operations such as embedding, which allow for building up increasingly refined representations. For example, mental images in spatial memory are connected through embedding, which allows for changing of their scale. In the case of time, the refinement operation splits the events. In these examples a hierarchical system has proven useful as a finite representation of a spatio-temporal continuum. Formal logic is used to formally describe the system.
Functional hierarchies are based on task decomposition. A subtask represents one level of hierarchy. Usually each of the subtasks requires different types of spatial objects with different interaction among them. Consequently, each level is expected to have different ontology. In case of functional hierarchies, a hierarchization method usually starts with the more general task and ends at the specific task level. This corresponds to the top-down hierarchization method.
A multilevel highway navigation (Timpf et al. 1992) is an example of a functional hierarchy. Its conceptual model consists of the Planning level, Instructional level, and Driving level each describing a subtask in planning and navigating a journey. The most general level is the planning task that involves a highway network consisting of highways, places and interchanges. The next lower level provides sufficient instruction information for navigating such as entrances and exits. The lowest level describes the objects and actions necessary to drive a vehicle according to the instructions. The full formal specification is available in (Timpf 1992).
Another example of a functional hierarchy is Kuipers famous semantic hierarchy of robot’s movement (Kuipers and Levitt 1988; Kuipers and Byun 1991; Kuipers et al. 1993) consisting of Control, Procedural, Topological to Metric level. Each of these levels has different ontology, describing different levels of information needed to move around. For example, places, paths and regions on the topological level, linked by topological relations such as connectivity, order and containment, create a topological map of space. The same types of objects on the metrical level, linked by metric relations such as distance, direction, or shape, provide metric information for movement such as amount of rotation and travel distance. Transitions of objects and actions from one level to objects and actions on another level are described by a set of rules.
In this section we give an example in which a method of hierarchical spatial reasoning has been applied to model wayfinding in a hierarchically structured network (Car and Frank 1994; Car 1998). First we describe the design steps, and the give a brief overview of the modeling and formalization methods used.
The modeling method used here is known as conceptual modeling. Conceptual modeling is modeling of real-world situations on a higher level of abstraction, before a detailed logical and physical design takes place (Brodie, Mylopoulos and Schmidt 1984). Conceptual models provide the description of space that is closer to human conceptualization and its semantics. They communicate the formalized ideas of space and as such enhance communication between domain expert, system designer and end-user. Research on conceptual modeling, particularly developing suitable methods for specification of large, complex models requires further efforts.
A formalization method introduced here uses object orientation as a design method, formal specifications, and a functional programming language as a specification and prototyping (Car and Frank 1997). The object-oriented approach has been accepted as appropriate to modeling complex data structures and hierarchically organized knowledge domains. Software engineering proposes object orientation as a design method (Khoshafian and Abnous 1990) because there is a strong correspondence between the idea to model both the structure of an object and its behavior and the way humans build classes of similar objects according to their experience (Lakoff 1987). The main concern of the introduction of the object-oriented method for modeling spatial data in GIS applications is the attempt to capture more semantics than the existing data models do (Egenhofer and Frank 1992; Worboys 1994). In a relational data model, for example, all data is represented in tabular form, whereas the object-oriented model considers complex objects as individual units with certain behavior (see, for example, (Herring 1991; Mainguenaud 1995)).
Formal specifications support object-oriented design because of their ability to describe the structure of objects and operations applicable to them. The formal specifications method combines the advantages of data abstraction with an axiom-based (mathematical) method to describe semantics (Guttag, Horowitz and Musser 1978). Denotational semantics (Stoy 1977) show how to use mathematical methods to describe semantics, which is a direct link to functional programming (Frank and Kuhn 1995). Formal specifications and functional programming languages are based on similar mathematical theories and use similar syntax.
Functional programming languages (Bird and Wadler 1988) allow to formally check specifications, and to observe if the specifications capture the intended behavior. The executable code is treated as a prototype. A prototype is expected to show if the implementation is possible and if a formal model behaves as expected. The functional language Gofer (Jones 1994) is used as the specification language. In Gofer it is possible to describe abstract behavior of objects, to construct specific objects, and describes how they achieve the intended behavior. The code produced by a functional programming language is clearly readable, and allows for the insight to be gained from reading or writing specifications. Gofer enables specification and prototyping that are integrated in a single and easy to use environment.
This is a contribution to the research on the development of suitable methods for specifications of large, complex systems.
The conceptual modeling method is used to model hierarchical wayfinding. The conceptual model of hierarchical wayfinding is based on the proposed theory of hierarchical spatial reasoning. The model describes the hierarchical structure of a road network and explains how the reasoning process progresses on such a structure. The tools used are graph theory, object orientation, algebraic specifications and functional programming.
According to the requirements of the hierarchical spatial reasoning, the conceptual modeling process consists of the following major steps: First, a model for the nonhierarchical case is designed. It includes a model of a road network at only one level of representation and a shortest path algorithm. Second, a hierarchical structure is introduced and a set of rules is given stating how the algorithm determines the shortest path in such a structure. In the third step results achieved by the hierarchical algorithm will be analyzed and compared to the results achieved by the nonhierarchical algorithm. In the last step the performance of the hierarchical algorithm is analyzed and compared to the performance of the nonhierarchical algorithm.
The nonhierarchical case. We start with specifying a generic graph based on which a bidirectional, weighted, and hierarchical graph are then built. As an application of it, we give a specification of a road network for the nonhierarchical and hierarchical case. Such graphs can then be used for the shortest path determination. The following assumptions are made about the graph in order to preserve the simplicity of the model:
A road network can be seen a special case of a bidirectional graph, which in turn, is a special case of a generic graph. To derive a formal model of such a road network, the generic graph has to be specified first. A road network is also a weighted graph, which requires introduction of weights.
The complete set of objects is collected and brought together into an ontology. An ontology is an abstracted, idealized model of reality containing only those objects, relations among them, and rules that govern them, which are of interest in a particular reasoning system being designed (Davis 1990). These objects, i.e., their structure and behavior, are then formalized with the help of formal specifications.
The best known algorithm for shortest paths determination is Dijkstra’s algorithm (Dijkstra 1959). This algorithm determines the lengths of the shortest paths between the given node and any other node in a graph. The original implementation of Dijkstra’s algorithm runs in O(n2) time, n being a number of nodes in a graph. This is the optimal running time for a fully dense graph (i.e., a graph where relatively few of the possible edges are missing (Sedgewick 1983)). Improvements of the running time can be achieved through different implementations (Ahuja, Thomas L. Magnanti and Orlin 1993): e.g., using adjacency lists.
The hierarchical case. The ontology for the nonhierarchical case is enriched by hierarchical levels. A bottom-up operation based on the road classification criterion, extracts a subgraph from the basic graph creating a structural hierarchy. The lowest level contains the entire network. Thus, the ontology contains the objects node, edge, graph and level.
The hierarchical algorithm is a nonhierarchical algorithm -- Dijkstra’s algorithm --enriched by a set of rules how to process a hierarchical structure. Dijkstra’s algorithm determines the shortest path in a single level. A set of rules states which part of the graph to use, when to switch between the levels, and how to combine single-level, partial results into a complete solution. The underlying idea of the hierarchical algorithm is the stepwise reduction of the initial graph causing the flat algorithm to operate on a subgraph. The improvement of the running time is, therefore, achieved by reducing the size of the graph, and this is enabled through the hierarchical structure of the network.
We have shown that the strategy of hierarchical subdivision of graphs improves the performance of the standard, nonhierarchical shortest path algorithm. The hierarchical algorithm is formally described, which allows to see how such algorithms are structured in general (i.e., nonhierarchical algorithm, hierarchical structure, rules to process the levels). From the formal description further properties of the hierarchical wayfinding can be derived (e.g., that wayfinding occurs in a subgraph, which in turn, corresponds to the human wayfinding).
The impact of this research on hierarchy and its use for modeling is quite large. The applied methods and results provide better insight into the theory of HSR. The major contribution to the theory is in combining advances in human knowledge and representation, and hierarchical reasoning with classical wayfinding algorithms. The theory is expected to be useful in cases where large datasets or incomplete spatial information needs processing. In-car navigation is such a case.
The method of formalization used here has proven useful, particularly to define objects in a conceptual model (i.e., their structure and operations). Gofer, as a specification tool, produced executable specification, which adds a new aspect to the formalization for the GIS purposes. Gofer-specifications were relatively easy to write and read, which was helpful in checking syntax. Executable code enabled immediate testing, i.e., prototyping; we were able observe the behavior of the model.
A formal specification of the model is available in form of a code written in the functional language Gofer and its full version can be found (Car 1997). The model was tested using theoretical data in order to test its captured behavior. Results so far confirm the validity of the conceptual model designed in this study.
Hierarchy is a powerful mechanism for dealing with complex spatial systems as it reduces the cognitive load and speeds up the reasoning process. Understanding of basic concepts of spatial hierarchies is, therefore, crucial in the design of conceptual models of space. In this paper we suggested a framework for developing concepts of spatial hierarchies and their use for spatial reasoning, which is based on the general hierarchy theory. In particular, we argued that Hierarchical Spatial Reasoning can be understood as a GeoComputation-methodology for the following reasons:
In fact, it offers a new playground for testing the model using theoretical data first. The expected results are, for example, various parameters of the model. Once the model has been proved as valid, we can then apply it to solve real-world problems, and adjust it further if necessary.
An interesting and still open question considers the notion of satisficing results produced by hierarchical spatial reasoning. Can we measure the goodness of a result? If so, what are the good candidates? Are they related to a particular application, or are they application-independent? For example, if a hierarchical algorithm is used to determine the shortest path is in a network, a tolerance for an acceptable difference between the optimal solution and the hierarchical one can be a percentage of the length of the shortest edge in a graph or of the length of an average edge size, length of a car (in-car navigation), etc..
Another research direction is related to scale as one of the fundamental yet poorly defined concepts in Geographic Science ((Goodchild and Proctor 1997; Quattrochi and Goodchild 1997), for further information visit also http://www.ncgia.ucsb.edu/varenius/scale/). We think that hierarchy and scale are related issues, and therefore, posit a hypothesis that the basic concepts of spatial hierarchies can be used to define basic concepts of scale. This hypothesis is based on the assumption that the scale is a consequence of hierarchization (Car 1998). The idea is to analyze the existing concepts of scale following the aspects of the concepts of spatial hierarchy. The proposed framework is an analogy to the application of the general hierarchy theory to the hierarchies of space. The expected outcome is a derivation of the underlying common structure (elements and properties) of scale and its classification.
Ahuja, R. K., Thomas L. Magnanti and J. B. Orlin (1993). Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs, NJ, Prentice Hall.
Batty, M. and P. Longley (1994). Fractal Cites: A Geometry of Form and Function. London, Academic Press Limited.
Bird, R. and P. Wadler (1988). Introduction to Functional Programming. Hemel Hempstead (UK), Prentice Hall International.
Brodie, M. L., J. Mylopoulos and J. W. Schmidt, Eds. (1984). On Conceptual Modelling, Springer-Verlag.
Car, A. (1997). Hierarchical Spatial Reasoning: Theoretical Consideration and its Application to Modeling Wayfinding. Vienna, Austria, Dept. of Geoinformation, Technical UniversityVienna, published Ph.D. thesis.
Car, A. (1998). Hierarchical Wayfinding - A Model and its Formalization. In Geographic Information Research: Transatlantic Perspectives. Craglia, M. and H. Onsrud. London, Taylor & Francis.
Car, A. (1998). Hierarchy and Scale - Research proposal. NCGIA-Varenius meeting on Scale and Detail in Cognition of Geographic Information in Santa Barbara, CA, 14-16 May 1998.
Car, A. and A. Frank (1997). "Formalisierung konzeptioneller Modelle für GIS - Methode und Werkzeug." Zeitschrift für Vermessungswesen 122(3): 99-114.
Car, A. and A. U. Frank (1994). General Principles of Hierarchical Spatial Reasoning - The Case of Wayfinding. Spatial Data Handling (SDH 94), Edinburgh, Scotland, T.C. Waugh, the IGU Commission on GIS, and the Association for Geographic Information.
Car, A. and A. U. Frank (1994). Modelling a Hierarchy of Space Applied to Large Road Networks. In IGIS'94: Geographic Information Systems. International Workshop on Advanced Research in GIS. Monte Verita, Ascona, Switzerland. Nievergelt, J., Thomas Roos, Hans-Jörg Scheck and P. Widmayer. Berlin, Heidelberg, New York, Springer-Verlag. 884: 15-24.
Coffey, W. J. (1981). Geography: Towards a General Spatial Systems Approach. London, New York, Methuen Co.
Cohn, A. G. (1995). A Hierarchical Representation of Qualitative Shape Based on Connection and Convexity. In Spatial Information Theory-A Theoretical Basis for GIS. Frank, A. U. and W. Kuhn. Berlin-Heidelberg-New York, Springer. 988: 311-326.
Couclelis, H. and N. Gale (1986). "Space and spaces." Geografske Annaler(68B): 1-12.
Davis, E. (1990). Representations of Commonsense Knowledge. San Mateo, California, Morgan Kaufmann Publishers.
De Floriani, L. and E. Puppo (1992). A Hierarchical Triangle-Based Model for Terrain Description. In Theories and Methods of Spatio-Temporal Reasoning in Geographic Space. Frank, A. U., I. Campari and U. Formentini. Berlin Heidelberg, Springer-Verlag. 639: 236-251.
Dibble, C. (1996). Theory in a Complex World: Agent-Based Simulations of Georgaphic Systems. First International Conference on GeoComputation, 17-19 September 1996, Leeds, UK.
Dijkstra, E. W. (1959). "A note on two problems in connection with graphs." Numerische Mathematik(1): 269-271.
Dutton, G. (1996). "Improving location specificity of map data - a multi-resolution, metadata-driven approach and notion." International Journal of Geographical Information Systems 10(3): 253-268.
Egenhofer, M. J. and A. U. Frank (1992). "Object-Oriented Modeling for GIS." URISA Journal 4(2): 3-19.
Egenhofer, M. J. and D. M. Mark (1995). Naive Geography. In Spatial Information Theory-A Theoretical Basis for GIS. Frank, A. U. and W. Kuhn. Berlin-Heidelberg-New York, Springer. 988: 1-15.
Fotheringam, A. S. (1992). Encoding Spatial Information: The Evidence for Hierarchical Processing. In Theories and Methods of Spatio-Temporal Reasoning in Geographic Space. Frank, A. U., I. Campari and U. Formentini. Berlin Heidelberg, Springer Verlag. 639: 269-287.
Frank, A. and S. Timpf (1994). "Multiple Representations for Cartographic Objects in a Multi-Scale Tree - An Intelligent Graphical Zoom." Computers and Graphics, Special Issue on Modelling and Visualization of Spatial Data in GIS 18(6): 823-829.
Frank, A. U. and W. Kuhn (1995). Specifying Open GIS with Functional Languages. In Advances in Spatial Databases (SSD'95). Egenhofer, M. J. and J. R. Herring. Portland, Maine, Springer-Verlag. 951: 184-195.
Frank, A. U., W. Kuhn, W. Hölbling, et al. (1997). Gofer as used at GeoInfo/TU Vienna, Dept. of Geoinformation, Technical University Vienna.
Glasgow, J. (1995). A Formalism for Model-Based Spatial Planning. In Spatial Information Theory-A Theoretical Basis for GIS. Frank, A. U. and W. Kuhn. Berlin-Heidelberg-New York, Springer. 988: 501-518.
Golledge, R. G. (1992). Do People Understand Spatial Concepts: The Case of First-Order Primitives. In Theories and Methods of Spatio-Temporal Reasoning in Geographic Space. Frank, A. U., I. Campari and U. Formentini. Berlin Heidelberg, Springer-Verlag. 639: 1-21.
Goodchild, M. and J. Proctor (1997). "Scale in a Digital Geographic World." Geographical & Environmental Modelling 1(1): 5-23.
Guttag, J. V., E. Horowitz and D. R. Musser (1978). The Design of Data Type Specifications. In Current Trends in Programming Methodology: Vol. 4 - Data Structuring. Yeh, R. T. Englewood Cliffs, New Jersey, Prentice-Hall, Inc.: 60-79.
Habel, C. (1991). Hierarchical Representations of Spatial Knowledge: Aspects of Embedding and Granularity. Second International Colloquium on Cognitive Science, San Sebastian, 7-11 May 1991.
Habel, C. (1994). Discretness, Finiteness, and Structure of Topological Spaces. In Topological Foundation of Cognitive Science. Papers from the Workshop at the FISI-CS, Buffalo, NY, July 9-10, 1994. Eschenbach, C., C. Habel and B. Smith. Hamburg, Graduiertenkolleg Kognitionswissenschaft Hamburgh. Report 37: 81-90.
Habel, C. (1995). Representing Space and Time: Discrete, Dense or Continuous? - Is that the Question? In Parts and Wholes - Integrity and Granularity. Eschenbach, C. and W. Heydrich. Hamburg, Graduiertenkolleg Kognitionswissenschaft Hamburgh. Report 49: 97-107.
Hernandez, D. (1991). Relative Representation of Spatial Knowledge: The 2-D Case. In Cognitive and Linguistic Aspects of Geographic Space. Mark, D. and A. Frank. Dordrecht, Boston, London, Kluwer Academic Press: 373-385.
Herring, J. (1991). "TIGRIS: A data model for an object-oriented geographic information system." Computers and Geosciences 18: 443-452.
Hirtle, S. C. and J. Jonides (1985). "Evidence of Hierarchies in Cognitive Maps." Memory & Cognition 13(3): 208-217.
Jones, M. P. (1994). The Implementation of the Gofer Functional Programming System, Yale University.
Khoshafian, S. and R. Abnous (1990). Object Orientation - Concepts, Languages, Databases, User Interfaces. New York, NY, John Wiley & Sons.
Koestler, A. (1967). The Ghost in the Machine. London, Pan.
Kuipers, B. and T. S. Levitt (1988). "Navigation and Mapping in Large-Scale Space." AI Magazine 9(2): 25 - 43.
Kuipers, B., R. Froom, W-Y. Lee, et al. (1993). The Semantic Hierarchy in Robot Learning. In Robot Learning. Connell, J. and S. Mahadevan. Dordrecht, Boston, London, Kluwer Academic: 1-24.
Kuipers, B. J. and Y.-T. Byun (1991). "A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations." Robotics and Autonomous Systems 8(8): 17.
Lakoff, G. (1987). Women, Fire, and Dangerous Things: What Categories Reveal About the Mind. Chicago, The University of Chicago Press.
Lavers, C. and R. Haines-Young (1993). Spatial Heterogenity and New Technology. In Landscape Ecology and GIS. Haines-Young, R., D. Green and S. Cousins. London, Taylor & Francis: 57-74.
Mainguenaud, M. (1995). "Modelling the Network Component of Geographic Information Systems." International Journal of Geographical Information Systems 9(6): 575-593.
Mark, D. M. and A. U. Frank (1989). Concepts of Space and Spatial Languages. AUTO-CARTO 9, Ninth International Symposium on Computer-Assisted Cartography, Baltimore, MD, American Society for Photogrammetry and Remote Sensing and American Congress on Surveying and Mapping.
Mark, D. M. and A. U. Frank (1996). "Experiential and Formal Models of Space." Environment and Planning B: Planning and Design 23: 2-24.
McNamara, T. P., J. K. Hardy and S. C. Hirtle (1989). "Subjective Hierarchies in Spatial Memory." Journal of Environmental Psychology: Learning, Memory, and Cognition 15(2): 211-227.
Palmer, E. S. (1977). "Hierarchical Structure in Perceptual Representation." Cognitive Psychology(9): 441-474.
Quattrochi, D. and M. Goodchild, Eds. (1997). Scale in Remote Sensing and GIS. Boca Raton, CRC Press Inc., Lewis Publishers.
Samet, H. (1984). "The Quadtree and Related Hierarchical Data Structures." ACM Computing Surveys 16(2): 187-260.
Sedgewick, R. (1983). Algorithms, Addison-Wesley Publishing Company, Inc.
Shapiro, J., J. Waxman and D. Nir (1992). "Level Graphs and Approximate Shortest Path Algorithms." Networks 22: 691-717.
Simon, H. A. (1973). The Organization of Complex Systems. In Hierarchy Theory. Pattee, H. New York, Braziller: 1-27.
Simon, H. A. (1979). Rational Choice and the Structure in the Environment. In Models and Thought. Volume 1 (Chapter 1.2): 20-28.
Stoy, J. (1977). Denotational Semantics. Cambridge MA, MIT Press.
Timpf, S. (1992). Conceptual Modelling of Highway Navigation. Master Thesis, University of Maine, USA,
Timpf, S. (1998). Hierarchical Structures in Map Series. Ph.D. thesis, Dept. of Geoinformation, Technical University Vienna, Vienna.
Timpf, S. and A. U. Frank (1997). Using Hierarchical Spatial Data Structures for Hierarchical Spatial Reasoning. In Spatial Information Theory - A Theoretical Basis for GIS (International Conference COSIT'97). Hirtle, S. C. and A. U. Frank. Berlin-Heidelberg, Springer-Verlag. 1329: 69-83.
Timpf, S., G. S. Volta, D. W. Pollock, et al. (1992). A Conceptual Model of Wayfinding Using Multiple Levels of Abstraction. In GIS - from Space to Theory: Theories and Methods of Spatio-Temporal Reasoning. Frank, A. U., I. Campari and U. Formentini. Berlin Heidelberg, Springer-Verlag. 639: 348-367.
Worboys, M. F. (1994). "Object-Oriented Approaches to Geo-Referenced Information." International Journal for Geographical Information Systems 8(4): 385-399.