Teng Dejun, Liang Yanhui, Vo Hoang, Kong Jun, Wang Fusheng
Stony Brook University, USA.
Waymo LLC, USA.
ACM Trans Spat Algorithms Syst. 2022 Jun;8(2). doi: 10.1145/3502221. Epub 2022 Feb 12.
3D spatial data has been generated at an extreme scale from many emerging applications, such as high definition maps for autonomous driving and 3D Human BioMolecular Atlas. In particular, 3D digital pathology provides a revolutionary approach to map human tissues in 3D, which is highly promising for advancing computer-aided diagnosis and understanding diseases through spatial queries and analysis. However, the exponential increase of data at 3D leads to significant I/O, communication, and computational challenges for 3D spatial queries. The complex structures of 3D objects such as bifurcated vessels make it difficult to effectively support 3D spatial queries with traditional methods. In this article, we present our work on building an efficient and scalable spatial query system, for large-scale 3D data with complex structures. iSPEED adopts effective progressive compression for each 3D object with successive levels of detail. Further, iSPEED exploits structural indexing for complex structured objects in distance-based queries. By querying with data represented in successive levels of details and structural indexes, iSPEED provides an option for users to balance between query efficiency and query accuracy. iSPEED builds in-memory indexes and decompresses data on-demand, which has a minimal memory footprint. iSPEED provides a 3D spatial query engine that can be invoked on-demand to run many instances in parallel implemented with, but not limited to, MapReduce. We evaluate iSPEED with three representative queries: 3D spatial joins, 3D nearest neighbor query, and 3D spatial proximity estimation. The extensive experiments demonstrate that iSPEED significantly improves the performance of existing spatial query systems.
3D空间数据已从许多新兴应用中以极高的规模生成，如自动驾驶的高清地图和3D人类生物分子图谱。特别是，3D数字病理学提供了一种革命性的方法来对人体组织进行3D映射，这对于通过空间查询和分析推进计算机辅助诊断和理解疾病非常有前景。然而，3D数据的指数级增长给3D空间查询带来了重大的I/O、通信和计算挑战。3D对象（如分叉血管）的复杂结构使得用传统方法有效支持3D空间查询变得困难。在本文中，我们展示了我们在构建一个高效且可扩展的空间查询系统方面的工作，该系统用于处理具有复杂结构的大规模3D数据。iSPEED对每个3D对象采用有效的渐进式压缩，具有连续的细节层次。此外，iSPEED在基于距离的查询中对复杂结构对象采用结构索引。通过使用连续细节层次表示的数据和结构索引进行查询，iSPEED为用户提供了在查询效率和查询准确性之间进行平衡的选项。iSPEED构建内存索引并按需解压缩数据，内存占用最小。iSPEED提供了一个3D空间查询引擎，可以按需调用以并行运行多个实例，该引擎通过（但不限于）MapReduce实现。我们用三个代表性查询评估iSPEED：3D空间连接、3D最近邻查询和3D空间邻近估计。大量实验表明，iSPEED显著提高了现有空间查询系统的性能。
