DOT: A Spatial Access Method Using Fractals

Existing Database Management Systems (DBMSs) do not handle efficiently multi-dimensional data such as boxes, polygons, or even points in a multi-dimensional space. We examine access methods for these data with two design goals in mind: (a) efficiency in terms of search speed and space overhead and (b) ability to be integrated in a DBMS easily. We propose a method to map multidimensional objects into points in a 1- dimensional space; thus, traditional primary-key access methods can be applied, with very few extensions on the part of the DBMS. We propose such mappings based on fractals; we implemented the whole method on top of a B+-tree, along with several mappings. Simulation experiments on several distributions of the input data show that a modified Hilbert curve gives the best results, even when compared to R-trees [7].