An Improved Hierarchical Datastructure for Nearest Neighbor Search
Mengdie Nie, Zhijie Wang, Chunjing Gan, Zhe Quan, Bin Yao, Jian Yin · Proceedings of the AAAI Conference on Artificial Intelligence · 2019
Nearest neighbor search is a fundamental computational tool and has wide applications. In past decades, many datastructures have been developed to speed up this operation. In this paper, we propose a novel hierarchical datastructure for nearest neighbor search in moderately high dimension. Our proposed method maintains good run time guarantees, and it outperforms several state-of-the-art methods in practice.