Diplomarbeit
High resolution indexing for CAD databases
Inhalt
The management of complex spatial objects in many non-standard database
applications, such as computer-aided design (CAD), imposes new requirements
on spatial database systems, in particular on efficient query processing.
In the past two decades various index structures have been proposed to
support this process. Recently, there has been an increasing awareness
that it is indispensable to integrate these index structures into fully-fledged
database systems.
In this master thesis a new spatial index is introduced, which supports
the intersect predicate on a data type TSpatialObject. This new access
method, called X-RI-tree, can easily be implemented on top of an object-relational
database management system, exploiting its extensible indexing framework.
Thus, fundamental services of underlying commercial database systems can
be fully reused, including transactions, concurrency control, and recovery.
The X-RI-tree is a multi step index for grey interval sequences, which
can be generated out of spatial objects via space filling curves. Each
of these grey intervals consists of an interval hull, aggregated information
of the grey interval, and a detailed attached black interval sequence.
This structure is reflected in the query process, which is based on three
consecutive filter steps. In a first filter step, all overlapping pairs
of grey database and query intervals are determined, by means of a slightly
altered RI-tree. In a second filter step a so called fast grey test is
used to determine intersecting intervals without examining the attached
interval sequences. In a last third filter step, an expensive BLOB test
is carried out, scrutinizing the attached interval sequences.
Ergebnis
Both the RI-tree and the X-RI-tree were implemented on top of an Oracle
Server Release 8.1.7, using PL/SQL for the computational main memory based
programming.
The experimental evaluation of a well parameterized X-RI-tree, compared
to the optimized version of the RI-tree, can be summarized as follows:
-
Using the X-RI-tree improves the secondary storage behavior at least by
an order of magnitude.
-
Using the X-RI-tree dramatically reduces the session footprint.
-
Using the X-RI-tree improves the response time of collision queries by
an order of magnitude.
-
Using the X-RI-tree improves the response time of box queries by an order
of several magnitudes, because the concept of grey intervals is especially
beneficial for top-down dynamically created query objects.
.
Personen
Downloads
paper (pdf 2.047 KB)
talk (ppt 1.269 KB)
Homepages: 
DBSInstitutLMU
21.02.2001, Marco Pötke
