---
_id: '9827'
abstract:
- lang: eng
  text: '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.'
article_processing_charge: No
article_type: original
author:
- first_name: Bapi
  full_name: Chatterjee, Bapi
  id: 3C41A08A-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-2742-4028
- first_name: Ivan
  full_name: Walulya, Ivan
  last_name: Walulya
- first_name: Philippas
  full_name: Tsigas, Philippas
  last_name: Tsigas
citation:
  ama: Chatterjee B, Walulya I, Tsigas P. Concurrent linearizable nearest neighbour
    search in LockFree-kD-tree. <i>Theoretical Computer Science</i>. 2021;886:27-48.
    doi:<a href="https://doi.org/10.1016/j.tcs.2021.06.041">10.1016/j.tcs.2021.06.041</a>
  apa: Chatterjee, B., Walulya, I., &#38; Tsigas, P. (2021). Concurrent linearizable
    nearest neighbour search in LockFree-kD-tree. <i>Theoretical Computer Science</i>.
    Elsevier. <a href="https://doi.org/10.1016/j.tcs.2021.06.041">https://doi.org/10.1016/j.tcs.2021.06.041</a>
  chicago: Chatterjee, Bapi, Ivan Walulya, and Philippas Tsigas. “Concurrent Linearizable
    Nearest Neighbour Search in LockFree-KD-Tree.” <i>Theoretical Computer Science</i>.
    Elsevier, 2021. <a href="https://doi.org/10.1016/j.tcs.2021.06.041">https://doi.org/10.1016/j.tcs.2021.06.041</a>.
  ieee: B. Chatterjee, I. Walulya, and P. Tsigas, “Concurrent linearizable nearest
    neighbour search in LockFree-kD-tree,” <i>Theoretical Computer Science</i>, vol.
    886. Elsevier, pp. 27–48, 2021.
  ista: Chatterjee B, Walulya I, Tsigas P. 2021. Concurrent linearizable nearest neighbour
    search in LockFree-kD-tree. Theoretical Computer Science. 886, 27–48.
  mla: Chatterjee, Bapi, et al. “Concurrent Linearizable Nearest Neighbour Search
    in LockFree-KD-Tree.” <i>Theoretical Computer Science</i>, vol. 886, Elsevier,
    2021, pp. 27–48, doi:<a href="https://doi.org/10.1016/j.tcs.2021.06.041">10.1016/j.tcs.2021.06.041</a>.
  short: B. Chatterjee, I. Walulya, P. Tsigas, Theoretical Computer Science 886 (2021)
    27–48.
corr_author: '1'
date_created: 2021-08-08T22:01:31Z
date_published: 2021-09-13T00:00:00Z
date_updated: 2024-10-09T21:00:45Z
day: '13'
department:
- _id: DaAl
doi: 10.1016/j.tcs.2021.06.041
external_id:
  isi:
  - '000694718900004'
intvolume: '       886'
isi: 1
keyword:
- Concurrent data structure
- kD-tree
- Nearest neighbor search
- Similarity search
- Lock-free
- Linearizability
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://publications.lib.chalmers.se/records/fulltext/232185/232185.pdf
month: '09'
oa: 1
oa_version: Submitted Version
page: 27-48
publication: Theoretical Computer Science
publication_identifier:
  issn:
  - 0304-3975
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Concurrent linearizable nearest neighbour search in LockFree-kD-tree
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 886
year: '2021'
...