An Investigation of Grid-enabled Tree Indexes for Spatial Query Processing
An Investigation of Grid-enabled Tree Indexes for Spatial Query Processing
复制标题
用于空间查询处理的支持网格的树索引的研究
DOI：
10.1145/3347146.3359384
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Aref, Walid G.
中科院分区：
文献类型：
--
作者：
Shin, Jaewoo;Mahmood, Ahmed R.;Aref, Walid G.
基于二维树的空间索引（例如四叉树或 k-d 树）通常用于索引空间数据。然而，这两种类型的索引都有局限性。尽管二维树可以处理倾斜数据，但索引遍历和树维护可能会很昂贵。相比之下，空间网格的更新开销较低，但不适合倾斜数据。在本文中，我们研究了将网格增强为基于树的索引以进行空间查询处理。我们引入了Grid-Enabled Tree索引（简称GE-Tree）；将网格增强为二维树索引的混合空间索引。特别是，我们研究了在四叉树的叶级使用网格来促进树导航和维护。以额外存储为代价，GE-Tree 实现了恒定时间的树搜索、插入、更新和叶节点邻居查找操作，这与传统二维树中的对数时间形成鲜明对比，例如，在 S ×S 空间中的四叉树情况下为 O(log S)。此外，我们还说明了如何使用支持网格的树来促进范围和 k 最近邻操作。使用真实空间数据的实验结果突出了使用支持网格的树与用于范围和 k-NN 操作的常规空间分区树相比的权衡。此外，对于叶节点访问操作（例如点位置搜索、邻居查找搜索操作和 k 最近邻居搜索），GE 树的性能比传统树或仅网格索引高出两倍。
Two-dimensional tree-based spatial indexes (e.g., the quad tree or the k-d tree) are commonly used for indexing spatial data. However, both types of indexes have limitations. Although two-dimensional trees can handle skewed data, index traversal and tree maintenance can be expensive. In contrast, a spatial grid has low update overhead, but is not suitable for skewed data. In this paper, we investigate the augmentation of a grid into tree-based indexing for spatial query processing. We introduce the Grid-Enabled Tree index (the GE-Tree, for short); a hybrid spatial index that augments a grid into two-dimensional tree indexes. In particular, we investigate the use of a grid at the leaf level of a quadtree to facilitate tree navigation and maintenance. At the expense of the extra storage, the GE-Tree achieves constant-time tree search, insert, update, and leaf node neighbor finding operations, in contrast to the log time in conventional two-dimensional trees, e.g., O(log S) in S ×S space as in the case of the quadtree. Also, we illustrate how the range and k-nearest-neighbor operations can be facilitated using grid-enabled trees. Experimental results using real spatial data highlight the tradeoffs of when using grid-enabled trees pay off in contrast to regular space-partitioning trees for range and k-NN operation. Also, the GE-Tree outperforms conventional tree or grid-only indexes by up to two times for leaf node access operations, e.g., as in point-location search, neighbor-finding search operations, and the k-nearest neighbor search.