如何使用cdist或TensorFlow加速大规模点集的最近点匹配？

Great question—when dealing with hundreds of thousands of points, the naive cdist approach (which runs in O(n*m) time) is going to be painfully slow. Here are several much more efficient implementations that avoid relying on downsampling:

1. Use KD-Tree/Ball Tree (Exact Nearest Neighbor) #

For 2D data, KD-Tree is a perfect fit—it builds a spatial index in O(n log n) time, and each nearest neighbor query runs in O(log n) time, which is a massive improvement over brute-force. Scipy has a built-in implementation that's easy to use:

import pandas as pd
from scipy.spatial import KDTree

# Load your datasets
map_points = pd.read_csv("map_points.csv")  # 380k rows, columns like 'x', 'y'
path_points = pd.read_csv("path_points.csv")  # 350k rows, same columns

# Build KD-Tree from map points
kdtree = KDTree(map_points[['x', 'y']].values)

# Query nearest neighbor for each path point
# Returns (distance, index of nearest map point)
distances, nearest_indices = kdtree.query(path_points[['x', 'y']].values, k=1)

# Attach results to path points dataframe
path_points['nearest_map_x'] = map_points.loc[nearest_indices, 'x'].values
path_points['nearest_map_y'] = map_points.loc[nearest_indices, 'y'].values
path_points['distance_to_nearest'] = distances

Ball Tree is another solid option (better optimized for high-dimensional data, but works great here too)—just replace KDTree with BallTree from the same scipy.spatial module.

2. Approximate Nearest Neighbor (ANN) with FAISS #

If you need even faster performance and can tolerate tiny amounts of configurable approximation, FAISS (Facebook's library for efficient similarity search) is a game-changer. It's optimized for massive datasets and can leverage CPU/GPU acceleration:

import pandas as pd
import faiss
import numpy as np

# Convert data to numpy arrays (FAISS works best with float32)
map_np = map_points[['x', 'y']].values.astype('float32')
path_np = path_points[['x', 'y']].values.astype('float32')

# Build a flat L2 index (exact, but still faster than cdist; use IVF for larger data)
index = faiss.IndexFlatL2(2)
index.add(map_np)

# Query nearest neighbors (k=1)
distances, nearest_indices = index.search(path_np, 1)

# Flatten results (since search returns 2D arrays)
path_points['distance_to_nearest'] = distances.flatten()
path_points['nearest_map_x'] = map_points.loc[nearest_indices.flatten(), 'x'].values
path_points['nearest_map_y'] = map_points.loc[nearest_indices.flatten(), 'y'].values

For even more speed with ultra-large datasets, use an inverted file (IVF) index (e.g., faiss.IndexIVFFlat). You'll need to train it on a sample of your map points first, but it cuts query time drastically.

3. Grid-Based Spatial Partitioning (No Extra Libraries) #

If you don't want to install additional libraries, you can split your map points into a grid. For each path point, only compute distances to map points in the same grid cell (and adjacent cells, to avoid missing closer points just outside the cell):

import pandas as pd
import numpy as np

# Define grid bin size (adjust based on your data's scale)
bin_size = 1.0  # Example: 1 unit in your coordinate system

# Assign grid cell IDs to map points
map_points['x_bin'] = pd.cut(map_points['x'], bins=np.arange(map_points['x'].min(), map_points['x'].max()+bin_size, bin_size))
map_points['y_bin'] = pd.cut(map_points['y'], bins=np.arange(map_points['y'].min(), map_points['y'].max()+bin_size, bin_size))
map_groups = map_points.groupby(['x_bin', 'y_bin'])

def find_nearest_in_grid(row):
    # Get the current path point's grid cell
    x_bin = pd.cut([row['x']], bins=map_groups.groups.keys().levels[0])[0]
    y_bin = pd.cut([row['y']], bins=map_groups.groups.keys().levels[1])[0]
    
    # Check current cell and adjacent cells
    nearby_bins = [
        (x_bin, y_bin),
        (x_bin.left - bin_size, y_bin), (x_bin.right, y_bin),
        (x_bin, y_bin.left - bin_size), (x_bin, y_bin.right),
        (x_bin.left - bin_size, y_bin.left - bin_size), (x_bin.right, y_bin.right),
        (x_bin.left - bin_size, y_bin.right), (x_bin.right, y_bin.left - bin_size)
    ]
    
    # Collect all nearby map points
    nearby_points = []
    for bin_pair in nearby_bins:
        if bin_pair in map_groups.groups:
            nearby_points.extend(map_groups.get_group(bin_pair)[['x', 'y']].values.tolist())
    
    if not nearby_points:
        # Fallback to full dataset if no nearby points (edge cases)
        nearby_points = map_points[['x', 'y']].values.tolist()
    
    # Compute distances and find nearest
    distances = np.linalg.norm(np.array(nearby_points) - np.array([row['x'], row['y']]), axis=1)
    nearest_idx = np.argmin(distances)
    nearest_point = nearby_points[nearest_idx]
    
    return pd.Series([nearest_point[0], nearest_point[1], distances[nearest_idx]])

# Apply to path points
path_points[['nearest_map_x', 'nearest_map_y', 'distance_to_nearest']] = path_points.apply(find_nearest_in_grid, axis=1)

This reduces the number of distance calculations per path point significantly, especially if your points are evenly distributed.

4. GPU-Accelerated Exact Search #

If you have access to an NVIDIA GPU, libraries like cuML (RAPIDS) or cuPy can port the KD-Tree/brute-force search to the GPU, handling large datasets in a fraction of the CPU time:

import cudf
from cuml.neighbors import NearestNeighbors

# Load data into GPU DataFrames
map_gdf = cudf.read_csv("map_points.csv")
path_gdf = cudf.read_csv("path_points.csv")

# Build NearestNeighbors model
nn = NearestNeighbors(n_neighbors=1)
nn.fit(map_gdf[['x', 'y']])

# Query
distances, nearest_indices = nn.kneighbors(path_gdf[['x', 'y']])

# Merge results back to path_gdf
path_gdf['nearest_map_x'] = map_gdf.loc[nearest_indices.flatten(), 'x'].values
path_gdf['nearest_map_y'] = map_gdf.loc[nearest_indices.flatten(), 'y'].values
path_gdf['distance_to_nearest'] = distances.flatten()

# Convert back to pandas if needed
path_points = path_gdf.to_pandas()

Quick Comparison of Methods #

Pick the one that fits your hardware, accuracy needs, and library constraints!

内容的提问来源于stack exchange，提问作者Kyle