LRU-LC: Fast Estimating Cardinality of Flows over Sliding Windows

Jingsong SHAN  Jianxin LUO  Guiqiang NI  Yinjin FU  Zhaofeng WU  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E99-D   No.10   pp.2629-2632
Publication Date: 2016/10/01
Publicized: 2016/06/29
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2015EDL8263
Type of Manuscript: LETTER
Category: Fundamentals of Information Systems
Keyword: 
streaming data,  flow,  sketch,  cardinality,  sliding window,  

Full Text: PDF(211.6KB)>>
Buy this Article



Summary: 
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.