WFRF:(Chatterjee Bapi 1982)
Search: WFRF:(Chatterjee Bapi 1982) > (2015) > Concurrent Lineariz...
- 1 of 2
- Previous record
- Next record
- To hitlist
- Chatterjee, Bapi,1982Chalmers tekniska högskola,Chalmers University of Technology (author)
Concurrent Linearizable Nearest Neighbour Search in LockFree-kD-tree
- BookEnglish2015
Publisher, publication year, extent ...
- 2015
- electronicrdacarrier
Numbers
- LIBRIS-ID:oai:research.chalmers.se:d535e5de-bdb6-49b9-bfc4-2ccff2b5986f
- https://research.chalmers.se/publication/232185URI
Supplementary language notes
- Language:English
- Summary in:English
Part of subdatabase
- SwePubSwePub
Classification
Notes
- The Nearest neighbour search (NNS) is an important problem in a large number of application domains dealing with multidimensional data. In concurrent settings, where dynamic modi?cations are allowed, a linearizable implementation of NNS is highly desirable to discover the latest nearest neighbour of a given target data-point. In this paper, we introduce 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 commonly 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 indexingstructure, PH-tree.
Subject headings and genre
- NATURVETENSKAP Data- och informationsvetenskap Programvaruteknik hsv//swe
- NATURAL SCIENCES Computer and Information Sciences Software Engineering hsv//eng
- NATURVETENSKAP Data- och informationsvetenskap Systemvetenskap, informationssystem och informatik hsv//swe
- NATURAL SCIENCES Computer and Information Sciences Information Systems hsv//eng
- NATURVETENSKAP Data- och informationsvetenskap Datavetenskap hsv//swe
- NATURAL SCIENCES Computer and Information Sciences Computer Sciences hsv//eng
- linearizability
- lock-free
- kD-tree
- nearest neighbor search
- concurrent data structure
- similarity search
Added entries (persons, corporate bodies, meetings, titles ...)
- Walulya, Ivan,1985Chalmers tekniska högskola,Chalmers University of Technology(Swepub:cth)ivanw (author)
- Tsigas, Philippas,1967Chalmers tekniska högskola,Chalmers University of Technology(Swepub:cth)tsigas (author)
- Chalmers tekniska högskola (creator_code:org_t)
Internet link
To the university's database
- 1 of 2
- Previous record
- Next record
- To hitlist
Find more in SwePub
- By the author/editor
- Chatterjee, Bapi ...
- Walulya, Ivan, 1 ...
- Tsigas, Philippa ...
- About the subject
-
- NATURAL SCIENCES
- NATURAL SCIENCES
- and Computer and Inf ...
- and Software Enginee ...
-
- NATURAL SCIENCES
- NATURAL SCIENCES
- and Computer and Inf ...
- and Information Syst ...
-
- NATURAL SCIENCES
- NATURAL SCIENCES
- and Computer and Inf ...
- and Computer Science ...
- By the university
- Chalmers University of Technology
Search outside SwePub
- Extend your search to:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - National Library Systems
- LIBRIS.kb.se
