ANONYMOUS QUERY PROCESSING IN ROAD NETWORKS

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 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. 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. Our techniques exploit existing network database infrastructure, requiring no specialized storage schemes or functionalities. We experimentally compare alternative designs in real road networks and demonstrate the effectiveness of our techniques.

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. Even though a user may create a fake ID to access the service, her location alone may disclose her actual identity. Linking a position to an individual is possible by various means, such as publicly available information (e.g., city maps and telephone directories), physical observation, cell-phone signal triangulation, etc.

User privacy may be threatened because of the sensitive nature of accessed data; e.g., inquiring for pharmacies that offer medicines for diseases associated with a social stigma, or asking for nearby addiction recovery groups (Alcoholics/Narcotics Anonymous, etc). Another source of threats comes from less sensitive data (e.g., gas station locations, shops, restaurants, etc) that may reveal the user’s interests and shopping needs, resulting gina flood of unsolicited advertisements through e-coupons and personal messages. To solve this problem the following general approach is taken. When a user wishes to pose a query, she sends her location to a trusted server, the anonymizer (AZ), through a secure connection (e.g., SSL). The latter obfuscates her location, replacing it with an anonymizing spatial region (ASR) that enclosesu. The ASR is then forwarded to the LS. Ignoring where exactlyu is, the LS retrieves (and reports to the AZ) a candidate set (CS) that is guaranteed to contain the query results for any possible user location inside the ASR. The AZ receives the CS and reports tou the subset of candidates that corresponds to her original query. In order for the AZ to produce valid ASRs, the users send location updates whenever they move (through their secure connection).

The ASR construction at the AZ (i.e., the anonymization process) abides by the user’s privacy requirements. Particularly, specified an anonymity degreeK byu, the ASR satisfies two properties: (i) it containsu and at least anotherK−1 users, and (ii) even if the LS knew the exact locations of all users in the system, it would not be able to infer with a

probability higher than1/K who among those included in the ASR is the querying oneUsers are often interested in location-based queries such as r-range and kNN queries, in the context of a road network. Given a distance threshold r and a user location u, the r-range query returns all objects within (network) distance r from u. On the other hand, the kNN query retrieves the k objects that are closest to u. In the rest of the paper, the term distance refers to the network distance, and the r-range and kNN queries refer to their network versions (unless otherwise specified). Papadias et al. developed efficient indexing and processing methods for the above queries.

They proposed the following disk-based structures for indexing the road network and the data objects:

(i)                 the adjacency index packs adjacency lists of network nodes into disk blocks,

(ii)               the edge R-tree spatially indexes the network edges, and

(iii)             the object R-tree

(ORT) organizes the locations of the data objects. Recently, considerable research interest has focused on preventing identity inference in location-based services. Studies in this area 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). Processing is based on Theorem 1. A direct implementation of the theorem uses (network-based) search operations as offthe-shelf building blocks. Thus, the NAP query evaluation methodology is readily deployable on existing systems, and can be easily adapted to different network storage schemes, as we discuss in Section 5.3. As a case study, in this section we focus on the storage scheme and the network expansion framework of [30], in order to provide a concrete NAP prototype. we propose the network-based anonymization and processing (NAP) framework, the first system for Kanonymous query processing in road networks. NAP relies on a global user ordering and bucketization that satisfies reciprocity and guarantees K-anonymity. We identify the ordering characteristics that affect subsequent processing, and qualitatively compare alternatives.

Then, we propose query evaluation techniques that exploit these characteristics. In addition to user privacy, NAP achieves low computational and communication costs, and quick responses overall. It is readily deployable, requiring only basic network operations. In the traditional spatial anonymity model, the data owner (e.g., a location-based service) makes its data available using a location server. It may, however, be the case that the owner is outsourcing its database to a third-party (and, thus, untrusted) location server. A challenge here is how to encrypt the owner’s data so that they are hidden from the location server, while it can still process anonymous queries. Another interesting question is how (anonymous) users could verify that the location server did not tamper with the original owner data.

SYSTEM ANALYSIS:

EXISTING SYSTEM:  

      Existing method a current location-based services where users have to report their exact locations to the database server in order to obtain their desired services. For example, a mobile user asking about her nearest restaurant has to report her exact location. With untrusted service providers, reporting private location information may lead to several privacy threats. LS make 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.            Existing an peer-to-peer (P2P) spatial cloaking algorithm in which mobile and stationary users can entertain location-based services without revealing their exact location information. The main idea is that before requesting any location-based service, the mobile user will form a group from her peers via single-hop communication and/or multi-hop routing. Then the spatial cloaked area is computed as the region that covers the entire group of peers. 

PROPOSED SYSTEM: 

      In this paper, we propose the network-based anonymization and processing (NAP) framework, the first system for K- anonymous query processing in road networks. NAP relies on a global user ordering and bucketization that satisfies reciprocity and guarantees K-anonymity. We identify the ordering characteristics that affect subsequent processing, and qualitatively compare alternatives. Then, we propose query evaluation techniques that exploit these characteristics. In addition to user privacy, NAP achieves low computational and communication costs, and quick responses overall. It is readily deployable, requiring only basic network operations. 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. Our techniques exploit existing network database infrastructure, requiring no specialized storage schemes or functionalities. We experimentally compare alternative designs in real road networks and demonstrate the effectiveness of our techniques.

HARDWARE & SOFTWARE REQUIREMENTS:

HARDWARE REQUIREMENTS: 

·                     System                        :           Pentium IV 2.4 GHz.

·                     Hard Disk                   :           40 GB.

·                     Floppy Drive               :           1.44 Mb.

·                     Monitor                       :           15 VGA Colour.

·                     Mouse                         :           Logitech.

·                     Ram                             :           512 MB.

  

SOFTWARE REQUIREMENTS: 

·                     Operating system        :           Windows XP Professional.

·                     Coding Language       :           ASP .Net.