Exploit every bit: Effective caching for high-dimensional nearest neighbor search (extended abstract)
Bo Ming Tang, Man Lung Yiu, Kien A. Hua · 2017
In high-dimensional kNN search, both exact and approximate kNN solutions incur considerable time in the candidate refinement phase. In this paper, we investigate a caching solution to reduce the candidate refinement time. Our caching method HC-O is faster than EXACT caching by at least an order of magnitude, on an approximate index (C2LSH). Our work is also applicable to exact indexes (e.g., iDistance, VPtree and VA-file).