Parallel execution of kNN-queries on in-memory K-D trees

Abstract

Parallel algorithms for main memory databases become an increasingly interesting topic as the amount of main memory and the number of CPU cores in computer systems increase. This paper suggests a method for parallelizing the k-d tree and its kNN search algorithm as well as suggesting optimizations. In empirical tests, the resulting modified k-d tree outperforms both the k-d tree and a parallelized sequential search for medium dimensionality data (6-13 dimensions).