Search

We introduce the quad-kd tree: a general purpose and hierarchical data structure for the storage of multidimensional points. Quad-kd trees include point quad trees and kd trees as particular cases and therefore they could constitute a general framework for the study of fundamental properties of trees similar to them. Besides, quad-kd trees can be tuned by means of insertion heuristics and bucketing techniques to obtain trade-offs between their costs in time and space. We propose three such heuristics and we show analytically and experimentally their competitive performance. Our analytical results back the experimental outcomes and suggest that the quad-kd tree is a flexible data structure that can be tailored to the resource requirements of a given application., Peer Reviewed, Postprint (author's final draft)

In this thesis, a new multidimensional data structure, the q-kd tree, for storing points lying in a multidimensional space is defined, implemented and experimentally analyzed. This new data structure has k-d trees and quad-trees as particular cases. The main difference between q-kd trees and either kd-trees or quad-trees is the way in which discriminants are assigned to each node of the tree. While this is fixed for kd-trees and quad-trees, it is variable for q-kd trees. We propose two different ways for assigning discriminants to nodes, the heuristics: Split Tendency and Prob-of-1. These heuristics allow us to build what we call quasi-optimal q-kd trees and randomly-split q-kd trees respectively. Experimentally we 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., Incoming