Spatial joins using seeded trees
Spatial joins using seeded trees
复制标题
DOI：
10.1145/191839.191881
复制
发表时间：
1994-05
期刊：
影响因子：
--
通讯作者：
Ming-Ling Lo;C. Ravishankar
中科院分区：
文献类型：
--
作者：
Ming-Ling Lo;C. Ravishankar
现有的空间连接方法假设参与数据集的索引存在。此假设对于涉及多个地图图层叠加的应用程序或涉及非空间选择的查询是不现实的。在本文中，我们探讨了一个空间连接方法，动态地构建索引树称为种子树在连接时间。该方法使用连接过程中涉及的数据集的知识。种子树是一种类似R树的结构，分为种子层和生长层。种子层中的节点用于在树构造期间引导树生长。种子层还可以用于在构建过程中过滤掉一些输入数据，从而减小树的大小。我们开发了一种技术，使用中间链表在树的建设和显着加快树的建设过程。该技术允许大量的随机磁盘访问在树的建设被替换为较小数量的顺序访问。我们的性能研究表明，使用种子树的空间连接在磁盘I/O方面明显优于使用其他方法的空间连接。除了使用种子级过滤之外，所产生的CPU损失也较低。
Existing methods for spatial joins assume the existence of indices for the participating data sets. This assumption is not realistic for applications involving multiple map layer overlays or for queries involving non-spatial selections. In this paper, we explore a spatial join method that dynamically constructs index trees called seeded trees at join time. This methods uses knowledge of the data sets involved in the join process. Seeded trees are R-tree like structures, and are divided into the seed levels and the grown levels. The nodes in the seed levels are used to guide tree growth during tree construction. The seed levels can also be used to filter out some input data during construction, thereby reducing tree size. We develop a technique that uses intermediate linked lists during tree construction and significantly speeds up the tree construction process. The technique allows a large number of random disk accesses during tree construction to be replaced by smaller numbers of sequential accesses. Our performance studies show that spatial joins using seeded trees outperform those using other methods significantly in terms of disk I/O. The CPU penalties incurred are also lower except when seed-level filtering is used.