1 Search Results for "Li, Mengdu"


Document
Deletion without Rebalancing in Non-Blocking Binary Search Trees

Authors: Meng He and Mengdu Li

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)


Abstract
We present a provably linearizable and lock-free relaxed AVL tree called the non-blocking ravl tree. At any time, the height of a non-blocking ravl tree is upper bounded by log_d (2m) + c, where d is the golden ratio, m is the total number of successful INSERT operations performed so far and c is the number of active concurrent processes that have inserted new keys and are still rebalancing the tree at this time. The most significant feature of the non-blocking ravl tree is that it does not rebalance itself after DELETE operations. Instead, it performs rebalancing only after INSERT operations. Thus, the non-blocking ravl tree is much simpler to implement than other self-balancing concurrent binary search trees (BSTs) which typically introduce a large number of rebalancing cases after DELETE operations, while still providing a provable non-trivial bound on its height. We further conduct experimental studies to compare our solution with other state-of-the-art concurrent BSTs using randomly generated data sequences under uniform distributions, and find that our solution achieves the best performance among concurrent self-balancing BSTs. As the keys in access sequences are likely to be partially sorted in system software, we also conduct experiments using data sequences with various degrees of presortedness to better simulate applications in practice. Our experimental results show that, when there are enough degrees of presortedness, our solution achieves the best performance among all the concurrent BSTs used in our studies, including those that perform self-balancing operations and those that do not, and thus is potentially the best candidate for many real-world applications.

Cite as

Meng He and Mengdu Li. Deletion without Rebalancing in Non-Blocking Binary Search Trees. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{he_et_al:LIPIcs.OPODIS.2016.34,
  author =	{He, Meng and Li, Mengdu},
  title =	{{Deletion without Rebalancing in Non-Blocking Binary Search Trees}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{34:1--34:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.34},
  URN =		{urn:nbn:de:0030-drops-71032},
  doi =		{10.4230/LIPIcs.OPODIS.2016.34},
  annote =	{Keywords: concurrent data structures, non-blocking data structures, lock-free data structures, self-balancing binary search trees, relaxed AVL trees}
}
  • Refine by Author
  • 1 He, Meng
  • 1 Li, Mengdu

  • Refine by Classification

  • Refine by Keyword
  • 1 concurrent data structures
  • 1 lock-free data structures
  • 1 non-blocking data structures
  • 1 relaxed AVL trees
  • 1 self-balancing binary search trees

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail