@article{9827,
  abstract     = {The Nearest neighbour search (NNS) is a fundamental problem in many application domains dealing with multidimensional data. In a concurrent setting, where dynamic modifications are allowed, a linearizable implementation of the NNS is highly desirable.This paper introduces the LockFree-kD-tree (LFkD-tree ): a lock-free concurrent kD-tree, which implements an abstract data type (ADT) that provides the operations Add, Remove, Contains, and NNS. Our implementation is linearizable. The operations in the LFkD-tree use single-word read and compare-and-swap (Image 1 ) atomic primitives, which are readily supported on available multi-core processors. We experimentally evaluate the LFkD-tree using several benchmarks comprising real-world and synthetic datasets. The experiments show that the presented design is scalable and achieves significant speed-up compared to the implementations of an existing sequential kD-tree and a recently proposed multidimensional indexing structure, PH-tree.},
  author       = {Chatterjee, Bapi and Walulya, Ivan and Tsigas, Philippas},
  issn         = {0304-3975},
  journal      = {Theoretical Computer Science},
  keywords     = {Concurrent data structure, kD-tree, Nearest neighbor search, Similarity search, Lock-free, Linearizability},
  pages        = {27--48},
  publisher    = {Elsevier},
  title        = {{Concurrent linearizable nearest neighbour search in LockFree-kD-tree}},
  doi          = {10.1016/j.tcs.2021.06.041},
  volume       = {886},
  year         = {2021},
}