When teaching a graduate course on retrieval algorithms, it occurred to me that there was no single resource that covered the foundations of vector retrieval or a treatise that dealt with the fascinating literature on nearest neighbor search and all the beautiful theory behind it.

So I decided to write one, particularly geared towards graduate students, with an emphasis on the theoretical foundations of the field. I hope “Foundations of Vector Retrieval” proves a helpful reference, one that makes it a bit easier for you to pick up this topic, navigate the literature, continue this research, and make new discoveries!

What does vector retrieval ask for? A query point q is surrounded by a collection of data points in a two-dimensional Euclidean example. Three nearest points are highlighted and ordered by their distance from q. The challenge is to find these neighbors efficiently in much larger and higher-dimensional collections. What does vector retrieval ask for? a b c q return the nearest points 1. a distance 0.44 2. b distance 0.79 3. c distance 1.02 A 2-D Euclidean example; real collections may have millions of high-dimensional points.
The basic retrieval problem in a two-dimensional Euclidean example: find the data points nearest the query q. Here a, b, and c are the three nearest points, ordered by distance in consistent arbitrary units. Indexes aim to find useful neighbors without scanning every point. View largerScroll sideways for the full sketch.

I have made a copy freely available on arXiv. If you prefer a hard copy, you can read it as paperback. You can cite the work using the following bibtex entry:

@book{Bruch_2024,
   title={Foundations of Vector Retrieval},
   ISBN={9783031551826},
   publisher={Springer Nature Switzerland},
   author={Bruch, Sebastian},
   year={2024}
}