The SkipTrie, low-depth concurrent search without rebalancing

DOI10.1145/2484239.2484270MaRDI QIDQ5176079zbMATH OpenOpenAlexFDO

Authors Rotem Oshman, Nir Shavit

Publication date 2 March 2015

Published in Proceedings of the 2013 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2484239.2484270

zbMATH Keywords

amortized analysisconcurrent data structurespredecessor queries

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Information storage and retrieval of data (68P20) Distributed algorithms (68W15)

Recommendations

• Skip trees, an alternative data structure to skip lists in a concurrent approach
• Efficient lock-free binary search trees
• A Simple Optimistic Skiplist Algorithm
• Some observations on skip-lists
• Skip lift: a probabilistic alternative to red-black trees

Cited in

(6)

• Non-blocking Patricia tries with replace operations
• Skip-Splay: Toward Achieving the Unified Bound in the BST Model
• Skip trees, an alternative data structure to skip lists in a concurrent approach
• NUMASK: high performance scalable skip list for NUMA
• Leaplist: lessons learned in designing TM-supported range queries
• A Simple Optimistic Skiplist Algorithm

This page was built for publication: The SkipTrie, low-depth concurrent search without rebalancing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5176079)