Binary Quantization + Hamming Retrieval

Background

Binary embedding quantisation turns 32-bit float vectors into 1-bit signatures by thresholding at zero. The 32x storage savings come with a small recall hit; Hamming distance (the count of differing bits) between signatures approximates angular distance between the originals, so retrieval still works.

Problem statement

Implement two functions:

• binarise(embs) — input (n, d) float array; return (n, d) bool array where each entry is True iff the float is $\ge 0$.
• hamming_search(query_bin, db_bin, k) — input bool query (length $d$), bool db (n, d), integer $k$; return the indices of the top-$k$ db rows by ascending Hamming distance.

Input

• embs / db_bin — 2-D array; rows are vectors.
• query_bin — 1-D bool array of length $d$.
• k — int >= 1.

Output

• binarise returns np.ndarray of bool, same shape.
• hamming_search returns list[int] of length $\min(k, n)$.

Examples

Example 1 — binarise shape preserved

Input:  embs shape=(5, 16)
Output: bool array shape=(5, 16)

Example 2 — Hamming top-1 on self

Input:  query = db_bin[3]
Output: [3]   # exact match has distance 0

Example 3 — ordering by distance

Input:  query=[T, T], db=[[T, T], [T, F], [F, F]]
Output: [0, 1, 2]   # distances 0, 1, 2

Constraints

• query_bin.shape[0] == db_bin.shape[1] (dim match).
• Tie-break by lower index via stable sort.
• $k$ may exceed $n$; in that case return all $n$.

Notes

• Why it works. For zero-mean, isotropic vectors, the Hamming distance between sign-bit signatures is monotone in the angular distance — so nearest-neighbour orderings approximately match.
• Production extras. Scalar (int8) quantisation is the middle ground: 4x compression with much better recall than 1-bit. Matryoshka-trained embeddings binary-quantise especially cleanly.