A reusable and single-interactive model for secure approximate k-nearest neighbor query in cloud

In this work, we present a novel model to remove the above limitations. Specifically, a reusable and single-interactive SANN paradigm is proposed in Euclidean high-dimensional space. Firstly, we present a secure variation of B+-tree (i.e., Bc-tree) to quickly locate high-dimensional candidates in cloud by leveraging on comparable encryption. Based on that, an arbitrary query requestor acquires approximate k-nearest neighbors by linearly scanning over candidates. Meanwhile, two refinements, multi-index strategy and boosting refinement strategy, are proposed to further improve the accuracy of search result and overcome the high-dependency of bandwidth, respectively. In the end, through extensive evaluations on four data sets, the proposed mechanisms are demonstrated to be superior in the tradeoff between accuracy and security.