کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952474 | 1442038 | 2016 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Dynamic range majority data structures
ترجمه فارسی عنوان
ساختار دادههای اکثریت داده های محدوده دینامیکی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
ساختارهای داده، محدوده پرس و جو، اکثریت محدوده، گیرنده های سنگین
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Given a set P of n coloured points on the real line, we study the problem of answering range α-majority (or “heavy hitter”) queries on P. More specifically, for a query range Q, we want to return each colour that is assigned to more than an α-fraction of the points contained in Q. We present a new data structure for answering range α-majority queries on a dynamic set of points, where αâ(0,1). Our data structure uses O(n) space, supports queries in O((lgâ¡n)/α) time, and updates in O((lgâ¡n)/α) amortized time. If the coordinates of the points are integers, then the query time can be improved to O(lgâ¡n/(αlgâ¡lgâ¡n)). For constant values of α, this improved query time matches an existing lower bound, for any data structure with polylogarithmic update time. We also generalize our data structure to handle sets of points in d dimensions, for dâ¥2, as well as dynamic arrays, in which each entry is a colour.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 647, 27 September 2016, Pages 59-73
Journal: Theoretical Computer Science - Volume 647, 27 September 2016, Pages 59-73
نویسندگان
Amr Elmasry, Meng He, J. Ian Munro, Patrick K. Nicholson,