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
Times are displayed in time zone: Tijuana, Baja California change

15:45 - 17:00: Search and Index (Mediterranean Ballroom)Main Conference
Chair(s): Idit KeidarTechnion - Israel institute of technology
15:45 - 16:10
Non-Blocking Interpolation Search Trees with Doubly-Logarithmic Running Time
Main Conference
Trevor BrownUniversity of Waterloo, Aleksandar ProkopecOracle Labs, Dan AlistarhIST Austria
16:10 - 16:35
YewPar: Skeletons for Exact Combinatorial Search
Main Conference
Blair ArchibaldUniversity of Glasgow, Patrick MaierUniversity of Stirling, Rob StewartHeriot-Watt University, Phil TrinderUniversity of Glasgow
16:35 - 17:00
XIndex: A Scalable Learned Index for Multicore Data Storage
Main Conference
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