Selection by rank in K‐dimensional binary search trees. Issue 1 (6th December 2012) - Duch, Amalia
Abstract In this work we show how to augment general purpose multidimensional data structures, such as K‐d trees, to efficiently support search by rank (that is, to locate the i‐th smallest element along the j‐th coordinate, for given i and j) and to find the rank of a given item along a given coordinate. To do so, we introduce two simple, practical and very flexible algorithms – Select‐by‐Rank and Find‐Rank – with very little overhead. Both algorithms can be easily implemented and adapted to several spatial indexes, although their analysis is far from trivial. We are able to show that for random K‐d trees of size n the expected number of nodes visited by Find‐Rank is Pn, i=Θ(n1−1/K) for i=o(n) or i=n−o(n), and Pn, i=fK(i/n)·nα+o(nα) for i=xn+o(n) (with 0<x<1), where 1−1/K≤α<1 depends on the dimension K and the variant of K‐d tree under consideration. We also show that Select‐by‐Rank visits gK(i/n)·nαlnn+O(nα) nodes on average, where i=xn+o(n) is the given rank and the exponent α is as above. We give the explicit form of the functions fK(x) and gK(x), both are bounded in [0, 1] and they depend on K, on the variant of K‐d tree under consideration, and, eventually, on the specific coordinate j for which we execute our algorithms. As a byproduct of the analysis of our algorithms, but no less important, we give the average‐case analysis of a partial match search in random K‐d trees when the query is not random. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 14–37, 2014