CLEANN: Lock-Free Augmented Trees for Low-Dimensional κ-Nearest Neighbor Search

We develop a linearizable lock-free data structure, the CLEANN-tree (Concurrent Linearizable Efficient Augmented Nearest Neighbor tree), for low dimensional κ-nearest-neighbor searching. The data structure maintains a set of points P in d dimensions under insertion and deletion, while supporting queries that, given a point, return the k nearest points in P. The CLEANN-tree is constructed by modifying a kd-tree, a type of spatial decomposition commonly used for κ-nearest neighbor searching, for the concurrent environment. It is the first such concurrent structure---two previous structures were either not linearizable or only supported κ=1. Furthermore CLEANN-tree stores an augmented value (more specifically, a bounding box) in each internal node of the kd-tree. These bounding boxes significantly improve query performance by allowing more aggresive pruning. However, correctly and efficiently maintaining these augmented values is challenging in the linearizable lock-free setting because queries can examine large parts of the structure, which might be changing, and an insert or delete can require updating all the augmented values from the leaf to the root.