Facebook AI Similarity Search (Faiss)

This app, now almost 5 years old (warning, NSFW):

http://driftwheeler.com

uses a custom brute force search in CUDA, based on bitonic sort (https://en.m.wikipedia.org/wiki/Bitonic_sorter) and a fractional norm distance metric (f=0.5, i.e., sqrt):

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23...

In 2017, on a low-end GPU, the indexing took about 10 minutes of 100% utilization, for a dozen patches covering each of 50,000 images (feature vectors were 1,024 32-bit floats).

After that, the app just queries a precomputed list (256 precomputed matches per query) depending on where in the image the user pressed. Even with hundreds of simultaneous users, it can hardly keep a $5 Linode busy.

Good times...

I’ve used annoy [0] for vector-similarity search before. Does anyone know the differences between Faiss and annoy? Thanks!

[0] https://github.com/spotify/annoy

Here's a list of vector similarity search projects: https://github.com/currentsapi/awesome-vector-search, you can find other alternative method than faiss. Disclosure : I am the maintainer of this lists

If a government had many streams of temporal data, eg coordinates of people's locations, is it just a matter of no cache availability and computation that would slow this down?

If neither of those were concerns, I imagine applying a heuristic on points through time to predict where they would be next. If it's a sleep range, it would expect the current "pixel" on the next step until 9am. That might increase memory and computation costs, but increase speed with a reduction in accuracy.

If you're in the government blink once to confirm.

Is the Voronoi partition the best/most commonly used solution in practice? Or are there better tricks for this problem?