Skip to main content

Nearest neighbor search on Earth's surface with a GPU

Project description

Vincenty nearest neighbor search using CUDA

Nearest neighbor search algorithm on Earth's surface that runs on a GPU and uses Vincenty's formula


Nearest Neighbour Search is the key component of location data analysis:

  • Nearest Neighbour Index is based on measuring distances between points
  • Both global pattern analysis algorithms (Global Moran’s I, Getis-Ord General G), as well as local pattern analysis algorithms (Anselin Local Moran's I, Getis Ord GI *) with the k-nn approach to define neighbours are based on measuring distances between points

Using Vincenty’s formula allows performing location analysis on any location using geographic coordinates.

Presentation slides


  • CUDA-enabled GPU with compute capability 2.0 or above with an up-to-data Nvidia driver.
  • CUDA toolkit


pip install vincenty-cuda-nns

Usage example

import geopandas as gpd  # here just for example
import numpy as np
from vincenty_cuda_nns import CudaTree

df = gpd.read_file('points.geojson')

# data is array of points like [longitude, latitude]
points = np.stack(df['geometry']).astype(np.float32)

# build tree for the data
cuda_tree = CudaTree(points, leaf_size=4)

# query over the tree for tree nearest neighbors (+1 for itself)
distances, indices = cuda_tree.query(points, n_neighbors=4)

# you can also find distances from andother dataset
from_points = (np.random.random((100, 2)) * 180) - 90

distances, indices = cuda_tree.query(from_points)

Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

vincenty-cuda-nns-0.2.2.tar.gz (5.5 kB view hashes)

Uploaded source

Built Distribution

vincenty_cuda_nns-0.2.2-py3-none-any.whl (19.0 kB view hashes)

Uploaded py3

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page