Privacy-Preserving Near Neighbor Search via Sparse Coding with Ambiguation
This work addresses the problem of privacy in near neighbor search for users concerned about data leakage during similarity queries.
This paper introduces a framework for privacy-preserving approximate near neighbor search using stochastic sparsifying encoding. The method, called sparse coding with ambiguation (SCA), ensures that any point in a neighborhood has an equiprobable chance of being chosen, and it was tested on synthetic and real image datasets.
In this paper, we propose a framework for privacy-preserving approximate near neighbor search via stochastic sparsifying encoding. The core of the framework relies on sparse coding with ambiguation (SCA) mechanism that introduces the notion of inherent shared secrecy based on the support intersection of sparse codes. This approach is `fairness-aware', in the sense that any point in the neighborhood has an equiprobable chance to be chosen. Our approach can be applied to raw data, latent representation of autoencoders, and aggregated local descriptors. The proposed method is tested on both synthetic i.i.d data and real large-scale image databases.