发明名称 |
ADAPTIVE DISTINCT COUNTING FOR NETWORK-TRAFFIC MONITORING AND OTHER APPLICATIONS |
摘要 |
In one embodiment, a counting method of the invention uses an adaptive sketching-update process to compress an unknown cardinality into a counter value that counts the number of binary ones in a hashed bitmap vector. The sketching- update process is probabilistic in nature and uses bit-flip probabilities that are adaptively decreased as the counter value increases. Parameters of the sketching- update process are selected so that the relative error of cardinality estimates obtained based on the counter values is relatively small and substantially constant over a relatively wide range of cardinalities, e.g., from one to about one million. Due to the latter property, the counting method can advantageously be implemented in the form of embedded software that relies on a relatively small, fixed amount of memory. |
申请公布号 |
WO2011119436(A1) |
申请公布日期 |
2011.09.29 |
申请号 |
WO2011US29036 |
申请日期 |
2011.03.18 |
申请人 |
ALCATEL-LUCENT USA INC.;CHEN, AIYOU;CAO, JIN;MENTEN, LARRY |
发明人 |
CHEN, AIYOU;CAO, JIN;MENTEN, LARRY |
分类号 |
H04L12/26 |
主分类号 |
H04L12/26 |
代理机构 |
|
代理人 |
|
主权项 |
|
地址 |
|