The ruler: recall and compression

Measuring the size: compression ratio

The easy axis first. How much smaller did the data get? Take the original size and divide it by the compressed size; that number is the compression ratio. A vector (a list of numbers, here 128 of them) stored as 32-bit floats takes 512 bytes. Squash each number to a single byte and it takes 128, a ratio of 4 times. Squash the whole vector down to 8 bytes, as a method later in this course (product quantization) can, and the ratio is 64 times. Bigger is better, and it is exact.

Measuring the damage: recall@k

Accuracy is subtler. For search, what matters is not whether a stored number is slightly off, but whether you still find the right neighbours. So we measure recall@k: of the true k nearest points to a query, how many does the search still return after compression. Perfect recall is 1.0; if compression makes you miss one of the true four, recall@4 drops to 0.75.

The dark dot below is a query. Four points are its true nearest neighbours. Drag the coarseness knob to compress harder: points blur onto a grid, the search starts returning the wrong ones, and a true neighbour turns red the moment it gets dropped.

No search engine required

A quiet but important point: you can measure recall without building any fast search index at all. Compare every compressed point against the query by brute force, take the nearest k, and check them against the exact answer. It is slow, but it isolates exactly what we want to grade: the quality of the compression itself, not the speed of the lookup. Speed is a separate project's job.

With both axes pinned down, recall on one and compression ratio on the other, we can draw the curve that every method in this course competes on. Time to build the first method.

Key takeaways