Introduction

If you already have a distance matrix, you do not need to recompute distances from raw feature vectors just to find nearest neighbors. The problem becomes an ordering task: for each row, ignore the point’s distance to itself and find the indices with the smallest remaining values.

Understand the Matrix Structure

A full distance matrix for n points is usually an n x n array where entry (i, j) is the distance between point i and point j.

Typical properties are:

• the matrix is square
• the diagonal is zero for self-distance
• symmetric metrics produce a symmetric matrix

Once you have that matrix, nearest-neighbor lookup is mostly sorting or partial sorting of each row.

Pure NumPy Approach

If you just want the nearest neighbors for every point, NumPy is often enough.

1import numpy as np
2
3def nearest_neighbors_from_distance_matrix(dist_matrix, k=1):
4    if dist_matrix.shape[0] != dist_matrix.shape[1]:
5        raise ValueError("distance matrix must be square")
6
7    matrix = dist_matrix.copy()
8    np.fill_diagonal(matrix, np.inf)
9
10    indices = np.argpartition(matrix, kth=k-1, axis=1)[:, :k]
11    row_indices = np.arange(matrix.shape[0])[:, None]
12    distances = matrix[row_indices, indices]
13
14    order = np.argsort(distances, axis=1)
15    indices = np.take_along_axis(indices, order, axis=1)
16    distances = np.take_along_axis(distances, order, axis=1)
17
18    return indices, distances
19
20
21d = np.array([
22    [0.0, 1.2, 3.5, 2.0],
23    [1.2, 0.0, 0.8, 4.1],
24    [3.5, 0.8, 0.0, 1.1],
25    [2.0, 4.1, 1.1, 0.0],
26])
27
28idx, dist = nearest_neighbors_from_distance_matrix(d, k=2)
29print(idx)
30print(dist)

This approach is straightforward and efficient when the distance matrix already fits in memory.

Use scikit-learn with a Precomputed Metric

If you want scikit-learn’s interface, use metric='precomputed':

1import numpy as np
2from sklearn.neighbors import NearestNeighbors
3
4d = np.array([
5    [0.0, 1.2, 3.5, 2.0],
6    [1.2, 0.0, 0.8, 4.1],
7    [3.5, 0.8, 0.0, 1.1],
8    [2.0, 4.1, 1.1, 0.0],
9])
10
11model = NearestNeighbors(n_neighbors=2, metric='precomputed')
12model.fit(d)
13
14distances, indices = model.kneighbors(d)
15print(indices)
16print(distances)

This is convenient when your workflow already uses scikit-learn and you want consistency with the rest of your modeling pipeline.

Exclude Self-Neighbors Intentionally

A common detail is whether the point itself should count as a neighbor. In most nearest-neighbor tasks, the answer is no, which is why the diagonal is treated specially.

In the NumPy example, the diagonal is replaced with infinity so self-distance is never selected. In library-based tools, check whether the returned neighbors include the query point itself and adjust n_neighbors accordingly.

Watch Out for Ties and Meaning of Distance

If several points have the same distance, the returned order among tied neighbors may not be stable unless you sort fully after selection.

Also, a distance matrix is only as meaningful as the metric used to build it. If the matrix mixes incomparable scales or contains approximate values, the nearest-neighbor results will reflect that.

Common Pitfalls

The most common mistake is forgetting to exclude the diagonal. If self-distance remains zero, each point becomes its own nearest neighbor.

Another issue is assuming every matrix is valid for every algorithm. Some tools expect a true metric or a symmetric matrix, while your matrix may only be a generic pairwise dissimilarity table.

People also use a full sort when they only need a few nearest neighbors. Partial sorting with argpartition is often cheaper.

Finally, if the matrix is very large, remember that an n x n distance matrix already uses O(n^2) memory. In that situation, computing neighbors from raw data may be more scalable than storing the whole matrix.

Summary

• With a precomputed distance matrix, nearest-neighbor search becomes a row-wise ordering problem.
• Use NumPy for direct control or scikit-learn with metric='precomputed' for a library workflow.
• Exclude self-distances so points do not select themselves.
• Use partial sorting when you only need the top k neighbors.
• Make sure the distance matrix meaning matches the assumptions of your downstream task.