R2.6 · LESSON 6 OF 6

Approximation tradeoffs

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

THE IDEA

Approximation trade-offs

An approximate index gives up some recall for speed. Judge it on recall, latency, memory and build/update cost together, against the requirement of your application. In the toy table the exact scan needs 80 ms; index A is 40× faster but finds only 90% of the true neighbours, index B is 16× faster with 96% recall at 1.33× the memory.

minimum recall the application needs0.95

option	recall	latency (ms)	memory (GB)	build (min)	qualifies?
exact scan	1	80	3	0	yes
index A	0.9	2	3.5	10	no
index B	0.96	5	4	25	yes
index C	0.99	20	4.5	40	yes

fastest that qualifies: index B (5 ms, 16× faster than the scan, 1.33× the memory)

Choose by recall, latency, memory and build/update cost together. An index that is fastest but misses the information your application needs is the wrong index.

Set the recall the application needs.

Predict first. Is fastest query latency alone enough to choose an index?

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

Pick an index under a recall requirement by hand, then write the selection and Pareto code.

minimum recall the application needs0.95

option	recall	latency (ms)	memory (GB)	build (min)	qualifies?
exact scan	1	80	3	0	yes
index A	0.9	2	3.5	10	no
index B	0.96	5	4	25	yes
index C	0.99	20	4.5	40	yes

fastest that qualifies: index B (5 ms, 16× faster than the scan, 1.33× the memory)

Choose by recall, latency, memory and build/update cost together. An index that is fastest but misses the information your application needs is the wrong index.

fastest option with recall ≥ 0.95 speed-up over the exact scan memory ratio (2 decimals)

To do: Exact scan: recall 1.0, 80 ms. Index A: 0.90, 2 ms. Index B: 0.96, 5 ms. Index C: 0.99, 20 ms. The application needs recall ≥ 0.95. Which candidate is fastest among those that qualify? Type its name (A, B, C or exact)
To do: How many times faster is that index than the exact scan?
To do: It uses 4.0 GB against the exact scan's 3.0 GB. How many times the memory (2 decimals)?

Part 2. Do it in code

qualifying(configs, min_recall): the configs (dicts with name, recall, ms, gb, build) whose recall is at least min_recall.
fastest_qualifying(configs, min_recall): the name of the qualifying config with the lowest ms (the first on ties); None if none qualifies.
speedup(config, baseline): baseline ms / config ms. memory_ratio(config, baseline): config gb / baseline gb.
pareto_front(configs): the names of configs that are not dominated: a config is dominated if another is at least as good on recall (higher or equal) AND on ms (lower or equal) and strictly better on at least one.
qps(config): queries per second for one worker = 1000 / ms.

def qualifying(configs, min_recall):
    pass

def fastest_qualifying(configs, min_recall):
    pass

def speedup(config, baseline):
    pass

def memory_ratio(config, baseline):
    pass

def pareto_front(configs):
    pass

def qps(config):
    pass

Ctrl/⌘ + Enter runs it

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

CHECK YOUR UNDERSTANDING

Is fastest query latency alone enough to choose an index?

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.