Building a Balanced k-d Tree in O(kn log n) Time

1. INTRODUCTION

• Because successive k-d tree levels use different coordinate keys, AVL- and red-black-tree rebalancing cannot build a balanced k-d tree.The typical alternative is to find the median at every recursive subdivision; Bentley showed that linear-time median finding would yield O(n log n) construction, and Blum et al. gave a guaranteed O(n) algorithm [6].Source: §1 · p. 1
• Merge sort and heap sort find a median in guaranteed O(n log n) time, leading to O(n log^2 n) balanced-tree construction.Quicksort has O(n) best-case median finding but O(n log n) worst-case complexity.Source: §1 · p. 1
• Presorting each dimension and maintaining those sorted orders during construction avoids further sorting and guarantees O(kn log n) worst-case complexity.The paper notes that a similar-looking prior algorithm appears in Procopiuc et al. [14].Source: §1 · p. 1

2.1 The O (kn log n) Algorithm

• Three merge sorts order index arrays by cyclic super keys x:y:z, y:z:x, and z:x:y, leaving the tuples array unchanged.The colon denotes concatenation of coordinate values; the first coordinate named is the most significant part of the super key.Source: §2.1 · pp. 1–2
• At each split, the median in the already sorted array selects the pivot while the other index arrays are partitioned, preserving their sorted order and avoiding further sorting.The index corresponding to the median tuple is omitted from the child arrays, and recursion constructs the less-than and greater-than subtrees.Source: §2.1 · pp. 2–3
• Super-key ordering makes identical tuples contiguous, so duplicates can be removed in one pass through each sorted index array.The tree has less-than and greater-than children but no equal child; the super keys ensure identical tuples are adjacent in each index array.Source: §2.1 · p. 3
• Reusing the index arrays cyclically requires copying one index array at each recursion level and avoids allocating new index arrays at every level.The implementation also requires a temporary index array; its overall stated complexity is O(kn log n).Source: §2.1 · pp. 3–4

2.2 Parallel Execution

• The parent thread processes one half while a child thread processes the other, but the strategy requires about n/2 threads for a balanced tree and caps spawning at the available-thread limit.Beyond the maximum spawning depth, the current thread processes both halves.Source: §2.2 · p. 4
• The thread-allocation strategy supports only integer powers of two, though synchronization is limited to a parent and one child thread.The implementation measures total construction time across one to eight threads on randomly generated four-dimensional inputs; its fitted curve has r = 0.9867.Source: §2.2 · p. 4, §2.3 · p. 4

2.3 Results for the O (kn log n) Algorithm

• r = 0.998 indicates an adequate fit: measured construction times are proportional to n log2(n) for the tested four-dimensional inputs.Figure 3 plots total merge-sorting, duplicate-removal, and tree-building time against n log2(n) for 2^18 through 2^24 randomly generated 32-bit tuples.Source: §2.3 · p. 4, Figure 3 · p. 4

3.1 The O (n log n) Algorithm

• The O(n log n) method uses an initial merge sort and duplicate removal, then finds each recursive median in O(n) time while partitioning the index array.Non-overlapping recursive halves make the construction amenable to parallel execution.Source: §3.1 · p. 5
• O(n log n) time comprises initial sorting plus O(n log n) partitioning across log2(n) recursion levels; storage includes the tuple, index, and temporary arrays.The tuple array is immutable; the index and temporary arrays are no longer needed after construction.Source: §3.1 · p. 5

3.2 Results for the O (n log n) Algorithm

• For 2^18–2^24 randomly generated 32-bit tuples, total time was fit against n log2(n), with r = 0.9986 indicating an adequate fit.Figure 5 plots total time against n log2(n); measurements include merge sorting, duplicate removal, and tree construction.Source: §3.2 · p. 5, Figure 5 · p. 5
• For 2^24 randomly generated 32-bit tuples, total time across one to eight threads was fit to Equation 1, with r = 0.9958 indicating an acceptable fit.Figure 6 plots total merge-sorting, duplicate-removal, and tree-building time against thread count.Source: §3.2 · p. 6, Figure 6 · p. 6

4. DISCUSSION

• Both algorithms take time proportional to n log^2(n) and run about three times faster with eight threads than with one.The measurements used an Intel quad-core i7 supporting two concurrent threads per core.Source: §4 · p. 6
• The runtime model adds a term linear in q for a performance limitation that Amdahl’s model omits; shared-cache contention may contribute.The model describes this additional limitation as mc(q − 1).Source: §4 · p. 6
• For the quad-core test, the fitted model predicts minimum execution times at q = 5.87 threads for O(kn log n) and q = 6.15 for O(n log n).The authors attribute the predicted decline beyond eight threads to relatively large fitted mc values.Source: §4 · p. 6
• For 2–6 dimensions, the O(kn log n) algorithm’s time rises proportionally with k, while the O(n log n) algorithm’s does not; they tie at k = 4.The dashed-line slope for O(n log n) may reflect random-integer generation rather than dimension scaling.Source: §4 · p. 6
• The O(kn log n) algorithm requires an n-element temporary array and k n-element index arrays, versus n/2 and one n-element index array for O(n log n).Both also store the n k-dimensional tuples.Source: §4 · p. 7
• Replacing merge sort with insertion sort for the median finder’s small arrays improved O(n log n) builder performance by 30%.The small arrays contain five elements, and the original merge sort was not optimized for them.Source: §4 · p. 7

5. CONCLUSION

• The proposed k-d tree builder guarantees O(kn log n) computational complexity for n points and k dimensions.Source: §5 · p. 7
• At k = 4, the proposed O(kn log n) builder performs equally to the O(n log n) builder.Source: §5 · p. 7
• Eight-thread execution improves performance by a factor of three over single-threaded execution for either algorithm.The processor was an Intel quad-core i7 supporting two concurrent threads per core.Source: §5 · p. 7

• The earlier implementations of the O(n log n) and O(kn log n) k-d tree-building algorithms were superseded by the source code described in Section 6.9.Source: Source Code · p. 7

6.1 Optimized Super Key Comparison

• Comparing super keys’ most significant portions before the loop avoids loop overhead in the common case and improves both tree-building algorithms.The serial comparison otherwise checks portions from most to least significant until a difference appears.Source: §6.1 · p. 7

6.2 Optimized Merge Sort

• Concurrent merging and reduced copying improve both tree-building algorithms’ performance.The merge sort can merge the two halves with two threads rather than one.Source: §6.2 · p. 7

6.3 Optimized Partitioning

• Concurrent partitioning and avoiding index-array copying improve the O(kn log n) algorithm, with the copying optimization reaching O[(k −1)n log n].The copying optimization requires precomputing log2 n vectors that specify index-array permutations by tree level.Source: §6.3 · p. 8

6.4 Precomputing the Modulus

• Precomputing the modulus for each tree level eliminates n/2 −log2 n modulus computations.The values can be stored in an array of log2 n elements.Source: §6.4 · p. 8

6.5 Optimized Median Selection

• The O(n log n) algorithm may improve by selecting medians with an explicit decision tree instead of insertion sort.The proposed alternative avoids the insertion sort’s greater number of comparisons and memory accesses.Source: §6.5 · p. 8

6.6 Deferred Merge Sort and Partitioning

• Presorting in one dimension and deferring other sorts and partitions until needed reduces the work of the O(kn log n) algorithm.Partitioning in a dimension is deferred until after that dimension has been sorted.Source: §6.6 · p. 8
• The four-dimensional illustration cycles through x-, y-, z-, and w-based super keys before continuing the tree-building algorithm.Once all dimensions are sorted, construction proceeds as in the original O(kn log n) algorithm.Source: §6.6 · p. 8
• The equations predict that deferred sorting and partitioning improve performance by factors inversely proportional to log2 n and directly proportional to k −1 and k, respectively.The sorting and partitioning predictions are stated separately for the two operations.Source: §6.6 · p. 8

6.7 Performance Measurements

• 28% and 26% performance improvements were achieved by the optimized O(n log n) and O(kn log n) algorithms, respectively, on 4-dimensional tuples.The benchmark used 2^24 randomly generated 64-bit tuples; equations 4 and 5 predicted 6% and 8% improvements, respectively.Source: §6.7 · p. 9
• 65% and 34% performance improvements were achieved by the optimized O(n log n) and O(kn log n) algorithms, respectively, on 8-dimensional tuples.The comparison used 2^24 randomly generated 64-bit tuples and the non-optimized O(kn log n) algorithm as its baseline; the authors attribute the larger O(n log n) gain to its complexity being independent of k.Source: §6.7 · p. 9

6.8 Nearest Neighbors

• Nearest-neighbor search finds m neighbors and orders them by distance; reverse-nearest-neighbor search identifies points for which a given point is a nearest neighbor.The reverse search first finds each point’s m nearest neighbors, then appends the query point to the corresponding reverse-neighbor lists, using a unique lock for each list.Source: §6.8 · p. 9
• Figure 8 plots total execution time against thread count for nearest- and reverse-nearest-neighbor searches on 2^22 three-dimensional tuples.The measurements used randomly generated 64-bit integers.Source: Figure 8 · p. 9, §6.8 · p. 9

• BSD 3-Clause-licensed C++ implementations are provided for the O(n log n) and O(kn log n) algorithms.Source: §6.9 · p. 9
• The test programs build and test either a k-d tree or a k-d tree-based key-to-multiple-value map using either algorithm.The tree and map tests are “test kdtree.cpp” and “test kdmap.cpp,” respectively.Source: §6.9 · p. 9
• The map test may improve performance by storing tuples in tree nodes rather than in the Figure 1 Tuples array, avoiding one level of indirection.The program may also be compiled to build a k-d tree instead of a map.Source: §6.9 · p. 9
• The two test programs exercise the corresponding tree and map implementations and their heap-sort and merge-sort files.The source files are listed separately for the tree test and map test.Source: §6.9 · p. 9
• The node implementations support region searches, nearest-neighbor queries, and nearest- and reverse-nearest-neighbor searches across all tree points.The cited search algorithms address points inside a k-dimensional hyper-rectangular region, nearest neighbors to a query point, and nearest and reverse nearest neighbors for all points.Source: §6.9 · p. 9
• Tree building and region searches use multiple threads, query-point nearest-neighbor search uses one thread, and all-point nearest- and reverse-nearest-neighbor searches use multiple threads.Source: §6.9 · p. 9

• The runtime model separates non-parallelizable time, single-thread parallelizable time divided by thread count, and a cache-contention term proportional to q − 1.The parameters are t_s, t_1, and m_c, respectively.Source: §6.10 · p. 10
• The fitting procedure uses f = 1/q and g = q − 1, and Figures 4 and 6 show least-squares fits of execution-time data for the non-optimized O(kn log n) and O(n log n) algorithms.For q > 2, average f and g values are used because the thread count is not constant across all recursion levels.Source: §6.10 · p. 10
• Least-squares fitting estimates t_s, t_1, and m_c by minimizing an error function and solving three simultaneous linear equations.The equations are obtained by setting the error function’s partial derivatives to zero; the parameters may be solved using Cramer’s rule.Source: §6.10 · p. 10
• The model’s fit quality is assessed using the linear multiple-correlation coefficient calculated from the correlations among f, g, and execution time.Source: §6.10 · p. 10
• With 12 requested threads, the 2^22-tuple tree uses 2, 4, 8, then 12 threads across its first three and remaining recursion levels, while the processor executes at most 12 concurrently.For q = 4, 8, and 12, the average values are calculated to account for the differing thread counts at different recursion levels.Source: §6.10 · p. 10
• The optimized O(n log n) algorithm’s total time—including initial merge sort, duplicate removal, and tree building—was plotted against thread count for n = 2^22 randomly generated 64-bit 3D tuples.Figure 9 reports the measured total time in seconds.Source: §6.10 · p. 10, Figure 9 · p. 11