What is it about?
Furthest Neighbor Search (FNS) is a fundamental problem with wide applications in many fields, such as data mining and pattern recognition. In this paper, we introduce a novel concept of the Reverse Locality-Sensitive Hashing (RLSH) family and develop a novel Reverse Query-Aware LSH (RQALSH) scheme for high-dimensional FNS over external memory. Our theoretical studies show that RQALSH enjoys a guarantee on query quality. To further speed up RQALSH, we propose a heuristic variant named RQALSH* to reduce the number of candidates vastly. Extensive experiments on four large-scale real-life datasets show that our proposed RQALSH and RQALSH* schemes are much more efficient than two state-of-the-art methods QDAFN and DrusillaSelect, especially in high-dimensional spaces.
Featured Image
Photo by Daniel Lerman on Unsplash
Why is it important?
Existing hashing schemes for FNS are designed for internal memory. The existing techniques for external memory, such as the furthest point Voronoi diagram and the tree-based methods, are only suitable for low-dimensional cases. In this paper, we propose the first provable LSH scheme for high-dimensional FNS over external memory, which might be insightful for the young researchers to continue work on this topic.
Perspectives
I hope this paper could bring new thought to people who design basic data structures for FNS problem or other fundamental similarity search problems.
Dr Qiang Huang
National University of Singapore
Read the Original
This page is a summary of: Two Efficient Hashing Schemes for High-Dimensional Furthest Neighbor Search, IEEE Transactions on Knowledge and Data Engineering, December 2017, Institute of Electrical & Electronics Engineers (IEEE),
DOI: 10.1109/tkde.2017.2752156.
You can read the full text:
Resources
Contributors
The following have contributed to this page
