---
_id: '9827'
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.'
article_processing_charge: No
article_type: original
author:
- first_name: Bapi
  full_name: Chatterjee, Bapi
  id: 3C41A08A-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-2742-4028
- first_name: Ivan
  full_name: Walulya, Ivan
  last_name: Walulya
- first_name: Philippas
  full_name: Tsigas, Philippas
  last_name: Tsigas
citation:
  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>
  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>
  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.
  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>.
  short: B. Chatterjee, I. Walulya, P. Tsigas, Theoretical Computer Science 886 (2021)
    27–48.
date_created: 2021-08-08T22:01:31Z
date_published: 2021-09-13T00:00:00Z
date_updated: 2023-08-10T14:27:43Z
day: '13'
department:
- _id: DaAl
doi: 10.1016/j.tcs.2021.06.041
external_id:
  isi:
  - '000694718900004'
intvolume: '       886'
isi: 1
keyword:
- Concurrent data structure
- kD-tree
- Nearest neighbor search
- Similarity search
- Lock-free
- Linearizability
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://publications.lib.chalmers.se/records/fulltext/232185/232185.pdf
month: '09'
oa: 1
oa_version: Submitted Version
page: 27-48
publication: Theoretical Computer Science
publication_identifier:
  issn:
  - 0304-3975
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Concurrent linearizable nearest neighbour search in LockFree-kD-tree
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 886
year: '2021'
...
---
_id: '5549'
abstract:
- lang: eng
  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."
article_processing_charge: No
author:
- first_name: Andreas
  full_name: Fellner, Andreas
  id: 42BABFB4-F248-11E8-B48F-1D18A9856A87
  last_name: Fellner
citation:
  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>'
  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>'
  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>.'
  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.'
  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>.'
  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>.'
  short: A. Fellner, (2015).
contributor:
- first_name: Jan
  id: 44CEF464-F248-11E8-B48F-1D18A9856A87
  last_name: Kretinsky
datarep_id: '28'
date_created: 2018-12-12T12:31:29Z
date_published: 2015-08-13T00:00:00Z
date_updated: 2024-02-21T13:52:07Z
day: '13'
ddc:
- '004'
department:
- _id: KrCh
- _id: ToHe
doi: 10.15479/AT:ISTA:28
ec_funded: 1
file:
- access_level: open_access
  checksum: b8bcb43c0893023cda66c1b69c16ac62
  content_type: application/zip
  creator: system
  date_created: 2018-12-12T13:02:31Z
  date_updated: 2020-07-14T12:47:00Z
  file_id: '5597'
  file_name: IST-2015-28-v1+2_Fellner_DataRep.zip
  file_size: 49557109
  relation: main_file
file_date_updated: 2020-07-14T12:47:00Z
has_accepted_license: '1'
keyword:
- Markov Decision Process
- Decision Tree
- Probabilistic Verification
- Counterexample Explanation
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
publisher: Institute of Science and Technology Austria
publist_id: '5564'
related_material:
  record:
  - id: '1603'
    relation: popular_science
    status: public
status: public
title: 'Experimental part of CAV 2015 publication: Counterexample Explanation by Learning
  Small Strategies in Markov Decision Processes'
tmp:
  image: /images/cc_0.png
  legal_code_url: https://creativecommons.org/publicdomain/zero/1.0/legalcode
  name: Creative Commons Public Domain Dedication (CC0 1.0)
  short: CC0 (1.0)
type: research_data
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...