Scalable balanced k -d tree construction for distributed data

Abstract

k-d trees are fundamental data structures with wide-ranging applications in scientific computing, particularly in statistics and data science, including decision tree range search, clustering, nearest neighbor queries, and local regression. We introduce a scalable method for constructing k-d trees over distributed datasets that approximates the median for each recursive data split in a single pass. The resulting MapReduce algorithm achieves O(N) construction time and O(1) memory usage, making it well suited for deployment in distributed environments such as Spark. We establish theoretical bounds on the quality of the median approximations, and support our findings with simulation studies assessing both accuracy and scalability. We further demonstrate the utility of the approach through an application to distributed M-estimation in regression.