Approximate k-Nearest Neighbour (ANN) methods are often used for mining
information and aiding machine learning on large scale high-dimensional
datasets. ANN methods typically differ in the index structure used for
accelerating searches, resulting in various recall/runtime trade-off points.
For applications with static datasets, runtime constraints and dataset
properties can be used to empirically select an ANN method with suitable
operating characteristics. However, for applications with dynamic datasets,
which are subject to frequent online changes (like addition of new samples),
there is currently no consensus as to which ANN methods are most suitable.
Traditional evaluation approaches do not consider the computational costs of
updating the index structure, as well as the frequency and size of index
updates. To address this, we empirically evaluate 5 popular ANN methods on two
main applications (online data collection and online feature learning) while
taking into account these considerations. Two dynamic datasets are used,
derived from the SIFT1M dataset with 1 million samples and the DEEP1B dataset
with 1 billion samples. The results indicate that the often used k-d trees
method is not suitable on dynamic datasets as it is slower than a
straightforward baseline exhaustive search method. For online data collection,
the Hierarchical Navigable Small World Graphs method achieves a consistent
speedup over baseline across a wide range of recall rates. For online feature
learning, the Scalable Nearest Neighbours method is faster than baseline for
recall rates below 75%.

近似 k 最近邻（ANN）方法常用于大规模高维数据集上的信息挖掘和机器学习，针对动态数据集和在线特征学习等应用，我们通过实证评估了 5 种流行的 ANN 方法，结果表明在动态数据集中，k-d 树方法不适用，并且在在线数据收集和在线特征学习方面，层次可导航小世界图方法和可扩展最近邻方法分别比基线方法更快速。