Databases Reference
In-Depth Information
Algorithm 1
dichotomicArea
1:
orient
:=
HOR
2:
area
:= the total area
3:
if
(
|
usersIn
(
area
)
|
<k
)
then return null
;
4:
while true do
5:
subAreas
:=
partitionArea
(
area, orient
)
6:
if
∃
a
∈
subAreas
s.t. 0
<
|
usersIn
(
a
)
|
<k
then
7:
return
area
8:
else
9:
area
:=
a
j
∈ subAreas
s.t.
i ∈ usersIn
(
a
j
)
10:
if
orient
=
HOR
then
orient
:=
VER
11:
else
orient
:=
HOR
12:
end if
13:
end while
user identifier; Then, considering the user
u
in the middle
4
, it partitions the
users into two blocks: the ones before
u
, and the remaining ones. In order to
choose the first axis used to order the users,
dichotomicPoints
computes, for
each axis, the difference between the maximum and minimum value of users's
locations projected on that axis and then choose the one having the higher
difference
5
.
Similarly to
dichotomicArea
, computation terminates when any of the two
blocks of the partition contain less than
k
users; Then it returns the MBR
of all the users' locations in those two blocks. This algorithm has some sim-
ilarities with the
Anonymize
algorithm presented in [13] despite they have
been independently designed. The data structure used in the implementation
of
dichotomicPoints
consists of two arrays,
order
x
and
order
y
, containing the
users ordered according to the horizontal and vertical axis, respectively. At
each iteration, the user locations that are not in the same block as the issuer
are removed from the two arrays. So, at each iteration it is necessary to find
the user location in the middle of the correct array, to count how many users
will be in each block and to remove the users that are not in the same block as
the issuer. The first two operations can be performed in constant time, while
the last one requires a time linear in the size of the two arrays. Since the
number of iterations is logarithmic in the number of users and each iteration
requires time linear in the number of the users, the worst case time complexity
of the algorithm is
O
(
|
I
|·
log(
|
I
|
)).
4
When there is an even number
r
of users, user
u
is the one in position r/2 +1.
5
A slightly different version of
dichotomicPoints
was presented in [15]; The only
difference is the way the first axis used to order users is chosen.
