Divided \(k-d\) trees (Q1180539)

The paper proposes a new dynamic data structure, the divided \(k-d\)-tree, supporting range queries in two and more dimensions. A modified version furthermore supports splits and concatenates in all dimensions. Exact match queries can be answered in time \(O(\log(n))\). The worst case complexity for the dynamic updates and the range query is up to a multiplicative factor of \(O(\log^{1/d})\) equal to that of the best known data structure for range queries in linear storage: the quad-tree and the \(k-d\)-tree; these structures are, however, not easy to maintain under inserts and deletes, and if they are made dynamic at all they can't be balanced and therefore the worst case search and update time can easily degrade. The structure, which is easiest explained for dimension 2, shares in its design the key idea from the original \(k-d\)-tree; at every level of the tree divide the nodes in the subtree according to one of the dimensions. But rather than letting the dimensions alternate as in the original \(k- d\)-tree, the dimension remains fixed till about half way down the tree; subsequently the other dimension is used. By carefully balancing the tree size at the intermediate level the polylog factor in the performance estimates of the structure is optimized. The generalization for dimensions \(d>2\) is straightforward. The structure is build from \(2-3\)-trees for which a well known efficient split-concatenate algorithm exists; this structure, with some modifications can be extended to make the devided \(k-d\)-tree concatenable in all dimensions with an update query time equal to the divided \(k-d\)- tree as described before.