Range Queries in Non-blocking k-ary Search Trees

2017/12/14 by Trevor Brown, Brown, Trevor, Hillel Avni +1 · 1 citation
Computer Science · #Algorithms and Data Compression #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.1712.05101

openalex publication_date 2017/12/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a linearizable, non-blocking k-ary search tree (k-ST) that supports fast searches and range queries. Our algorithm uses single-word compare-and-swap (CAS) operations, and tolerates any number of crash failures. Performance experiments show that, for workloads containing small range queries, our k-ST significantly outperforms other algorithms which support these operations, and rivals the performance of a leading concurrent skip-list, which provides range queries that cannot always be linearized.

Cited by

• MTASet: A Tree-based Set for Efficient Range Queries in Update-heavy Workloads

Related

• Persistent Non-Blocking Binary Search Trees Supporting Wait-Free Range Queries
• Wait-free Trees with Asymptotically-Efficient Range Queries
• A Query-Driven Approach to Space-Efficient Range Searching
• Faster Concurrent Range Queries with Contention Adapting Search Trees Using Immutable Data
• Wait-Free Updates and Range Search using Uruv