Dynamic Pipelining of Multidimensional Range Queries. The problem of evaluating orthogonal range queries efficiently has been studied widely in the data structures community. It has been common wisdom for several years that for queries containing more than 20%  of  the  elements  of  the  dataset  a  linear  scanning  of  the  data  was the most efficient solution. In recent experimental works using modern hardware xe2x80x93with main memory and parallelismxe2x80x93 the conclusion is that linear scan is preferable for almost every query configuration (even containing a 1% of the data). In this work we propose an alternative approach to evaluate multidimensional range queries based on the dynamic pipeline paradigm xe2x80x93using main memory and concurrency. Our aim is to prove that under this  framework,  it  is  possible  to  beat  the  performance  of  linear scanning  by  the  one  of  hierarchical  multidimensional  data  structures xe2x80x93such as kd trees, quad trees, Rtrees or similar.

NonBlocking Interpolation Search Trees with DoublyLogarithmic Running Time 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 interpolationbased data structures were investigated in the past, their nonblocking concurrent variants have received very little attention so far.NIn this paper, we propose the first nonblocking 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.NTrevor BrownUniversity