In outsourced spatial databases, the LBS provides query services to the clients on behalf of the data owner. However, the LBS provider is not always trustworthy and it may send incomplete or incorrect query results to the clients. Therefore ensuring spatial query integrity is critical. Efficient kNN query verification techniques which utilize the influence zone to check the integrity of query results. kNN query continuously reports the k results (restaurants) nearest to a moving query point. In order to minimize the communication cost between the service provider and the mobile client, a framework for authenticating both the query results and the safe regions of moving kNN queries is proposed. The proposed method can perform moving kNN query authentication with small communication costs and overhead.

Query processing, security, integrity, nearest neighbor and protection

[1] N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger, “The R*-tree: An efficient and robust access method for points and rectangles,” in Proc. ACM SIGMOD Int. Conf. Manage. Data,1990, pp. 322–331.
[2] N. Bruno, S. Chaudhuri, and L. Gravano, “Stholes: A multidimensional workload-aware histogram,” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2001, pp. 211–222.
[3] M. A. Cheema, L. Brankovic, X. Lin, W. Zhang, and W. Wang, “Continuous monitoring of distance based range queries,” IEEE Trans. Knowl. Data Eng., vol. 23, no. 8, pp. 1182–1199, Aug. 2010.
[4] H. Hu, J. Xu, Q. Chen, and Z. Yang, “Authenticating locationbased services without compromising location privacy,” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2012, pp. 301–312.
[5] L. Hu, W.-S. Ku, S. Bakiras, and C. Shahabi, “Verifying spatial queries using voronoi neighbors,” in Proc. 18th SIGSPATIAL Int. Conf. Adv. Geographic Inform. Syst., 2010, pp. 350–359.
[6] G. S. Iwerks, H. Samet, and K. P. Smith, “Maintenance of K-nn and spatial join queries on continuously moving points,” ACM Trans. Database Syst., vol. 31, no. 2, pp. 485–536, 2006.
[7] A. Kundu and E. Bertino, “Structural signatures for tree data structures,” Proc. VLDB Endowment, vol. 1, no. 1, pp. 138–150, 2008.
[8] A. Kundu and E. Bertino, “How to authenticate graphs without leaking,” in Proc. 13th Int. Conf. Extending Database Technol., 2010, pp. 609–620.
[9] F. Li, M. Hadjieleftheriou, G. Kollios, and L. Reyzin, “Dynamic authenticated index structures for outsourced databases,” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2006, pp. 121–132.
[10] F. Li, K. Yi, M. Hadjieleftheriou, and G. Kollios, “Proof-infused streams: Enabling authentication of sliding window queries on streams,” in Proc. 33rd Int. Conf. Very Large Data Bases, 2007,pp. 147–158.
[11] X. Lin, J. Xu, and H. Hu, “Authentication of location-based skyline queries,” in Proc. 20th ACM Int. Conf. Inform. Knowl. Manage., 2011, pp. 1583–1588.
[12] X. Luo, P. Zhou, E. W. W. Chan, W. Lee, R. K. C. Chang, and R. Perdisci, “Httpos: Sealing information leaks with browser-side obfuscation of encrypted flows,” in Proc. Netw. Distrib. Syst. Security Symp., 2011.
[12] X. Luo, P. Zhou, E. W. W. Chan, W. Lee, R. K. C. Chang, and R. Perdisci, “Httpos: Sealing information leaks with browser-side obfuscation of encrypted flows,” in Proc. Netw. Distrib. Syst. Security Symp., 2011.
[13] R. C. Merkle, “A certified digital signature,” in Proc. Adv. Cryptology, 1989, pp. 218–238.
[14] S. Nutanong, R. Zhang, E. Tanin, and L. Kulik, “The V*-Diagram:
A query-dependent approach to moving knn queries,” Proc.VLDB Endowment, vol. 1, no. 1, pp. 1095–1106, 2008.
[15] A. Okabe, B. Boots, K. Sugihara, and S. Chiu, Spatial Tessellations:Concepts and Applications of Voronoi Diagrams, 2nd ed. Hoboken, NJ, USA: Wiley, 2000.
[16] H. Pang, A. Jain, K. Ramamritham, and K.-L. Tan, “Verifying completeness of relational query results in data publishing,” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2005, pp. 407–418.
[17] H. Pang and K. Mouratidis, “Authenticating the query results of text search engines,” Proc. VLDB Endowment, vol. 1, no. 1, pp. 126–137, 2008.
[18] H. Pang, J. Zhang, and K. Mouratidis, “Scalable verification for outsourced dynamic databases,” Proc. VLDB Endowment, vol. 2,no. 1, pp. 802–813, 2009.
[19] S. Papadopoulos, Y. Yang, S. Bakiras, and D. Papadias, “Continuous spatial authentication,” in Proc. 11th Int. Symp. Adv. Spatial Temporal Databases, 2009, pp. 62–79.
[20] S. Papadopoulos, Y. Yang, and D. Papadias, “CADS: Continuous authentication on data streams,” in Proc. 33rd Int. Conf. Very Large Data Bases, 2007, pp. 135–146.
[21] R. Sion, “Query execution assurance for outsourced databases,”in Proc. 31st Int. Conf. Very Large Data Bases, 2005, pp. 601–612.
[22] Z. Song and N. Roussopoulos, “K-nearest neighbor search for moving query point,” in Proc. 7th Symp. Spatio-Temporal Database, 2001, pp. 79–96.
[23] Y. Tao, D. Papadias, and Q. Shen, “Continuous nearest neighbor search,” in Proc. 28th Int. Conf. Very Large Data Bases, 2002, pp. 287–298.