Qualitative Spatial Configuration Queries

This work is about human beings and Geographic Information Systems (GIS). More specifically, it introduces methods and techniques to foster natural interaction among the two; an interaction that becomes continuously more important as technological improvements bring GIS technology within general public's reach. A glaring example concerns, for instance, Volunteered Geographic Information projects that relies on the intervention of volunteers - i.e., not necessarily GIS experts - to build and share freely accessible spatial datasets.According to the current state of the art, there is a fundamental representational gap that, by hindering the coveted natural interaction, prevents non-experts from fully exploiting GIS power: if on the one hand human beings prefer to represent and reason about space in a qualitative manner, on the other hand, GIS mainly resort to quantitative representations. To bridge such a gap, a new typology of queries is presented in this work: Qualitative Spatial Relation Queries (QSRQ) involve spatial predicates defined in mathematical structures known as qualitative calculi. Such predicates provide both a computer-readable definition and a cognitively-adequate semantics to represent and reason about given spatial aspects - e.g., topology or direction. An extensible theoretical and practical framework is presented that allows for enabling QSRQ in GIS. Moreover, a classification of such queries is provided based on their solving complexity and the focus is shifted on the discussion of a new type of spatial access methods - Qualitative Spatial Access Methods (QSAM) - designed for resolving the hardest QSRQ category, termed Qualitative Spatial Configuration Queries. QSAM draw upon a qualitative spatial relation reduction/reconstruction paradigm in order to face the exponential explosion in the amount of information bits introduced by the qualitative formalism. Four different types of QSAM are presented, evaluated, and compared with respect to the space-time performance that they allow for reaching with both synthetic and real spatial datasets.