Databases Reference
In-Depth Information
element
in the PHL such that the area of
r
i
contains the location
identified by the point
x
j
,y
j
and the time interval of
r
i
contains the instant
t
j
.
x
j
,y
j
,t
j
Then, given the set
R
of all requests issued to a certain SP, a subset
of requests
R
issued by the same user
u
is said to satisfy
Historical k-Anonymity
if there exist
k
=
{
r
1
,...,r
m
}
−
1PHLs
P
1
,...,P
k−
1
for
k
−
1users
1, is LT-consistent with
R
.
The open problem in this case is how to generalize each request in order to
obtain traces that are historical
k
-anonymous. One problem is that the LTS
has to generalize each request when it is issued, without having the knowledge
of the future users' locations nor the future requests that are to be issued. A
separate problem is to avoid long traces; indeed, the longer is a trace, the
more each request needs to be generalized in order to guarantee historical
k
-anonymity.
different from
u
, such that each
P
j
,
j
=1
,...,k
−
5 Experimental results
This section presents an extensive experimental evaluation of the algorithms
in Section 4. Tests were performed using artificial data with uniform as well
as non-uniform distribution of users in the considered area.
6
Users' locations
were generated by the moving object generator developed by Brinkhoff [6]
that was set to create 100
,
000 user locations in the metropolitan area of San
Francisco. The total area of the map is about 25
,
000 km
2
while the total
perimeter is about 630 km. The resulting average density of users for km
2
is
4
.
067. Two main parameters have been considered for each test: the value
k
,
representing the degree of anonymity, and the total number
p
of users in the
test. We are interested in three output values from the tests: a) the perimeter
of the output region, b) the area of that region, and c) the computation time.
We implemented the algorithms using Java, and performed our tests on a
Linux machine with two 2,4Ghz Pentium Xeon processors and 4GB of shared
RAM. All the output values presented in this section are obtained by running
1
,
000 tests and taking the average or maximum value, as indicated in the
specific experiment.
To compare the perimeter of the regions returned by the generalization
algorithms with the one having the smallest perimeter, we implemented the
optimalUnsafe
algorithm. This algorithm computes the set of
k
1 users such
that the perimeter of the MBR including these users and the issuer is minimal.
The idea of
optimalUnsafe
is to search the best perimeter of the MBRs for
each set containing the issuer and other
k
−
1 users. Hence, the complexity of
the algorithm is exponential in
p
; However, we developed several optimization
techniques that make the algorithm in most cases computable in time linear
−
6
The experimental results summarized in the figures of this section are obtained
on non-uniform distributions, if not explicitly said otherwise in the captions.
