2011 | OriginalPaper | Chapter
Is Simhash Achilles?
Authors : Qixia Jiang, Yan Zhang, Liner Yang, Maosong Sun
Published in: Information Retrieval Technology
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Simhash generates compact binary codes for the input data thus improves the search efficiency. Most recent works on Simhash are designed to speed-up the search, generate high-quality descriptors, etc. However, few works discuss in what situations Simhash can be directly applied. This paper proposes a novel method to quantitatively analyze this question. Our method is based on Support Vector Data Description (SVDD), which tries to find a tighten sphere to cover most points. Using the geometry relation between the unit sphere and the SVDD sphere, we give a quantitative analysis on in what situations Simhash is feasible. We also extend the basic Simhash to handle those unfeasible cases. To reduce the complexity, an approximation algorithm is proposed, which is easy for implementation. We evaluate our method on synthetic data and a real-world image dataset. Most results show that our method outperforms the basic Simhash significantly.