Databases Reference
In-Depth Information
the same number of users. Unfortunately, the high computational complexity
of
optimalUnsafe
makes it impossible to evaluate this algorithm for values of
k
larger than 14. For this reason, in the remaining of this section, this algorithm
is ignored.
Figures 7(a) and 7(b) show the average area of the region returned by
C
I
-
unsafe and
C
I
-safe algorithms, respectively, with values of
k
higher than in
the previous test (up to
k
= 180). Similar results have been obtained consid-
ering the average perimeter. It can be noticed that
dichotomicPoints
returns
smaller regions with respect to
hilbASR
,
dichotomicArea
and
intervalCloak-
ing
. Figure 7(b) shows that the curve referring to
dichotomicPoints
does not
grow regularly but has some “steps”. This is due to the fact that the algo-
rithm partitions the number of points until it finds a set containing less than
k
users. The number of iterations is given by:
log(
k
)
. Therefore, there are
executions of the algorithm with different values of
k
that iterate the same
number of times, hence computing, at the last iteration, the same number of
users. Consequently, these executions return regions with similar area. Pre-
dictably, the
C
I
-unsafe algorithms generally return smaller regions than the
C
I
-safe ones as, intuitively, the
C
I
-safe algorithms have more constraints on
the output regions.
100
intervalCloaking
casper
nnASR
80
60
40
20
0
20
60
100
140
180
k
(a)
C
I
-unsafe algorithms.
100
hilbASR
dichotomicArea
dichotomicPoints
80
60
40
20
0
20
60
100
140
180
k
(b)
C
I
-safe algorithms.
Fig. 7.
Average area with
p
= 100
,
000 and
k ≤
180.
