22-08-2012, 01:21 PM
[u]Anonymous Query Processing in Road Networks[/u]
Anonymous Query.pdf (Size: 408.41 KB / Downloads: 44)
Abstract
The increasing availability of location-aware mobile devices
has given rise to a flurry of location-based services (LBS). Due to the
nature of spatial queries, an LBS needs the user position in order to process
her requests. On the other hand, revealing exact user locations to a
(potentially untrusted) LBS may pinpoint their identities and breach their
privacy. To address this issue, spatial anonymity techniques obfuscate
user locations, forwarding to the LBS a sufficiently large region instead.
Existing methods explicitly target processing in the Euclidean space,
and do not apply when proximity to the users is defined according to
network distance (e.g., driving time through the roads of a city). In this
paper, we propose a framework for anonymous query processing in road
networks. We design location obfuscation techniques that (i) provide
anonymous LBS access to the users, and (ii) allow efficient query
processing at the LBS side.
INTRODUCTION
The low cost and small size of positioning equipment (e.g.,
GPS receivers) have allowed their embedding into PDAs and
mobile phones. The wide availability of these location-aware
portable devices has given rise to a flourishing industry of
location-based services (LBS). An LBS makes spatial data
available to the users through one or more location servers
(LS) that index and answer user queries on them. Examples
of spatial queries could be “Where is the closest hospital to
my current location?” or “Which pharmacies are open within
a 1 km radius?”. In order for the LS to be able to answer such
questions, it needs to know the position of the querying user.
There exist many algorithms for efficient spatial query
processing, but the main challenge in the LBS industry is of a
different nature. In particular, users are reluctant to use LBSs,
since revealing their position may link to their identity.
RELATED WORK
Section 2.1 reviews related work on road network databases
and Section 2.2 surveys the literature on spatial anonymity.
Query Processing in Road Networks
Basic Notation. In general, a road network can be modeled
as a weighted graph G = (N;E). N contains the network
nodes, while E is the set of edges. Nodes n in N model road
intersections, locations of road turns, or positions where traffic
conditions change (e.g., a street gets narrower). On the other
hand, every edge e connects two nodes and is associated with
a non-negative weight w(e). Weight w(e) may represent, for
instance, the traveling time from one node to the other. Figure
2 shows an example of a road network. Edge n1n2 has weight
3, and its endpoints are nodes n1 and n2. Let p be a point on
an edge e with weight w(e). The partial weight from p to
an end-node of e is proportional to their (Euclidean) distance,
while the sum of the two partial weights is equal to w(e).
For instance, object o1 (shown as a solid point) lies on edge
n3n4 and has partial weights 1 and 3 from nodes n3 and n4,
respectively. Similarly, user u (the hollow point) falls on edge
n2n3 and both of its partial weights are 2.
Anonymous Location-based Queries
Recently, considerable research interest has focused on preventing
identity inference in location-based services. Studies
in this area [17], [14], [28], [23] typically assume the
model described in Section 1, proposing spatial cloaking
(i.e., location obfuscation) techniques. In the following, we
describe existing techniques for ASR computation (at the
AZ) and query processing (at the LS). At the end, we cover
alternative location privacy approaches and discuss why they
are inappropriate to our problem setting.
Spatial Cloaking at the AZ. In general, the AZ applies the
concept of K-anonymity [33] to hide the querying user location
u. The idea is to compute an anonymizing spatial region
(ASR), containing u and at least K