Thumbnail
Access Restriction
Subscribed

Author Xiao, Qingjun ♦ Ling, Yibei ♦ Chen, Min ♦ Chen, Shigang
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Cardinality estimation ♦ Big network data ♦ Network stream monitoring
Abstract Cardinality estimation over big network data consisting of numerous flows is a fundamental problem with many practical applications. Traditionally the research on this problem focused on using a small amount of memory to estimate each flow's cardinality from a large range (up to \$10^9\$). However, although the memory needed for each flow has been greatly compressed, when there is an extremely large number of flows, the overall memory demand can still be very high, exceeding the availability under some important scenarios, such as implementing online measurement modules in network processors using only on-chip cache memory. In this paper, instead of allocating a separated data structure (called estimator) for each flow, we take a different path by viewing all the flows together as a whole: Each flow is allocated with a virtual estimator, and these virtual estimators share a common memory space. We discover that sharing at the register (multi-bit) level is superior than sharing at the bit level. We propose a framework of virtual estimators that allows us to apply the idea of sharing to an array of cardinality estimation solutions, achieving far better memory efficiency than the best existing work. Our experiment shows that the new solution can work in a tight memory space of less than 1 bit per flow or even one tenth of a bit per flow --- a quest that has never been realized before.
Description Affiliation: University of Florida, Gainesville, FL, USA (Xiao, Qingjun; Chen, Shigang; Chen, Min) || Telcordia Technologies & Applied Research, Piscataway, NJ, USA (Ling, Yibei)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2014-01-10
Publisher Place New York
Journal ACM SIGMETRICS Performance Evaluation Review (PERV)
Volume Number 43
Issue Number 1
Page Count 12
Starting Page 417
Ending Page 428


Open content in new tab

   Open content in new tab
Source: ACM Digital Library