KNN in the Jaccard space
Ming Hua Ouyang · 2016
The first step of the K-nearest neighbor classification is to find the K-nearest neighbors of the query. A basic operation in calculating Jaccard distance is to count the number of ones in a binary vector - population count. This article focuses on finding the K-nearest neighbors in a high-dimensional Jaccard space. There are two main contributions. First, software methods for population count are improved and implemented in Advanced Vector Extensions. They are faster than the hardware instruction. Second, a new method for KNN is proposed. Jaccard distance is a metric. After the K-nearest neighbors of a vector are found, their K-nearest neighbors must be in a hypersphere with a radius determined by the triangle inequality. Sequential computation and parallelization by OpenMP and POSIX Threads are implemented. The new method is up to six to 11 times faster than the classic method.