Research Group Geoinformation

Home | Research | Publications | Download | Projects | Teaching | Staff

... to the Cartography Group

Mueller Rudi

Improving Spatial Access to Databases

1. Hypothesis

The Spatial Location Code in combination with a field-tree, as proposed by Oosterom and Vijlbrief in [1], in comparison with Quad-trees and Morton Numbers improves access to spatial databases.

2. Description

The thesis consists of two parts:
  • It should be possible to improve performance of spatial access to databases by using the field-tree and the Spatial Location Code in comparison with the traditional Quad-tree and Morton Numbers combination.
  • A model will be built using a functional language which checks for relations between Minimum Bounding Rectangles to prove the usefulness of the field-tree and Spatial Location Code combination.

The following sections provide a more detailed description of these tasks.

2.1 Spatial Location Code


Modern spatial databases, like ORACLE’s Spatial Data Option, use quad-trees to adaptively divide space into small segments, which contain geographic objects. These objects, or rather the cells, in which they are located, are numbered using Morton Numbers. Search keys use these numbers in a B*-tree. This B*-tree implements an index.

Substantive research has been done to improve this technique by using different indexing structures. We believe that modern databases implement indices very well. Especially concurrency problems, which usually arise in tree-structures used as indexing structures, are handled by modern database systems. We will prove that it is possible to improve the performance for spatial retrieval of modern spatial databases without altering their internal structure. We will replace the quad-tree and Morton-Numbers combination by a solution which uses a field-tree and the Spatial Location Code. This means, that we will not have to change the indexing structure. We provide the indexing B*-tree with a different set of location identifiers.

The Model

The goal of this part of the thesis is to build a model of a spatial database using the field-tree and the Spatial Location Code. This model will be realized in a functional language, most likely HASKELL.

This model will process objects which are to be stored in the database. These objects are inserted in the field-tree and assigned a Spatial Location Code. This code will then be stored in a B*-tree.

One important measurement for performance is disk and memory I/O. To achieve minimal I/O the objects of a given scene should be stored in a minimal number of leafs in the B*-tree. A reference model using quad-tree and Morton Numbers will be implemented to prove the increased performance.

2.2 Relations

The second goal of the thesis is to prove the usefulness of the Spatial Location Code by moving the test for relations between the stored objects away from the layer of Minimal Bounding Rectangles (MBR) to the layer of the Spatial Location Code. This means that a model will be built that tests for the various relations (e.g. object A inside object B) by comparison of the Spatial Location Code rather than by testing the MBRs as they are. See [2] for a description of the various relations.

To prove that this can be done, a model will be built in a functional language, most likely HASKELL. Spatial objects will be tested using the Spatial Location Code of their MBRs. There will be no direct comparison of the objects, therefore the implementation may result in "false hits". "False rejects" are nevertheless not permitted.


[1] Peter van Oosterom, Tom Vijlbrief, "The Spatial Location Code", SDH’96

[2] Dimitris Papadias, Times Sellis, Yannis Theodoridis, Max J. Egenhofer, "Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees", Management of data , 1995.

Powered by CMSimple