nach oben

Soft Computing

Erschienen in:

02.07.2015 | Methodologies and Application

Enabling efficient approximate nearest neighbor search for outsourced database in cloud computing

verfasst von: Jianfeng Wang, Meixia Miao, Yaqian Gao, Xiaofeng Chen

Erschienen in: Soft Computing | Ausgabe 11/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Approximate nearest neighbor (ANN) search in high-dimensional space has been studied extensively in recent years. However, it supports only ANN search over plaintext in traditional locality-sensitive hashing (LSH). How to perform ANN search over encrypted data becomes a new challenging task. In this paper, we make an attempt to formally address the problem. We propose a new secure and efficient ANN search scheme over encrypted data based on SortingKeys-LSH (SK-LSH) and mutable order-preserving encryption (mOPE). In our construction, a secure index is generated by incorporating SK-LSH with mOPE, which can simultaneously achieve efficient ANN search and ensure data confidentiality. Furthermore, the proposed solution can achieve efficient range query on encrypted data. Security analysis demonstrates that our construction can achieve the desired security properties.

Vorheriger Artikel Relative density degree induced boundary detection for one-class SVM

Nächster Artikel Functional and non-functional requirements prioritization: empirical evaluation of IPA, AHP-based, and HAM-based approaches

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

When \({\mathcal {L}} ({\mathcal {L}}>1)\) compound hash functions are adopted. \({\mathcal {L}}\) binary search tree is generated in the same way.

To simplify the discussion, we consider only one compound hash function adopted in the construction.

Based on the idea of SK-LSH, It can easily be derived that the page with the smallest distance to its corresponding compound hash key of the query point must be in {\(P_{L}\), \(P_{R}\)}.

http://kdd.ics.uci.edu/databases/CorelFeatures/.

Agrawal R, Kiernan J, Srikant R, Xu Y (2004) Order preserving encryption for numeric data. In: Proceedings of the 2004 ACM SIGMOD international conference on Management of data, ACM, pp 563–574

Athitsos V, Potamias M, Papapetrou P, Kollios G (2008) Nearest neighbor retrieval using distance-based hashing. In: IEEE 24th International Conference on Data Engineering, 2008. IEEE ICDE 2008, pp 327–336

Boldyreva A, Chenette N, Lee Y, Oneill A (2009) Order-preserving symmetric encryption. In: Advances in Cryptology-EUROCRYPT 2009, Springer, pp 224–241

Boldyreva A, Chenette N, ONeill A (2011) Order-preserving encryption revisited: Improved security analysis and alternative solutions. In: Advances in Cryptology-CRYPTO 2011, Springer, pp 578–595

Datar M, Immorlica N, Indyk P, Mirrokni VS (2004) Locality-sensitive hashing scheme based on p-stable distributions. In: Proceedings of the twentieth annual symposium on Computational geometry, ACM, pp 253–262

Friedman JH, Bentley JL, Finkel RA (1977) An algorithm for finding best matches in logarithmic expected time. ACM Trans Math Softw 3(3):209–226CrossRefMATH

Gan J, Feng J, Fang Q, Ng W (2012) Locality-sensitive hashing scheme based on dynamic collision counting. In: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, ACM, pp 541–552

Indyk P, Motwani R (1998) Approximate nearest neighbors: towards removing the curse of dimensionality. In: Proceedings of the thirtieth annual ACM symposium on Theory of computing, ACM, pp 604–613

Jia Y, Wang J, Zeng G, Zha H, Hua XS (2010) Optimizing kd-trees for scalable visual descriptor indexing. In: 2010 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) IEEE, pp 3392–3399

Katayama N, Satoh S (1997) The sr-tree: an index structure for high-dimensional nearest neighbor queries. In: The 1997 ACM SIGMOD international conference on Management of data, ACM, pp 369–380

Li J, Wang Q, Wang C, Cao N, Ren K, Lou W (2010) Fuzzy keyword search over encrypted data in cloud computing. In: 2010 Proceedings IEEE INFOCOM IEEE, pp 1–5

Lin KI, Jagadish HV, Faloutsos C (1994) The tv-tree: an index structure for high-dimensional data. VLDB J 3(4):517–542CrossRef

Liu Y, Cui J, Huang Z, Li H, Shen HT (2014) Sk-lsh: an efficient index structure for approximate nearest neighbor search. Proc VLDB Endow 7(9):745–756

Lu W, Varna AL, Wu M (2010) Security analysis for privacy preserving search of multimedia. In: 2010 17th IEEE International Conference on Image Processing (ICIP), IEEE, pp 2093–2096

Lv Q, Josephson W, Wang Z, Charikar M, Li K (2007) Multi-probe lsh: efficient indexing for high-dimensional similarity search. In: Proceedings of the 33rd international conference on Very large data bases, VLDB Endowment, pp 950–961

Meiser S (1993) Point location in arrangements of hyperplanes. Inf Comput 106(2):286–303MathSciNetCrossRefMATH

Nister D, Stewenius H (2006) Scalable recognition with a vocabulary tree. In: 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, IEEE, pp 2161–2168

Popa RA, Li FH, Zeldovich N (2013) An ideal-security protocol for order-preserving encoding. In: 2013 IEEE Symposium on Security and Privacy (SP), IEEE, pp 463–477

Roussopoulos N, Kelley S, Vincent F (1995) Nearest neighbor queries. In: ACM sigmod record. ACM, vol 24, pp 71–79

Shi E, Bethencourt J, Chan TH, Song D, Perrig A (2007) Multi-dimensional range query over encrypted data. In: IEEE Symposium on Security and Privacy, 2007. SP’07, IEEE, pp 350–364

Song DX, Wagner D, Perrig A (2000) Practical techniques for searches on encrypted data. In: Proceedings 2000 IEEE Symposium on Security and Privacy IEEE, S&P 2000, pp 44–55

Tao Y, Yi K, Sheng C, Kalnis P (2009) Quality and efficiency in high dimensional nearest neighbor search. In: Proceedings of the 2009 ACM SIGMOD International Conference on Management of data. ACM, pp 563–576

Tao Y, Yi K, Sheng C, Kalnis P (2010) Efficient and accurate nearest neighbor and closest pair search in high-dimensional space. ACM Trans Database Syst (TODS) 35(3):20CrossRef

Wang B, Yu S, Lou W, Hou YT (2014) Privacy-preserving multi-keyword fuzzy search over encrypted data in the cloud. In: 2014 Proceedings IEEE INFOCOM

Wang J, Wang N, Jia Y, Li J, Zeng G, Zha H, Hua XS (2014) Trinary-projection trees for approximate nearest neighbor search. IEEE Trans Pattern Anal Mach Intell 36:388–403CrossRef

Weber R, Schek HJ, Blott S (1998) A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. VLDB 98:194–205

Xiao L, Yen IL, Huynh DT (2012) Extending order preserving encryption for multi-user systems. IACR Cryptol ePrint Arch 2012:192

Yum DH, Kim DS, Kim JS, Lee PJ, Hong SJ (2012) Order-preserving encryption for non-uniformly distributed plaintexts. In: Information Security Applications. Springer, pp 84–97

Titel: Enabling efficient approximate nearest neighbor search for outsourced database in cloud computing
verfasst von: Jianfeng Wang
Meixia Miao
Yaqian Gao
Xiaofeng Chen
Publikationsdatum: 02.07.2015
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 11/2016
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-015-1758-6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 11/2016

Analyzing users’ activity in online social networks over time through a multi-agent framework

Optimized hierarchical routing technique for wireless sensors networks

Simplified interval-valued intuitionistic fuzzy integrals and their use in park siting

Functional and non-functional requirements prioritization: empirical evaluation of IPA, AHP-based, and HAM-based approaches

Relative density degree induced boundary detection for one-class SVM

A tournament-based competitive-cooperative multiagent architecture for real parameter optimization