Titelaufnahme

Titel
A formal approach to implement dimension-independent spatial analyses / Farid Karimipour
VerfasserKarimipour, Farid
Begutachter / BegutachterinFrank, Andrew U. ; Kropatsch, Walter G.
Erschienen2011
UmfangXIII, 157 Bl. : Ill., graph. Darst.
HochschulschriftWien, Techn. Univ., Diss., 2011
SpracheEnglisch
Bibl. ReferenzOeBB
DokumenttypDissertation
Schlagwörter (DE)Multi-dimensional spatial analyses/ 3D spatial data/ Moving objects/ Abstraction/ Formal theories/ Algebraic structures/ Algebraic specifications/ Lifting/ Delaunay triangulation/ Voronoi diagrams/ Functional programming languages/ Haskell
Schlagwörter (EN)Multi-dimensional spatial analyses/ 3D spatial data/ Moving objects/ Abstraction/ Formal theories/ Algebraic structures/ Algebraic specifications/ Lifting/ Delaunay triangulation/ Voronoi diagrams/ Functional programming languages/ Haskell
Schlagwörter (GND)Geoinformationssystem / Raumdaten / Analyse / Formale Methode / Mehrdimensionalität
URNurn:nbn:at:at-ubtuw:1-40709 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
A formal approach to implement dimension-independent spatial analyses [2.06 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Extension of 2D spatial analyses to higher dimensions, e.g., 3D and temporal, is one of the requirements to handle real world phenomena in GIS. The current approach is to design a technical solution to extend a certain 2D spatial analysis to a new multi-dimensional space with the least increase in complexity and speed. This technical approach has resulted in developments that cannot be generalized. The result of following such an approach in the software development stage is recoding each spatial analysis, separately, for each dimension. Therefore, the code for a, say, general 2D/3D static and moving objects supporting GIS is nearly four times the current code size, offering four variants:

static 2D, moving 2D, static 3D, and moving 3D. The complexity of such a growth of code written in one of the currently popular programming languages is hard to manage, resulting in numerous bugs.

This thesis investigates spatial analyses based on their dimension independent characteristics, toward achieving a general solution. It intends to provide an integrated framework for spatial analyses of different multi-dimensional spaces a GIS should support. This framework will be independent of the objects to which the analyses are applied and spatial analyses are formally defined by combinations of the elements of this integrated framework.

To implement this approach, spatial analyses are formally expressed hierarchically where each analysis is defined as a combination of simpler ones. These definitions are independent of dimension and the hierarchy ends in a set of primary operations, which cannot be further decomposed. A set of required data types are also identified. Having implemented the dimensionally independent data types and operations, they all will be extended to a specific space (e.g., moving points) by applying the mappings.

The required abstraction of the proposed approach is the subject of algebra that ignores those properties of operations that depend on the objects they are applied to. The desired spaces are structurally equivalent, so they are described by the same algebra. Having implemented the required data types and operations, their extension to a specific space is viable by applying the (structure preserving) mapping.

The proposed approach has been evaluated through implementation of Delaunay triangulation for 2D and 3D static and moving points in the functional programming languages Haskell and their efficiency has been evaluated. The achieved results certify the hypothesis of the research says that "studying spatial analyses based on their dimension independent characteristics leads to a consistent solution toward implementation of a multi-dimensional GIS".

Complexity and speed are factors used to evaluate the performance of an extension technique in current research. However, the aim here is to avoid recoding each spatial analysis for each dimension.

Thus, the main concern of this research is on mathematical validation of the conceptual framework and investigation of its implementation issues.

Nevertheless, the results show that the proposed approach does not affect the big O complexity and speed for applying the spatial analyses on objects of higher dimensions.

Zusammenfassung (Englisch)

Extension of 2D spatial analyses to higher dimensions, e.g., 3D and temporal, is one of the requirements to handle real world phenomena in GIS. The current approach is to design a technical solution to extend a certain 2D spatial analysis to a new multi-dimensional space with the least increase in complexity and speed. This technical approach has resulted in developments that cannot be generalized. The result of following such an approach in the software development stage is recoding each spatial analysis, separately, for each dimension. Therefore, the code for a, say, general 2D/3D static and moving objects supporting GIS is nearly four times the current code size, offering four variants:

static 2D, moving 2D, static 3D, and moving 3D. The complexity of such a growth of code written in one of the currently popular programming languages is hard to manage, resulting in numerous bugs.

This thesis investigates spatial analyses based on their dimension independent characteristics, toward achieving a general solution. It intends to provide an integrated framework for spatial analyses of different multi-dimensional spaces a GIS should support. This framework will be independent of the objects to which the analyses are applied and spatial analyses are formally defined by combinations of the elements of this integrated framework.

To implement this approach, spatial analyses are formally expressed hierarchically where each analysis is defined as a combination of simpler ones. These definitions are independent of dimension and the hierarchy ends in a set of primary operations, which cannot be further decomposed. A set of required data types are also identified. Having implemented the dimensionally independent data types and operations, they all will be extended to a specific space (e.g., moving points) by applying the mappings.

The required abstraction of the proposed approach is the subject of algebra that ignores those properties of operations that depend on the objects they are applied to. The desired spaces are structurally equivalent, so they are described by the same algebra. Having implemented the required data types and operations, their extension to a specific space is viable by applying the (structure preserving) mapping.

The proposed approach has been evaluated through implementation of Delaunay triangulation for 2D and 3D static and moving points in the functional programming languages Haskell and their efficiency has been evaluated. The achieved results certify the hypothesis of the research says that "studying spatial analyses based on their dimension independent characteristics leads to a consistent solution toward implementation of a multi-dimensional GIS".

Complexity and speed are factors used to evaluate the performance of an extension technique in current research. However, the aim here is to avoid recoding each spatial analysis for each dimension.

Thus, the main concern of this research is on mathematical validation of the conceptual framework and investigation of its implementation issues.

Nevertheless, the results show that the proposed approach does not affect the big O complexity and speed for applying the spatial analyses on objects of higher dimensions.