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