Bitmap algorithms for counting active flows on high speed links

By Cristian Estan, George Varghese, M. Fisk. ACM/SIGCOMM Internet Measurement Conference, 2003

409 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/673f79762c4136fe0853846a2e51bf7ea7c17a0d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

An optimal algorithm for the distinct elements problem (2010, methodology): “…n ) O ( ε − 2 (log( ε − 1 ) + log log n )) Algorithm III in the paper [16] O ( ε − 2 log log n + log n ) - Assumes random oracle, additive error [17] O ( ε − 2 log n ) - Assumes random oracle [6] O ( ε − 2 log n ) O (log( ε − 1 )) [19] O ( ε − 2 log log n + log n ) - Assumes random oracle,…”
Building a better NetFlow (2004, neutral): “ANF guarantees that it will never report more (cid:13)ow records and it will report fewer only for pathological tra(cid:14)c mixes such as fewer than M large (cid:13)ows generating all the tra(cid:14)c or an extremely lightly loaded link.”
Automated Worm Fingerprinting (2004, methodology): “tic counting [12] and multiresolution bitmaps [11] can provide accurate counts they require significantly more”
Software Defined Traffic Measurement with OpenSketch (2013, positive): “The multi-resolution bitmap [21] uses a similar idea to count the number of unique elements in each range.”
HyperLogLog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm (2013, background): “In [14] the authors compare 12 algorithms analytically and the most promising 8 experimentally on a single data set with 1.9 · 106 distinct elements, among them LogLog, LinearCounting and MultiresolutionBitmap [5], a multiscale version of LinearCounting.”
Efficient and reliable low-power backscatter networks (2012, methodology): “…exists an absolute constant C > 1 such that for any ǫ , δ ∈ ( 0, 1 ) , if the number of slots per step s is equal to C log ( 1 /δ ) /ǫ 2 , then with probability at least We note the proof is similar in nature to the standard analysis of streaming and estimation algorithms as seen in [15, 32, 29].”
Cardinality Estimators do not Preserve Privacy (2018, methodology): “These applications include network monitoring [22], on-line analytical processing [35, 40], query processing, and database management [42].”
Packet Transactions: High-Level Programming for Line-Rate Switches (2015, background): “Examples include active queue management [53, 52, 67, 74, 76], scheduling [88], congestion control with switch feedback [64, 93, 60, 28], network measurement [98, 51, 50], security [34], and trafﬁc load balancing [27].”
Data streaming algorithms for efficient and accurate estimation of flow size distribution (2004, methodology): “Our design is inspired by a multi-resolution scheme used in [6].”
HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm (2007, background): “Introduction The purpose of this note is to present and analyse an efficient algorithm for estimating the number of distinct elements, known as the cardinality, of large data ensembles, which are referred to here as multisets and are usually massive streams (read-once sequences).”
A scalable distributed information management system (2004, background): “[13], this information is useful for a variety of applications such as intrusion detection (e.”