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 t

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.