Multi-colored quadtrees for GIS: Exploiting bit-parallelism for rapid boolean overlay
Multi-colored quadtrees for GIS: Exploiting bit-parallelism for rapid boolean overlay
复制标题
GIS 的多色四叉树：利用位并行性进行快速布尔叠加
DOI：
10.1016/0167-8655(88)90096-7
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
Terence R. Smith
中科院分区：
文献类型：
--
作者：
S. Menon;P. Gao;Terence R. Smith
近年来，已经构建了许多使用四叉树作为底层数据结构的基于镶嵌的 GIS。目前，几乎普遍的趋势是将主题图层表示为二元线性四叉树的集合，每个四叉树对应图层中的每种颜色（值）。在这样的方案中，集合操作是通过二元四叉树的并集和交集来执行的。本文提出了一种替代数据库方案，其中层存储为单个彩色四叉树，使用位列表来存储树中较高节点的值。这允许使用并行位掩码操作通过树的单个自上而下遍历来执行层内任何值集的并集。实验证据表明，这些位图多色四叉树可以加快 GIS 中各层之间的颜色选择和布尔叠加速度。此外，一到四和秋季四叉树的最新发展意味着现在可以在 GIS 中利用常规四叉树的层次结构，而无需支付相关的存储费用。使用这些开发的实验结果表明，与使用二进制四叉树集合（层中的每个值一个）相比，使用位映射多色四叉树表示层对于集合操作来说具有更高的空间和时间效率。
A number of tesselation based GIS using quadtrees as the underlying data structure have been constructed in recent years. At present there is an almost universal trend towards the representation of a thematic layer as a collection of binary, linear quadtrees, one for each color (value) in the layer. In such a scheme set operations are carried out by taking unions and intersections of binary quadtrees. This paper presents an alternative database scheme where a layer is stored as a single multicolored quadtree, using a bit-list to store values at higher nodes in the tree. This allows the union of any set of values within a layer to be carried out by a single top down traversal of the tree, using parallel bit-masking operations. Experimental evidence is presented to show that these Bit-Mapped Multi-Colored quadtrees lead to faster colour selection and boolean overlay between layers in a GIS. Furthermore, the recent development of One-To-Four and Autumnal quadtrees have meant that it is now possible to exploit the hierarchical structure of regular quadtrees in GIS without paying an associated storage penalty. Experimental results using these developments are presented to show that representing a layer using a Bit-Mapped Multi-Colored quadtree is more space and time efficient for set operations in comparison to the use of a collection of binary quadtrees, one for each value in the layer.