A Survey on Lock-free Binary Search Tree

Sangjin Lee; Seokjoo Cho; Kiet Tuan Pham; Sunggon Kim; Yongseok Son

doi:10.1109/ICTC55196.2022.9952812

A Survey on Lock-free Binary Search Tree

Sangjin Lee, Seokjoo Cho, Kiet Tuan Pham, Sunggon Kim, Yongseok Son

Dept. of Computer Science and Engineering

Chung-Ang University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

Binary Search Tree is the data structure that has fast search speed and easy addition, removal of elements. Due to these advantages, binary search tree (BST) is one of the frequently used data structures of these days. However, most binary search tree schemes use locking technique to support multiple access of multiple threads for synchronization. Unfortunately, this locking techniques significantly reduce the performance of BST. Locking techniques block or spin the threads that has not obtained the lock until the thread that has obtained the lock completes its job. Thus, to improve the performance of BST, efficient concurrent programming technique should be applied, such as lock-free technique. In this paper, we conduct a comparison of existing lock-free/non-blocking BST methods. We analyze operations and evaluate the strengths and weaknesses of each schemes.

Original language	English
Title of host publication	ICTC 2022 - 13th International Conference on Information and Communication Technology Convergence
Subtitle of host publication	Accelerating Digital Transformation with ICT Innovation
Publisher	IEEE Computer Society
Pages	1136-1138
Number of pages	3
ISBN (Electronic)	9781665499392
DOIs	https://doi.org/10.1109/ICTC55196.2022.9952812
State	Published - 2022
Event	13th International Conference on Information and Communication Technology Convergence, ICTC 2022 - Jeju Island, Korea, Republic of Duration: 19 Oct 2022 → 21 Oct 2022

Publication series

Name	International Conference on ICT Convergence
Volume	2022-October
ISSN (Print)	2162-1233
ISSN (Electronic)	2162-1241

Conference

Conference	13th International Conference on Information and Communication Technology Convergence, ICTC 2022
Country/Territory	Korea, Republic of
City	Jeju Island
Period	19/10/22 → 21/10/22

Keywords

Binary Search Tree (BST)
Concurrency
Data Structure
Lock-Free Algorithm

Access to Document

10.1109/ICTC55196.2022.9952812

Cite this

Lee, S., Cho, S., Pham, K. T., Kim, S., & Son, Y. (2022). A Survey on Lock-free Binary Search Tree. In ICTC 2022 - 13th International Conference on Information and Communication Technology Convergence: Accelerating Digital Transformation with ICT Innovation (pp. 1136-1138). (International Conference on ICT Convergence; Vol. 2022-October). IEEE Computer Society. https://doi.org/10.1109/ICTC55196.2022.9952812

@inproceedings{5b425fe287df4cbeb0b4e0a06b5e35f2,

title = "A Survey on Lock-free Binary Search Tree",

abstract = "Binary Search Tree is the data structure that has fast search speed and easy addition, removal of elements. Due to these advantages, binary search tree (BST) is one of the frequently used data structures of these days. However, most binary search tree schemes use locking technique to support multiple access of multiple threads for synchronization. Unfortunately, this locking techniques significantly reduce the performance of BST. Locking techniques block or spin the threads that has not obtained the lock until the thread that has obtained the lock completes its job. Thus, to improve the performance of BST, efficient concurrent programming technique should be applied, such as lock-free technique. In this paper, we conduct a comparison of existing lock-free/non-blocking BST methods. We analyze operations and evaluate the strengths and weaknesses of each schemes.",

keywords = "Binary Search Tree (BST), Concurrency, Data Structure, Lock-Free Algorithm",

author = "Sangjin Lee and Seokjoo Cho and Pham, \{Kiet Tuan\} and Sunggon Kim and Yongseok Son",

note = "Publisher Copyright: {\textcopyright} 2022 IEEE.; 13th International Conference on Information and Communication Technology Convergence, ICTC 2022 ; Conference date: 19-10-2022 Through 21-10-2022",

year = "2022",

doi = "10.1109/ICTC55196.2022.9952812",

language = "English",

series = "International Conference on ICT Convergence",

publisher = "IEEE Computer Society",

pages = "1136--1138",

booktitle = "ICTC 2022 - 13th International Conference on Information and Communication Technology Convergence",

}

Lee, S, Cho, S, Pham, KT, Kim, S & Son, Y 2022, A Survey on Lock-free Binary Search Tree. in ICTC 2022 - 13th International Conference on Information and Communication Technology Convergence: Accelerating Digital Transformation with ICT Innovation. International Conference on ICT Convergence, vol. 2022-October, IEEE Computer Society, pp. 1136-1138, 13th International Conference on Information and Communication Technology Convergence, ICTC 2022, Jeju Island, Korea, Republic of, 19/10/22. https://doi.org/10.1109/ICTC55196.2022.9952812

A Survey on Lock-free Binary Search Tree. / Lee, Sangjin; Cho, Seokjoo; Pham, Kiet Tuan et al.
ICTC 2022 - 13th International Conference on Information and Communication Technology Convergence: Accelerating Digital Transformation with ICT Innovation. IEEE Computer Society, 2022. p. 1136-1138 (International Conference on ICT Convergence; Vol. 2022-October).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A Survey on Lock-free Binary Search Tree

AU - Lee, Sangjin

AU - Cho, Seokjoo

AU - Pham, Kiet Tuan

AU - Kim, Sunggon

AU - Son, Yongseok

PY - 2022

Y1 - 2022

N2 - Binary Search Tree is the data structure that has fast search speed and easy addition, removal of elements. Due to these advantages, binary search tree (BST) is one of the frequently used data structures of these days. However, most binary search tree schemes use locking technique to support multiple access of multiple threads for synchronization. Unfortunately, this locking techniques significantly reduce the performance of BST. Locking techniques block or spin the threads that has not obtained the lock until the thread that has obtained the lock completes its job. Thus, to improve the performance of BST, efficient concurrent programming technique should be applied, such as lock-free technique. In this paper, we conduct a comparison of existing lock-free/non-blocking BST methods. We analyze operations and evaluate the strengths and weaknesses of each schemes.

AB - Binary Search Tree is the data structure that has fast search speed and easy addition, removal of elements. Due to these advantages, binary search tree (BST) is one of the frequently used data structures of these days. However, most binary search tree schemes use locking technique to support multiple access of multiple threads for synchronization. Unfortunately, this locking techniques significantly reduce the performance of BST. Locking techniques block or spin the threads that has not obtained the lock until the thread that has obtained the lock completes its job. Thus, to improve the performance of BST, efficient concurrent programming technique should be applied, such as lock-free technique. In this paper, we conduct a comparison of existing lock-free/non-blocking BST methods. We analyze operations and evaluate the strengths and weaknesses of each schemes.

KW - Binary Search Tree (BST)

KW - Concurrency

KW - Data Structure

KW - Lock-Free Algorithm

UR - https://www.scopus.com/pages/publications/85143253500

U2 - 10.1109/ICTC55196.2022.9952812

DO - 10.1109/ICTC55196.2022.9952812

M3 - Conference contribution

AN - SCOPUS:85143253500

T3 - International Conference on ICT Convergence

SP - 1136

EP - 1138

BT - ICTC 2022 - 13th International Conference on Information and Communication Technology Convergence

PB - IEEE Computer Society

T2 - 13th International Conference on Information and Communication Technology Convergence, ICTC 2022

Y2 - 19 October 2022 through 21 October 2022

ER -

A Survey on Lock-free Binary Search Tree

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this