For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
LRU-LC: Fast Estimating Cardinality of Flows over Sliding Windows
Jingsong SHAN Jianxin LUO Guiqiang NI Yinjin FU Zhaofeng WU
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2016/10/01
Online ISSN: 1745-1361
Type of Manuscript: LETTER
Category: Fundamentals of Information Systems
streaming data, flow, sketch, cardinality, sliding window,
Full Text: PDF(211.6KB)>>
Estimating the cardinality of flows over sliding windows on high-speed links is still a challenging work under time and space constrains. To solve this problem, we present a novel data structure maintaining a summary of data and propose a constant-time update algorithm for fast evicting expired information. Moreover, a further memory-reducing schema is given at a cost of very little loss of accuracy.