Graph Algorithms

We have seen two major classes of algorithms that approach the top-k retrieval problem in their own unique ways. One recursively partitions a vector collection to model its geometry, and the other hashes the vectors into predefined buckets to reduce the search space. Our next class of algorithms takes yet a different view of the question. At a high level, our third approach is to “walk” through a collection, hopping from one vector to another, where every hop gets us spatially closer to the optimal solution. This chapter reviews algorithms that use a graph data structure to implement that idea.