Sampling Algorithms

Nearly all of the data structures and algorithms we reviewed in the previous chapters are designed specifically for either nearest neighbor search or maximum cosine similarity search. MIPS is typically an afterthought. It is often cast as NN or MCS through a rank-preserving transformation and subsequently solved using one of these algorithms. That is so because inner product is not a proper metric, making MIPS different from the other vector retrieval variants. In this chapter, we review algorithms that are specifically designed for MIPS and that connect MIPS to the machinery underlying multiarm bandits.