TY - GEN
T1 - Estimating top N hosts in cardinality using small memory resources
AU - Ishibashi, Keisuke
AU - Mori, Tatsuya
AU - Kawahara, Ryoichi
AU - Hirokawa, Yutaka
AU - Kobayashi, Atsushi
AU - Yamamoto, Kimihiro
AU - Sakamoto, Hitoaki
PY - 2006/1/1
Y1 - 2006/1/1
N2 - We propose a method to find N hosts that have the N highest cardinalities, where cardinality is the number of distinct items such as the number of flows, ports, or peer hosts. The method also estimates their cardinalities. While existing algorithms to find the top N frequent items can be directly applied to find N hosts that send the N largest numbers of packets through packet data stream, finding hosts that have the N highest cardinalities requires tables of previously seen items for each host to check whether an item of an arrival packet is new, which requires a lot of memory. Even if we use the existing cardinality estimation methods, we still need to have cardinality information about each host. In this paper, we use the property of cardinality estimation, in which the cardinality of intersections of multiple data sets can be estimated with cardinality information of each data set. Using the property, we propose an algorithm that does not need to maintain tables for each host, but only for partitioned addresses of a host and estimate the cardinality of a host as the intersection of cardinalities of partitioned addresses. We also propose a method to find top N hosts in cardinalities which is to be monitored to detect anomalous behavior in networks. We evaluate our algorithm through actual backbone traffic data. While the estimation accuracy of our scheme degrades for small cardinalities, as for the top 100 hosts, the accuracy of our algorithm with 4, 096 tables is almost the same as having tables of every hosts.
AB - We propose a method to find N hosts that have the N highest cardinalities, where cardinality is the number of distinct items such as the number of flows, ports, or peer hosts. The method also estimates their cardinalities. While existing algorithms to find the top N frequent items can be directly applied to find N hosts that send the N largest numbers of packets through packet data stream, finding hosts that have the N highest cardinalities requires tables of previously seen items for each host to check whether an item of an arrival packet is new, which requires a lot of memory. Even if we use the existing cardinality estimation methods, we still need to have cardinality information about each host. In this paper, we use the property of cardinality estimation, in which the cardinality of intersections of multiple data sets can be estimated with cardinality information of each data set. Using the property, we propose an algorithm that does not need to maintain tables for each host, but only for partitioned addresses of a host and estimate the cardinality of a host as the intersection of cardinalities of partitioned addresses. We also propose a method to find top N hosts in cardinalities which is to be monitored to detect anomalous behavior in networks. We evaluate our algorithm through actual backbone traffic data. While the estimation accuracy of our scheme degrades for small cardinalities, as for the top 100 hosts, the accuracy of our algorithm with 4, 096 tables is almost the same as having tables of every hosts.
UR - http://www.scopus.com/inward/record.url?scp=70349655967&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70349655967&partnerID=8YFLogxK
U2 - 10.1109/ICDEW.2006.56
DO - 10.1109/ICDEW.2006.56
M3 - Conference contribution
AN - SCOPUS:70349655967
T3 - ICDEW 2006 - Proceedings of the 22nd International Conference on Data Engineering Workshops
BT - ICDEW 2006 - Proceedings of the 22nd International Conference on Data Engineering Workshops
A2 - Zhou, Xiaofang
A2 - Barga, Roger S.
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 22nd International Conference on Data Engineering Workshops, ICDEW 2006
Y2 - 3 April 2006 through 7 April 2006
ER -