Acceleration of the κ-nearest neighbor method using inclusion and exclusion

摘要

The termination conditions were previously derived by us to stop the search procedure for finding the κ-nearest neighbors and a branch and bound algorithm equipped with these conditions was proposed. In this study, we examine under which conditions we can limit our search space even when such terminations cannot be applied. Indeed, an inclusion condition to narrow the search space and an exclusion condition to exclude some samples from the search are described. With some experiments, we confirm the validity of these conditions.