Anonymous Spatial Query on Non-Uniform Data

Anonymous Spatial Query on Non-Uniform Data

Shyue-Liang Wang (Department of Information Management, National University of Kaohsiung, Kaohsiung, Taiwan), Chung-Yi Chen (Department of Information Management, National University of Kaohsiung, Kaohsiung, Taiwan), I-Hsien Ting (Department of Information Management, National University of Kaohsiung, Kaohsiung, Taiwan) and Tzung-Pei Hong (Department of Computer Science and Information Engineering, National University of Kaohsiung, Kaohsiung, Taiwan)
Copyright: © 2013 |Pages: 18
DOI: 10.4018/ijdwm.2013100103
OnDemand PDF Download:
No Current Special Offers


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.
Article Preview


In a Location-Based Service, such as Google map or Bing map under a cloud computing environment, a user/client is allowed to issue queries (e.g. containing user’s GPS location) to retrieve k nearest Point-Of-Interests around user’s physical location from database server. With the voluminous sales of smart phones which are mostly equipped with GPS, location-based service is gaining more and more popularity. For example, Twitter’s recent integration of user location in Tweets has helped increase the use of the location-based services. Facebook too is following suit, launching its own location-based service, Facebook Places. However, one of the concerns using these services is the negative effects on privacy.

Consider the following scenario (Saint-Jean, 2005): Alice is looking for gold in California. What Alice does is look for a place with a little gold and follow the trace. Now, Alice wants to find gold in a place where no mining patent has been awarded, but many patents have been awarded in California during the gold rush. What Alice does is to walk around California with a GPS and a notebook computer. Whenever she finds a trace of gold she follows it querying if any patent has been awarded in that location. If she finds a trace of gold in a piece of land with no issued patent she can request the patent and start mining for gold.

The problem is that she is worried that Bob’s Mining Patents Inc., the service she queries the patents from, might cheat on her. Because Bob knows she is looking for gold in California (Alice said so when signing up for Bob’s service), he knows that, if she queries from some location, then there is gold there. So, if she queries a location and there is no patent awarded, Bob may run to the patent office and get the mining patent for that location.

Within a pervasive computing environment today (Asonov, 2004), many negative effects, in addition to the scenario mentioned above, could be associated with failure to protect location privacy. For examples: 1. Location-based “spam”: Location could be used by unscrupulous businesses to bombard an individual with unsolicited marketing for products or services related to that individual’s location. 2. Personal wellbeing and safety: Location is inextricably linked to personal safety. Unrestricted access to information about an individual’s location could potentially lead to harmful encounters, for example stalking or physical attacks. 3. Intrusive inferences: Location constrains our access to spatiotemporal resources, like meetings, medical facilities, our homes, or even crime scenes. Therefore, location can be used to infer other personal information about an individual, such as that individual’s political views, state of health, or personal preferences.

Complete Article List

Search this Journal:
Open Access Articles
Volume 18: 4 Issues (2022): Forthcoming, Available for Pre-Order
Volume 17: 4 Issues (2021): 2 Released, 2 Forthcoming
Volume 16: 4 Issues (2020)
Volume 15: 4 Issues (2019)
Volume 14: 4 Issues (2018)
Volume 13: 4 Issues (2017)
Volume 12: 4 Issues (2016)
Volume 11: 4 Issues (2015)
Volume 10: 4 Issues (2014)
Volume 9: 4 Issues (2013)
Volume 8: 4 Issues (2012)
Volume 7: 4 Issues (2011)
Volume 6: 4 Issues (2010)
Volume 5: 4 Issues (2009)
Volume 4: 4 Issues (2008)
Volume 3: 4 Issues (2007)
Volume 2: 4 Issues (2006)
Volume 1: 4 Issues (2005)
View Complete Journal Contents Listing