Databases Reference
In-Depth Information
the
k
1 users that are the closest to the issuer, and returns the MBR of the set
containing
i
, the issuer, and the
k
−
1 users closest to
i
. In our implementation
of the
nnASR
algorithm we used a kd-Tree to store users' locations, making
possible to compute
k
Nearest Neighbor queries in logarithmic expected time
with respect to the number of users.
−
4.2
C
I
-safe algorithms
To the best of our knowledge, the first
C
I
-safe generalization algorithm was
proposed by Kalnis et al. [11], and it was called
hilbASR
. The idea of
hilbASR
is to exploit the Hilbert space filling curve to define a total order among users'
locations. A data structure is then used to store users in the order defined
through the Hilbert space filling curve. Intuitively, the
hilbASR
generalization
algorithm partitions the data structure into blocks of
k
users: the first block
from the user in position 0 to the user in position
k
−
1 and so on (note that
the last block can contain up to 2
1 users). The algorithm then returns
the MBR computed considering the position of the users that are in the same
block as the issuer. The worst case time complexity of
hilbASR
is
O
(
log
(
·
k
−
)).
A different
C
I
-safe algorithm was proposed by Mascetti et al [15] and was
called
dichotomicArea
. Starting from the total area monitored by the LTS,
the
dichotomicArea
algorithm (Algorithm 1) iteratively partitions the area
into two adjacent rectangles of equal size. The partitioning is done along the
horizontal and vertical axis, altenatively in each iteration. The input of the
algorithm consists of the degree of anonymity
k
and the issuer
i
. The output
is
null
if less than
k
users are located in the total area monitored by the LTS,
otherwise the algorithm returns an area in which at least
k
users are located.
The algorithm terminates when at least 1 and at most
k
|
I
|
1 users are located in
any of the two sub-areas. Algorithm
dichotomicArea
is an instance of a class of
algorithms presented in [3]; in that paper it is proved that any generalization
algorithm that iteratively partitions the set of users, and that terminates when
any block contains less then
k
users, is a
C
I
-safe algorithm. At each iteration,
dichotomicArea
partitions the set of users according to their location with
respect to the sub-areas. If no user is located in a sub-area, then the set of
users is not partitioned and iteration continues. On the contrary, if one of the
sub-areas contains more than one user but less than
k
, execution terminates.
The data structure that we used in the implementation of the algorithm is
similar to the one we used for the implementation of
IntervalCloaking
.The
only difference is that each internal node has two children instead of four.
Consequently, the time complexity of the algorithm is the same as the one for
IntervalCloaking
.
A second generalization algorithm belonging to the class presented in [3]
is called
dichotomicPoints
. The idea is to use a different partitioning func-
tion, named
partitionPoints
. The users are totally ordered according to their
locations considering first one axis, then the other, and if necessary even the
−
