Optimizing Static and Adaptive Probing
Schedules for Rapid Event Detection

arXiv:1509.02487v2 [] 10 Sep 2015

Ahmad Mahmoody, Evgenios M. Kornaropoulos, and Eli Upfal
Department of Computer Science, Brown University
{ahmad, evgenios, eli}@cs.brown.edu

Abstract. We formulate and study a fundamental search and detection
problem, Schedule Optimization, motivated by a variety of real-world
applications, ranging from monitoring content changes on the web, social
networks, and user activities to detecting failure on large systems with
many individual machines.
We consider a large system consists of many nodes, where each node
has its own rate of generating new events, or items. A monitoring application can probe a small number of nodes at each step, and our goal
is to compute a probing schedule that minimizes the expected number
of undiscovered items at the system, or equivalently, minimizes the expected time to discover a new item in the system.
We study the Schedule Optimization problem both for deterministic and
randomized memoryless algorithms. We provide lower bounds on the
cost of an optimal schedule and construct close to optimal schedules
with rigorous mathematical guarantees. Finally, we present an adaptive
algorithm that starts with no prior information on the system and converges to the optimal memoryless algorithms by adapting to observed
data.

1

Introduction

We introduce and study a fundamental stochastic search and detection problem,
Schedule Optimization, that captures a variety of practical applications, ranging
from monitoring content changes on the web, social networks, and user activities
to detecting failure on large systems with many individual machines.
Our optimization problem consists of a large set of units, or nodes, that
generate events, or items, according to a random process with known or unknown
parameters. A detection algorithm can discover new items in the system by
probing a small number of nodes in each step. This setting defines a discrete,
infinite time process, and the goal of the stochastic optimization problem is to
construct a probing schedule that minimizes the long term expected number of
undiscovered items in the system, or equivalently, minimizes the expected time
to discover a new item in the system.
We outline several important applications of this schedule optimization problem:

News and Feed Aggregators. To provide up to date summary of the news, news
aggregator sites need to constantly browse the Web, and often also the blogosphere and social networks, for new items. Scanning a site for new items requires
significant communication and computation resources, thus the news aggregator
can scan only a few sites simultaneously. The frequency of visiting a site has to
depend on the likelihood of finding new items in that site. [9,21,1]
Algorithmic Trading on Data. An emerging trend in algorithmic stock trading
is the use of automatic search through the Web, the blogosphere, and social
networks for relevant information that can be used in fast trading, before it appears in the more popular news sites [4,14,5,17,11,8,16]. The critical issue in this
application is the speed of discovering new events, but again there is a resource
limit on the number of sites that the search algorithm can scan simultaneously.
Detecting Anomaly and Machine Malfunction. In large server farm or any other
large collection of semi-autonomous machines a central controller needs to identify and contain anomalies and malefactions as soon as possible, before they
spread in the system. To minimize interference with the system’s operation the
controller must probe only a small number of machines in each step.
1.1

Our Contribution

We consider an infinite, discrete time process in which n nodes generate new
items according to a stochastic process which is governed by a generating vector
π (see Section 3 for details). An algorithm can probe up to c nodes per step to
discover all new items in these nodes. The goal is to minimize the cost of the
algorithm (or the probing schedule), which we define as the long term (steady
state) expected number of undiscovered items in the system.
We first show that the obvious approach of probing at each step the nodes
with maximum expected number of undiscovered items at that step is not optimal. In fact, the cost of such a schedule can be arbitrary far from the optimal.
Our first result toward the study of efficient schedules is a lower bound on
the cost of any deterministic or random schedule as a function of the generating
vector π.
Next we assume that the generating vector π is known and study explicit
constructions of deterministic and random schedules. We construct a deterministic schedule whose cost is within a factor of (3 + (c − 1)/c) of the optimal cost,
and a very simple, memoryless random schedule with cost that is within a factor
of (2 + (c − 1)/c) from optimal, where c is the maximum number of probes at
each step.
Finally, we address the more realistic scenario in which the generating vector,
π, is not known to the algorithm and may change in time. We construct an
adaptive scheduling algorithm that learns from probing the nodes and converges
to the optimal memoryless random schedule.

2

Related Work

The News and Feed Aggregation problem is a very well-studied topic, in which
the general goal is to obtain the updates of news websites (e.g. by RSS feeds).
Among many introduced objectives [19,9,1] in studying this problem, the most
similar one to our cost function is the delay function presented by [21]. In [21] it
is assumed that the rates of the news publication does not change, where in our
setting these rates may change and our algorithm (Adaptive) can adapt itself
to the new setting. Also, we assume at any given time the number of probes is
fixed (or bounded) regarding the limited computational power for simultaneous
probes, but [21] uses a relaxed assumption by fixing the number of probes over
a time window of a fixed length which may result in high number of probes at a
single time step. Finally, [21] introduces a deterministic algorithm in which the
number of probes to each feed is obtained by applying the Lagrange multipliers
method (very similar result to Theorem 3), but they loose the guarantee on
optimality of their solution, by rounding the estimated number of probes to
integers. In contrast, our solution provides theoretical guarantee on optimality
of our output schedule.
Web-crawling is another related topic, where a web-crawler aims to obtain
the most recent snapshots of the web. However, it differs from our model substantially: in web-crawling algorithm data get updated, so missing some intermediate
snapshot would not affect the quality of the algorithm, where in our model data
are generated and they all need to be processed [3,22].
There has been an extensive work on Outbreak Detection (motivated in part
by the “Battle of Water Sensors Network” challenge [20]) using statistic or mobile
sensor in physical domains, and regarding a variety of objectives [13,10,7]. Our
model deviates from the Outbreak Detection problem as it is geared to detection
in virtual networks such as the Web or social networks embedded in the Internet,
where a monitor can reach (almost) any node at about the same cost.
Another related problem is the Emerging Topic Detection problem, where the
goal is to identify emergent topics in a social network, assuming full access to
the stream of all postings. Besides having different objectives, our model differs
mainly in this accessibility assumption: the social network providers have an
immediate access to all tweets or postings as they are submitted to their servers,
whereas in our model we consider an outside observer who needs an efficient
mechanism to monitor changes, without having such full access privilege [2,15].
In the next section, we formally define our model and the Schedule Optimization problem.

3

Model and Problem Definition

We study an infinite, discrete time process in which a set of n nodes, indexed
by 1, . . . , n, generate new items according to a random generating process. The
generating process at a given time step is characterized by a generating vector
π = (π1 , . . . , πn ), where πi is the expected number of new items generated at

node i at that step (by either a Bernoulli or a Poisson process). The generation
processes in different nodes are independent.
We focus first on a static generating process in which the generating vector
does not change in time. We then extend our results to adapt to generating
vectors that change in time.
Our goal is to detect new events as fast as possible by probing in each step
a small number of nodes. In particular, we consider probing schedules that can
probe up to c nodes per step.
Definition 1 (Schedule). A c-schedule is a function S : N → {1, . . . , n}c
specifying a set of c nodes to be probed at any time t ∈ N. A deterministic
function S defines a deterministic schedule, otherwise the schedule is random.
Definition 2 (Memoryless Schedule). A random schedule is memoryless if
it is defined by a vector p = (p1 , . . . , Q
pn ) such that at any step the schedule probes
a set C of c items with probability j∈C pi independent of any other event. In
that case we use the notation S = p.
Definition 3 (Cyclic Schedule). A schedule, S, is ℓ-cyclic if there is a finite
time t0 such that from time t0 on, the schedule repeats itself every period of ℓ
steps. A schedule is cyclic if it is ℓ-cyclic for some positive integer ℓ.
The quality of a probing schedule is measured by the speed in which it
discovers new items in the system. When a schedule probes a node i at a time
t, all items that were generated at that node by time t − 1 are discovered (thus,
each item is not discovered in at least one step). We define the cost of a probing
schedule as the long term expected number of undiscovered items in the system.
Definition 4 (Cost). The cost of schedule S in a system of n nodes with generating vector π is
t
t
n
1X  S ′ 
1 XX  S ′ 
E Qi (t ) ,
E Q (t ) = lim
t→∞ t
t→∞ t
′
′
i=1

cost (S, π) = lim

t =1

t =1

′
QSi (tP
)

where
is the number of undiscovered items at node i and at time t′ , and
n
S ′
S ′
Q (t ) =
i=1 Qi (t ). The expectation is taken over the distribution of the
generating system and the probing schedule.
While the cost can be unbounded for some schedules, the cost of the optimal
schedule is always bounded. To see that, consider a round-robin schedule, S, that
probes each node every n steps. Clearly no item is undiscovered in this schedule
for more than nP
steps, and the expected number
Pn of items generated in an interval
n
ofP
n steps is n i=1 πi . Thus, QS (t) ≤ n i=1 πi , which implies cost (S, π) ≤
n
n i=1 πi . Therefore, without loss of generality we can restrictour
 discussion

to bounded cost schedules. Also, note that when the sequence E QS (t) t∈N
 S 
converges we have cost (S, π) = lim E Q (t) (Cesaro Means [6]).
t→∞
One can equivalently define the cost of a schedule in terms of the expected
time that an item is in the system until it is discovered.

Lemma 1. Let ωiS be the expected waiting time of an item generated at node i
until node i is probed by schedule S. Then
cost (S, π) =

n
X

πi ωiS .

i=1

Proof. Following the definition of the cost function we have
"
 S ′ #
Pt
n
n
t
n
X
E
Qi (t )
1 XX  S ′  X
′
t =1
cost (S, π) = lim
lim
πi ωiS ,
E Qi (t ) =
=
t→∞ t
t→∞
t
′
i=1
i=1
i=1
t =1

where the last eqaulity is obtained by applying Little’s Law [12].

⊓
⊔

Corollary 1. A schedule that minimizes the expected number of undiscovered
items in the system simultaneously minimizes the expected time that an item is
undiscovered.
Pn
Corollary 2. For any schedule S, cost (S, π) ≥ i=1 πi .

Proof. As mentioned above, when we probe a node i at time t we discover only
the items that have been generated by time t − 1. Therefore, ωiS ≥ 1, and by
Lemma 1 the proof is complete.
⊓
⊔
Now, our main problem is defined as the following:
Definition 5 (Schedule Optimization). Given a generating vector π and a
positive integer c, find a c-schedule with minimum cost.
When the generating vector is not known a priori to the algorithm the goal
is to design a schedule that converges to an optimal one. For that we need the
following definition:
Definition 6 (Convergence). We say scheduleh S converges
to schedule S ′ , if
i
 S 
S′
for any generating vector π, lim E Q (t) − E Q (t) = 0.
t→∞

4

Results

We start this section by, first, showing that the obvious approach of maximizing
the expected number of detections at each step is far from optimal. We then
prove a lower bound on the cost of any schedule, and provide deterministic and
memoryless c-schedules that are within a factor of (3 + (c − 1)/c) and (2 +
(c − 1)/c), respectively, from the optimal. Finally, we introduce an algorithm,
Adaptive , which outputs a schedule A that converges to the optimal memoryless
1-schedule when the generating vector π is not known in advance. We also show
that Adaptive can be used to obtain a c-schedule Ac whose cost is within (2 +
(c − 1)/c) factor of any optimal c-schedule.
Throughout this section, by τiS (t) we mean the number of steps from the last
time that node i was probed until time t, while executing schedule S; if i has

not been probed so far, we let τiS (t) = t. Using the definition, it is easy to see
that




E QSi (t) = πi E τiS (t) ,
(1)

when the expectations are over the randomness of both S and π. Therefore, if
the expectation is over only the randomness of π we have


E QSi (t) = πi τiS (t).
4.1

(2)

On Maximizing Immediate Gain

Let S be a 1-schedule that at each step, probes the node with the maximum
expected number of undetected items. By (2), the expected number of undetected
items at node i and at time t is πi τiS (t), and thus, S(t) = arg maxi πi τiS (t).
Now, suppose πi = 2−i , for 1 ≤ i ≤ n. Since the probability that node 1 has
an undetected item in each step is at least 1/2, node i is probed no more than
once in each 2i−1 steps. Thus, the expected number of time steps that an item at
1
2i−1 +1
i−1
node i will stay undetected is at least 2i−1
2i−2 . Using
(1 +
P. n. .+ 2 ) =Pn 2 −i>i−2
Lemma 1, the cost of this schedule is at least i=1 πi ωi > i=1 2 2
= Ω(n).
Now, consider an alternative schedule
that
probes
node
i
in
each
step
with
Pn
−j/2
2
.
The
expected
number
of
steps
probability 2−i/2 /Z, where Z =
j=1
between two probes of i is Z/2−i/2 , and the cost of this schedule is
n
X
i=1

2−i

2−i/2
Pn
−j/2
j=1 2

!−1



=

n
X
j=1

2

2−j/2  = O(1).

Thus, optimizing immediate gain is not optimal in this problem.
4.2

Lower Bound on Optimal Cost

In this section we provide a lower bound on the optimal cost, i.e., the cost of an
optimal schedule.
Theorem 1. For any c-schedule O with finite cost we have

!2 
n
n
X

X
√
1
πi ,
cost (O, π) ≥ max
.
πi


2c
i=1

i=1

P
Proof. First, by Corollary 2, cost (O, π) ≥ ni=1 πi . Now we show cost (O, π) ≥

P
2
n √
1
πi . Fix a positive integer t > 0, and suppose during the time ini=1
2c
terval [0, t], O probes node i at steps t1 , t2 , . . . , tni . Let t0 = 0 and tni +1 = t.
So, the sequence t0 , . . . , tni +1 partition the interval [0, t] into ni + 1 intervals

Ii (j) = [tj + 1, tj+1 ], for 0 ≤ j ≤ ni , and the length of Ii (j) is ℓi (j) = tj+1 − tj .
Applying the Cauchy-Schwartz inequality we have:
2

ni
ni
ni
X
X
X
ℓi (j)
1≥
ℓi (j)2
j=0

j=0

j=0

2



ni
X
1
1
t2
t2

ℓi (j)2 ≥
=⇒
ℓi (j) =
.
1−
=
ni + 1 j=0
ni + 1
ni
ni + 1
j=0
ni
X

′
′
For t′ ∈ Ii (j), QO
i (t ) is a Poisson random variable with parameter πi (t − tj ).
Therefore,
t
X
t=1

ni
ni
X
X
 O ′ 

 X
′
(1 + . . . + ℓi (j))
E
Q
(t
)
=
π
E QO
(t
)
=
i
i
i
j=0

j=0 t′ ∈Ii (j)

= πi

ni
X
j=0



ni
ℓi (j)(ℓi (j) + 1)
πi t2
1
πi X
.
ℓi (j)2 ≥
1−
≥
2
2 j=0
2 ni
ni + 1

By summing over all nodes and averaging over t, we have


n X
t
n
X
1  O ′  X 1 πi t2
1
1−
E Qi (t ) ≥
t
t 2 ni
ni + 1
i=1 t′ =1
i=1
! n

!

n
n
X
X πi t 
πi t
1 X ni
1
1
=
≥
1−
1−
2 ni
ni + 1
c i=1 t
2 ni
ni + 1
i=1
i=1
s
!
 2
n
1
1 X√
,
(3)
1−
πi
≥
2c i=1
ni + 1
where in the second
Pnline we use the fact that if the schedule executed c probes
in each step then i=1 nti ≤ c, and the third line is obtained by applying the
Cauchy-Schwartz inequality.
It remains to show that for any schedule with finite cost, and any i such that
πi > 0, lim ni = ∞. For sake of contradiction assume that there is a time s such
t→∞


that the node i is never probed by O at time t > s. So, E QO
i (t) = π(t − s) and
 
Pt
πi (t−s)(t−s−1)
which converges to
we have cost (O, π) ≥ 1t t′ =s E QO
i (t) = t
2
∞ as t → ∞, which is a contradiction. Hence, for all i, lim ni = ∞, and using
t→∞

(4.2) we obtain

1
cost (O, π) ≥ lim
t→∞ 2c
which completes the proof.

n
X
√
i=1

s
πi
1−

1
ni + 1

!2

1
=
2c

n
X
√
πi
i=1

!2

,
⊓
⊔

4.3

Deterministic (3 + (c − 1)/c)-Approximation Schedule

We construct a deterministic
1-schedule in which each node i is probed approxPn √
πj
j=1
√
imately every ni =
steps, and using that, present our (3 + (c − 1)/c)πi
approximation schedule. For each i let ri be a nonnegative integer such that
2ri ≥ ni > 2ri −1 , and let ρ = maxi ri .

Lemma 2. There is a 2ρ -cyclic 1-schedule D such that node i is probed exactly
every 2ri steps.
Pn
Proof. Without loss of generality assume i=1 2−ri = 1, otherwise we can add
auxiliary nodes to complete the sum to 1, with the powers (ri ’s) associated with
the auxiliary nodes all bounded by ρ.
We prove the lemma by induction on ρ. If ρ = 0, then there is only one node,
and the schedule is 1-cyclic. Now, assume the statement holds for all ρ′ < ρ.
Since the smallest frequency is 2−ρ , and the sum of the frequencies is 1, there
must be two nodes, v and u, with same frequency 2−ρ . Join the two nodes to
a new node w with frequency 2−ρ+1 . Repeat this process for all nodes with
frequency 2−ρ . We are left with a collection of
> 2−ρ .
 nodes all with frequencies
ρ−1
′
By the inductive hypothesis there is a 2
-cyclic schedule D such that each
node i is probed exactly each 2ri steps. In particular a node w that replaced u
and v is probed exactly each 2−ρ+1 steps.
Now, we create an 2ρ -schedule, D, whose cycle is obtained by repeating the
cycle of D′ two times. For each probe to w that replaced a pair u, v, in the first
cycle we probe u and in the second cycle we probe v. Thus, u and v are probed
exactly every 2ρ steps, and the new schedule does not change the frequency of
probing nodes with frequency larger than 2−ρ .
⊓
⊔
Theorem 2. The cost of the deterministic 1-schedule D is no more than 3 times
of the optimal cost.
Proof.
i is probed
exactly every 2ri steps. Using 2ri −1 <
Pn √ By Lemma 2 each nodeP
√
n
π
π
2·
j
j
j=1
j=1
√
√
+ 1, and therefore
we have 2ri + 1 ≤
πi
πi
r

r

2 i
2 i
t
1X  D ′ 
1 X
πi 2ri (2ri + 1)
1 t X  D ′ 
′
lim
E
Q
(t
)
=
π
t
=
E Qi (t ) = lim
i
i
t→∞ t
t→∞ t 2ri
2 ri ′
2 ri
2
t′ =1
t =1
t′ =1
!
Pn √
n
X
√
πi
πi 2 j=1 πj
√
+ 1 = πi ·
πj + .
≤
√
2
πi
2
j=1

Thus by Theorem 1, we have


n
t
n
n
n
X
1 X X  D ′  X √
√  1X
πi
cost (D, π) = lim
E Qi (t ) ≤
πi ·
πj +
t→∞ t
2 i=1
i=1 ′
i=1
j=1
t =1



=

2

n
n
X
1X
√ 
πj
+
πj ≤ 3 · cost (O, π) ,
2 j=1
j=1

where cost (O, π) is the optimal cost.

⊓
⊔

Using the previous deterministic 1-schedule, the following corollary provides
a c-schedule whose cost is within (3 + (c − 1)/c) factor of the optimal cost.
Corollary 3. There is a deterministic c-schedule Dc whose cost is at most
(3 + (c − 1)/c) times of the optimal cost.
Proof. Consider the execution of the deterministic 1-schedule D constructed
in Theorem 2 on generating vector 1c π. Let Dc be a deterministic c-schedule
obtained by grouping c consecutive probes of D into one step. Suppose O is an
optimal c-schedule. Applying equation (1),
cost (Dc , π) =

n
X

n
X
πi

c

πi ωiD =

c

i=1

i=1

= cost (D, π) +

n
X
i=1

=

3
2c

n
X
√
πi
i=1

!2

c

cωiD ≤

n
X
πi
i=1

c

(ωiD + c − 1)

n
X
(c − 1)πi
≤3
c
i=1

+

n
X
(c − 1)πi

c

i=1

≤

r

πi
c

!2

+

n
X
(c − 1)πi
i=1

c



c−1
cost (O, π) ,
3+
c

where the first inequality holds because some items could be detected in less
than c steps in the 1-schedule but are counted in one full step of the c-schedule.
The last inequality is obtained by applying Theorem 1.
⊓
⊔
4.4

On Optimal Memoryless Schedule

Here, we consider memoryless schedules, and show that the memoryless 1-schedule
with minimum cost can be easily computed. We call a memoryless schedule
with minimum cost among memoryless schedules, an optimal memoryless schedule. We also provide an upper bound on the minimum cost of a memoryless
c-schedule.
Theorem 3. Let R = (p1 , . . . , pn ) be a memoryless 1-schedule.
Then cost (R, π) ≥
√
Pn √ 2
i
Pn π√
,
and
the
equality
holds
if
and
only
if
p
=
π
i
i
i=1
πj , for all i.
j=1

Proof. Since probing each node i is a geometric distribution with parameter
pi , the expected time until an item generated in node P
i is discovered, is ωiR =
n
πi
∗
1/pi . Therefore, by Lemma 1, we have cost (R, π) =
i=1 pi . We find p =
argminS=p cost (R, π), using the Lagrange multipliers:
∂
∂pj

n
X
πi
i=1

pi

+λ

n
X
i=1

pi

!

= 0 =⇒ pj ∝

√
πj .

Therefore, cost (R, π) is minimized if pi =

√
i
Pn π√
πj ,
j=1

and in this case the (mini-

mized) cost will be

cost (R, π) =

n
X
i=1



√πi ·

n
X
√
j=1



πj  =

n
X
√
πi
i=1

!2

.⊓
⊔

Corollary 4. The cost of the optimal memoryless 1-schedule is within a factor
of 2 of the cost of any optimal 1-schedule.
Pn √ 2
Proof. The cost of the schedule R in Theorem 3 is
i=1 πi , which is
bounded by 2 · cost (O, π) for an optimal 1-schedule O using Theorem 1.
⊓
⊔
Corollary 5. There is memoryless c-schedule, Rc , whose cost is within a factor
of (2 + (c − 1)/c) of any optimal c-schedule.
Proof. Suppose Rc is a memoryless c-schedule obtained by choosing c probes
in each step, each chosen according to the optimal memoryless 1-schedule, R,
computed in Theorem 3. Using the same argument as in the proof of Corollary 3
we have
1
cost (R , π) ≤
c
c

n
X
√
πi
i=1

!2

n

+

c−1X
πi ≤
c i=1



c−1
2+
cost (O, π) ,
c

for an optimal c-schedule O.
4.5

⊓
⊔

On Adaptive Algorithm for Memoryless Schedules

Assume now that the scheduling algorithm starts with no information on the
generating vector π (or that the vector has changed). We design and analyze
an adaptive algorithm, Adaptive, that outputs a schedule A convergent to the
optimal memoryless algorithm R (see Section 4.4) by gradually learning the
vector π by observing the system. To simplify the presentation we present and
analyze a 1-schedule algorithm. The results easily scale up to any integer c >
1, where the adaptive algorithm outputs a c-schedule convergent to Rc (as in
Section 4.4).
Each iteration of the algorithm Adaptive starts with an estimate π̃ = (π̃1 , . . . , π̃n )
of the unknown generating vector π = (π1 , . . . , πn ). Based on this
estimate the
√
i
algorithm chooses to probe node i with probability pi (t) = Pn π̃√
(which is
j=1

π̃j

the optimal memoryless schedule if tπ was the correct estimate). If nodes i is

max(1,c

)

i0
, where ci0 is
probed at time t, the estimate of πi is updated to π̃i0 ←
t
the total number of new items discovered in that node since time 0.
Algorithm 1: Adaptive

Outputs: A(t), for t = 1, 2, . . ..
begin
(c1 , . . . , cn ) ← (0, . . . , 0);
(π̃1 , . . . , π̃n ) ← (1, . . . , 1);
for t = 1, 2, . . . do
for i ∈ {1, . . . , √
n} do
i
;
pi (t) ← Pn π̃√
j=1

π̃j

A(t) ∼ p(t);
output A(t);
c′ ← number of new items caught at i0 ;
ci0 ← ci0 + c′ ;
π̃i0 ←

max(1,ci0 )
;
t

We denote the output of Adaptive schedule by A and the optimal memoryless 1-schedule by R = p∗ = (p∗1 , . . . , p∗n ); see Section 4.4. Our main result of
this section is the following theorem.
Theorem 4. The schedule A converges to R, and thus, cost (A, π) = cost (R, π).
To prove Theorem 4 we need the following lemmas.
Lemma 3. For any time t and i ∈ [n] we have pi (t) ≥

1
√
.
n t

Proof. It is easy to see that pi (t) will reach its lowest value at time t only if for
1
j 6= i we have π̃j = 1 and π̃i = t−1
(which requires i to be probed at time t − 1).
Therefore, pi (t) ≥

√
1/ t−1
√
1/ t−1+n−1

=

1 √
1+(n−1) t−1

≥

1
√
.
n t

⊓
⊔



1/3
Define δ(t) = 4n exp − π∗ t6
and let N0 be the smallest integer t such that




 √ 
1/3
1/2−ǫ
. Note that one can choose δ(t) = 4n exp − π∗ t 6
exp − 2nt ≤ 2 exp − π∗ t6

for any ǫ ∈ (0, 1/2), and for convenience we chose ǫ = 1/6.

Lemma 4. For any time t ≥ N0 , with probability ≥ 1 − δ(t)/2, all the nodes
are probed during the time interval [t/2, t) .
Proof. By Lemma 3, the probability of not probing i during the time interval
[t/2, t) is at most
t−1
Y

(1 − pi (t′ )) ≤

t′ =t/2


t/2


1
π∗ t1/3
δ(t)
− t√
1− √
≤ e 2n t ≤ 2 exp −
=
.
6
2n
n t

A union bound over all the nodes completes the proof.

⊓
⊔

Lemma 5. Suppose node i is probed at a time t′ > t/2. Then,
h
i δ(t)
1
.
Pr |π̃i (t′ ) − πi | > t− 3 πi <
2n
Proof. We estimate π from t′ > t/2 steps, each with πi expected number of new
items. Applying a Chernoff bound [18] for the sum of t′ independent random
variables with either Bernulli or Poisson distribution we have
!
!
h
i
− 23
− 23
′
1
t
δ(t)
t
π
t
π
t
i
∗
Pr |π̃i (t′ ) − πi | > t− 3 πi < 2 exp −
≤ 2 exp −
=
.⊓
⊔
3
6
2n
Note that by union bound, Lemma 5 holds, with probability at least 1−δ(t)/2,
for all the nodes that are probed after t/2.
Lemma 6. Suppose t ≥ N0 . With probability at least 1 − δ(t) we have for all
i ∈ [n],

1−

1
t1/3 + 1



p∗i

≤

s

1 − t−1/3 ∗
p ≤ pi (t) ≤
1 + t−1/3 i

s

1 + t−1/3 ∗
p ≤
1 − t−1/3 i


1+

1
t1/3 − 1



p∗i

Proof. Applying Lemma 4, Lemma 5 and a union bound, with probability 1−δ(t)
all the nodes are probed during
the time [t/2, t) and |π̃i (t) − πi | ≤ t−1/3 πi for
√
π̃i (t)
all i ∈ [n]. Since pi (t) = P √
, we obtain
j

π̃j (t)

s
s
p
√
πi
1
(1 − t−1/3 )πi
1 − t−1/3
1 − t−1/3 ∗
P √ =
=
pi ≥ (1− 1/3
)p∗i
pi (t) ≥ P p
−1/3
−1/3
−1/3
π
1
+
t
1
+
t
t
+
1
j
(1
+
t
)π
j
j
j

where the last inequality uses the Taylor series of
obtained by a similar argument.

√
1 + x. The upper bound is
⊓
⊔

Corollary 6. The variation distance between the distribution p(t) = (p1 (t), . . . , pn (t))
used by algorithm Adaptive at time t ≥ N0 , and the distribution p∗ = (p∗i , . . . , p∗n )
used by the optimal memoryless algorithm satisfy
n

k p(t) − p∗ k=

1X
n
t→∞
+ δ(t) −→ 0.
|pi (t) − p∗i | ≤ 1/3
2 i=1
t −1

Finally, we present our proof for Theorem 4.
Proof of Theorem 4. Recall that we defined τiS (t) as the number of steps from
the last time
node

 i was
 probed until time t in an execution of an schedule
 that
S, and E QSi = πi E τiS (t) .

Let F (t) indicate the event that the inequalities in Lemma 6 are held for
∀t′ ∈ [t/2, t). Therefore, Pr [F (t)] < 1 − δ(t/2)·t
by applying union bound over
2
all t′ ∈ [t/2, t), and using the fact that δ(t′ ) ≤ δ(t/2). Therefore,
n
n
X



 X




πi E τiR (t)
πi E τiA (t) −
|E QA (t) − E QR (t) | =
i=1

i=1

≤
≤
+

n
X
i=1

n
X
i=1

n
X
i=1





πi E τiA (t) − E τiR (t)




πi E τiA (t) − E τiA (t) | F (t)




πi E τiA (t) | F (t) − E τiR (t) ,

where we used the triangle inequality for both inequalities. So, it suffices to show
that for every i,








lim E τiA (t) − E τiA (t) | F (t) = lim E τiA (t) | F (t) − E τiR (t) = 0.
t→∞

t→∞

τiA (t)

Obviously,
≤ t. Now by letting t ≥ 2N0 we have,

 A 



E τi (t) = Pr [F (t)] E τiA (t) | F (t) + Pr [¬F (t)] E τiA (t) | ¬F (t)

 δ(t/2)t

 δ(t/2)t2
≤ E τiA (t) | F (t) +
t = E τiA (t) | F (t) +
.
2
2

(4)

We also get
E



τiA (t)







δ(t/2)t
E τiA (t) | F (t)
(5)
≥ 1−
2

 δ(t/2)t  A


 δ(t)t2
= E τiA (t) | F (t) −
E τi (t) | F (t) ≥ E τiA (t) | X −
.
2
2
1/3

δ(t/2)t2
2
t→∞

Note that lim

= lim 4ne

− π∗ t√
3
6

2

t→∞

t2 = 0, and thus by (4) and (5) we have









lim E τiA (t) − E τiA (t) | F (t) = 0 ⇒ lim E τiA (t) − E τiA (i) | F (t) = 0.

t→∞

t→∞

(6)



Now, we show that lim E τiA (t) | F (t) − E τiR (t) = 0. So here, we ast→∞



sume F (t) holds. So for every i ∈ [n], node i is probed in [t/2, t), and for all
t′ ∈ [t/2, t) we have




(i) pi (t′ ) ≥ 1 − t′1/31 +1 p∗i ≥ 1 − (t/2)11/3 +1 p∗i . So,


E τiA (t) | F (t) ≤


1−

1

(t/2)1/3 + 1

−1

 1

1
−1/3
=
.
1
+
(t/2)
p∗i
p∗i


(ii) pi (t′ ) ≤ 1 +

1
t′1/3 −1




p∗i ≤ 1 +



E τiA (t) | F (t) ≥


1+

1
(t/2)1/3 −1

1
(t/2)1/3 − 1



p∗i . Hence,

−1

 1

1
−1/3
=
1
−
(t/2)
.
p∗i
p∗i



Obviously E τiR (t) = p1∗ , since probing node i by R can be viewed as a geoi
metric distribution with parameter p∗i , and since δ(t) → 0 as t → ∞ we have
 1





1
E τiR (t) = ∗ = lim 1 − (t/2)−1/3 ∗ ≤ lim E τiA (t) | F (t)
t→∞
t→∞
pi
pi
 1



1
≤ lim 1 + (t/2)−1/3 ∗ = ∗ = E τiR (t) .
t→∞
pi
pi

Therefore,





lim |E τiA (t) | F (t) − E τiR (t) | = 0.

t→∞

(7)





Thus, by (6) and (7) we have lim |E QA (t) − E QR (t) | = 0, and A converges



t→∞ Pn √ 2
πi , it implies that lim E QA (t) =
to S, and since lim E QS (t) =
i=1
t→∞
t→∞
Pn √ 2
= cost (A, π) (by Cesaro Mean [6]).
⊓
⊔
i=1 πi
Note that one can obtain an adaptive schedule Ac by choosing c probes
in each step, at each round of Adaptive, and using similar argument as in
Section 4.4 (and similar to Corollary 3), it is easy to see that Ac converges to
Rc .
Finally, if π changes, the Adaptive algorithm converges to the new optimal
memoryless algorithm, as the change in the rate of generating new items is
observed by Adaptive.

References
1. Bright, L., Gal, A., Raschid, L.: Adaptive pull-based policies for wide area data
delivery. ACM Transactions on Database Systems (TODS) 31(2), 631–671 (2006)
2. Cataldi, M., Di Caro, L., Schifanella, C.: Emerging topic detection on twitter based
on temporal and social terms evaluation. In: Proceedings of the Tenth International
Workshop on Multimedia Data Mining. pp. 4:1–4:10. MDMKDD ’10, ACM, New
York, NY, USA (2010)
3. Dasgupta, A., Ghosh, A., Kumar, R., Olston, C., Pandey, S., Tomkins, A.: The
discoverability of the web. In: Proceedings of the 16th international conference on
World Wide Web. pp. 421–430. ACM (2007)
4. Delaney, A.: The growing role of news in trading automation (Oct 2009),
http://www.machinereadablenews.com/images/dl/Machine_Readable_News_and_Algorithmic_Trading.pdf
5. Group, D.B.: Alphaflash trader automated trading based on economic events
(2015), http://www.alphaflash.com/product-info/alphaflash-trader
6. Hardy, G.H.: Divergent series, vol. 334. American Mathematical Soc. (1991)

7. Hart, W., Murray, R.: Review of sensor placement strategies for contamination
warning systems in drinking water distribution systems. Journal of Water Resources Planning and Management 136(6), 611–619 (2010)
8. Hope,
B.:
How
computers
trawl
a
sea
of
data
for
stock
picks.
The
Wall
Street
Journal
(Apr
2015),
http://www.wsj.com/articles/how-computers-trawl-a-sea-of-data-for-stock-picks-1427941801?KEYWORDS
9. Horincar, R., Amann, B., Artières, T.: Online refresh strategies for content based
feed aggregation. World Wide Web pp. 1–35 (2014)
10. Krause, A., Leskovec, J., Guestrin, C., VanBriesen, J., Faloutsos, C.: Efficient sensor placement optimization for securing large water distribution networks. Journal
of Water Resources Planning and Management 134(6), 516–526 (2008)
11. Latar, N.L.: The robot journalist in the age of social physics: The end of human
journalism? In: The New World of Transitioned Media, pp. 65–80. Springer (2015)
12. Leon-Garcia, A.: Probability, Statistics, and Random Processes For Electrical Engineering (3rd Edition). Prentice Hall, 3 edn. (1 2008)
13. Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J.M., Glance,
N.S.: Cost-effective outbreak detection in networks. In: Berkhin, P., Caruana, R.,
Wu, X. (eds.) KDD. pp. 420–429. ACM (2007)
14. Ltd.,
E.A.:
Discovering
the
web’s
hidden
alpha
(Jun
2014),
http://www.eaglealpha.com/whitepaper_pdf
15. Mathioudakis, M., Koudas, N.: Twittermonitor: Trend detection over the twitter
stream. In: Proceedings of the 2010 ACM SIGMOD International Conference on
Management of Data. pp. 1155–1158. SIGMOD ’10, ACM, New York, NY, USA
(2010)
16. McKinney, W.: Structured Data Challenges in Finance and Statistics (Nov 2011),
http://www.slideshare.net/wesm/structured-data-challenges-in-finance-and-statistics
17. Mitra, G., Mitra, L.: The handbook of news analytics in finance, vol. 596. John
Wiley & Sons (2011)
18. Mitzenmacher, M., Upfal, E.: Probability and computing: Randomized algorithms
and probabilistic analysis. Cambridge University Press (2005)
19. Oita, M., Senellart, P.: Deriving dynamics of web pages: A survey. In: TWAW
(Temporal Workshop on Web Archiving) (2011)
20. Ostfeld, A., et al.: The battle of the water sensor networks (bwsn): A design challenge for engineers and algorithms. Journal of Water Resources Planning and Management 134(6), 556–568 (2008)
21. Sia, K.C., Cho, J., Cho, H.K.: Efficient monitoring algorithm for fast news alerts.
Knowledge and Data Engineering, IEEE Transactions on 19(7), 950–961 (2007)
22. Wolf, J.L., Squillante, M.S., Yu, P., Sethuraman, J., Ozsen, L.: Optimal crawling strategies for web search engines. In: Proceedings of the 11th international
conference on World Wide Web. pp. 136–147. ACM (2002)

