Direct private query in location-based services with GPU run time analysis

Springer Science and Business Media LLC - Tập 71 - Trang 537-573 - 2014
Charles Asanya1, Ratan Guha1
1Department of Electrical Engineering and Computer Science, University of Central Florida, Orlando, USA

Tóm tắt

Private query in location-based service allows users to request and receive nearest point of interest (POI) without revealing their location or object received. However, since the service is customized, it requires user-specific information. Problems arise when a user due to privacy or security concerns is unwilling to disclose this information. Previous solutions to hide them have been found to be deficient and sometimes inefficient. In this paper, we propose a novel idea that will partition objects into neighborhoods supported by database design that allows a user to retrieve the exact nearest POI without revealing its location, or the object retrieved. The paper is organized into two parts. In the first part, we adopted the concept of topological space to generalize object space. To help limit information disclosed and minimize transmission cost, we create disjointed neighborhoods such that each neighborhood contains no more than one object. We organize the database matrix to align with object location in the area. For optimization, we introduce the concept of kernel in graphical processing unit (GPU), and we then develop parallel implementation of our algorithm by utilizing the computing power of the streaming multiprocessors of GPU and the parallel computing platform and programming model of Compute Unified Device Architecture (CUDA). In the second part, we study serial implementation of our algorithm with respect to execution time and complexity. Our experiment shows a scalable design that is suitable for any population size with minimal impact to user experience. We also study GPU–CUDA parallel implementation and compared the performance with CPU serial processing. The results show 23.9 $$\times $$ improvement of GPU over CPU. To help determine the optimal size for the parameters in our design or similar scalable algorithm, we provide analysis and model for predicting GPU execution time based on the size of the chosen parameter.

Tài liệu tham khảo

Martin T (2002) An evaluation of 911 as an effective community alerting system to augment the role of emergency system. In: National Fire Academy Executive Fire officer Program, Branson, MO

Xu J, Tang X, Hu H, DU J (2010) Privacy-conscious location-based queries in mobile environments. Proc. In: Proceedings of the IEEE Transactions On Parallel and Distributed Systems ’10, vol 21, pp 313–326, March 2010

Sweeney L (2002) K-anonymity: a model for protecting privacy. Int J Uncertain Fuzziness Knowl Based Syst 10:557–570

Samarati P (2002) Protecting respondents identities in microdata release. In: IEEE Transaction on Knowledge and Data Engineering, vol i3, pp 1010–1027, August 2002

Kalnis P, Ghinita G, Mouratidis K, Papadias D (2007) Preventing location-based identity inference in anonymous spatial queries. IEEE Trans Knowl Data Eng 19:1719–1733

Ghinita G, Kalnis P, Khoshgozaran A, Khoshgozaran C, Tan K (2008) Privacy queries in location based services: Anonymizers are not necessary, pp 121–132, June 9–12

R. Vishwanathan. EXPLORING PRIVACY IN LOCATION-BASED SERVICES USING CRYPTOGRAPHIC PROTOCOLS. PhD thesis, Univ. of North Texas, May 2011

Mahafzah B (2013) Performance assessment of multithreaded quicksort algorithm on simultaneous multithreaded architecture. J Supercomput 66:339–363

Mahafzah B (2014) Performance evaluation of parallel multithreaded a* heuristic search algorithm. J Inf Sci 40:363–375

Silvestri C, Lettich F, Orlando S, Jensen CS (2014) Gpu-based computing of repeated range queries over moving objects. In: Parallel, Distributed and Network-Based Processing (PDP), 2014 22nd Euromicro International Conference on IEEE, Torino, Italy, pp 640–647 February 12–14, 2014

Liang S, Liu Y, Wang C, Jian L (2010) Design and evaluation of a parallel k-nearest neighbor algorithm on cuda-enabled gpu. In: Web Society (SWS), 2010 IEEE 2nd Symposium on IEEE, pp 53–60, Beijing, China, August 16–17, 2010

Gieseke F, Heinermann J, Oancea C, Igel C (2014) Buffer k-d trees: Processing massive nearest neighbor queries on gpus. In: Proceedings of the 31st International Conference on Machine Learning, Beijing, China, 2014Beijing, China, pp 172–180

Ghinita G (2008) Understanding the privacy-efficiency trade-off in location based queries. ACM Springl Irvine 2008:1–5

Gruteser M, Grunwald D (2003) Anonymous usage of location-based services through spatial and temporal cloaking. In: Proceedings of ICMSAS 1st International Conference on Mobile Systems, Applications and Services Mobisys’03, pp 31–42

Shin H, Atluri V, Vaidya J (2008) A profile anonymization model for privacy in a personalized location based service environment. In: Proceedings of IEEE ICMDM’08, pp 73–80, Newark, NJ, April 27–30

Gedik B, Liu L (2008) Protecting location privacy with personalized k-anonymity: architecture and algorithms. J IEEE Trans Mob Comput 7:1–18

Gedik B, Liu L (2005) Location privacy in mobile systems: A personalized anonymization model. In: Proceedings of ICDCS International Conference on Distributed Computing Systems, Columbus, OH, pp 620–629

Gedik B, Liu L (2004) A customizable k-anonymity model for protecting location privacy. In: Proceedings of ICDCS International Conference on Distributed Computing Systems, pp 620–629

Kohlweiss M, Faust S, Fritsch L, Gedrojc B, Preneel B (2007) Efficient oblivious augmented maps: Location-based services with a payment broker. In: Proceedings of ACM 7th international conference on Privacy enhancing technologies PET’07, pp 77–94, Springer-Verlag, Berlin, Heidelberg

Cheng R, Zhang F (2009) An improved privacy protocol in location based service, pp 1–4, December 19–20

Kelley JL (2008) General topology. Ishi Press, Sep 2008

Kushilevitzr K, Ostrovsky R (1997) Replication Is Not Needed: Single Database, Computationally-Private Information Retrieval. In: Proceedings of IEEE 38th Annual Symposium on Foundations of Computer Science, pp 364–373, October 20–22

Asanya C, Guha R (2013) Anonymous retrieval of k-nn poi in location based srvices (lbs). In: Proceedings of WORLDCOMP International Conference on Security and Management, SAM ’13, Las Vegas, NV, USA, pp 51–56, July 22–25

NVIDIA. Nvidia’s next generation cuda compute architecture:kepler tm gk110. 1.0. http://www.nvidia.com/content/PDF/kepler/NVIDIA-Kepler-GK110-Architecture-Whitepaper.pdf

Rodengen JL (2000) The Legend of Amdahl. Write Stuff Syndicate, 1st edn, Aug 2000

Cook S (2013) A Developer’s Guide To Parallel computing with GPUs. Morgan Kaufman, 225 Wyman street, Waltham, MA 02451, USA

Cazalas’ J (2012) EFFICIENT AND SCALABLE EVALUATION OF CONTINUOUS, SPATIO-TEMPORAL QUERIES IN MOBILE COMPUTING ENVIRONMENTS. PhD thesis, Univ. of Central Florida, May 2012

USBGN. Geographic names information system domestic and antarctic names state and topical gazetteer. Electronic, October 2013. http://geonames.usgs.gov/domestic/download_data.htm

City of Boston (2013) Boston: a city of neighborhoods. Exploring boston’s neighborhoods Sep 2013. http://www.cityofboston.gov/neighborhoods/

City of Boston (2013) Data boston: Active food establishment. Electronic Publication, 2013. https://data.cityofboston.gov/Permitting/Active-Food-Establishment-Licenses/gb6y-34cq

Sinnot RW (1984) Virtues of the Haversine. Sky and Telescope, vol 68, issue 2, p. 158. http://daimi.au.dk/~dam/thesis/Sky_and_Telescope_1984.pdf

Zhang Y, Owens JD (2011) A quantitative performance analysis model for gpu architectures. In: IEEE High Performance Computer Architecture (HPCA), 2011 IEEE 17th International Symposium on, San Antonio, TX, pp 382–393, February 12–16

Thông tin
Thông tin xuất bản

Springer Science and Business Media LLC

Tập 71

537-573

Thông tin tác giả