TY - JOUR
T1 - Finding frequent items over sliding windows with constant update time
AU - Hung, Regant Y.S.
AU - Lee, Lap Kei
AU - Ting, H. F.
N1 - Funding Information:
E-mail addresses: [email protected] (R.Y.S. Hung), [email protected] (L.-K. Lee), [email protected] (H.F. Ting). 1 This research was supported in part by Hong Kong RGC Grant HKU-7163/07E.
PY - 2010/3/1
Y1 - 2010/3/1
N2 - In this paper, we consider the problem of finding ε{lunate}-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 O (frac(1, ε{lunate})) query and update time, and uses O (frac(1, ε{lunate})) 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 O (frac(1, ε{lunate})).
AB - In this paper, we consider the problem of finding ε{lunate}-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 O (frac(1, ε{lunate})) query and update time, and uses O (frac(1, ε{lunate})) 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 O (frac(1, ε{lunate})).
KW - Approximation algorithms
KW - On-line algorithms
UR - https://www.scopus.com/pages/publications/76849084439
U2 - 10.1016/j.ipl.2009.01.027
DO - 10.1016/j.ipl.2009.01.027
M3 - Article
AN - SCOPUS:76849084439
SN - 0020-0190
VL - 110
SP - 257
EP - 260
JO - Information Processing Letters
JF - Information Processing Letters
IS - 7
ER -