Sökning: id:"swepub:oai:research.chalmers.se:55f22516-a7cd-44dd-bfc2-95f101a32fb0" >
Concurrent lineariz...
Concurrent linearizable nearest neighbour search in lockfree-kd-Tree
-
- Chatterjee, Bapi, 1982 (författare)
- Chalmers tekniska högskola,Chalmers University of Technology
-
- 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)
- 2018-01-04
- 2018
- Engelska.
-
Ingår i: ACM International Conference Proceeding Series. - New York, NY, USA : ACM. ; Part F133180
- 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 modi-fications are allowed, a linearizable implementation of 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 (CAS) 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 signi cant speed-up compared to the implementations of an existing sequential kD-Tree and a recently proposed multidimensional indexing structure, PH-Tree. © 2018 Copyright held by the owner/author(s).
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences (hsv//eng)
- NATURVETENSKAP -- Data- och informationsvetenskap -- Programvaruteknik (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Software Engineering (hsv//eng)
Publikations- och innehållstyp
- kon (ämneskategori)
- ref (ämneskategori)