A Novel Approach Based on Nearest Neighbor Search on Encrypted Databases

(*) Corresponding author

Authors' affiliations

DOI's assignment:
the author of the article can submit here a request for assignment of a DOI number to this resource!
Cost of the service: euros 10,00 (for a DOI)


Data mining services which permit designers and individuals to store their data to a server, and reduce maintenance cost. The spatial queries  does not provide privacy, because the  location of the query reveal sensitive information about the query. Only authorized user is allowed to access the query, even though service provider not able to view the query. This paper focuses on adducing a novel k- nearest neighbor search on the encrypted database. It describes the strong location privacy that renders a query identical in data space from any location. Due to communication cost in query processing, existing work fails to hold this search. We include a method that endeavors strong location privacy, by amalgamate Metric Preserving Transformation (MPT). Empirical results reveal that efficacy and performance of the adduced methodology has been increased and as compared to the existing methodologies
Copyright © 2013 Praise Worthy Prize - All rights reserved.


Data Privacy; Encryption; Nearest Neighbor Search; Protection; Query Processing; Security

Full Text:



R. Agrawal, J. Kiernan, R. Srikant, and Y. Xu, "Order preserving encryption for numeric data," presented at the Proceedings of the 2004 ACM SIGMOD international conference on Management of data, Paris, France, 2004.

V. Athitsos, M. Potamias, P. Papapetrou, and G. Kollios, "Nearest neighbor retrieval using distance-based hashing," in Data Engineering, 2008. ICDE 2008. IEEE 24th International Conference on, 2008, pp. 327-336.

S. Berchtold, B. Ertl, D. A. Keim, H.-P. Kriegel, and T. Seidl, "Fast nearest neighbor search in high-dimensional space," in Data Engineering, 1998. Proceedings., 14th International Conference on, 1998, pp. 209-218.

L. Bouganim and P. Pucheral, "Chip-secured data access: Confidential data on untrusted servers," in Proceedings of the 28th international conference on Very Large Data Bases, 2002, pp. 131-142.

N. Cao, Z. Yang, C. Wang, K. Ren, and W. Lou, "Privacy-preserving query over encrypted graph-structured data in cloud computing," in Distributed Computing Systems (ICDCS), 2011 31st International Conference on, 2011, pp. 393-402.

C. Clifton, M. Kantarcioglu, J. Vaidya, X. Lin, and M. Y. Zhu, "Tools for privacy preserving distributed data mining," ACM SIGKDD Explorations Newsletter, vol. 4, pp. 28-34, 2002.

J. Feigenbaum, M. Liverman, and R. N. Wright, "Cryptographic protection of databases and software," Distributed Computing and Cryptography, vol. 2, pp. 161-172, 1991.

H. -P. Kriegel, P. Kröger, P. Kunath, and M. Renz, "Generalizing the optimality of multi-step k-nearest neighbor query processing," Advances in Spatial and Temporal Databases, pp. 75-92, 2007.

W. Lu, A. Swaminathan, A. L. Varna, and M. Wu, "Enabling search over encrypted multimedia databases," SPIE/IS&T Media Forensics and Security, pp. 7254-18, 2009.

T. Seidl and H. -P. Kriegel, "Optimal multi-step k-nearest neighbor search," in ACM SIGMOD Record, 1998, pp. 154-165.

M. Shaneck, Y. Kim, and V. Kumar, "Privacy preserving nearest neighbor search," Machine Learning in Cyber Trust, pp. 247-276, 2009.

J. Shashank, P. Kowshik, K. Srinathan, and C. Jawahar, "Private content based image retrieval," in Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on, 2008, pp. 1-8.

D. X. Song, D. Wagner, and A. Perrig, "Practical techniques for searches on encrypted data," in Security and Privacy, 2000. S&P 2000. Proceedings. 2000 IEEE Symposium on, 2000, pp. 44-55.

L. Sweeney, "k-anonymity: A model for protecting privacy," International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, vol. 10, pp. 557-570, 2002.

B. Yao, F. Li, and X. Xiao, "Secure nearest neighbor revisited," In Proceedings of 29th IEEE INternational Conference on Data Engineering(ICDE2013),Brisbane,Australia,2013.

G. R. Hjaltson and H.Samet,"Index-Driven Similarity Search in Metric Spaces", ACM Trans.Database Systems,Vol.28,n.4,pp.517-580,2003.

M. L. Yiu, I. Assent, C. S. Jensen, Fellow, and P.Kalnis, "Outsorced Similarity Search On Metric Data Assets"IEEE Transactions on KnowledgeQueries Using Space and Data Engineering, Vol. 24, n. 2, 2012.

A. Khoshgozaran and C. Shahbi,"Blind Evaluation of Nearest Neigrbor Queries Using Space Transformation to Preserve Location Privacy", Proceedings 10th International Conference Advances in Spatial and Temporal Databases(SSTD),PP.239-257, 2007.

G. Ghintia, P. Kalnis, A. Khoshgozaran, C. Shahbi, and K.L.Tan," Private Queries in Location Based Services:Anonymizers are not necessary",Proceedings ACM SIGMOD International Conference on Management of Data,pp 121-132,2008.

H. Moutachouik, B. Ouhbi, H. Behja, B. Frikh, A. Marzak, H. Douzi, Hybrid Method for Information Retrieval based on the similarity between queries, (2012), International Review on Computers and Software (IRECOS), 7 (6), pp. 2960-2967.

S. Hadi, R. Beg, S. Rizvi, An Intelligent Tree Based Clustering Method for Large Multi Dimensional Data, (2009) International Review on Computers and Software (IRECOS), 4 (6), pp. 648-651.

K. Liang, F. Chen, X. Qu, Research and Application of SVM in Large Scaled Data Set Processing, (2012) International Review on Computers and Software (IRECOS), 7 (4), pp. 1536-1540.

E. Zagrouba, S. Ouni, W. Barhoumi, A Reliable Image Retrieval System Based on Spatial Disposition Graph Matching, (2007) International Review on Computers and Software (IRECOS), 2 (2), pp. 108-117.


  • There are currently no refbacks.

Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2022 Praise Worthy Prize