Space-filling Curves for High-performance Data Mining
Space-filling Curves for High-performance Data Mining
复制标题
用于高性能数据挖掘的空间填充曲线
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
C. Böhm
中科院分区：
文献类型：
--
作者：
C. Böhm
空间填充曲线，如希尔伯特曲线，皮亚诺曲线和Z阶映射自然数或真实的数从二维或更高维空间到一维空间保持局部性。它们有许多应用，如搜索结构，计算机图形学，数值模拟，密码学，并可用于使各种算法的缓存无关。在本文中，我们描述了希尔伯特曲线的一些细节。我们定义的希尔伯特曲线的Mealy-type的有限自动机，确定从二维坐标空间的希尔伯特阶值，反之亦然，在对数的步骤。我们定义了一个上下文无关的语法来生成整个曲线的时间是线性的生成坐标/顺序值对的数量，即每个坐标对或顺序值的恒定时间。我们还审查了两种不同的策略，使生成的曲线没有通常的限制，方型网格的边长是2的幂。最后，我们详细介绍了一些应用，即矩阵乘法、Cholesky分解、Floyd-Warshall算法、k-Means聚类和相似性连接。
Space-filling curves like the Hilbert-curve, Peano-curve and Z-order map natural or real numbers from a two or higher dimensional space to a one dimensional space preserving locality. They have numerous applications like search structures, computer graphics, numerical simulation, cryptographics and can be used to make various algorithms cache-oblivious. In this paper, we describe some details of the Hilbert-curve. We define the Hilbert-curve in terms of a finite automaton of Mealy-type which determines from the two-dimensional coordinate space the Hilbert order value and vice versa in a logarithmic number of steps. And we define a context-free grammar to generate the whole curve in a time which is linear in the number of generated coordinate/order value pairs, i.e. a constant time per coordinate pair or order value. We also review two different strategies which enable the generation of curves without the usual restriction to square-like grids where the side-length is a power of two. Finally, we elaborate on a few applications, namely matrix multiplication, Cholesky decomposition, the Floyd-Warshall algorithm, k-Means clustering, and the similarity join.