Quad-K-d Trees

We introduce the Quad-K-d tree (or simply QK-d tree) a hierarchical and general purpose data structure for the storage of multidimensional points, which is a generalization of point quad trees and K-d trees at once. QK-d trees can be tuned by means of insertion heuristics to obtain trade-offs between their costs in time and space. We propose three such heuristics and show analytically and experimentally their competitive performance. On the one hand, our analytical results back the experimental outcomes and suggest that QK-d trees could constitute a general framework for the study of inherent properties of trees akin to K-d trees and quad trees. On the other hand, our experimental results indicate that the QK-d tree is a flexible data structure, which can be tailored to the resource requirements of a given application.