Three-Dimensional Spatial Join Count exploiting CPU Optimized STR R-Tree
Three-Dimensional Spatial Join Count exploiting CPU Optimized STR R-Tree
复制标题
利用 CPU 优化的 STR R 树的三维空间连接计数
DOI：
10.1109/bigdata.2016.7840944
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Osamu Tatebe
中科院分区：
文献类型：
--
作者：
Ryuya Mitsuhashi;Hideyuki Kawashima;Takahiro Nishimichi;Osamu Tatebe
在这项研究中，我们试图解决关于空间连接计数的问题，在该问题中，对于给定的模拟结果，光晕周围的粒子数量只被计数一次。高效的空间索引是加速计算的必要条件，因此，我们提出了一种CPU优化的排序瓦递归R-树，它采用并行基数排序和线程池节点打包以及单指令多数据指令。在对天文数据进行的实验中，与使用传统的CPU优化R树相比，该方法的性能提高了26.8倍。我们还提出了一种局部物化的方法来处理超出主存容量的大量数据。为了加速该方法，我们提出了一种构造-搜索-销毁流水线，该流水线利用线程池来隐藏索引构造和销毁的延迟。与传统的CPU优化R-树相比，流水线方法的性能提高了27.5倍。我们所有的代码都可以在GitHub上找到。
In this study, we attempt to address the issue regarding the spatial join count, where in the number of particles around a halo is counted only once for a given simulation result. An efficient spatial index is necessary for accelerated counting; therefore, we propose a CPU optimized sort-tile-recursive R-tree that employs a parallel radix sort and node packing with thread pool and single instruction multiple data instructions. In an experiment conducted with astronomical data, the proposed method demonstrates an improvement in performance by 26.8 times compared with that using a conventional CPU optimized R-tree. We also propose a partial materialization approach to handle large amount of data that exceeds the capacity of main memory. To accelerate the approach, we propose a construct-search-destruct pipeline that exploits a thread pool to conceal the latency of the construction and destruction of the index. The pipelining method achieves an improvement in performance by 27.5 times compared with that of a conventional CPU optimized R-tree. All our codes are available on GitHub.