[{"status":"public","date_created":"2021-08-08T22:01:31Z","month":"09","isi":1,"intvolume":"       886","article_type":"original","publisher":"Elsevier","volume":886,"publication_status":"published","abstract":[{"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.","lang":"eng"}],"oa":1,"_id":"9827","title":"Concurrent linearizable nearest neighbour search in LockFree-kD-tree","publication":"Theoretical Computer Science","year":"2021","author":[{"id":"3C41A08A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2742-4028","full_name":"Chatterjee, Bapi","first_name":"Bapi","last_name":"Chatterjee"},{"full_name":"Walulya, Ivan","first_name":"Ivan","last_name":"Walulya"},{"last_name":"Tsigas","first_name":"Philippas","full_name":"Tsigas, Philippas"}],"quality_controlled":"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>.","ista":"Chatterjee B, Walulya I, Tsigas P. 2021. Concurrent linearizable nearest neighbour search in LockFree-kD-tree. Theoretical Computer Science. 886, 27–48.","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>","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.","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>","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>."},"main_file_link":[{"url":"https://publications.lib.chalmers.se/records/fulltext/232185/232185.pdf","open_access":"1"}],"publication_identifier":{"issn":["0304-3975"]},"scopus_import":"1","page":"27-48","date_published":"2021-09-13T00:00:00Z","keyword":["Concurrent data structure","kD-tree","Nearest neighbor search","Similarity search","Lock-free","Linearizability"],"external_id":{"isi":["000694718900004"]},"doi":"10.1016/j.tcs.2021.06.041","language":[{"iso":"eng"}],"department":[{"_id":"DaAl"}],"day":"13","date_updated":"2023-08-10T14:27:43Z","type":"journal_article","oa_version":"Submitted Version","article_processing_charge":"No","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8"},{"language":[{"iso":"eng"}],"doi":"10.1515/bmt-2013-4181","has_accepted_license":"1","department":[{"_id":"PeJo"}],"date_updated":"2021-12-02T12:51:12Z","type":"journal_article","oa_version":"Submitted Version","day":"01","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","article_processing_charge":"No","publication_identifier":{"issn":["0013-5585"],"eissn":["1862-278X"]},"date_published":"2013-08-01T00:00:00Z","file":[{"file_id":"10397","date_updated":"2021-12-01T14:38:08Z","success":1,"access_level":"open_access","checksum":"cdfc5339b530a25d6079f7223f0b1f16","file_name":"Schloegl_Abstract-BMT2013.pdf","date_created":"2021-12-01T14:38:08Z","relation":"main_file","file_size":149825,"content_type":"application/pdf","creator":"schloegl"}],"external_id":{"pmid":["24042795"]},"keyword":["biomedical engineering","data analysis","free software"],"publication_status":"published","abstract":[{"lang":"eng","text":"Stimfit is a free cross-platform software package for viewing and analyzing electrophysiological data. It supports most standard file types for cellular neurophysiology and other biomedical formats. Its analysis algorithms have been used and validated in several experimental laboratories. Its embedded Python scripting interface makes Stimfit highly extensible and customizable."}],"publication":"Biomedical Engineering / Biomedizinische Technik","title":"Stimfit: A fast visualization and analysis environment for cellular neurophysiology","pmid":1,"ddc":["005","610"],"oa":1,"_id":"10396","year":"2013","citation":{"apa":"Schlögl, A., Jonas, P. M., Schmidt-Hieber, C., &#38; Guzman, S. J. (2013). Stimfit: A fast visualization and analysis environment for cellular neurophysiology. <i>Biomedical Engineering / Biomedizinische Technik</i>. Graz, Austria: De Gruyter. <a href=\"https://doi.org/10.1515/bmt-2013-4181\">https://doi.org/10.1515/bmt-2013-4181</a>","mla":"Schlögl, Alois, et al. “Stimfit: A Fast Visualization and Analysis Environment for Cellular Neurophysiology.” <i>Biomedical Engineering / Biomedizinische Technik</i>, vol. 58, no. SI-1-Track-G, 000010151520134181, De Gruyter, 2013, doi:<a href=\"https://doi.org/10.1515/bmt-2013-4181\">10.1515/bmt-2013-4181</a>.","ista":"Schlögl A, Jonas PM, Schmidt-Hieber C, Guzman SJ. 2013. Stimfit: A fast visualization and analysis environment for cellular neurophysiology. Biomedical Engineering / Biomedizinische Technik. 58(SI-1-Track-G), 000010151520134181.","chicago":"Schlögl, Alois, Peter M Jonas, C. Schmidt-Hieber, and S. J. Guzman. “Stimfit: A Fast Visualization and Analysis Environment for Cellular Neurophysiology.” <i>Biomedical Engineering / Biomedizinische Technik</i>. De Gruyter, 2013. <a href=\"https://doi.org/10.1515/bmt-2013-4181\">https://doi.org/10.1515/bmt-2013-4181</a>.","short":"A. Schlögl, P.M. Jonas, C. Schmidt-Hieber, S.J. Guzman, Biomedical Engineering / Biomedizinische Technik 58 (2013).","ama":"Schlögl A, Jonas PM, Schmidt-Hieber C, Guzman SJ. Stimfit: A fast visualization and analysis environment for cellular neurophysiology. <i>Biomedical Engineering / Biomedizinische Technik</i>. 2013;58(SI-1-Track-G). doi:<a href=\"https://doi.org/10.1515/bmt-2013-4181\">10.1515/bmt-2013-4181</a>","ieee":"A. Schlögl, P. M. Jonas, C. Schmidt-Hieber, and S. J. Guzman, “Stimfit: A fast visualization and analysis environment for cellular neurophysiology,” <i>Biomedical Engineering / Biomedizinische Technik</i>, vol. 58, no. SI-1-Track-G. De Gruyter, 2013."},"author":[{"first_name":"Alois","last_name":"Schlögl","id":"45BF87EE-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-5621-8100","full_name":"Schlögl, Alois"},{"last_name":"Jonas","first_name":"Peter M","full_name":"Jonas, Peter M","orcid":"0000-0001-5001-4804","id":"353C1B58-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Schmidt-Hieber, C.","last_name":"Schmidt-Hieber","first_name":"C."},{"last_name":"Guzman","first_name":"S. J.","full_name":"Guzman, S. J."}],"quality_controlled":"1","date_created":"2021-12-01T14:35:35Z","month":"08","conference":{"name":"BMT: Biomedizinische Technik ","end_date":"2013-09-21","location":"Graz, Austria","start_date":"2013-09-19"},"article_number":"000010151520134181","status":"public","intvolume":"        58","file_date_updated":"2021-12-01T14:38:08Z","article_type":"original","publisher":"De Gruyter","volume":58,"issue":"SI-1-Track-G"}]