کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
415665 681222 2013 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Efficient external memory structures for range-aggregate queries
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Efficient external memory structures for range-aggregate queries
چکیده انگلیسی

We present external memory data structures for efficiently answering range-aggregate queries. The range-aggregate problem is defined as follows: Given a set of weighted points in RdRd, compute the aggregate of the weights of the points that lie inside a d-dimensional orthogonal query rectangle. The aggregates we consider in this paper include count, sum, and max. First, we develop a structure for answering two-dimensional range-count queries that uses O(N/B)O(N/B) disk blocks and answers a query in O(logBN) I/Os, where N is the number of input points and B is the disk block size. The structure can be extended to obtain a near-linear-size structure for answering range-sum queries using O(logBN) I/Os, and a linear-size structure for answering range-max queries in O(logB2N) I/Os. Our structures can be made dynamic and extended to higher dimensions.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 46, Issue 3, April 2013, Pages 358–370
نویسندگان
, , , , ,