The Wallsend projectProduct quantisation on 729 neighbourhood profiles
Store each profile in fewer bytes, search the compressed store, and count how many true neighbours survive.
The learner downloads census table TS007A from Nomis for every output area in North Tyneside and divides each count by the area's total, giving 18 shares per area, one for each five-year age band. Two areas count as similar when their 18 shares are close. For each of Wallsend's 163 output areas the program finds the 10 most similar areas in the whole borough using full-precision numbers. That is the correct answer. Stored as ordinary 64-bit numbers, each profile takes 144 bytes. The question is how much smaller it can get before the search starts returning the wrong neighbours.
The obvious approach is to round each share, keeping fewer bits for it. Product quantisation does something cleverer. It cuts the 18 numbers into pieces, say nine pieces of two, and for each piece learns a small codebook of typical values with k-means clustering. A profile is then stored as nine codebook numbers. With 256 entries per codebook, each code fits in one byte.
Share of the true 10 nearest output areas found when searching compressed profiles, averaged over the 163 Wallsend queries (our Python; product quantisation averaged over five random starts)| How each profile is stored | Bytes per profile | True neighbours found |
|---|
| Full 64-bit numbers | 144 | 100% |
| Each share rounded to 8 bits | 18 | 98.8% |
| Each share rounded to 4 bits | 9 | 82.0% |
| Product quantisation, 9 pieces, 256 codes each | 9 | 91.5% |
| Each share rounded to 2 bits | 4.5 | 36.2% |
| Product quantisation, 6 pieces, 64 codes each | 4.5 | 68.4% |
| Product quantisation, 3 pieces, 256 codes each | 3 | 68.0% |
| Product quantisation, 2 pieces, 256 codes each | 2 | 58.6% |
At every size where we tested both, product quantisation came out ahead. With 9 bytes a profile it finds 91.5% of the true neighbours where rounding finds 82.0%; at 4.5 bytes the gap is 68.4% against 36.2%. Even squeezed into 2 bytes, it still finds more than half. The reason is that the codebooks learn which combinations of values actually occur. Rounding spends bits evenly on every possible value, most of which no real neighbourhood ever has.
There is a catch, and learners are expected to find it. The codebooks have to be stored too. With 256 codes per piece they hold 4,608 numbers, while the whole raw table of North Tyneside is only 13,122. For 729 profiles the saving is an illusion. Product quantisation earns its keep when there are millions of stored vectors sharing the same small codebooks, which is exactly the situation inside a large AI search system.
Ages 8 to 11
Describe classmates by five traits, then by two, and see who gets matched with the wrong friend.
Ages 11 to 15
Store the profiles with fewer bits in Python and measure how the list of nearest areas changes.
Ages 15 and up
Write k-means and product quantisation with NumPy, then test recall against bytes on all 729 areas.
Data and limits
Census 2021 table TS007A via Nomis, and the ONS lookup from output areas to built-up areas, both under the Open Government Licence. The profiles, the searches and the percentages are our own. Similar age mixes say nothing about the people who live in an area, and a different set of variables would give different neighbours.
