I think your results are pretty strongly predicated on the fact that we have immensely powerful computers these days such that brute forcing is a viable option

I think your results are pretty strongly predicated on the fact that we have immensely powerful computers these days such that brute forcing is a viable option in many casual real world situations (detect objects in a picture). In fact exact NN algoirthms for high dimensional embeddings converge to linear search performance as the dimensionality increase so a brute force NN is often a good choice always. But that doesn't mean there aren't other problems where the datasets are truly large and require fast query responses (bioinformatics, GIS, anomaly detection...). Which is where you get approximate nearest neighbor search. Haar transform is useful if you dont expect your object to ever rotate or significantly change size, but for more robust image recognition i would suggest david lowes' sift. Which actually spurred much of the approximate nearest neighbor search space, since you didn't necessarily need the closest match, rather just something that was near. Currently the optimal approximate nearest neighbor search algorithm has complexity O(n^rho+d log n) where rho is typically less than 0.37.