Ahmet Salih BUYÜKKAYHAN, Taflan İmre GÜNDEM

Assignment as a location-based service in outsourced databases

:Location-based services provide opportunities to organizations for tracking and utilizing their resources. Moreover, some corporations prefer to outsource their database management services. In the literature, privacy preservation techniques in outsourced spatial databases for several query types, such as nearest neighbor, K-nearest neighbor, and proximity search, have been examined. In this paper, we present an efficient application of the capacity and coverageconstrained assignment query on outsourced spatial databases. In the proposed technique, we introduce a novel spatial transformation strategy (square spiral encoding) to achieve privacy efficiently for approximate assignment query results. To process the assignment query, we use the parallel auction algorithm. We implemented and tested the assignment query with the proposed technique for correctness and efficiency.

PDF

___

[1] C¸ okpınar S, G¨undem T˙I. Positive and negative association rule mining on XML data streams in database as a service concept. Expert Syst Appl 2012; 39: 7503-7511.
[2] Unay O, Gundem TI. Parallel processing of encrypted xml documents in database as a service concept. Inf Technol Control 2010; 39: 301-309.
[3] Unay O, Gundem TI. A survey on querying encrypted XML documents for databases as a service. SIGMOD Record 2008; 37: 12-20.
[4] Chow CY, Mokbel M, Liu X. Spatial cloaking for anonymous location-based services in mobile peer-to-peer environments. GeoInformatica 2011; 15: 351-380.
[5] Gedik B, Ling L. Protecting Location privacy with personalized k-anonymity: architecture and algorithms. IEEE T Mobile Comput 2008; 7: 1-18.
[6] Khoshgozaran A, Shirani-Mehr H, Shahabi C. Blind evaluation of nearest neighbor queries using space transformation to preserve location privacy. GeoInformatica 2013; 17: 599-634.
[7] Hacıg¨um¨u¸s H, Iyer B, Li C, Mehrotra S. Executing SQL over encrypted data in the database-service-provider model. In: Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data; 36 June 2002; Madison, WI, USA. New York, NY, USA: ACM. pp. 216-227.
[8] Indyk P, Woodruff D. Polylogarithmic private approximations and efficient matching. In: Halevi S, Rabin T, editors. Theory of Cryptography. Berlin, Germany: Springer, 2006. pp. 245-264.
[9] Bilogrevic I, Jadliwala M, Joneja V, Kalkan K, Hubaux J-P, Aad I. Privacy-preserving optimal meeting location determination on mobile devices. IEEE T Inf Foren Sec 2014; 9: 1141-1156.
[10] Khoshgozaran A, Shahabi C, Shirani-Mehr H. Location privacy: going beyond K-anonymity, cloaking and anonymizers. Knowl Inf Syst 2011; 26: 435-465.
[11] Ghinita G, Kalnis P, Khoshgozaran A, Shahabi C, Tan K-L. Private queries in location based services: anonymizers are not necessary. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of data; 912 June 2008; Vancouver, Canada. New York, NY, USA: ACM. pp. 121-132.
[12] Lien I, Lin Y, Shieh J, Wu J. A novel privacy preserving location-based service protocol with secret circular shift for k-NN search. IEEE T Inf Foren Sec 2013; 8: 863-873.
[13] Cormen TH. Introduction to Algorithms. 2nd ed. Boston, MA, USA: MIT Press, 2001.
[14] Karp RM, Vazirani UV, Vazirani VV. An optimal algorithm for on-line bipartite matching. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing; 1317 May 1990; Baltimore, MD, USA. New York, NY, USA: ACM. pp. 352-358.
[15] Kuhn HW. The Hungarian method for the assignment problem. Nav Res Logist Q 1955; 2: 83-97.
[16] Munkres J. Algorithms for the assignment and transportation problems. J Soc Ind Appl Math 1957; 5: 32-38.
[17] Derigs U. The shortest augmenting path method for solving assignment problems motivation and computational experience. Ann Oper Res 1985; 4: 57-102.
[18] Bertsekas DP. Auction algorithms for network flow problems: a tutorial introduction. Comput Optim Appl 1992; 1: 7-66.
[19] Bertsekas DP, Castanon DA. Parallel synchronous and asynchronous implementations of the auction algorithm. Parallel Comput 1991; 17: 707-732.
[20] Konan AR, G¨undem T˙I, Kaya ME. Assignment query and its implementation in moving object databases. Int J Inf Tech Decis 2010; 9: 349-372.
[21] U LH, Yiu ML, Mouratidis K, Mamoulis N. Capacity constrained assignment in spatial databases. In: Proceedings of the 2008 ACM SIGMOD international conference on Management of Data; 912 June 2008; Vancouver, Canada. New York, NY, USA: ACM. pp. 15-28.
[22] U LH, Mouratidis K, Mamoulis N. Continuous spatial assignment of moving users. VLDB J 2010; 19: 141-160.
[23] Orlin JB, Lee Y. QuickMatch: A Very Fast Algorithm for the Assignment Problem. Cambridge, MA, USA: MIT Press, 1993.
[24] G¨orlach A, Heinemann A, Terpstra W. Survey on location privacy in pervasive computing. In: Robinson P, Vogt H, Wagealla W, editors. Privacy, Security and Trust within the Context of Pervasive Computing. New York, NY, USA: Springer, 2005. pp. 23-34.
[25] Kalnis P, Ghinita G, Mouratidis K, Papadias D. Preventing location-based identity inference in anonymous spatial queries. IEEE T Knowl Data En 2007; 19: 1719-1733.
[26] Ghinita G, Kalnis P, Kantarcioglu M, Bertino E. A hybrid technique for private location-based queries with database protection. In: Mamoulis N, Seidl T, Pedersen T, Torp K, Assent I, editors. Advances in Spatial and Temporal Databases. Berlin, Germany: Springer, 2009. pp. 98-116.
[27] Mokbel MF, Chow CY, Aref WG. The new Casper: query processing for location services without compromising privacy. In: Proceedings of the 32nd International Conference on Very Large Databases; 1215 September 2006; Seoul, Korea. pp. 763-774.
[28] Gruteser M, Grunwald D. Anonymous usage of location-based services through spatial and temporal cloaking. In: Proceedings of the 1st International Conference on Mobile Systems, Applications and Services; 58 May 2003; San Francisco, CA, USA. New York, NY, USA: ACM. pp. 31-42.
[29] Zhang C, Huang Y. Cloaking locations for anonymous location based services: a hybrid approach. GeoInformatica 2009; 13: 159-182.
[30] Radu S, Carbunar B. On the computational practicality of private information retrieval. In: Proceedings of Network and Distributed System Security Symposium; 28 February2 March 2007; San Diego, CA, USA.
[31] Khoshgozaran A, Shahabi C. Blind evaluation of nearest neighbor queries using space transformation to preserve location privacy. In: Proceedings of the 10th International Conference on Advances in Spatial and Temporal Databases; 1618 July 2007; Boston, MA, USA. Berlin, Germany: Springer-Verlag. pp. 239-257.
[32] Lin D, Bertino E, Cheng R, Prabhakar S. Location privacy in moving-object environments. T Data Privacy 2009; 2: 21-46.
[33] Yiu ML, Christian SJ, Xuegang H, Hua L. SpaceTwist: managing the trade-offs among location privacy, query performance, and query accuracy in mobile services. In: Proceedings of the IEEE 24th International Conference on Data Engineering; 712 April 2008; Cancun, Mexico. New York, NY, USA: IEEE. pp. 366-375.
[34] Yiu ML, Ghinita G, Jensen C, Kalnis P. Enabling search services on outsourced private spatial data. VLDB J 2010; 19: 363-384.
[35] Yiu ML, Ghinita G, Jensen CS, Kalnis P. Outsourcing search services on private spatial data. In: Proceedings of the IEEE 25th International Conference on Data Engineering; 29 March2 April 2009; Shanghai, China. New York, NY, USA: IEEE. pp. 1140-1143.
[36] Cha GH, Chung CW. A new indexing scheme for content-based image retrieval. Multimed Tools Appl 1998; 6: 263-288.
[37] Stein M, Ulam S, Wells M. A visual display of some properties of the distribution of primes. Am Math Mon 1964: 516-520.