arXiv Open Access 2017

Range Queries in Non-blocking $k$-ary Search Trees

Trevor Brown Hillel Avni

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.DC

Penulis (2)

Trevor Brown

Hillel Avni

Format Sitasi

APA MLA BibTeX

Brown, T., Avni, H. (2017). Range Queries in Non-blocking $k$-ary Search Trees. https://arxiv.org/abs/1712.05101

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2017
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓