Retrieval Stability in High Dimensions

We are about to embark on a comprehensive survey and analysis of vector retrieval methods in the remainder of this monograph. It may thus sound odd to suggest that you may not need any of these clever ideas in order to perform vector retrieval. Sometimes, under bizarrely general conditions that we will explore formally in this chapter, an exhaustive search (where we compute the distance between query and every data point, sort, and return the top k) is likely to perform much better in both accuracy and search latency! The reason why that may be the case has to do with the approximate nature of algorithms and the oddities of high dimensions. We elaborate this point by focusing on the top-1 case.