Kanva: A Lock-free Learned Search Data Structure

Lock-free concurrent data structures offer throughput with scalability and guarantees for the completion of operations on multicore computers. Recently, queries using machine learning models trained to predict the data distribution have gained remarkable attention. Yet, to our knowledge, no existing lock-free data structure employs them. This paper introduces a lock-free search structure that supports concurrent updates, membership, and range queries accelerated by a shallow hierarchy of lightweight machine learning models. The proposed approach significantly outperforms the current state-of-the-art lock-free data structures in many workload and data distribution settings. Ours is the first provably linearizable learned lock-free concurrent range search index.