Dynamic NN-Descent: An Efficient k-NN Graph Construction Method

As a classic <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i>-NN graph construction method, NN-Descent has been adopted in various applications for its simplicity, genericness, and efficiency. However, its memory consumption is high due to the employment of two extra supporting graph structures. In this paper, a novel <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i>-NN graph construction method is proposed. Similar to NN-Descent, the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i>-NN graph is constructed by doing cross-matching continuously on the sampled neighbors on each neighborhood. Whereas different from NN-Descent, the cross-matching is undertaken directly on the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i>-NN graph under construction. It makes the extra graph structures adopted to support the cross-matching no longer necessary. Moreover, no synchronization between different threads is needed within one iteration. The high-quality graph is constructed at the high-speed efficiency and considerably better memory efficiency over NN-Descent on both the multi-thread CPU and the GPU.