[{"language":[{"iso":"eng"}],"doi":"10.1016/j.tcs.2021.06.041","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","publication_identifier":{"issn":["0304-3975"]},"scopus_import":"1","page":"27-48","date_published":"2021-09-13T00:00:00Z","external_id":{"isi":["000694718900004"]},"keyword":["Concurrent data structure","kD-tree","Nearest neighbor search","Similarity search","Lock-free","Linearizability"],"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":[{"orcid":"0000-0002-2742-4028","full_name":"Chatterjee, Bapi","id":"3C41A08A-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Bapi"},{"full_name":"Walulya, Ivan","last_name":"Walulya","first_name":"Ivan"},{"last_name":"Tsigas","first_name":"Philippas","full_name":"Tsigas, Philippas"}],"quality_controlled":"1","citation":{"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>.","ista":"Chatterjee B, Walulya I, Tsigas P. 2021. Concurrent linearizable nearest neighbour search in LockFree-kD-tree. Theoretical Computer Science. 886, 27–48.","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>.","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.","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>"},"main_file_link":[{"open_access":"1","url":"https://publications.lib.chalmers.se/records/fulltext/232185/232185.pdf"}],"status":"public","date_created":"2021-08-08T22:01:31Z","month":"09","isi":1,"intvolume":"       886","article_type":"original","publisher":"Elsevier","volume":886},{"datarep_id":"28","keyword":["Markov Decision Process","Decision Tree","Probabilistic Verification","Counterexample Explanation"],"file":[{"date_created":"2018-12-12T13:02:31Z","relation":"main_file","creator":"system","content_type":"application/zip","file_size":49557109,"date_updated":"2020-07-14T12:47:00Z","file_id":"5597","access_level":"open_access","checksum":"b8bcb43c0893023cda66c1b69c16ac62","file_name":"IST-2015-28-v1+2_Fellner_DataRep.zip"}],"date_published":"2015-08-13T00:00:00Z","ec_funded":1,"department":[{"_id":"KrCh"},{"_id":"ToHe"}],"has_accepted_license":"1","license":"https://creativecommons.org/publicdomain/zero/1.0/","doi":"10.15479/AT:ISTA:28","oa_version":"Published Version","date_updated":"2024-02-21T13:52:07Z","type":"research_data","contributor":[{"first_name":"Jan","last_name":"Kretinsky","id":"44CEF464-F248-11E8-B48F-1D18A9856A87"}],"day":"13","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"08","date_created":"2018-12-12T12:31:29Z","status":"public","publist_id":"5564","file_date_updated":"2020-07-14T12:47:00Z","publisher":"Institute of Science and Technology Austria","project":[{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"abstract":[{"text":"This repository contains the experimental part of the CAV 2015 publication Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.\r\nWe extended the probabilistic model checker PRISM to represent strategies of Markov Decision Processes as Decision Trees.\r\nThe archive contains a java executable version of the extended tool (prism_dectree.jar) together with a few examples of the PRISM benchmark library.\r\nTo execute the program, please have a look at the README.txt, which provides instructions and further information on the archive.\r\nThe archive contains scripts that (if run often enough) reproduces the data presented in the publication.","lang":"eng"}],"title":"Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes","_id":"5549","oa":1,"related_material":{"record":[{"id":"1603","status":"public","relation":"popular_science"}]},"ddc":["004"],"tmp":{"short":"CC0 (1.0)","legal_code_url":"https://creativecommons.org/publicdomain/zero/1.0/legalcode","name":"Creative Commons Public Domain Dedication (CC0 1.0)","image":"/images/cc_0.png"},"year":"2015","citation":{"mla":"Fellner, Andreas. <i>Experimental Part of CAV 2015 Publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes</i>. Institute of Science and Technology Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:28\">10.15479/AT:ISTA:28</a>.","apa":"Fellner, A. (2015). Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:28\">https://doi.org/10.15479/AT:ISTA:28</a>","ista":"Fellner A. 2015. Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes, Institute of Science and Technology Austria, <a href=\"https://doi.org/10.15479/AT:ISTA:28\">10.15479/AT:ISTA:28</a>.","chicago":"Fellner, Andreas. “Experimental Part of CAV 2015 Publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.” Institute of Science and Technology Austria, 2015. <a href=\"https://doi.org/10.15479/AT:ISTA:28\">https://doi.org/10.15479/AT:ISTA:28</a>.","short":"A. Fellner, (2015).","ieee":"A. Fellner, “Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.” Institute of Science and Technology Austria, 2015.","ama":"Fellner A. Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes. 2015. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:28\">10.15479/AT:ISTA:28</a>"},"author":[{"full_name":"Fellner, Andreas","id":"42BABFB4-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas","last_name":"Fellner"}]}]