arXiv:1710.03155v3 [cs.DS] 15 Oct 2017

Fast Flow Volume Estimation
Ran Ben Basat

Gil Einziger

Technion

Nokia Bell Labs

Technion

sran@cs.technion.ac.il

gil.einziger@nokia.com

roy@cs.technion.ac.il

ABSTRACT

of flow volumes in both streams and sliding windows.
Finally, per flow measurements are not enough for
certain functionalities like anomaly detection and Distributed Denial of Service (DDoS) attack detection [40,
43]. In such attacks, each attacking device only generates a small portion of the traffic and is not a heavy
hitter. Yet, their combined traffic volume is overwhelming. Hierarchical heavy hitters (HHH) aggregates traffic
from IP addresses that share some common prefix [6].
In a DDoS, when attacking devices share common IP
prefixes, HHH can discover the attack. To that end, we
consider volume based HHH detection as well.
Before explaining our contribution, let us first motivate why packet counting solutions are not easily adaptable to volume estimation. Counter algorithms typically maintain a fixed set of counters [3, 4, 16, 29, 34,
35, 39] that is considerably smaller than the number
of flows. Ideally, counters are allocated to the heavy
hitters. When a packet from an unmonitored flow arrives, the corresponding flow is allocated the minimal
counter [35] or a counter whose value has dropped below a dynamically increased threshold [34].
We refer to a stream in which each packet is associated with aweight is as a weighted stream. Similarly,
we refer to streams without weights, or when all packets
receive the same weight as unweighted. For unweighted
streams, ordered data structures allow constant time
updates and queries [3,35], since when a counter is incremented, its relative order among all counters changes by
at most one. Unfortunately, maintaining the counters
sorted after a counter increment in a weighted stream
either requires to search for its new location, which incurs a logarithmic cost, or resorting to logarithmic time
data structures like heaps. The reason is that if the
counter is incremented by some value w, its relative position might change by up to w positions. This difficulty
motivates our work1 .

The increasing popularity of jumbo frames means growing
variance in the size of packets transmitted in modern networks. Consequently, network monitoring tools must maintain explicit traffic volume statistics rather than settle for
packet counting as before. We present constant time algorithms for volume estimations in streams and sliding windows, which are faster than previous work. Our solutions are
formally analyzed and are extensively evaluated over multiple real-world packet traces as well as synthetic ones. For
streams, we demonstrate a run-time improvement of up to
2.4X compared to the state of the art. On sliding windows,
we exhibit a memory reduction of over 100X on all traces
and an asymptotic runtime improvement to a constant. Finally, we apply our approach to hierarchical heavy hitters
and achieve an empirical 2.4-7X speedup.

1.

Roy Friedman

INTRODUCTION

Traffic measurement is vital for many network algorithms such as routing, load balancing, quality of service, caching and anomaly/intrusion detection [18, 20,
28, 37]. Typically, networking devices handle millions
of flows [38, 41]. Often, monitoring applications track
the most frequently appearing flows, known as heavy
hitters, as their impact is most significant.
Most works on heavy hitters identification have focused on packet counting [3, 17, 42]. However, in recent
years jumbo frames and large TCP packets are becoming increasingly popular and so the variability in packet
sizes grows. Consequently, plain packet counting may
no longer serve as a good approximation for bandwidth
utilization. For example, in data collected by [23] in
2014, less than 1% of the packets account for over 25%
of the total traffic. Here, packet count based heavy hitters algorithms might fail to identify some heavy hitter
flows in terms of bandwidth consumption.
Hence, in this paper we explicitly address monitoring
of flow volume rather than plain packet counting. Further, given the rapid line rates and the high volume of
accumulating data, an aging mechanism such as a sliding window is essential for ensuring data freshness and
the estimation’s relevance. Hence, we study estimations

1.1

Contributions

1
The most naive approach treats a packet of size w as w
consecutive arrivals of the same packet in the unweighted
case, resulting in linear update times, which is even worse.

1

We contribute to the following network measurement
problems: (i) stream heavy hitters, (ii) sliding window
heavy hitters, (iii) stream hierarchical heavy hitters.
Specifically, our first contribution is Frequent items Algorithm with a Semi-structured Table (FAST), a novel
algorithm for monitoring flow volumes and finding heavy
hitters. FAST processes elements in worst case O(1)
time using asymptotically optimal space. We formally
prove and analyze the performance of FAST. We then
evaluate FAST on 5 real Internet packet traces from a
data center and backbone networks, demonstrating a
2.4X performance gain compared to previous works.
Our second contribution is Windowed Frequent items
Algorithm with a Semi-structured Table (WFAST), a
novel algorithm for monitoring flow volumes and finding
heavy hitters in sliding windows. We evaluate WFAST
on five Internet traces and show that its runtime is reasonably fast, and that it requires as little as 1% of the
memory of previous work [27]. We analyze WFAST and
show that it operates in constant time and is space optimal, which asymptotically improves both the runtime
and the space consumption of previous work. We believe that such a dramatic improvement makes volume
estimation over a sliding window practical!
Our third contribution is Hierarchical Frequent items
Algorithm with a Semi-structured Table (HFAST), which
finds hierarchical heavy hitters. HFAST is created by
replacing the underlying HH algorithm in [36] (Space
Saving) with FAST. We evaluate HFAST and demonstrate an asymptotic update time improvement as well
as an empirical 2.4-7X speedup on real Internet traces.

2.
2.1

and are mostly suitable for software implementation.
The work of [3] suggests a compact static memory implementation of Space Saving that may be more accessible for hardware design. Yet, software implementations are becoming increasingly relevant in networking
as emerging technologies such as NFVs become popular.
Alas, most previous works rely on sorted data structures such as Stream Summary [35] or SAIL [3] that only
operate in constant time for unweighted updates. Thus,
a logarithmic time heap based implementation of Space
Saving was suggested [12] for the more general volume
counting problem. IM-SUM, DIM-SUM [5] and BUSSS [19] are very recent algorithms developed for the
volume heavy-hitters problem (only for streams, with
no sliding windows support). BUS offers a randomized
algorithm that operates in constant time. IM-SUM operates in amortized O(1) time and DIM-SUM in worst
case constant time. Empirically, DIM-SUM it is slower
than FAST. Additionally, DIM-SUM requires 2+φ
 counters, for some φ > 0, for guaranteeing N · M ·  error
and operating in O(φ−1 ) time. FAST only needs half as
many counters for the same time and error guarantees.

2.2

Sliding Windows

Heavy hitters on sliding windows were first studied
by [1]. Given an accuracy parameter (ε), a window
size (W ) and a maximal increment size (M ), such algorithms estimate flows’ volume on the sliding window
with an additive error that is at most W · M · ε.
Their algorithm
requires O 1 log2 1 counters and

1
1
O  log  time for queries and updates. The work
of [30] reduces
the space requirements and update time

to O 1 . An improved algorithm with a constant update time is given in [26]. Further,
[3] provided an al
gorithm that requires O 1 for queries and supports
constant time updates and item frequency queries.
The weighted variant of the problem was only
 studied
by [27], whose algorithm operates in O A time and

requires O A space for a W ·M ·ε approximation; here,
A ∈ [1, M ] is the average packet size in the window.
In this work, we suggest an algorithm
for the weighted

problem that (i) uses optimal O 1 space,
 (ii) performs
heavy hitters queries in optimal O 1 time, and (iii)
performs volume queries and updates in constant time.

RELATED WORK
Streams

Sketches such as Count Sketch (CS) [8] and Count
Min Sketch (CMS) [15] are attractive as they enable
counter sharing and need not maintain a flow to counter
mapping for all flows. Sketches typically only provide
a probabilistic estimation, and often do not store flow
identifiers. Thus, they cannot find the heavy hitters,
but only focus on the volume estimation problem. Advanced sketches, such as Counter Braids [32], Randomized Counter Sharing [31] and Counter Tree [9], improve
accuracy, but their queries require complex decoding.
In counter based algorithms, a flow table is maintained, but only a small number of flows are monitored.
These algorithms differ from each other in the size and
maintenance policy of the flow table, e.g., Lossy Counting [34] and its extensions [16, 39], Frequent [29] and
Space Saving [35]. Given ideal conditions, counter algorithms are considered superior to sketch based techniques. Particularly, Space Saving was empirically shown
to be the most accurate [11,12,33]. Many counter based
algorithms were developed by the databases community

2.3

Hierarchical Heavy Hitters

Hierarchical Heavy Hitters (HHH) were addressed,
e.g., in [13, 14, 21, 36, 43]. HHH algorithms monitor aggregates of flows that share a common prefix. To do so,
HHH algorithms treat flows identifiers as a hierarchical
domain. We denote by H the size of this domain.
The full and partial ancestry algorithms [14] are trie
based algorithms that require O H log N space and
operate at O (H log N ) time. The state of the art [36]
algorithm requires O H space and its update time for
2

Symbol
S
N
M
W
U
[r]
φ
vx
v
c
x
W
vx
d
W
v


weighted inputs is O H log( 1 ) . It solves the approximate HHH problem by dividing it into multiple simpler
heavy hitters problems. In our work, we replace the
underlying heavy hitters algorithm of [36]
 with FAST,
which yields a space complexity of O H and an update
complexity of O(H). That is,
 we improve the update
complexity from O H log 1 to O (H).

3.

PRELIMINARIES

x


θ

Meaning
stream
number of elements in the stream
maximal value of an element in the stream
window size
the universe of elements
the set {0, 1, ..., r − 1}
FAST performance parameter.
the volume of an element x in S
an estimation of vx
the volume of element x in the last W elements of S
W
an estimation of vx
estimation accuracy parameter
heavy hitters threshold parameter

Given a set U and a positive integer M ∈ N+ , we say
that S is a (U, M )-weighted stream if it contains a seTable 1: List of Symbols
quence of hid, weighti pairs. Specifically: S = hp1 , p2 , . . . pN i,
where ∀i ∈ 1, . . . , N : pi ∈ U × {1, . . . M }. Given a
packet pi = (di , wi ), we say that di is pi ’s id while wi is
its weight; N is the stream length, and M is the maximal packet size. Notice that the same packet id may
possibly appear multiple times in the stream, and each
such occurrence may potentially be associated with a
different weight. Given a (U, M )-weighted stream S, we
denote vx , the volume of id x, as the
P total weight of all
packets with id x. That is: vx , i∈{1,...,N }: wi . For a
Figure 1: An example of how FAST utilizes the SOS
di =x
structure. Here, flows are partially ordered according to
+
window size W ∈ N , we denote the window volume of
the third digit (100’s), and each flow maintains its own
id x as its total weight of packetsPwith id x within the
remainder; e.g., the estimated volume of D is vc
D = 583.
W
last W packets, that is: vx ,
i∈{N −W +1,...,N }: wi .
di =x
are not known in advance. Hence, it is impossible to
We seek algorithms that support the operations:
a-priori allocate counters only to these flows. The basic
ADD(hx, wi): append a packet with identifier x and
notations used in this work are listed in Table 1.
weight w to S.
Query(x): return an estimate vbx of vx .
4. FREQUENT ITEMS ALGORITHM WITH
W
W
WinQuery(x): return an estimate vc
x of vx .
A SEMI-STRUCTURED TABLE (FAST)
We now formally define the main problems in this work:
In this section, we present Frequent items Algorithm
(, M)-Volume Estimation: Query(x) returns an
with a Semi-structured Table (FAST), a novel algorithm
estimation (vbx ) that satisfies vx ≤ vbx ≤ vx + N · M · .
that achieves constant time weighted updates. FAST
(W, , M)-Volume Estimation: WinQuery(x) reW
c
c
uses a data structure called Semi Ordered Summary
W
W
turns an estimation (vx ) that satisfies vx ≤ vx ≤
W
(SOS), which maintains flow entries in a semi ordered
vx + W · M · .
manner. That is, similarly to previous works, SOS
(θ, , M)-Approximate Weighted Heavy Hitters:
groups flows according to their volume, each of which
returns a set H ⊆ U such that:
is called a volume group. The volume groups are main∀x ∈ U :(vx > N · M · θ =⇒ x ∈ H) ∧
tained in an ordered list. Each volume group is associated with a value C that determines the volume of its
(vx < N · M · (θ − ) =⇒ x ∈
/ H).
nodes. Unlike existing data structures, counters within
(W, θ, , M)-Approximate Weighted Heavy Hiteach volume group are kept unordered.
ters: returns a set H ⊆ U such that
Unlike previous works, the grouping is done at coarse
granularity. Each node (inside a group) includes a vari∀x ∈ U :(vxW > W · M · θ =⇒ x ∈ H) ∧
able called Remainder (denoted R). The volume esti(vxW < W · M · (θ − ) =⇒ x ∈
/ H).
mate of a flow is C + R where R is the remainder of its
Our heavy hitter definitions are asymmetric. That
volume node and C is the value of its volume group.
This semi-ordered structure is unique to SOS and enis, they require that flows whose frequency is above the
ables it to serve weighted updates in O(1). Volume
threshold of N · M · θ (or W · M · θ) are included in
the list, but flows whose volume is slightly less than the
queries are satisfied in constant time using a separate
threshold can be either included or excluded from the
aggregate hash table which maps between each flow
identifier and its SOS node. FAST then uses SOS to
list. This relaxation is necessary as it enables reducing the required amount of space to sub linear. Let us
find a near-minimum flow when needed.
emphasize that the identities of the heavy hitter flows
Figure 1 provides an intuitive example for the case
3

qt (x) the value of Query(x) after seeing t elements.
We slightly abuse the notation and refer to t also as the
time at which the tth element arrived, where time here
is discrete. We denote by Ct the set of elements with
an allocated counter at time t, by rx,t the value of rx
and by cx,t the value of cx . Also, we denote the volume
P
at time t as vx,t , i∈{1,...,t}: wi . All missing proofs

Algorithm 1 FAST (M, , φ)
Initialization:

1:
2:
3:
4:
5:
6:
7:

C ← ∅, ∀x : cx ← 0, rx ← 0,




M ·φ
1+φ
s ←
+ 1 ,C ←
2


function Add(Item x, Weight w)
if x ∈ C or |C|
j < Ckthen
cx ← cx + rx +w
s

8:
9:
10:
11:
12:
13:
14:
15:

rx ← (rx + w) mod s
C ← C ∪ {x}
else
Let m ∈ argminy∈C (cy )
k
j
cx ← cm + s−1+w
s

di =x

appear in Appendix A.
We now show that FAST has a one-sided error.
. arbitrary minimal item

Lemma 1. For any t ∈ N, after seeing any (U, M )weighted stream S of length t, for any x ∈ U : vx ≤ vbx .

rx ← (s − 1 + w) mod s
C ← C \ {m} ∪ {x}
function Query(x)
if x ∈ C or |C| < C then
return rx + s · cx
else
return s − 1 + s · miny∈C cy

We continue by showing that FAST is accurate if
there are only a few distinct items.
m
l
disLemma 2. If the stream contains at most 1+φ

tinct elements then FAST provides an exact estimation
of an items volume upon query.

M = 1, 000. Here, the volume of an item is calculated
by both its group counter (C) and the item’s remainder
(R), e.g., the volume of A is 400 + 32 = 432. Flows
are partially ordered according to their third digit, i.e.,
in multiples of 100, or M/10. Within a specific group,
however, items are unordered, e.g., A, B and J are unordered but all appear before items with volume of at
least 500. As the number of lists to skip prior to an
addition is O(1), the update complexity is also O(1).
Intuitively, flows are only ordered according to volume groups and if we make sure that the maximal weight
can only advance a flow a constant number of flow
groups then SOS operates in constant time. Alas, keeping the flows only partially ordered increases the error. We compensate for such an increase by requiring
a larger number of SOS entries compared to previously
suggested fully ordered structures. The main challenge
in realizing this idea is to analyze the accuracy impact
and provide strong estimation guarantees.

4.1

We now analyze the sum of counters in C.
Lemma 3. For any t ∈ N, after seeing any
(U, M )-weighted
stream S of length t, FAST satisfies:
P
Query(x)
≤ t · M · (1 + φ/2).
x∈Ct
Next, we show a bound on FAST’s estimation error.
Lemma 4. For any t ∈ N, after seeing any (U, M )weighted stream S of length t, for any x ∈ U : vbx ≤
vx + t · M · .
Next, we prove a bound on the run time of FAST.
 
Lemma 5. let φ > 0, FAST adds in O φ1 time.
Next, we combine Lemma 1, Lemma 4 and Lemma 5
to conclude the correctness of the FAST algorithm.
Theorem
l
m 2. For any constant φ > 0, when allocated
1+φ
C ,
counters, FAST operates in constant time


FAST - Accurate
l
m Description

and solves the (, M )-Volume Estimation problem.

FAST employs 1+φ
counters, for some non-negative

constant φ ≥ 0. φ determines how ordered SOS is: for
φ = 0, we get full order, while for φ > 0, it is only ordered up to M ·φ/2 (all flows that fall into the same volume group are unordered, and each group holds a range
of M ·φ/2 values). The runtime is, however, O(1/φ) and
is therefore
constant for any fixed φ. We note that an

Ω 1 counters lower bound is known [35]. Thus, FAST
is asymptotically optimal for constant φ. The pseudo
code of FAST appears in Algorithm 1.

4.2

Finally, FAST also solves the heavy hitters problem:
Theorem
l 3.m For any fixed φ > 0, when allocated
counters, by returning {x ∈ U | vbx ≥
with C , 1+φ

N ·M ·θ}, FAST solves the (θ, , M )-Weighted Heavy
Hitters problem.

5.

WINDOWED FAST (WFAST)

We now present Windowed Frequent items Algorithm
with a Semi-structured Table (WFAST), an efficient algorithm for the (W, , M )-Volume Estimation and
(W, θ, , M )-Weighted Heavy Hitters problems.
We partition the stream into consecutive sequences of
size W
 called frames. Each frame is further divided into
k , 4 blocks, each of size W
k , which we assume is an
integer for simplicity. Figure 2 illustrates the setting.

FAST Analysis

We start by a simple useful observation
 
Observation 1. Let a, b ∈ N : a = b· ab +(a mod b).
For the analysis, we use the following notations: for
every item x ∈ U and stream length t, we denote by
4

Algorithm 2 WFAST (W, M, φ)
1:

Initialization: y ← F requentitemsAlgorithmwithaSemi −
structuredT able(M, 1/k, φ), o ← 0,
2:
B
←
Empt hash table,
b
←
Queue of k + 1 empty queues.
3: function add(Item x, Weight w)
4:
o ← o + 1 mod W
5:
if o = 0 then
. new frame starts
6:
y.flush()
. new block
7:
if o mod W
k = 0 then
8:
b.pop()
9:
b.append(new empty queue)
10:
if b.tail is not empty then
. remove oldest item
11:
oldID ← b.tail.pop()
12:
B[oldID] ← B[oldID] − 1
13:
if B[oldID] = 0 then
14:
B.remove(oldID) 

y .query(x)
15:
prevOverf lowCount ←
M W/k

Figure 2: The stream is divided into intervals of size
W called frames and each frame is partitioned into k
equal-sized blocks. The window of interest is also of size
W , and overlaps with at most 2 frames and k +1 blocks.
k
y
b
B
o

A constant k , d4/εe
A FAST instance using k(1 + φ) counters.
A queue of k + 1 queues.
An efficient implementation appears in [3].
The histogram of b, implemented using a hash table.
The offset within the current frame.

16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:

Table 2: Variables used by the WFAST algorithm.
WFAST uses a FAST instance y to estimate the volume of each flow within the current frame. Once a frame
ends (the stream length is divisible by W ), we “flush”
the instance, i.e., reset all counters and remainders to
0. Yet, we do not “forget” all information in a flush, as
high volume flows are stored in a dedicated data structure. Specifically,
wek sayjthat ank element x overflowed
j
qx,t
q
at time t if M W/k
> Mx,t−1
W/k . We use a queue of
queues structure b to keep track of which elements have
overflowed in each block. That is, each node of the main
queue represents a block and contains a queue of all elements that overflowed in its block. Particularly, the
secondary queues maintain the ids of overflowing elements. Once a block ends, we remove the oldest block’s
node (queue) from the main queue, and initialize a new
queue for the starting block. Finally, we answer queries
about the window volume of an item x by multiplying its overflows count by M W/k, adding the residual
count from y (i.e., the part that is not recorded in b),
plus 2M W/k to ensure an overestimation.
For O(1) time queries, we also maintain a hash table
B that tracks the overflow count for each item. That is,
for each element x, B[x] contains the number of times
x is recorded in b. Since multiple items may overflow in
the same block, we cannot update B once a block ends
in constant time. We address this issue by deamortizing B’s update, and on each arrival we remove a single
item from the queue of the oldest block (if such exists).
The pseudo code of WFAST appears in Algorithm 2
and a list containing its variables description appears
in Table 2. An efficient implementation of the queue of
queues b is described in [3].

5.1

y.add(x,
w)


y .query(x)
if
> prevOverf lowCount then
M W/k

. add item
. overflow

b.head.push(x)
if B.contains(x) then
B[x] ← B[x] + 1
else
B[x] ← 1
. adding x to B
function WinQuery(Item x)
if B.Contains(x) then
return M W/k · (B[x] + 2) + (y.query(x) mod M W/k)
else
. x has no overflows
return 2M W/k+y.query(x)

current time by W + o, and assume that item W is
the first element of P
the current frame. For convenience,
denote vx (t1 , t2 ) , i∈{t1 ,...,t2 }: wi , i.e., the volume of x
xi =x

between t1 and t2 . The goal is then to approximate the
window volume of x, which is defined as vxw , v(o+1, W +
o), i.e., the sum of weights in the timestamps within
ho + 1, o + 2, . . . , W + oi in which x arrived. We next
state the main correctness theorem for WFAST.
Theorem 4. Algorithm 2 solves the (W, , M )-Volume
Estimation problem.
Due to lack of space, the proof of the Theorem appears
in the Appendix.
As a corollary, Algorithm 2 can find heavy hitters.
Theorem 5. By returning all items x ∈ U for which
c
W
vx ≥ M W θ, Algorithm 2 solves (W, θ, , M )-Weighted
Heavy Hitters.

WFAST runtime analysis:
As listed in the pseudo code of WFAST (see Algorithm 2) and the description above, processing new elements requires adding them to the FAST instance y,
which takes O( φ1 ) time, and another O(1) operations.
The query processing includes O(1) operations and hash
tables accesses. For returning the heavy hitters, we go
over all of the items with allocated counters in time
O( 1+φ
 ). In summary, we get the following theorem:
Theorem 6. For any fixed φ > 0, WFAST processes
new elements and answers window-volume queries in
constant time, while finding the window’s weighted heavy
hitters in O( 1 ) time.

WFAST Analysis

We start by introducing several notations to be used
in this section. We mark the queried element by x, the
5

(a) SanJose14

(d) SanJose13

(b) YouTube

(e) DC1

(c) Chicago16

(f) Chicago15

Figure 3: Runtime comparison for a given error guarantee ( = 2−8 ). All algorithms provide the same guarantees
and FAST uses different φ values to show the speedup gained from allocating additional counters.

6.

HIERARCHICAL HEAVY HITTERS

lutions of plain heavy hitter problems. That is, each
prefix pattern has its own separate heavy hitters algorithm that is updated on each packet arrival. For
example, consider a packet whose source IP address is
101.102.103.104 where the (one dimensional) HHH measurements are carried according to source addresses. In
this case, the packet arrival is translated into the following five heavy hitters update operations: 101.102.103.104,
101.102.103.∗, 101.102.∗, 101.∗, and ∗. Finally, HHHs
are identified by calculating the heavy hitters of each
separate heavy hitters algorithm.
HFAST is derived by replacing the underlying heavy
hitters algorithm in [36] from Space Saving with heap [35]
to FAST. This asymptotically
improves the update com
plexity from O H log 1 to O (H), where H is the size
of the hierarchy. Since the analysis of [36] is indifferent to the internal implementation of the heavy hitters
algorithm, no analysis is required for HFAST.
Finally, we note that a hierarchical heavy hitters algorithm on sliding windows can be constructed using
the work of [36] by replacing each space saving instance
with our WFAST.
 The complexity of the proposed algorithm is O H space and O (H) update time. To our
knowledge, there is no prior work for this problem.

Hierarchical heavy hitters (HHH) algorithms treat IP
addresses as a hierarchical domain. At the bottom are
fully specified IP addresses such as p0 = 101.102.103.104.
Higher layers include shorter and shorter prefixes of the
fully specified addresses. For example, p1 = 101.102.103.∗
and p2 = 101.102.∗ are level 1 and level 2 prefixes of p0 ,
respectively. Such prefixes generalize an IP address. In
this example, p0 ≺ p1 ≺ p2 , indicating that p0 satisfies
the pattern of p1 , and any IP address that satisfies p1
also satisfies p2 . The above example refers to a single dimension (e.g., the source IP), and can be generalized to multiple dimensions (e.g., pairs of source IP
and destination IP). HHH algorithms need to find the
heavy hitter prefixes at each level of the induced hierarchy. For example, this enables identifying heavy hitters
subnets, which may be suspected of generating a DDoS
attack. The problem is formally defined in [14, 36].

Hierarchical Fast (HFAST)
Hierarchical FAST (HFAST) is derived from the algorithm of [36]. Specifically, the work of [36] suggests
Hierarchical Space Saving with a Heap(HSSH). In their
work, the HHH prefixes are distilled from multiple so6

(a) SanJose14

(d) SanJose13

(b) YouTube

(c) Chicago16

(e) DC1

(f) Chicago15

Figure 4: Runtime comparison as a function of accuracy guarantee () provided by the algorithms.

7.

EVALUATION

7.1

Our evaluation is performed on an Intel i7-5500U
CPU with a clock speed of 2.4GHz, 16 GB RAM and a
Windows 8.1 operating system. We compare our C++
prototypes to the following alternatives:
Count Min Sketch (CMS) [15] – a sketch based solution that can only solve the volume estimation problem.
Space Saving Heap (SSH) – a heap based implementation [12] of Space Saving [35] that has a logarithmic
runtime complexity.
Hierarchical Space Saving Heap (HSSH) – a hierarchical heavy hitters algorithm [36] that uses SSH as a
building block and operates in O(H log( 1ε )) complexity.
Full Ancestry – a trie based HHH algorithm suggested
by [14], which operates in O (H log N ) complexity.
Partial Ancestry – a trie based HHH algorithm suggested by [14], which operates in O (H log N ) complexity and is considered faster than Full Ancestry.
Related work implementations were taken from open
source libraries released by [11] for streams and by [36]
for hierarchical heavy hitters. As we have no access to
a concrete implementation of a competing sliding window protocol, we compare WFAST to Hung and Ting’s
algorithm [27] by conservatively estimating the space
needed by their approach. Each data point we report
here is the average of 10 runs.

Datasets

Our evaluation includes the following datasets. The
packet traces characteristics are summarized in Table 3.
The CAIDA backbone Internet traces that monitor
links in Chicago [24, 25] and San Jose [22, 23]. A datacenter trace from a large university [7] and a trace of
436K YouTube video accesses [10]. The weight of a
video is its length in seconds.
As shown in Table 3, the impact of jumbo frames
varies between backbone links. Yet, the weight of large
packets increases over time in both. In the San Jose
link, the number and volume of large packets have increased by 50% within a period of 6 months. In the
Chicago link, large packets are still insignificant, but
their number and volume have increased by 50% in two
months.

7.2

Effect of φ on Runtime

Recall that smaller φ yields space efficiency while the
runtime is proportional to φ1 , i.e, smaller φ is expected
to cause a slower runtime. In Appendix B, we show
runtime performance evaluation of FAST as a function
of φ for three different ε values (2−8 , 2−10 , 2−12 ). While
we indeed obtained a speedup with larger φ values, increasing φ beyond a certain small threshold has little
impact on performance. For the rest of our evaluation,
we focus on φ = 0.25 that offers attractive space/time
7

(a) SanJose14

(b) YouTube

(c) Chicago16

Figure 5: Space overheads of WFAST compared to previous works. Note that WFAST operates in constant time
while the other algorithm requires linear scanning of all counters.

(a) Chicago 16

(d) Chicago16

(b) YouTube

(e) YouTube

(c) DC1

(f) DC1

Figure 6: WFAST with varying window sizes (ε = 2−8 ) and varying ε (with a window size of W = 216 ).
trade off, as well as on φ = 4 that yields higher performance at the expense of more space.

7.3

while SSH only requires 1/. FAST can provide the
same error guarantee for different φ values, which affects
both runtime and the number of counters. Hence, FAST
is represented by a curve. As Figure 3 shows, in all
traces, allocating a few additional counters to the 1/ required by SSH allows FAST to achieve higher throughput. Additionally, on all traces, FAST provides faster
throughput than CMS with far fewer counters. While
FAST has larger per counter overheads than CMS, its
ID to counter mapping allows it to solve the Weighted

Speed vs. Space Tradeoff

To explain the tradeoff proposed by FAST, we measured the runtime of the various algorithms for a fixed
error guarantee. Here, SSH and CMS are fully determined by the error guarantees (set to be  = 2−8 ) and
thus have a single measurement point. CMS requires
more counters as it uses 10 rows of de/e counters each,
8

(a) SanJose14

(b) Chicago15

(c) Chicago16

Figure 7: Runtime comparison of HHH algorithms as a function of their accuracy guarantee ().
Trace
Chicago16
Chicago15
SanJose14
SanJose13
DC1

Date(Y/M/D)
2016/02/18
2015/12/17
2014/06/19
2013/12/19
2010

#Packets
97 M
85 M
112 M
97 M
7.3M

Total volume
94 GB
80 GB
149 GB
110 GB
6.1GB

Mean size
1046
1013
1424
1225
894

Max size
49458
64134
65535
65528
1476

% large packets
0.34%
0.22%
0.78%
0.49%
0%

% large packet traffic
0.5%
0.34%
25.02%
18.81%
0%

Table 3: A summary of key characteristics of the real Internet traces used in this work.
Heavy Hitters problem that CMS cannot.

7.4

Figure 6 shows the operation speed of WFAST for different window sizes and different ε values. There is little
dependence in window size and ε with the exception of
the DC1 dataset. In this dataset, since the average and
maximal packet sizes are similar, the inner working of
WFAST causes overflows to be more frequent when ε
is close to the window size. Thus, to achieve similar
performance as the other traces one needs sufficiently
large window size in this trace.

Operation Speed Comparison

Figure 4 presents a comparative analysis of the operation speed of previous approaches. Recall that CMS is
a probabilistic scheme; we configured it with a failure
probability of 0.1%. For FAST, we used two configurations: φ = 4 (4FAST) and φ = 0.25 (0.25FAST).
As can be observed, 4FAST and 0.25FAST are considerably faster than the alternatives in Chicago16 and
YouTube. In SanJose14 and SanJose13, SSH is as fast
as 4FAST for a large  (small number of counters). Yet,
as  decreases and the number of counters increases,
SSH becomes slower due to its logarithmic complexity. In contrast, CMS is almost workload independent.
When considering only previous work, in some workloads CMS is faster than SSH, mainly because SSH’s
performance is workload dependent.

7.5

7.6

Hierarchical Heavy Hitters

In Figure 7, we evaluate the speed of our HFAST
compared to the algorithm of [36], which is denoted by
HSSH, as well as the Partial Ancestry and Full Ancestry algorithms by [14]. We used the library of [36] for
their own HSSH implementation as well as for the Partial Ancestry and Full Ancestry implementations. Since
the library was released for Linux, we used a different
machine for our HFAST evaluation. Specifically, we
used a Dell 730 server running Ubuntu 16.04.01 release.
The server has 128GB of RAM and an Intel(R) Xeon(R)
CPU E5-2667 v4 @ 3.20GHz processor.
We used two dimensional source/destination hierarchies in byte granularity, where networks IDs are assumed to be 8, 16 or 24 bits long. The weight of each
packet is its byte volume, including both the payload
size and the header size. As depicted, HFAST is up
to 7 times faster than the best alternative and at least
2.4 times faster in every data point. It appears that
for large  values, HSSH is faster than the Partial and
Full Ancestry algorithms. Yet, for small  values, all
previous algorithms operate in similar speed.

Sliding Window

We evaluate WFAST compared to Hung and Ting’s
algorithm [27], which is the only one that supports
weighted updates on sliding windows. Figure 5 shows
the memory consumption of WFAST with parameters
φ = 4 and φ = 0.25 (4WFAST, 0.25FAST) compared to
Hung and Ting’s algorithm. All algorithms are configured to provide the same worst case error guarantee. As
shown, WFAST is up to 100 times more space efficient
than Hung and Ting’s algorithm. Sadly, we could not
obtain an implementation of Hung and Ting’s algorithm
and thus do not compare its runtime to WFAST. However, WFAST improves their update complexity from
O( A ), where A is the average packet size, to O(1).
9

8.

DISCUSSION

[16] Dimitropoulos, X., Hurley, P., and Kind, A. Probabilistic
Lossy Counting: An Efficient Algorithm for Finding Heavy
Hitters. ACM SIGCOMM CCR 38, 1 (2008).
[17] Einziger, G., Fellman, B., and Kassner, Y. Independent
Counter Estimation Buckets. In IEEE INFOCOM (2015).
[18] Einziger, G., and Friedman, R. TinyLFU: A Highly Efficient
Cache Admission Policy. In Euromicro PDP (2014).
[19] Einziger, G., Luizelli, M. C., and Waisbard, E. Constant time
weighted frequency estimation for virtual network
functionalities. In 2017 26th International Conference on
Computer Communication and Networks (IEEE ICCCN)
(2017).
[20] Garcia-Teodoro, P., Diaz-Verdejo, J. E., Macia-Fernandez,
G., and Vazquez, E. Anomaly-Based Network Intrusion
Detection: Techniques, Systems and Challenges. Computers
and Security (2009).
[21] Hershberger, J., Shrivastava, N., Suri, S., and Tóth, C. D.
Space Complexity of Hierarchical Heavy Hitters in
Multi-dimensional Data Streams. In ACM PODS (2005).
[22] Hick, P. CAIDA Anonymized Internet Trace, equinix-sanjose
2013-06-19 13:00-13:05 UTC, Direction B., 2014.
[23] Hick, P. CAIDA Anonymized Internet Trace, equinix-sanjose
2013-12-19 13:00-13:05 UTC, Direction B., 2014.
[24] Hick, P. CAIDA Anonymized Internet Trace, equinix-chicago
2015-12-17 13:00-13:05 UTC, Direction A., 2015.
[25] Hick, P. CAIDA Anonymized Internet Trace, equinix-chicago
2016-02-18 13:00-13:05 UTC, Direction A., 2016.
[26] Hung, R. Y. S., Lee, L., and Ting, H. Finding frequent items
over sliding windows with constant update time. Inf. Proc.
Let.10’ 110, 7.
[27] Hung, R. Y. S., and Ting, H. F. Finding Heavy Hitters over the
Sliding Window of a Weighted Data Stream. In LATIN (2008).
[28] Kabbani, A., Alizadeh, M., Yasuda, M., Pan, R., and
Prabhakar, B. AF-QCN: Approximate Fairness with Quantized
Congestion Notification for Multi-tenanted Data Centers. In
IEEE HOTI (2010).
[29] Karp, R. M., Shenker, S., and Papadimitriou, C. H. A Simple
Algorithm for Finding Frequent Elements in Streams and Bags.
ACM Transactions Database Systems 28, 1 (Mar. 2003).
[30] Lee, L., and Ting, H. F. A simpler and more efficient
deterministic scheme for finding frequent items over sliding
windows. In Proc. of PODS 2006.
[31] Li, T., Chen, S., and Ling, Y. Per-Flow Traffic Measurement
Through Randomized Counter Sharing. IEEE/ACM Trans. on
Networking (2012).
[32] Lu, Y., Montanari, A., Prabhakar, B., Dharmapurikar, S.,
and Kabbani, A. Counter Braids: a Novel Counter Architecture
for Per-Flow Measurement. In ACM SIGMETRICS (2008).
[33] Manerikar, N., and Palpanas, T. Frequent Items in Streaming
Data: An Experimental Evaluation of the State-of-the-Art.
Data Knowl. Eng. (2009).
[34] Manku, G. S., and Motwani, R. Approximate Frequency
Counts over Data Streams. In VLDB (2002).
[35] Metwally, A., Agrawal, D., and Abbadi, A. E. Efficient
Computation of Frequent and Top-k Elements in Data Streams.
In IN ICDT (2005).
[36] Mitzenmacher, M., Steinke, T., and Thaler, J. Hierarchical
Heavy Hitters with the Space Saving Algorithm. In ALENEX
(2012).
[37] Mukherjee, B., Heberlein, L., and Levitt, K. Network
Intrusion Detection. Network, IEEE 8, 3 (1994).
[38] Ramabhadran, S., and Varghese, G. Efficient Implementation
of a Statistics Counter Architecture. ACM SIGMETRICS
(2003).
[39] Rong, Q., Zhang, G., Xie, G., and Salamatian, K. Mnemonic
Lossy Counting: An efficient and accurate heavy-hitters
identification algorithm. In IEEE IPCCC (2010).
[40] Sekar, V., Duffield, N., Spatscheck, O., van der Merwe, J.,
and Zhang, H. LADS: Large-scale Automated DDOS Detection
System. In USENIX ATEC (2006).
[41] Shah, D., Iyer, S., Prabhakar, B., and McKeown, N.
Maintaining Statistics Counters in Router Line Cards. IEEE
Micro (2002).
[42] Tsidon, E., Hanniel, I., and Keslassy, I. Estimators Also Need
Shared Values to Grow Together. In IEEE INFOCOM (2012).
[43] Zhang, Y., Singh, S., Sen, S., Duffield, N., and Lund, C.
Online Identification of Hierarchical Heavy Hitters:
Algorithms, Evaluation, and Applications. ACM IMC.

In this paper, we presented algorithms for estimating
per flow traffic volume in streams, sliding windows and
hierarchical domains. Our algorithms offer both asymptotic and empirical improvements for these problems.
For streams, FAST processes packets in constant time
while being asymptotically space optimal. This is enabled by our novel approach of maintaining only a partial order between counters. An evaluation over realworld traffic traces has yielded a speed improvement of
up to 2.4X compared to previous work.
In the sliding window case, we showed that WFAST
works reasonably fast and offers 100x reduction in required space, bringing sliding windows to the realm of
possibility. For a given error of W · M · , WFAST re
quires O 1 counters while previous work uses O A ,
where A is the average packet size. Moreover, WFAST

runs in constant time while previous work runs in O A .
For hierarchical domains, we presented HFAST that
requires O( H ) space and has O(H) update complexity.
This improves over the O H log 1 update complexity of previous work. Additionally, we demonstrated
a speedup of 2.4X-7X on real Internet traces. To our
knowledge, there is no prior work on that problem and
we plan to examine its possible applications in the future. The code of FAST is available as open source [2].
We thank Yechiel Kimchi for helpful code optimization suggestions.

9.

REFERENCES

[1] Arasu, A., and Manku, G. S. Approximate counts and quantiles
over sliding windows. In ACM PODS 2004.
[2] Ben-Basat, R., and Einziger, G. FAST code. Available:
https://github.com/ranbenbasat/FAST.
[3] Ben-Basat, R., Einziger, G., Friedman, R., and Kassner, Y.
Heavy Hitters in Streams and Sliding Windows. In IEEE
INFOCOM (2016).
[4] Ben-Basat, R., Einziger, G., Friedman, R., and Kassner, Y.
Randomized admission policy for efficient top-k and frequency
estimation. In IEEE INFOCOM (2017).
[5] Ben-Basat, R., Einziger, G., Friedman, R., and Kassner, Y.
Optimal Elephant Flow Detection. In IEEE INFOCOM (2017).
[6] Ben Basat, R., Einziger, G., Friedman, R., Luizelli, M. C., and
Waisbard, E. Constant time updates in hierarchical heavy
hitters. In ACM SIGCOMM (2017).
[7] Benson, T., Akella, A., and Maltz, D. A. Network traffic
characteristics of data centers in the wild. In ACM
IMC (2010).
[8] Charikar, M., Chen, K., and Farach-Colton, M. Finding
Frequent Items in Data Streams. In EATCS ICALP (2002).
[9] Chen, M., and Chen, S. Counter Tree: A Scalable Counter
Architecture for Per-Flow Traffic Measurement. In IEEE ICNP
(2015).
[10] Cheng, X., Dale, C., and Liu, J. Statistics and Social Network
of YouTube Videos. In IWQoS (2008).
[11] Cormode, G., and Hadjieleftheriou, M. Finding Frequent
Items in Data Streams. VLDB 1, 2 (2008).
[12] Cormode, G., and Hadjieleftheriou, M. Methods for Finding
Frequent Items in Data Streams. J. VLDB 19, 1 (2010).
[13] Cormode, G., Korn, F., Muthukrishnan, S., and Srivastava, D.
Diamond in the Rough: Finding Hierarchical Heavy Hitters in
Multi-dimensional Data. SIGMOD 2004.
[14] Cormode, G., Korn, F., Muthukrishnan, S., and Srivastava, D.
Finding Hierarchical Heavy Hitters in Streaming Data. ACM
Trans. Knowl. Discov. Data 1, 4 (2008).
[15] Cormode, G., and Muthukrishnan, S. An Improved Data
Stream Summary: The Count-min Sketch and Its Applications.
J. Algorithms (2005).

10

APPENDIX

Proof of Lemma 3

A.

Proof. We prove the claim by induction on the stream
length t. Basis: t = 0.
In
P this case, all counters have value of 0 and thus
0 = t · (M · (1 + φ/2)).
x∈Ct qt (x) =P
Hypothesis: x∈Ct−1 qt−1 (x) ≤ (t − 1) · M · (1 + φ/2).
Step: hxt , wt i arrives at time t. We consider the following cases:
l
m
1. x ∈ Ct−1 or |Ct−1 | < 1+φ
. In this case, the

condition
j in Linek 2 is satisfied and thus cx,t =

MISSING PROOFS

Proof of Lemma 1
Proof. We prove vx,t ≤ qt (x) by induction over t.
Basis: t = 0. Here, we have vx,t = 0 = qt (x).
Hypothesis: vx,t−1 ≤ qt−1 (x)
Step: hxt , wt i arrives at time t. By case analysis:
Consider the case where the queried item x is not
the arriving one (i.e., x 6= xt ). In this case, we have
vx,t = vx,t−1 . If x ∈ Ct−1 but was evicted (Line 10)
then cx ∈ argminy∈Ct−1 (cy,t−1 ). This means that:

qt (x) =by


line
13

≤ s − 1 + s · argminy∈Ct (cy,t ) = qt (x),




+ (rx,t−1 + w)

mod s
(2)

Since the value of a query for every y ∈ Ct \ {x}
remains unchanged, we get that
X

X

qt (y) = qt (x) +

y∈Ct

qt−1 (y)

y∈Ct−1
y6=x

(by (3))

X

= w + qt−1 (x) +

qt−1 (y)

y∈Ct−1
y6=x

=w+

X

qt−1 (y)

y∈Ct−1

induction
hypothesis



≤ w + (t − 1) · (M · (1 + φ/2))
≤ M + (t − 1) · (M · (1 + φ/2))

(φ≥0)

≤ t · (M · (1 + φ/2)) .

l
m
2. x ∈
/ Ct−1 and |Ct−1 | = 1+φ
. In this case, the

condition of Line 2 is false and therefore cx,t =
cm,t−1 + s−1+w
(Line 8) and rx,t ← (s − 1 + w)
s
mod s (Line 9). From Observation 1 we get that

(1)

qt (x) =by Line rx,t + s · cx,t
13


s −1+w
= cm,t−1 +
+ (s − 1 + w)
s
= w + cm,t−1 + s − 1


Mφ
= qt−1 (m) − rm,t−1 +
+w
2


Mφ
≤ qt−1 (m) +
+ w.
2

qt (x) = rx,t + s · cx,t = (s − 1 + w) mod s



s −1+w
+s·
min cy,t−1 +
y∈Ct−1
s
(Observation 1) = s · min cy,t−1 + s − 1 + w
y∈Ct−1

(1)

induction
hypothesis

rx,t−1 + w
s

= w + cx,t−1 + rx,t−1 = qt−1 (x) + w.

On the other hand, when x arrives, the condition of
Line 2 was not satisfied, and thus



rx,t + s · cx,t

= cx,t−1 +

where the last equation follows from the query for x ∈
/
Ct (Line 15). Next, if x ∈ Ct−1 and x ∈ Ct , its estimated volume is determined by Line 13 and we get
qt (x) = qt−1 (x) ≥ vx,t−1 = vx,t . If x ∈
/ Ct−1 then
x ∈
/ Ct , so the values of qt (x), qt−1 (x) are determined
by line 15. Since the value of miny∈C cy can only increase over time, we have qt (x) ≥ qt−1 (x) ≥ vx,t and
the claim holds.
On the other hand, assume that we are queried about
the last item, i.e., x = xt . In this case, we get vx,t =
vx,t−1 + wt . We consider the following cases: First, if
x ∈ Ct−1 , then qt (x) = qt−1 (x)+wt . Using the hypothesis, we conclude that vx,t = vx,t−1 +wt ≤ qt−1 (x)+wt =
qt (x) as required. Next, if |Ct−1 | < C, we also have
qt (x) = qt−1 (x) + wt and the above analysis holds. Finally, if x ∈
/ Ct−1 and |Ct−1 | = C, then
y∈Ct−1

(Line 3) and rx,t = (rx,t−1 + w)

mod s (Line 4). By Observation 1 we get

qt−1 (x) = rx,t−1 + s · argminy∈Ct−1 (cy,t−1 )

qt−1 (x) = s − 1 + s · min cy,t−1 .

rx,t−1 +w
s

cx,t−1 +

= qt−1 (x) + w
≥ vx,t−1 + w = vx,t .

Proof of Lemma 2

mod s

(3)

As before, the value of a query for every y ∈ Ct \{x}
is unchanged, and since Ct−1 \ Ct = {m},

Proof. Since |C| ≤ C, we get that the conditions
in Line 2 and Line 13 are always satisfied. Before the
queried element x first appeared, we have rx = cx =
0 and thus Query(x)= 0. Once x appears once, it
gets a counter and upon every arrival with value w, the
estimation for x exactly increases by w, since x never
gets evicted (which can only happen in Line 7).

X

qt−1 (y)

y∈Ct−1


(by (3))

≤



induction
hypothesis



≤

≤

(φ≥0)

11

X

qt (y) = qt (x) − qt−1 (m) +

y∈Ct

Mφ
2



Mφ
2



Mφ
2



+w+

X

qt−1 (y)

y∈Ct−1

+ w + (t − 1) · (M · (1 + φ/2))
+ M + (t − 1) · (M · (1 + φ/2))

≤ t · (M · (1 + φ/2)) .

(a) SanJose14

(b) YouTube

(d) SanJose13

(c) Chicago16

(e) DC1

(f) Chicago15

Figure 8: The effect of parameter φ on operation
for different error guarantees (). φ influences the space
m
l speed
counters.
requirement as the algorithm is allocated with 1+φ


Proof of Lemma 4
Proof. First,lconsider
the case where the stream
m
1+φ
contains at most  distinct elements. By Lemma 2,
vbx ≤ vx and
l themclaim holds. Otherwise, we have seen
more than 1+φ
distinct elements, and specifically


t>


1+φ
.


min Query(y) ≤

(4)

t · M · (1 + φ/2)
t · M ·  · (1 + φ/2)
l
m
≤
.
1+φ
1+φ

(4)

> qt (y) + M φ/2.

t
1+φ


Finally, we apply (6) to conclude that once x arrives
with a cumulative volume of t · M · , it will never be
evicted (Line 7) and from that moment on its volume
will be measured exactly.

(5)



Proof of Lemma 5

Notice that ∀x ∈ Ct , Query(x) is determined in Line 13;
that is, qt (x) = rx,t + s · cx,t . Next, observe that an
item’s remainder value is bounded by s − 1 (Line 4 and
Line 9). Thus,
∀x, y ∈ Ct : qt (x) ≥ s + qt (y) =⇒ cx,t > cy,t .

Proof. As mentioned before, FAST utilizes the SOS
data structure that answers queries in O(1). Updates
are a bit more complex as we need to handle weights
and thus may be required to move the flow more than
once, upon a counter increase. Whenever we wish to
increase the value of a counter (Line 3 and Line 8), we
need to remove the item from its current group and
place it in a group that has the increased c value. This
means that for increasing a counter by n ∈ N, we have
to traverse at most n groups until we find the correct
location. Since the remainder value is at most s − 1
(Line 4 and Line 9), we get that at any
 time point, a
counter is increased by no more than s−1+w
(Line 3
s

(6)

By choosing y ∈ arg miny∈Ct qt (y), we get that if vx,t ≥
qt (y) + s, then qt (x) ≥ qt (y) + s and thus cx,t > cy,t .
Next, we show that if vx,t ≥ t·M ·, then cx > miny∈Ct cy
and thus x will never be the “victim” in Line 7:
qt (x) ≥ vx,t ≥ t · M ·  = t · M ·  ·

≥ qt (y) + M φ/2 ·

Next, since qt (x) and qt (y) are integers, it follows that


M ·φ
qt (x) ≥ qt (y) +
+ 1 = qt (y) + s.
2

From Lemma 3, it follows that
y∈Ct

(5)

1 + φ/2
+ M φ/2 ·
1+φ

t
1+φ


12

j
k
and Line 8). Finally, since s = M2·φ + 1 , we get that
the counter increase is bounded by


B.

bM · φ/2 + 1c − 1 + w
bM · φ/2 + 1c


<1+

w
2
≤1+ =O
M φ/2
φ

 
1
.
φ

MISSING FIGURE

Figure 8 shows runtime performance evaluation of
FAST as a function of φ for three different ε values
(2−8 , 2−10 , 2−12 ). While we indeed obtained a speedup
with larger φ values, increasing φ beyond a certain small
threshold has little impact on performance.

13

