R2.1 · LESSON 1 OF 6

Exact search

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

THE IDEA

The exact baseline

The simplest nearest-neighbour search compares the query with every stored vector, then keeps the best. It is called brute force or a flat scan. For 1000 vectors of dimension 128 it does 128,000 coordinate products; for a million vectors of dimension 768 it does 768 million. That may be too slow for the final system, but it is exactly correct, so it is the yardstick for any approximate index.

query x0query y0

rank	point	distance
1	B [1, 1]	1.414
2	C [-2, 0]	2
3	D [0, 3]	3
4	A [3, 4]	5

vectors1,000dimension128

a full scan = 1,000 × 128 = 128,000 coordinate products per query (before selecting the top results) It is exact and simple, so it is the baseline every approximate index is measured against.

Move the query among four points. Then change the corpus size.

Predict first. Can an approximate index be evaluated for exact-neighbour recall without a defined exact target?

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

Count a scan's work by hand and find the nearest points, then write brute-force search and the ground truth.

query x0query y0

rank	point	distance
1	B [1, 1]	1.414
2	C [-2, 0]	2
3	D [0, 3]	3
4	A [3, 4]	5

vectors1,000dimension128

a full scan = 1,000 × 128 = 128,000 coordinate products per query (before selecting the top results) It is exact and simple, so it is the baseline every approximate index is measured against.

products, 1000 × 128 products, 10⁶ × 768 nearest to [0,0] second nearest

To do: Brute force compares the query with every vector. 1000 vectors of dimension 128: coordinate products?
To do: One million vectors of dimension 768 (type the count, e.g. 7.68e8)?
To do: Query q = [0, 0]. Points A = [3, 4], B = [1, 1], C = [−2, 0], D = [0, 3]. Which is the exact nearest neighbour (Euclidean)? Type the letter
To do: And the second nearest?

Part 2. Do it in code

distances(q, X): Euclidean distances from the query to every row of X.
brute_force(q, X, k): the indices and distances of the k nearest rows, nearest first (ties: lower index first). k must be at least 1 (ValueError); if k exceeds the number of rows return all rows.
scan_cost(n_vectors, dim): coordinate products needed by a full scan.
exact_ground_truth(Q, X, k): for every query row the list of its k exact neighbour indices; this is the target an approximate index is judged against.

import numpy as np

def distances(q, X):
    pass

def brute_force(q, X, k):
    pass

def scan_cost(n_vectors, dim):
    pass

def exact_ground_truth(Q, X, k):
    pass

Ctrl/⌘ + Enter runs it

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

CHECK YOUR UNDERSTANDING

Can an approximate index be evaluated without a defined exact target?

ANoBYes

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.