Fast and secure similarity search in high dimensional space

Teddy Furon 1 Hervé Jégou 1 Laurent Amsaleg 1 Benjamin Mathon 1
1 TEXMEX - Multimedia content-based indexing
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : Similarity search in high dimensional space database is split into two worlds: i) fast, scalable, and approximate search algorithms which are not secure, and ii) search protocols based on secure computation which are not scalable. This paper presents a one-way privacy protocol that lies in between these two worlds. Approximate metrics for the cosine similarity allows speed. Elements of large random matrix theory provides security evidences if the size of the database is not too big with respect to the space dimension.
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-00857570
Contributor : Laurent Amsaleg <>
Submitted on : Wednesday, June 25, 2014 - 9:00:10 AM
Last modification on : Friday, November 16, 2018 - 1:25:05 AM
Long-term archiving on : Thursday, September 25, 2014 - 10:35:34 AM

File

paper.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-00857570, version 1

Citation

Teddy Furon, Hervé Jégou, Laurent Amsaleg, Benjamin Mathon. Fast and secure similarity search in high dimensional space. IEEE International Workshop on Information Forensics and Security, 2013, Guangzhou, China. ⟨hal-00857570⟩

Share

Metrics

Record views

662

Files downloads

289