EasyDeepLearn
Unsupervised Learning · section 3 of 9

Distance & scaling considerations

6 interview questions on distance & scaling considerations, each answered in full. Free to read, no account needed.

HNSW — how does it work?

hard
  • Hierarchical multi-layer graph.
  • Top layer: sparse long-range edges.
  • Lower layers: denser short-range.
  • Search: start at top, greedy traversal toward query, descend one layer, refine.
  • Insertion: probabilistically assign layer (exponential decay), connect to M nearest neighbors per layer.
  • Log-time search on average.
  • Trade-off knobs: M (neighbors per node), efconstruction  /  efsearch\mathrm{ef}_{\mathrm{construction}}\; / \;\mathrm{ef}_{\mathrm{search}} (search-time exploration).
#applications#similarityPermalink & quiz →

Product Quantization (PQ) — how does it compress vectors?

hard
  • Split d-dim vector into m sub-vectors of d/m dims.
  • Cluster each sub-vector space separately (k centroids per subspace, k typically 256).
  • Encode a vector as m codes (log⁡2(k)  bits  each)(\operatorname{log}_{2}(k)\;\mathrm{bits}\;\mathrm{each}).
  • Distance computed via precomputed lookup tables between query and centroids → very fast. 8-32× compression vs float32 with modest recall loss.
  • Foundation of FAISS's scale to billions of vectors.
#applications#similarityPermalink & quiz →

Locality-Sensitive Hashing (LSH) — the core trick.

hard
  • Hash function h such that P(h(x) = h(y)) is high for close x, y and low for far ones (opposite of crypto hash).
  • Different metric → different LSH family: MinHash for Jaccard (near-duplicate documents), SimHash for cosine, random hyperplane for cosine, Euclidean via random projections.
  • Multiple hash tables → high recall.
  • Standard for near-duplicate detection in web crawls, genomic sequence search.
#applications#similarityPermalink & quiz →

MinHash — how does it estimate Jaccard similarity?

hard
  • Given sets A, B: pick many random permutations of the universe.
  • For each permutation, MinHash(A) = smallest element of A under that permutation.
  • Fraction of permutations where MinHash(A) = MinHash(B) is an unbiased estimator of Jaccard(A, B) = |A ∩ B| / |A ∪ B|.
  • Compact signature (128-256 hashes) enables billion-set comparison.
  • Standard for near-duplicate detection in web crawlers (Bing, Google historically).
#applications#similarityPermalink & quiz →

Interview: your image dataset (10M) has near-duplicates — how do you dedup at scale?

hard
  • (1) Perceptual hashing (pHash / dHash / wHash): 64-bit hash → Hamming distance threshold catches near-duplicates and small edits.
  • Fast, cheap.
  • (2) Deep embedding-based (CLIP / DINOv2) + LSH or FAISS ANN for semantic near-duplicates (same subject, different pose).
  • (3) Combine both — pHash for pixel-level, embeddings for content.
  • Standard in training data prep for image generation (Stable Diffusion 3, Ideogram).
  • Also matters for benchmarking to avoid train-test leak.
#interview#applications#similarityPermalink & quiz →

Concretely, what goes wrong with distance-based methods in high dimensions?

hard
  • Distances concentrate: as dimensionality grows, the ratio between the nearest and farthest neighbour of a point tends towards one, so the very notion of a nearest neighbour loses discriminative power.
  • Volume also grows so fast that any realistic sample is sparse, meaning every point is effectively an outlier and density estimates have almost no support.
  • Irrelevant dimensions make this worse, since each contributes noise to the distance and dilutes the informative ones, which is why feature selection helps distance methods disproportionately.
  • The practical responses are to reduce dimensionality first, use a metric learned or chosen for the domain, use cosine distance where magnitude is uninformative, or switch to methods such as tree ensembles that select dimensions rather than aggregating over all of them.
#similarity#dimensionality-reductionPermalink & quiz →

Practise Unsupervised Learning

All 9 sectionsFlashcardsQuiz