دانلود مقاله ISI انگلیسی شماره 44139
عنوان فارسی مقاله

تجزیه و تحلیل رقابتی حفظ آیتم های مکرر از یک جریان

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی تعداد کلمات
44139 2015 10 صفحه PDF سفارش دهید محاسبه نشده
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
Competitive analysis of maintaining frequent items of a stream ☆☆☆
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Theoretical Computer Science, Volume 562, 11 January 2015, Pages 23–32

کلمات کلیدی
الگوریتم های آنلاین - تجزیه و تحلیل رقابتی - آیتم های مکرر - جریان داده
پیش نمایش مقاله
پیش نمایش مقاله تجزیه و تحلیل رقابتی حفظ آیتم های مکرر از یک جریان

چکیده انگلیسی

We study the classic frequent items problem in data streams, but from a competitive analysis point of view. We consider the standard worst-case input model, as well as a weaker distributional adversarial setting. We are primarily interested in the single-slot memory case and for both models we give (asymptotically) tight bounds of Θ(N) and Θ(N3) respectively, achieved by very simple and natural algorithms, where N   is the stream's length. We also provide lower bounds, for both models, in the more general case of arbitrary memory sizes of k≥1k≥1

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.