Efficient nearest neighbor search in high dimensional hamming space
作者：
Highlights：
• We address the problem of fast approximate nearest neighbor searching (ANN) in high dimensional Hamming space.
• Two existing techniques (LPP and KD-Tree) are combined in a novel and smart manner to achieve an elegant solution of the studied problem, while neither of them is competent for the studied problem.
• Detailed analysis on complexity and performance of the proposed method has been supplied.
• Extensive experiments with comparison to the state of the art have been reported to validate the effectiveness of the proposed method. The proposed method improves the searching accuracy of the state of the art by 30% (from 60% to 90%) when the searching speed maintains two orders of magnitude faster than the linear scan for a one million database. The speed up factor is even higher for larger database.
摘要
•We address the problem of fast approximate nearest neighbor searching (ANN) in high dimensional Hamming space.•Two existing techniques (LPP and KD-Tree) are combined in a novel and smart manner to achieve an elegant solution of the studied problem, while neither of them is competent for the studied problem.•Detailed analysis on complexity and performance of the proposed method has been supplied.•Extensive experiments with comparison to the state of the art have been reported to validate the effectiveness of the proposed method. The proposed method improves the searching accuracy of the state of the art by 30% (from 60% to 90%) when the searching speed maintains two orders of magnitude faster than the linear scan for a one million database. The speed up factor is even higher for larger database.
论文关键词：Binary feature,Feature matching,Approximate nearest neighbor search,Scalable image matching
论文评审过程：Received 16 March 2019, Revised 17 August 2019, Accepted 12 October 2019, Available online 13 October 2019, Version of Record 21 October 2019.
论文官网地址：https://doi.org/10.1016/j.patcog.2019.107082
