Space Partitioning For Privacy In Location-Based Services Continuous Nearest Neighbor Query

Keywords

Grid Partitioning; Hilbert Curve; PIR; Transition Point; Voronoi Cell

Abstract

With the help of location-aware mobile device user can issue a query and obtain information on nearest point of interest as it moves within a spatial network. This evolving computing paradigm offers great level of convenience to information access and usage. Nevertheless, the convenience comes with a price in the form of exposing user private information to potential abuse and misuse. This paper proposes a novel idea to protect user private information in a location-based services continuous nearest neighbor query with a focus on moving query and static object. Most proposed solutions for privacy use third party anonymizer, or offer protection only for snapshot query, however most queries are continuous. In this proposal we combine Voronoi tessellation and Hilbert curve order with R-tree index of geometric data storage to provide transition points that indicate where nearest neighbor changes. With a database arranged as a square matrix of size n bits, we execute double private information retrieval protocol in the server to return exact nearest neighbor point of interest throughout the query segment with minimal cost, and without revealing any user private information. Our experimental evaluation of the transmission cost using ns-3 simulator and the complexity analysis show a system capable of being scaled to different population size with minimal performance impact and with improvement on the complexity over related technique.

Publication Date

9-28-2015

Publication Title

IEEE International Symposium on Industrial Electronics

Volume

2015-September

Number of Pages

1408-1413

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/ISIE.2015.7281679

Socpus ID

84947230963 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84947230963

This document is currently not available here.

Share

COinS