Course contentsShow
← AI Engineering
Lesson 231 of 1,8866. Embeddings and Semantic SearchFree lesson

Top-K Retrieval Implementation

Implementing efficient top-k nearest neighbor search using sorting and heap-based approaches.

Top-K Retrieval Implementation

What You'll Learn

You'll learn how to efficiently retrieve the k most similar items from a collection of embeddings using sorting and heap-based approaches.

The Challenge of Finding the Best Matches

After computing cosine similarities between a query embedding and thousands (or millions) of document embeddings, you need the top k most similar results—not all of them. For example, a user searches and wants the 5 most relevant documents, not all 10,000 similarities ranked.

Two Practical Approaches

Sorting Approach (Simple)

The straightforward method: compute all similarities, sort them in descending order, and take the first k items.

Analogy: Like grading all exam papers, sorting them from highest to lowest score, then announcing the top 5 students.

This works well for smaller datasets (thousands of items) but requires sorting the entire list—potentially wasteful when you only need a handful of results.

Heap Approach (Efficient)

Use a min-heap of size k. As you scan similarities, maintain only the k largest values seen so far. When you encounter a larger value, replace the smallest item in your heap.

Analogy: Like keeping only the 5 highest exam scores in your hand as you grade papers. When you find a better score, drop the lowest one you're holding.

This approach uses less memory and avoids sorting everything—you only maintain k items at a time.

When to Use Each

  • Small datasets or infrequent queries: Sorting is fine and simpler to implement
  • Large datasets or real-time systems: Heap-based retrieval reduces computational overhead
  • Production systems: Consider approximate nearest neighbor libraries for even faster retrieval at massive scale

Key Takeaway: Top-k retrieval efficiently surfaces the most relevant results by using sorting for simplicity or heaps for memory efficiency, avoiding the cost of ranking every single similarity score.