# ML Wiki

## Bit Sampling LSH

• LSH for the Hamming Distance
• can convert $L_1$ to Hamming distance
• NNs are usually the same for $L_1$ and $L_2$
• see Figiel et al. "The dimension of almost spherical sections of convex bodies." 1977. [1]
• so it can be ("sort of") used for Euclidean spaces

### Hamming LSH

Suppose we have $P = \{ \mathbf p_i \}$ where $\mathbf p_i \in H^{d} = \{0, 1\}^{d}$ - i.t. points are in the (binary) Hamming Space of dimensionality $d$ (or $Cd$, in $C$ chunks of size $d$)

Hash Functions

## Sources

• Gionis, Aristides, Piotr Indyk, and Rajeev Motwani. "Similarity search in high dimensions via hashing." 1999. [2]