Design, Implementation and Preliminar Analysis of General Multidimensional Trees

OData support
Németh Krisztián
Department of Telecommunications and Media Informatics

In this thesis, a new multidimensional data structure for storing points in a multidimensional space is defined, implemented and then experimentally analyzed, the so-called q-kd tree.

This work starts with the summary of the background knowledge on the associative retrieval problem and on two well-known multidimensional data structures: the k-d trees and quad-trees, which are particular cases of this new data structure. This is followed by the definition of the q-kd tree and a proposition of two different heuristics: the so-called Split Tendency and the so-called Prob-of-1 that allow us to build what we call quasi-optimal q-kd trees and randomly-split q-kd trees.

Afterwards, we describe the development methodology of a software that allows us to experimentally analyze the space and time efficiency of our new data structure. In the software two kinds of q-kd trees are implemented together with random k-d trees and random quad-trees.

Based on the experimental results, we show that in the tested cases on one hand, k-d trees are more efficient in memory space than quad-trees, and on the other hand quad-trees are more efficient than k-d trees considering the internal path length.

The experiments also show that our variants of q-kd trees are in between quad-trees and k-d trees concerning the memory space and internal path length, and that by proper parameter settings it is possible to construct q-kd trees taylored to the space and time restrictions we can have. Therefore we can conclude that q-kd tree is a promising new data structure.


Please sign in to download the files of this thesis.