  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 rate 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%.
