  A sorted set (or map) is one of the most used data types in computer science.
In addition to standard set operations, like Insert, Remove, and Contains, it
can provide set-set operations such as Union,Intersection, and Difference. Each
of these set-set operations is equivalent to some batched operation: the data
structure should be able to execute Insert, Remove, and Contains on a batch of
keys. It is obvious that we want these "large" operations to be parallelized.
These sets are usually implemented with the trees of logarithmic height, such
as 2-3 trees, treaps, AVL trees, red-black trees, etc. Until now, little
attention was devoted to data structures that work asymptotically better under
several restrictions on the stored data. In this work, we parallelize
Interpolation Search Tree which is expected to serve requests from a smooth
distribution in doubly-logarithmic time. Our data structure of size n performs
a batch of m operations in O(m log log n) work and poly-log span.
