  We present here new mechanisms for hashing data via binary embeddings.
Contrary to most of the techniques presented before, the embedding matrix of
our mechanism is highly structured. That enables us to perform hashing more
efficiently and use less memory. What is crucial and nonintuitive is the fact
that imposing structured mechanism does not affect the quality of the produced
hash. To the best of our knowledge, we are the first to give strong theoretical
guarantees of the proposed binary hashing method by proving the efficiency of
the mechanism for several classes of structured projection matrices. As a
corollary, we obtain binary hashing mechanisms with strong concentration
results for circulant and Topelitz matrices. Our approach is however much more
general.
