Download pdf, 2 MiB - Infoscience

Chapter 2. Related Work
{sum}
i (value) = {v al ue}
m(a, b) = {a.sum + b.sum}
e(a) = a.sum
Partial state record:
Initializer:
Merger:
Evaluator:
Median: The median operator determines the value in the middle of an ordered set of values.
If the set contains an even number of values, the median operator determines the
arithmetic average of the two values in the middle of the set. For some applications,
median can be used instead of avg, especially if the set of values contains extremely
large or small numbers. The partial state record is duplicate-sensitive, has a variable
size, and consists of all the elements so far encountered. There is no known duplicateinsensitive form or implementation with a fixed-size partial state record of this operator.
As the sensor readings in X might arrive in any order, we first need to make an ordered
set Y = {x 1 , . . . , x n } where n = |X |, ∀y i ∈ Y → y i ∈ X and y i ≤ y i +1 ∀i = 1, . . . , n − 1.
median() =
y ⌊ n2 ⌋ + y ⌈ n2 ⌉
2
(2.7)
Mode: The mode operator determines the most frequent element in a set. There might be
multiple elements with equal occurrences, so the mode operator might not find a single
value. The partial state record is duplicate-sensitive, has a variable size, and consists
of a list of all unique values encountered, and for each value a count indicating how
often this value was encountered. There is no known duplicate-insensitive form or
implementation with a fixed-size partial state record of this operator.
First we must introduce a function that counts the number of occurrences of a given
element a:
count(a) =
X
δa,xi
(2.8)
x i ∈X
Then we can say that the mode of a set X is:
mode() = x i ∈ X s.t.∄(x j ∈ X , count(x j ) > count(x i ))
(2.9)
Count Unique: The count unique operator counts how many unique values are in a set of
values. The partial state record is duplicate-sensitive, has a variable size, and consists
of a list of all unique values encountered. There exists a duplicate-insensitive form of
this operator.
We first need to define a function to determine whether an element is the first occurrence
in the set:
(
1 if ∄(x j = x i , j < i ),
(2.10)
first(i ) =
0 otherwise
24