Two Efficient Hashing Schemes for High-Dimensional Furthest Neighbor Search
Qiang Huang, Jianlin Feng, Qiong Fang, Wilfred Ng · IEEE Transactions on Knowledge and Data Engineering · 2017
The$c$-Approximate Furthest Neighbor ($c$-AFN) search is a fundamental problem in many applications. However, existing hashing schemes for$c$-AFN search are designed for internal memory. The old techniques for external memory, such as furthest point Voronoi diagram and the tree-based methods, are only suitable for the low-dimensional case. In this paper, we introduce a novel concept of the Reverse Locality-Sensitive Hashing (RLSH) family which is directly designed for$c$-AFN search. Accordingly, we propose a new reverse query-aware LSH function, which is a random projection coupled with query-aware interval identification. Based on the reverse query-aware LSH functions, we introduce a novel Reverse Query-Aware LSH scheme named RQALSH for high-dimensional$c$-AFN search over external memory. Our theoretical studies show that RQALSH enjoys a guarantee on query quality. In addition, in order to further speed up RQALSH, we propose a heuristic variant named RQALSH$^*$which applies a data-dependent objects selection to largely reduce the number of data objects. In the experiment, we compare with two state-of-the-art hashing schemes QDAFN and DrusillaSelect which have been adapted for external memory. Extensive experiments on four real datasets show that our proposed RQALSH and RQALSH$^*$schemes significantly outperform these two methods.