Non-blocking interpolation search trees with doubly-logarithmic running time
Trevor Brown, Aleksandar Prokopec, Dan Alistarh
Abstract
Balanced search trees typically 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.
Topics & Concepts
Blocking (statistics)Interpolation (computer graphics)LogarithmComputer scienceKey (lock)AlgorithmRunning timeMathematicsArtificial intelligenceComputer networkComputer securityMathematical analysisMotion (physics)Parallel Computing and Optimization TechniquesAlgorithms and Data CompressionMass Spectrometry Techniques and Applications