Sub-linear Privacy-preserving Near-neighbor Search

Abstract

In Near-Neighbor Search (NNS), a new client queries a database (held by a server) for the most similar data (near-neighbors) given a certain similarity metric. The Privacy-Preserving variant (PP-NNS) requires that neither server nor the client shall learn information about the other party's data except what can be inferred from the outcome of NNS. The overwhelming growth in the size of current datasets and the lack of a truly secure server in the online world render the existing solutions impractical; either due to their high computational requirements or non-realistic assumptions which potentially compromise privacy. PP-NNS having query time \{\it sub-linear\} in the size of the database has been suggested as an open research direction by Li et al. (CCSW'15). In this paper, we provide the first such algorithm, called Secure Locality Sensitive Indexing (SLSI) which has a sub-linear query time and the ability to handle honest-but-curious parties. At the heart of our proposal lies a secu

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyriazi2016sub

Related papers

• A Scalable Solution To The Nearest Neighbor Search Problem Through Local-search Methods On Neighbor Graphs (2017)3.58
• Fast And Exact Fixed-radius Neighbor Search Based On Sorting (2022)6.77
• Privacy-preserving Near Neighbor Search Via Sparse Coding With Ambiguation (2021)3.58
• High Dimensional Similarity Search With Satellite System Graph: Efficiency, Scalability, And Unindexed Query Compatibility (2019)17.30
• MP-RW-LSH: An Efficient Multi-probe LSH Solution To ANNS In \(L_1\) Distance (2021)0.00
• Sublinear Time Nearest Neighbor Search Over Generalized Weighted Manhattan Distance (2021)0.00
• Sub-linear Memory Sketches For Near Neighbor Search On Streaming Data (2019)0.00
• Worst-case Performance Of Popular Approximate Nearest Neighbor Search Implementations: Guarantees And Limitations (2023)5.84