Re:Nearest neighbor indexes for similarity search
by PaulHoule on Thursday August 12, 2021 @08:37AM
(#28155456)
In most of the cases that I've done vector similarity search the number of vectors was a million or less (say the 300,000 public domain images from the Metropolitan Museum of Art I am looking at now) and in that case in-memory search with naive algorithms works very well and more complex algorithms are more trouble than they are worth.
I've also done similarity search over spiky vectors (have most of the weight in a few dimensions even if they aren't really sparse) with a conventional database (MySQL) in which case I could search a small fraction of the database and have a "proof" that there aren't going to be any more documents that will make it into the top N.
Generally though the hyperdimensional indexes just aren't as good as 1-d indexes, just as the 1-d indexes are a bit better than 2-d and 3-d indexes. (E.g. consider the problem of deciding which lines to draw if you're drawing a map of a small piece of the New Mexico-Arizona border, where the border is a long straight line that has both vertexes far away.)
I've also done similarity search over spiky vectors (have most of the weight in a few dimensions even if they aren't really sparse) with a conventional database (MySQL) in which case I could search a small fraction of the database and have a "proof" that there aren't going to be any more documents that will make it into the top N.
Generally though the hyperdimensional indexes just aren't as good as 1-d indexes, just as the 1-d indexes are a bit better than 2-d and 3-d indexes. (E.g. consider the problem of deciding which lines to draw if you're drawing a map of a small piece of the New Mexico-Arizona border, where the border is a long straight line that has both vertexes far away.)