  Building concurrent spatial trees is more complicated than binary search
trees since a space hierarchy should be preserved during modifications. We
present a non-blocking quadtree-quadboost-that supports concurrent insert,
remove, move, and contain operations. To increase its concurrency, we propose a
decoupling approach that separates physical adjustment from logical removal
within the remove operation. In addition, we design a continuous find mechanism
to reduce its search cost. The move operation combines the searches for
different keys together and modifies different positions with atomicity. The
experimental results show that quadboost scales well on a multi-core system
with 32 hardware threads. More than that, it outperforms existing concurrent
trees in retrieving two-dimensional keys with up to 109% improvement when the
number of threads is large. The move operation proved to perform better than
the best-known algorithm, with up to 47%.
