Rectangle-efficient aggregation in spatial data streams
Rectangle-efficient aggregation in spatial data streams
复制标题
空间数据流中的矩形高效聚合
DOI：
10.1145/2213556.2213595
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
David P. Woodruff
中科院分区：
文献类型：
--
作者：
Srikanta Tirthapura;David P. Woodruff
我们考虑了多维轴对齐矩形数据流上的聚集估计。矩形是空间数据库中最基本的基元对象，而矩形的高效聚集是一项基本任务。数据流模型已经成为处理海量数据库的事实模型，在这些数据库中，数据驻留在外部存储器或云中，并通过主存储器进行流动。对于点p，设n(P)表示流中所有包含p的矩形的权重之和，我们给出了基本问题的次最优解，包括(1)k阶频率矩Fk=∑点p|n(P)|k，(2)求给定p的n(P)的计数形式的刺激性查询，(3)识别重击点，即n(P)大的点p。FK的一个重要特例是F0，它对应于矩形并集的体积。这是计算几何学中一个著名的问题，被称为“Klee的测量问题”，我们的工作在维度大于1的流动模型中产生了第一个解。
We consider the estimation of aggregates over a data stream of multidimensional axis-aligned rectangles. Rectangles are a basic primitive object in spatial databases, and efficient aggregation of rectangles is a fundamental task. The data stream model has emerged as a de facto model for processing massive databases in which the data resides in external memory or the cloud and is streamed through main memory. For a point p, let n(p) denote the sum of the weights of all rectangles in the stream that contain p. We give near-optimal solutions for basic problems, including (1) the k-th frequency moment Fk = ∑ points p|n(p)|k, (2)~the counting version of stabbing queries, which seeks an estimate of n(p) given p, and (3) identification of heavy-hitters, i.e., points p for which n(p) is large. An important special case of Fk is F0, which corresponds to the volume of the union of the rectangles. This is a celebrated problem in computational geometry known as "Klee's measure problem", and our work yields the first solution in the streaming model for dimensions greater than one.