
190 Knowledge Discovery from Data Streams
Algorithm 31: Local L2 Thresholding.
Input of peer p
i
: , L, X
i,i
, N
i
, l
Global constants: A random seed s
Data structure for p
i
: For each p
j
∈ N
i
X
i,j
, |X
i,j
|, X
j,i
, |X
j,i
|,
last message
Output of peer p
i
: 0 if ||K
i
|| < , 1 otherwise
Computation of <
F
:
- Let R
in
= {~x : ||~x|| ≤ }
- Let ˆu
1
, . . . , ˆu
l
be pseudo-random unit vectors
- Let H
j
= {~x : ~x · ˆu
j
≥ }
- Let <
F
= {R
in
, H
1
, . . . , H
l
, T }
Computation of X
i,j
and |X
i,j
|:
|X
i,j
| ←
|K
i
|K
i
−|X
j,i
|X
j,i
|K
i
|−|X
j,i
|
w ← |X| ← |K
i
| − |X
j,i
|
while (A
i,j
/∈ R
F
(K
i
)orW
i,j
/∈ R
F
(K
i
)and|W
i,j
| 6= 0) do
w ← |w/2| and |X
i,j
← |K
i
| − |X
j,i
| − w|
Initialization: last message ← −∞, computeR ...