High Dimensional Exact $K$ Nearest Neighbor Search Using Lower Bound Technique and Parallel Computing

For the past decade, the K Nearest Neighbor (K-NN) search in high dimensional space has been explored extensively. Considerable theoretical and practical algorithms to accelerate approximate K-NN search have been presented. The approximate methods can improve searching efficiency and achieve satisfactory performance. Nevertheless, they are inherently approximation approaches and are not guaranteed to yield exact solutions. To obtain the K-NN results over high dimensional datasets efficiently while guaranteeing the same results as the linear search is a challenging task, attracting a large number of scholars. To this end, in this paper, we focus on improving the exact K-NN search efficiency over high dimensional datasets, and present a framework named LBPC to solve this problem. The lower bound based method and parallel computing are combined in LBPC to accelerate the exact K-NN search. In LBPC, the whole K-NN search task is divided into some sub-tasks and these sub-tasks can be conducted concurrently using the lower bound based method. The LBPC scheme allows users to utilize any lower bound to accelerate the exact K-NN query. In this paper, we use the segment mean to construct the lower bound and provide the theoretical analysis to show its computational efficiency and lower bound property. Various experiments are conducted to analyze the efficiency of LBPC, and the experimental results validate its effectiveness.