R-Grove: growing a family of R-trees in the big-data forest
R-Grove: growing a family of R-trees in the big-data forest
复制标题
R-Grove：在大数据森林中种植 R 树家族
DOI：
10.1145/3274895.3274984
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Ahmed Eldawy
中科院分区：
文献类型：
--
作者：
Tin Vu;Ahmed Eldawy
空间大数据的快速增长促使研究界开发多种空间大数据系统。无论其架构如何，所有这些系统的基本要求之一是跨机器有效地划分数据。广泛使用的大空间索引技术是通过为输入样本构建临时树并使用其叶节点作为分区边界来重用现有的搜索树，例如 R 树族。然而，我们在本文中表明，这种方法有很大的局限性，使其不适合大数据环境。本文研究了使用 R 树家族中的三种流行树来索引大空间数据，即 Guttman 的原始 R 树、R* 树和 RR* 树。我们表明，由于设计上的根本限制，整个 R 树家族还没有准备好在大数据森林中生长。为了克服这些限制，我们提出了三个新索引，即 R-Grove、R*-Grove 和 RR*-Grove，它们经过根本性修改以适应大数据，同时继承了传统索引对应物的主要特征。由于所有提出的索引均已开源公开，我们希望这些新索引能够被社区采用，以更好地服务于空间大数据研究。
The rapid growth of big spatial data urged the research community to develop several big spatial data systems. Regardless of their architecture, one of the fundamental requirements of all these systems is to partition the data efficiently across machines. A widely-used technique for big spatial indexing is to reuse existing search trees asis, e.g., the R-tree family, by building a temporary tree for a sample of the input and use its leaf nodes as partition boundaries. However, we show in this paper that this approach has major limitations that make it unsuitable for the big data environment. This paper studies the use of three popular trees from the R-tree family to index big spatial data, namely, the original R-tree by Guttman, R*-tree, and RR*-tree. We show that the entire family of R-trees is not ready to grow in the big data forest due to fundamental limitations in their design. To overcome these limitations, we propose three new indexes, namely, R-Grove, R*-Grove, and RR*-Grove, which are fundamentally modified to work with big data while inheriting the main characteristics of their traditional index counterparts. With all the proposed indexes publicly available as open source, we hope that these new indexes will be adopted by the community to better serve big spatial data research.