.png){kind=icon}
.png){kind=icon}
Return
Quadboost: A Scalable Concurrent Quadtree
.png){kind=icon}
OA
AI
DOI：10.1109/TPDS.2017.2762298.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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, in which the move operation combines the searches for different keys together and modifies different positions atomically. To increase its concurrency, a decoupling approach is proposed to separate physical adjustment from logical removal within the remove operation. In addition, we design a continuous find mechanism to reduce the search cost. Experimental results show that quadboost scales well on a multi-core system with 32 hardware threads. It outperforms existing concurrent trees in retrieving two-dimensional keys with up to 109 percent improvement when the number of threads is large. Furthermore, the move operation achieves better performance than the best-known algorithm with up to 47 percent.
Keywords:
Concurrent data structures
quadtree
continuous find
decoupling
LCA
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
5.2K
Citations:
1.1W