R2.5 · LESSON 5 OF 6

Trees and hashing

Implement an exact baseline, compute recall at k and explain approximate search and high-dimensional difficulty.

THE IDEA

Trees and hashing

Two classic ways to avoid scanning everything. KD-trees repeatedly split the points by one coordinate at the median; a search descends towards the query and then backtracks only into regions that could still contain something closer. It is exact and works well in low dimension. Locality-sensitive hashing maps similar items to the same bucket with high probability: with random hyperplanes each plane gives each vector a bit, and two vectors at angle θ get the same bit with probability 1 − θ/180°.

angle between the vectors (degrees)60hash bits (planes)8

one random plane: same bit with probability 1 − θ/180° = 0.667 (measured on 2000 random planes: 0.694) all 8 bits equal: 0.039 Similar vectors collide often; distant ones rarely: that is what makes the hash locality-sensitive.

Only schemes designed this way work (here: random hyperplanes for angle/cosine similarity). An arbitrary hash deliberately scatters similar inputs. KD-trees take the other route: they split coordinates into regions and can prune whole regions, which works well in low dimension and degrades as it grows.

Move the angle and the number of bits.

Predict first. Is any arbitrary hash function locality-sensitive?

Chapter context

An exact search compares every candidate under a defined metric. Approximate indexes reduce work by choosing promising candidates, accepting that some true nearest neighbors may be missed.

TRY IT YOURSELF

Part 1. Do it hands-on

Work out collision probabilities by hand, then build a KD-tree that matches brute force and a random-hyperplane hash whose collision rate you can measure.

angle between the vectors (degrees)60hash bits (planes)8

same bit at 90° at 60° (3 decimals) 8 bits all equal at 60° is any hash locality-sensitive? (yes/no)

To do: Random-hyperplane hashing for cosine similarity: one random plane gives each vector a bit (which side it is on). Two vectors at angle θ get the same bit with probability 1 − θ/180°. At θ = 90°?
To do: At θ = 60° (3 decimals)?
To do: With 8 independent planes, all 8 bits agree with probability (2/3)⁸ at 60°. (3 decimals)
To do: Is any arbitrary hash function (like a typical string hash) locality-sensitive? Type yes or no

Part 2. Do it in code

build_kdtree(points, depth=0): a nested dict {"point", "index", "axis", "left", "right"} (or None). Split on axis depth % d at the median; points is a list of (index, vector) pairs. Use the lower median (sorted position len//2) and send ties to the left subtree with index order as the tie-break.
kd_nearest(tree, q): the (index, distance) of the exact nearest neighbour, searching the near side first and visiting the far side only if the splitting plane is closer than the best distance so far.
lsh_planes(dim, bits, seed): a (bits, dim) matrix of standard-normal random hyperplane normals (np.random.default_rng(seed)).
lsh_signature(x, planes): the tuple of bits (1 if plane·x >= 0 else 0).
collision_probability(theta_degrees): 1 − θ/180 (the chance that one random plane gives two vectors the same bit).
empirical_collision(a, b, planes): the fraction of planes on which a and b get the same bit.

import numpy as np

def build_kdtree(points, depth=0):
    pass

def kd_nearest(tree, q):
    pass

def lsh_planes(dim, bits, seed):
    pass

def lsh_signature(x, planes):
    pass

def collision_probability(theta_degrees):
    pass

def empirical_collision(a, b, planes):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Is any arbitrary hash function locality-sensitive?

AYesBNo

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

An exact dense dot-product scan over N vectors of dimension d needs Nd coordinate products plus reductions.

\operatorname{recall@k}=\frac{|R_k\cap G_k|}{k}.

This assumes k ground-truth eligible neighbors. In a d-dimensional unit box, a sub-box spanning fraction r of every axis occupies fraction $r^d$ of the volume.

Worked example

Scanning 1000 vectors of dimension 128 uses 128,000 coordinate products, before selection and other overhead. If the true three neighbors are {A,B,C} and the returned set is {A,C,E}, recall@3 is 2/3. A sub-box spanning 0.1 of each of ten axes occupies only 10^-10 of the unit-box volume.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import isclose
assert 1000*128 == 128000
truth,returned={'A','B','C'},{'A','C','E'}
assert isclose(len(truth & returned)/3,2/3)
assert isclose(.1**10,1e-10)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Index recall is not the same as judged semantic relevance. High-dimensional behavior depends on the data manifold. Tie policies can affect reported recall for identical distances.