4 ms·

This reminded me of another, related task that comes up a lot in machine learning and IR: searching by vectors (rather than keywords). Aka k-NN (k nearest neigh

by Radim 10y ago

This reminded me of another, related task that comes up a lot in machine learning and IR: searching by vectors (rather than keywords). Aka k-NN (k nearest neighbors) search. Just as with fulltext search, there's no shortage of clever approximate algorithms for kNN vector search (with the additional caveat of the "curse of dimensionality"). And just as here, without careful tuning, a well-optimized brute force search blows most "clever", widely popular kNN implementations out of the water on large datasets [1]. There's certainly something to be said for simplicity and good "systems engineering". [1] http://rare-technologies.com/performance-shootout-of-nearest-neighbours-contestants/ http://rare-technologies.com/performance-shootout-of-nearest...

mempko 10y ago
This is especially true if you can fit all the data on a GPU. GPU is really really good computing cosine distance fast and in parallel.
mattb314 10y ago
Your linked blog post was a really good read, but I'm not totally sure if the correct takeaway was that brute force outperforms "clever" algorithms. Unless I misinterpreted the results, FLANN and Annoy (which implement hierarchical k-means and a binary space partitioning algorithm, respectively) both ran about 100x faster than brute force. Were you referring to the number of libraries the author couldn't get to work? This certainly might be a failure of over complicated algos, but it seemed more like an engineering failure than a performance failure to me.
- Radim 10y ago
  Well, complex algos and engineering failures go hand in hand :-) The approximative kNNs are superior if done well, no doubt about that. It's just that "doing them well" is a major challenge, even for well-established and well thought out tools, such as scikit-learn. So many things can go wrong, and despite the increased complexity & settling for approximative results, you can end up with worse runtime performance than O(n) brute force... The performance of brute force is pleasantly predictable and stable. I just found the parallels with OP's article (which is on fulltext search, a mostly unrelated field) interesting, that's all.

by Radim 10y ago

mempko 10y ago

This is especially true if you can fit all the data on a GPU. GPU is really really good computing cosine distance fast and in parallel.

mattb314 10y ago

Your linked blog post was a really good read, but I'm not totally sure if the correct takeaway was that brute force outperforms "clever" algorithms. Unless I misinterpreted the results, FLANN and Annoy (which implement hierarchical k-means and a binary space partitioning algorithm, respectively) both ran about 100x faster than brute force. Were you referring to the number of libraries the author couldn't get to work? This certainly might be a failure of over complicated algos, but it seemed more like an engineering failure than a performance failure to me.

Radim 10y ago
Well, complex algos and engineering failures go hand in hand :-) The approximative kNNs are superior if done well, no doubt about that. It's just that "doing them well" is a major challenge, even for well-established and well thought out tools, such as scikit-learn. So many things can go wrong, and despite the increased complexity & settling for approximative results, you can end up with worse runtime performance than O(n) brute force... The performance of brute force is pleasantly predictable and stable. I just found the parallels with OP's article (which is on fulltext search, a mostly unrelated field) interesting, that's all.