Branch-and-Bound Algorithms

One of the earliest approaches to the top-k retrieval problem is to partition the vector space recursively into smaller regions and, each time we do so, make note of their geometry. During search, we eliminate the regions whose shape indicates they cannot contain or overlap with the solution set. This chapter covers algorithms that embody this approach and discusses their exact and approximate variants.