Parallel Range, Segment and Rectangle Queries with Augmented Maps
Parallel Range, Segment and Rectangle Queries with Augmented Maps
复制标题
使用增强地图进行并行范围、线段和矩形查询
DOI：
10.1137/1.9781611975499.13
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
G. Blelloch
中科院分区：
文献类型：
--
作者：
Yihan Sun;G. Blelloch
范围查询、线段查询和矩形查询问题是计算几何中的基本问题，在许多领域都有广泛应用。尽管在这些问题上有大量的理论工作，但高效的实现可能很复杂。我们所知的并行算法的实际实现很少，而且大多数实现没有严格的理论界限。我们专注于这些查询的简单高效的并行算法和实现，它们在理论上有严格的最坏情况界限，在实践中有良好的并行性能。我们建议使用一个简单的框架（扩充映射）来对问题进行建模。基于扩充映射接口，我们开发了支持二维范围查询、线段查询和矩形查询的多层树结构和扫描线算法。对于扫描线算法，我们提出了一种并行范式并展示了相应的成本界限。我们所有的数据结构在理论上构建是高效的，并且实现了较低的并行深度。查询时间几乎与输出大小成线性关系。
我们使用一个并行扩充映射库实现了论文中描述的所有数据结构。基于该库，每个数据结构只需要大约100行C++代码。我们在大型数据集（多达\(10^8\)个元素）和一台具有72核（144个超线程）的机器上测试了它们的性能。并行构建实现了32 - 68倍的加速。查询的加速倍数高达126倍。我们的顺序实现无论是在构建还是查询方面都比CGAL库至少快2倍。在某些情况下，我们的顺序实现可能比Boost库中的R - 树稍慢（0.6 - 2.5倍），但查询性能比Boost显著更好（1.6 - 1400倍）。
The range, segment and rectangle query problems are fundamental problems in computational geometry, and have extensive applications in many domains. Despite the significant theoretical work on these problems, efficient implementations can be complicated. We know of very few practical implementations of the algorithms in parallel, and most implementations do not have tight theoretical bounds. We focus on simple and efficient parallel algorithms and implementations for these queries, which have tight worst-case bound in theory and good parallel performance in practice. We propose to use a simple framework (the augmented map) to model the problem. Based on the augmented map interface, we develop both multi-level tree structures and sweepline algorithms supporting range, segment and rectangle queries in two dimensions. For the sweepline algorithms, we propose a parallel paradigm and show corresponding cost bounds. All of our data structures are work-efficient to build in theory and achieve a low parallel depth. The query time is almost linear to the output size.
We have implemented all the data structures described in the paper using a parallel augmented map library. Based on the library each data structure only requires about 100 lines of C++ code. We test their performance on large data sets (up to $10^8$ elements) and a machine with 72-cores (144 hyperthreads). The parallel construction achieves 32-68x speedup. Speedup numbers on queries are up to 126-fold. Our sequential implementation outperforms the CGAL library by at least 2x in both construction and queries. Our sequential implementation can be slightly slower than the R-tree in the Boost library in some cases (0.6-2.5x), but has significantly better query performance (1.6-1400x) than Boost.
DOI：
10.1145/3210377.3210380
发表时间：
2018-05
期刊：
Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
G. Blelloch;Yan Gu;Yihan Sun;Julian Shun
通讯作者：
G. Blelloch;Yan Gu;Yihan Sun;Julian Shun