Skip to main content
Join the official 2020 Python Developers SurveyStart the survey!

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.

Files for vincenty-cuda-nns, version 0.2.2
Filename, size File type Python version Upload date Hashes
Filename, size vincenty_cuda_nns-0.2.2-py3-none-any.whl (19.0 kB) File type Wheel Python version py3 Upload date Hashes View
Filename, size vincenty-cuda-nns-0.2.2.tar.gz (5.5 kB) File type Source Python version None Upload date Hashes View

Supported by

Pingdom Pingdom Monitoring Google Google Object Storage and Download Analytics Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN DigiCert DigiCert EV certificate StatusPage StatusPage Status page