Databases Reference
In-Depth Information
Figures 8(a) and 8(b) show the average area of the regions returned by
the
C
I
-unsafe and
C
I
-safe algorithms when users' locations are uniformly
distributed in the map. We can notice that the three algorithms of Figure 8(b)
return regions with almost the same average area. Analogous results have been
obtained considering the perimeter. Comparing Figure 7(b) and Figure 8(b),
we can notice that the performance of
hilbASR
does not significantly differ
with the two distributions. On the other hand,
dichotomicArea
has by far
the worst performance in the non-uniform case. This is due to the fact that,
with a non-uniform distribution, there are regions with few users that lead
the
dichotomicArea
algorithm to terminate the execution after few iterations.
On the contrary,
dichotomicPoints
has significantly better performance in the
non-uniform distribution. This is due to the fact that the issuer of the request
is randomly chosen among the users, and in the non-uniform distribution,
users' density is much higher in some parts of the general area than in others;
Hence, on average, we have many requests from densely populated regions.
Unlike in Figures 7(a) and 7(b), with the uniform data set, the
C
I
-unsafe
algorithms generally perform similarly to the
C
I
-safe ones, with the exception
of
intervalCloaking
. The poor performance of
intervalCloaking
, is mainly due
to the fact that, by dividing at each step the area in 4 quadrants, it may hap-
pen to return areas that double those returned by the other algorithms. The
similar performance of the other algorithms can be intuitively understood
since, with uniform locations, i) it does not matter if we divide the region
based on number of users or based on the area (that is the main difference
between
dicothomicPoints
and
dicothomicArea
), and ii) the termination con-
dition of
C
I
-unsafe and
C
I
-safe algorithms is satisfied in a similar number of
steps. Indeed, the termination condition of
C
I
-safe algorithms imposes that
at least
k
users are included in each block of the partition, and this usually
causes less iterations (and larger output regions); however with a uniform dis-
tribution this condition is likely to be satisfied whenever the one for
C
I
-unsafe
algorithms is satisfied, leading to similar dimensions of the resulting areas.
Figure 9 shows the average computation time of the algorithms
dichotomic-
Points
for different values of
p
. The average computation time of Algorithms
nnASR
,
dichotomicArea
and
hilbASR
is less than 5 ms in each experiment
and we did not observe significant changes in the computation time for values
of
p
between 10
,
000 and 200
,
000. This is due to the fact that i) the time
complexity of the algorithms depends logarithmically in the size of
p
and ii)
the computation time of the algorithms is dominated by startup time. On
the contrary, the computation time of
dichotomicPoints
grows linearly with
p
. This result is consistent with the theoretical complexity analysis of the al-
gorithm. We also evaluated the time complexity of the algorithms for a fixed
p
and different values of
k
and we observed that the execution time of the
algorithms is almost not affected by the value of the parameter
k
.
