Sökning: WFRF:(Chatterjee Bapi 1982) >
Concurrent lineariz...
Concurrent linearizable nearest neighbour search in LockFree-kD-tree
-
- Chatterjee, Bapi, 1982 (författare)
- Institute of Science and Technology Austria
-
- Walulya, Ivan, 1985 (författare)
- Chalmers tekniska högskola,Chalmers University of Technology
-
- Tsigas, Philippas, 1967 (författare)
- Chalmers tekniska högskola,Chalmers University of Technology
-
(creator_code:org_t)
- Elsevier BV, 2021
- 2021
- Engelska.
-
Ingår i: Theoretical Computer Science. - : Elsevier BV. - 0304-3975. ; 886, s. 27-48
- Relaterad länk:
-
http://publications....
-
visa fler...
-
https://research.cha...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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 ([Formula presented] ) 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Språkteknologi (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Language Technology (hsv//eng)
- NATURVETENSKAP -- Data- och informationsvetenskap -- Bioinformatik (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Bioinformatics (hsv//eng)
- TEKNIK OCH TEKNOLOGIER -- Elektroteknik och elektronik -- Datorsystem (hsv//swe)
- ENGINEERING AND TECHNOLOGY -- Electrical Engineering, Electronic Engineering, Information Engineering -- Computer Systems (hsv//eng)
Nyckelord
- Linearizability
- kD-tree
- Similarity search
- Lock-free
- Nearest neighbour search
- Concurrent data structure
Publikations- och innehållstyp
- art (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas