Best First and Concentric Ball Tree : Improving Efficiency of K-Nearest Neighbors Search

The K-nearest neighbors(KNN) is often a necessary algorithm in many machine learning and data mining applications.There are several tree structure algorithm to implement KNN, like K-d tree search and Ball-tree search.Ball-tree search is a powerful algorithm to search KNN for high dimension.In this work, we focus on improving the efficiency of ball-tree.We propose concentric ball-tree which change the leaf node structure of ball-tree.We also use several heuristic to change the traverse order of ball-tree search.We empirically show that our approach can improve the efficiency a lot to save search time of KNN by reducing the number of visited data points, the number of visited node in tree structure.In addition, we find that concentric ball-tree scale well with the number of dimensions. It can improve more efficiency for traditional ball-tree at high dimension.We also show that the performance of ball-tree is data driven, and so dose concentric ball-tree.