Write a Blog >>
Tue 25 Feb 2020 15:45 - 16:10 - Search and Index (Mediterranean Ballroom) Chair(s): Idit Keidar

Most balanced search trees use key comparisons to guide their operations, and achieve logarithmic running time. By relying on numerical properties of the keys, interpolation search achieves lower search complexity and better performance. Although interpolation-based data structures were investigated in the past, their non-blocking concurrent variants have received very little attention so far.

In this paper, we propose the first non-blocking implementation of the classic interpolation search tree data structure. For arbitrary key distributions, the data structure ensures amortized O(log n) insertion and deletion. Furthermore, when input key distributions are smooth, lookups run in expected O(log log n) time, and insertion and deletion run in amortized O(log log n). To improve the scalability of insertion and deletion operations, we propose a novel, scalable concurrent rebuilding technique. We implement the concurrent interpolation search tree, and evaluate the efficiency of its operations.

Tue 25 Feb

PPoPP-2020-papers
15:45 - 17:00: Main Conference - Search and Index (Mediterranean Ballroom)
Chair(s): Idit KeidarTechnion - Israel institute of technology
PPoPP-2020-papers15:45 - 16:10
Talk
Trevor BrownUniversity of Waterloo, Aleksandar ProkopecOracle Labs, Dan AlistarhIST Austria
PPoPP-2020-papers16:10 - 16:35
Talk
Blair ArchibaldUniversity of Glasgow, Patrick MaierUniversity of Stirling, Rob StewartHeriot-Watt University, Phil TrinderUniversity of Glasgow
PPoPP-2020-papers16:35 - 17:00
Talk
Chuzhe TangShanghai Jiao Tong University, Youyun WangShanghai Jiao Tong University, Gansen HuShanghai Jiao Tong University, Zhiyuan DongShanghai Jiao Tong University, Zhaoguo WangShanghai Jiao Tong University, Minjie WangNew York University, Haibo ChenShanghai Jiao Tong University