EFFICIENT PROBABILISTIC COUNTING SCHEME FOR STREAM-EXPRESSION CARDINALITIES

In one embodiment, a method of monitoring a network. The method includes, at each node of a fixed set, constructing a corresponding vector of M components based on data packets received at the node during a time period, M being an integer greater than 1, the fixed set being formed of some nodes of the network; and, based on the constructed vectors, estimating how many of the received data packets have been received by all of the nodes of the set or estimating how many flows of the received data packets have data packets that have passed through all of the nodes of the set. The constructing includes updating a component of the vector of one of the nodes in response to the one of the nodes receiving a data packet. The updating includes selecting the component for updating by hashing a property of the data packet received by the one of the nodes.