Improving Spatial Access to Databases
Spatial Location Code in combination with a field-tree, as proposed by
Oosterom and Vijlbrief in , in comparison with Quad-trees and Morton
Numbers improves access to spatial databases.
The thesis consists of two parts:
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
- 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
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.
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.
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.
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.
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
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  for a description of the various
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.
 Peter van Oosterom, Tom Vijlbrief, "The Spatial Location Code", SDH’96
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.