Brute-Force K-Nearest Neighbors Search

What is k-Nearest Neighbor (k-NN) Search?

The core task of a vector database is similarity search. Given a query vector (e.g., representing an image or a piece of text), we want to find the items in our database that are most similar to it. In the high-dimensional space of vectors, "similarity" is synonymous with "proximity." The k-Nearest Neighbor (k-NN) problem is the formalization of this task: for a given query vector, find the k vectors in the database that are closest to it according to a chosen distance metric (like the Euclidean or Cosine distance we implemented in Module 2).

To solidify this concept, let's review a formal definition of the k-NN search problem.

The Brute-Force Algorithm: An Exhaustive Search

The most direct way to solve the k-NN problem is with a brute-force or exhaustive search. The principle is simple: compare the query vector to every single vector in the database, calculate all the distances, and then identify the k smallest ones. There are no shortcuts.

This exhaustive approach is often called a sequential scan, as it involves iterating through the entire dataset sequentially. While its computational cost is high, its great advantage is that it guarantees perfect accuracy. It will always find the true nearest neighbors. For this reason, it's considered the "gold standard" for evaluating the accuracy of more complex, faster algorithms.

The steps of the brute-force algorithm are straightforward. The paper you just looked at provides a clear, step-by-step breakdown.

From Algorithm to Implementation

The algorithm described is:

1. Compute the distance between the query q and all m reference points.
2. Sort the m distances.
3. Select the k points with the lowest distances.

Step 2, sorting all m distances, is inefficient if m is large and k is small. We don't need a fully sorted list of all m distances; we only care about the top k. A more efficient approach is to maintain a small, bounded list of the k best candidates found so far as we iterate through the database.

Here is a more practical implementation strategy:

1. Create a temporary array or list to hold up to k results (e.g., pairs of distance and vector_id).
2. Iterate through every vector in the database from i = 0 to m-1.
   a. Calculate the distance between the query vector and vector i.
   b. If the results list has fewer than k items, add the new result (distance, i) to the list.
   c. If the results list is full (has k items), find the result with the largest distance in the list. If the newly calculated distance is smaller than this largest distance, replace that entry with the new result.
3. After iterating through all m vectors, the list will contain the k nearest neighbors.
4. As a final step, sort this small list of k results by distance to present them in order.

This approach avoids the O(m log m) cost of a full sort, replacing it with a linear scan of size k at each step, making the cost of maintaining the list closer to O(m*k). In the next lesson, we will improve this further using a data structure specifically designed for this task: a max-heap.

For a clear walkthrough of this logic, the following video implements k-NN from scratch in Python. While the language is different, the core algorithm for finding and tracking the nearest neighbors is identical to our plan.

Implementing db_search_knn in C

Now, let's translate this into C code for our project. First, we need a structure to hold a single search result.

// In your main header file (e.g., vdb.h)



#include <stdint.h>

// Represents a single search result
typedef struct {
    float distance;
    uint32_t id; // The index of the vector in the database
} SearchResult;

Next, you will implement the search function itself. This function will live in your main implementation file (e.g., vdb.c). It will take the database handle, a query vector, the value of k, and an output array to store the results.

Here is a skeleton for your implementation. Your task is to fill in the logic.

#include <float.h> // For FLT_MAX

// Helper function to sort results by distance for the final output
int compare_search_results(const void* a, const void* b) {
    SearchResult* res_a = (SearchResult*)a;
    SearchResult* res_b = (SearchResult*)b;
    if (res_a->distance < res_b->distance) return -1;
    if (res_a->distance > res_b->distance) return 1;
    return 0;
}

// Performs a brute-force k-NN search.
// 'results' must be a pre-allocated array of size k.
void db_search_knn(Db* db, const float* query_vector, uint32_t k, SearchResult* results) {
    // 1. Initialize the results array with "worst possible" values.
    for (uint32_t i = 0; i < k; ++i) {
        results[i].distance = FLT_MAX;
        results[i].id = -1; // Invalid ID
    }

    uint32_t vector_count = db->metadata->vector_count;
    uint32_t dim = db->metadata->dim;

    // 2. Iterate through all vectors in the database.
    for (uint32_t i = 0; i < vector_count; ++i) {
        float* db_vector = (float*)(db->mapped_region + db->metadata->data_start_offset + (i * dim * sizeof(float)));
        
        // Calculate distance (using your function from Module 2, e.g., euclidean_distance_naive)
        float dist = euclidean_distance_naive(query_vector, db_vector, dim);

        // 3. Keep track of the top k results.
        // Find the current worst result in our candidate list.
        float max_dist_in_results = -1.0f;
        int worst_idx = -1;
        for (uint32_t j = 0; j < k; ++j) {
            if (results[j].distance > max_dist_in_results) {
                max_dist_in_results = results[j].distance;
                worst_idx = j;
            }
        }

        // If the new distance is better than the worst one in our list, replace it.
        if (dist < max_dist_in_results) {
            results[worst_idx].distance = dist;
            results[worst_idx].id = i;
        }
    }

    // 4. Sort the final k results by distance.
    qsort(results, k, sizeof(SearchResult), compare_search_results);
}

Your Task: Integrate this db_search_knn function into your project. You will need to use the euclidean_distance_naive function you wrote in Module 2. Make sure your Db struct and file layout logic from previous lessons are correctly used to locate the vector data. Write a small test in your main function to insert a few vectors and then perform a search to verify it works.

The Faiss library from Meta is a great example of a real-world, high-performance similarity search library. It provides a brute-force index called IndexFlatL2 that does exactly what we are implementing now.

Conclusion

In this lesson, you have implemented the most fundamental algorithm in similarity search. While simple, the brute-force k-NN search is an indispensable part of our project.

Here are the key takeaways:

• Brute-force k-NN (or sequential scan) is an exhaustive search that compares a query vector to every other vector in a dataset.
• It is computationally expensive, with a complexity of O(N*d) for N vectors of dimension d, but it guarantees 100% accuracy.
• This perfect accuracy makes it the "gold standard" for benchmarking faster, approximate search methods.
• An efficient implementation avoids sorting all N distances by maintaining a bounded list of the k best candidates found so far.

You've now built a correct, if slow, search capability. This is a major milestone. However, the linear scan to find the "worst" candidate in our results array at every step is a small but noticeable inefficiency.

In our next lesson, we will address this directly. You will learn how to use a bounded max-heap data structure to efficiently track the top 'k' candidates during a search. This will provide a significant performance improvement over our current array-based approach and introduce you to a classic and powerful computer science tool.