Octree k-nearest neighbor parallel query

Nearest neighbor queries have widespread applications in fields such as computer vision, data mining, pattern recognition, document retrieval, and geographic information systems.The traditional k-nearest neighbor algorithm based on branch-and-bound and octree requires the use of a priority queue to maintain the result set. However, in large-scale data scenarios, the efficiency of the priority queue decreases, leading to a decline in query efficiency. Additionally, implementing parallelism using tree-based storage structures, such as octree, can be challenging. This paper proposes a parallel k-nearest neighbor query algorithm for multi-core CPU environments based on octree. This method adopts a divide-and-conquer approach by dividing the dataset into multiple parts and constructing octree for each part. Then, it utilizes parallel max-heaps to calculate the distances of pruned data and selects the nearest K elements to achieve K-nearest neighbor query. This method utilizes multiprocessors for tree construction and result set maintenance, further accelerating the query speed. Experimental results show that in large-scale data scenarios, this method achieves significant acceleration compared to sequential query.