Concurrent linearizable nearest neighbour search in LockFree-kD-tree

Chatterjee B, Walulya I, Tsigas P. Concurrent linearizable nearest neighbour search in LockFree-kD-tree. Theoretical Computer Science.

Download
No fulltext has been uploaded. References only!

Journal Article | In Press | English

Scopus indexed
Author
Chatterjee, BapiIST Austria; Walulya, Ivan; Tsigas, Philippas
Department
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.
Publishing Year
Date Published
2021-07-08
Journal Title
Theoretical Computer Science
ISSN
IST-REx-ID

Cite this

Chatterjee B, Walulya I, Tsigas P. Concurrent linearizable nearest neighbour search in LockFree-kD-tree. Theoretical Computer Science. doi:10.1016/j.tcs.2021.06.041
Chatterjee, B., Walulya, I., & Tsigas, P. (n.d.). Concurrent linearizable nearest neighbour search in LockFree-kD-tree. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2021.06.041
Chatterjee, Bapi, Ivan Walulya, and Philippas Tsigas. “Concurrent Linearizable Nearest Neighbour Search in LockFree-KD-Tree.” Theoretical Computer Science. Elsevier, n.d. https://doi.org/10.1016/j.tcs.2021.06.041.
B. Chatterjee, I. Walulya, and P. Tsigas, “Concurrent linearizable nearest neighbour search in LockFree-kD-tree,” Theoretical Computer Science. Elsevier.
Chatterjee B, Walulya I, Tsigas P. Concurrent linearizable nearest neighbour search in LockFree-kD-tree. Theoretical Computer Science.
Chatterjee, Bapi, et al. “Concurrent Linearizable Nearest Neighbour Search in LockFree-KD-Tree.” Theoretical Computer Science, Elsevier, doi:10.1016/j.tcs.2021.06.041.

Link(s) to Main File(s)
Access Level
Restricted Closed Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar