کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428015 686590 2010 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Finding frequent items over sliding windows with constant update time
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Finding frequent items over sliding windows with constant update time
چکیده انگلیسی

In this paper, we consider the problem of finding ϵ-approximate frequent items over a sliding window of size N. A recent work by Lee and Ting (2006) [7] solves the problem by giving an algorithm that supports query and update time, and uses space. Their query time and memory usage are essentially optimal, but the update time is not. We give a new algorithm that supports O(1) update time with high probability while maintaining the query time and memory usage as .

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 110, Issue 7, 1 March 2010, Pages 257-260