Best First and Concentric Ball Tree : Improving Efficiency of K-Nearest Neighbors Search
Date Issued
2016
Date
2016
Author(s)
Hou, Ting-Chang
Abstract
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.
Subjects
K-nearest Neighbors
Ball-tree
Concentric Ball-tree
Heuristic
Unstable Priority Queue
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-105-R03922041-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):1b0d1ba099ea92d4316645a22d3b08ed