  Hashing is one of the most popular methods for similarity search because of
its speed and efficiency. Dense binary hashing is prevalent in the literature.
Recently, insect olfaction was shown to be structurally and functionally
analogous to sparse hashing [6]. Here, we prove that this biological mechanism
is the solution to a well-posed optimization problem. Furthermore, we show that
orthogonality increases the accuracy of sparse hashing. Next, we present a
novel method, Procrustean Orthogonal Sparse Hashing (POSH), that unifies these
findings, learning an orthogonal transform from training data compatible with
the sparse hashing mechanism. We provide theoretical evidence of the
shortcomings of Optimal Sparse Lifting (OSL) [22] and BioHash [30], two related
olfaction-inspired methods, and propose two new methods, Binary OSL and
SphericalHash, to address these deficiencies. We compare POSH, Binary OSL, and
SphericalHash to several state-of-the-art hashing methods and provide empirical
results for the superiority of the proposed methods across a wide range of
standard benchmarks and parameter settings.
