Localization With Approximate Nearest Neighbour Search

ABSTRACT Localization and place recognition are important tasks in many fields, including autonomous driving, robotics, and AR/VR applications. Local and global feature‐based solutions typically rely on exact nearest neighbour search methods, such as KD‐tree, to retrieve candidate places or frames and estimate the precise sensor position using point correspondences. However, in large‐scale applications, maintaining real‐time online processing without loss of performance can be challenging. We propose that by using an approximate nearest neighbour search method instead of exact methods, runtime can be significantly reduced without sacrificing accuracy. To demonstrate this, we developed a localization pipeline based on a keypoint voting mechanism, employing the hierarchical navigable small world (HNSW) structure as the nearest neighbour search method. Graph‐based structures like HNSW are widely used in other domains, such as recommender systems and large language models. We argue that for the use case of matching local feature descriptors, the slightly lower accuracy in terms of exact neighbours does not lead to a significant increase in localization error. We evaluated our pipeline on widely known datasets and performed parameter tuning of HNSW specifically for this use case.