Hall of Mirrors: A Novel Strategy to Address Locality in Geocoded-Based PoI Private Queries

Location privacy techniques try to protect user's information by altering, aggregating or generalizing it. Geographical codification techniques, like Geohash, can be used to protect individual locations altering the precision of the location so it represents wide area that contains the user's location but does not give out the exact coordinate. However, this transformation creates some problems when a simple range-based query wants to be performed over coded data: neighbor points may have quite different representations if they fall in different quadrants. This problem, named lack of locality, has been solved by extending the search area of the query by projecting the user's location in all adjacent grid cells and use the common prefix of the code to identify all the points in the adjacent cells, but the result set increases substantially, creating a problem for the user which needs to filter the useful results from the set returned by the extended query. In this work, the Hall of Mirrors, or HoM strategy is presented, which creates multiple representations of the points of interest in adjacent quadrants. This allows, not only the execution of the traditional common prefix query, but also distance-based queries from the user's location, using the numerical code difference, which overcomes the locality problem by obtaining the relevant points of interest - PoI and reduces the number of total results. Four PoI projection techniques are introduced and compared to the Adaptive Hilbert-Geohash, or AHG technique and the regular geographic query. The results of the experiments performed on a dataset of 827 points of interests in Bogota, Colombia, show that, compared to regular common prefix queries, distance-based HoM generates from 29% up to 91% fewer irrelevant results in the best scenarios. In addition, results show that HoM techniques can find the relevant points faster than the AHG technique, due to the nature of the points projection and better distance correspondence.