Compress vectors to a few small numbers: cut each one into pieces, run k-means on each piece to get a codebook, and store the number of the nearest centre. A query’s distance to every stored vector comes from a small table of piece-to-centre distances.
This interactive visualization needs JavaScript.