Efficient aggregation over objects with extent
Efficient aggregation over objects with extent
复制标题
DOI：
10.1145/543613.543629
复制
发表时间：
2002-06
期刊：
影响因子：
--
通讯作者：
Donghui Zhang;V. Tsotras;D. Gunopulos
中科院分区：
文献类型：
--
作者：
Donghui Zhang;V. Tsotras;D. Gunopulos
我们研究了在非零范围的对象上有效计算总和/计数/平均聚合的问题。最近有关计算多维聚合的工作集中在多维网格或一维间隔上具有零范围（点）的对象。然而，在许多空间和/或时空应用中，对象具有不同维度的范围，而它们可以位于应用空间中的任何位置。聚合谓词通常由多维框（框和聚合）来描述。我们研究该问题的两种变体。在简单的情况下，只要对象与查询框相交，该对象的值就会对整个聚合结果做出贡献。更复杂的是本文引入的功能框和聚合，其中对象按照其与查询框的交集大小成比例地参与聚合。我们首先证明这两个问题都可以简化为支配和查询。传统上，优势和查询是通过静态结构（ECDF 树）在主内存中进行寻址的。然后，我们提出了两个扩展，即 ECDF-B-tree，使该结构基于磁盘且动态。最后，我们介绍了结合了每个 ECDF-B 树优点的 DA 树。我们进行实验，比较 ECDF-B 树、BA 树和传统 R* 树（已增强以包含其索引节点上的聚合信息）在空间数据集上的性能。我们的评估再次证实 BA 树具有更稳健的性能。与增强的 R* 树相比，BA 树在查询性能方面提供了巨大的改进，但代价是一些有限的额外空间。
We examine the problem of efficiently computing sum/count/avg aggregates over objects with non-zero extent. Recent work on computing multi-dimensional aggregates has concentrated on objects with zero extent (points) on a multi-dimensional grid, or one-dimensional intervals. However, in many spatial and/or spatio-temporal applications objects have extent in various dimensions, while they can be located anywhere in the application space. The aggregation predicate is typically described by a multi-dimensional box (box-sum aggregation). We examine two variations of the problem. In the simple case an object's value contributes to the aggregation result as a whole as long as the object intersects the query box. More complex is the functional box-sum aggregation introduced in this paper, where objects participate in the aggregation proportionally to the size of their intersection with the query box. We first show that both problems can he reduced to dominance-sum queries. Traditionally dominance-sum queries are addressed in main memory by a static structure, the ECDF-tree. We then propose two extensions, namely the ECDF-B-trees, that make this structure disk-based and dynamic. Finally, we introduce the DA-tree that combines the advantages from each ECDF-B-tree. We run experiments comparing the performance of the ECDF-B-trees, the BA-tree and a traditional R*-tree (which has been augmented to include aggregation information on its index nodes) over spatial datasets. Our evaluation reaffirms that the BA-tree has more robust performance. Compared against the augmented R*-tree, the BA-tree offers drastic improvement in query performance at the expense of some limited extra space.