Anonymous Spatial Query on Non-Uniform Data

Location and local service is one of the hottest bunches of applications in recent years, due to the proliferation of Global Position System (GPS) and mobile web search technology. Spatial queries retrieving neighboring Point-Of-Interests (POI) require actual user locations for services. However, exposing the physical location of querier to service system may pose privacy threat to users, if malicious adversary has access to the system. To hinder the service system from obtaining the “true” location of querier, current obfuscation-based approach requires a trusted third party anonymizer. As for the data-encryption-based and cPIR-based approaches, they incur costly computation overheads. Although the secure hardware-aided PIR-based technique has been shown to be superior to formers, it did not consider the characteristics of data distribution of searching domain. To deal with the problem of non-uniform data distribution and efficient retrieval, we propose four schemes: MSQL, NSQL, MNSQL, MHBL, based on flexible multi-layer grids, non-empty lookup table and Hilbert space-filling curve for efficient storage and retrieval of POI data, so that improved performance of PIR-based techniques could be achieved. Numerical experiments demonstrate that the proposed techniques indeed deliver better efficiency under various criteria.