Scalable Multicore k-NN Search via Subspace Clustering for Filtering.

$k$<alternatives><inline-graphic xlink:type="simple" xlink:href="tang-ieq1-2372755.gif"/> </alternatives> Nearest Neighbors ($k$<alternatives> <inline-graphic xlink:type="simple" xlink:href="tang-ieq2-2372755.gif"/></alternatives>-NN) search is a widely used category of algorithms with applications in domains such as computer vision and machine learning. Despite the desire to process increasing amounts of high-dimensional data within these domains, $k$ <alternatives><inline-graphic xlink:type="simple" xlink:href="tang-ieq3-2372755.gif"/></alternatives>-NN algorithms scale poorly on multicore systems because they hit a memory wall. In this paper, we propose a novel data filtering strategy for $k$<alternatives><inline-graphic xlink:type="simple" xlink:href="tang-ieq4-2372755.gif"/> </alternatives>-NN search algorithms on multicore platforms. By excluding unlikely features during the $k$<alternatives><inline-graphic xlink:type="simple" xlink:href="tang-ieq5-2372755.gif"/> </alternatives>-NN search process, this strategy can reduce the amount of computation required as well as the memory footprint. It is complementary to the data selection strategies used in other state-of-the-art $k$<alternatives><inline-graphic xlink:type="simple" xlink:href="tang-ieq6-2372755.gif"/> </alternatives>-NN algorithms. A Subspace Clustering for Filtering (SCF) method is proposed to implement the data filtering strategy. Experimental results on four $k$ <alternatives><inline-graphic xlink:type="simple" xlink:href="tang-ieq7-2372755.gif"/></alternatives>-NN algorithms show that SCF can significantly improve their performance on three modern multicore platforms with only a small loss of search precision. [ABSTRACT FROM AUTHOR]