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

Application

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

Requirements

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

Installation

pip install vincenty-cuda-nns

Usage example

import geopandas as gpd
from vincenty_cuda_nns import CudaTree

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

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

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

# query over the tree for nearest neighbor (including itself)
distances, indices = cuda_tree.query(n_neighbors=2)

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.1.5
Filename, size File type Python version Upload date Hashes
Filename, size vincenty_cuda_nns-0.1.5-py3-none-any.whl (18.2 kB) File type Wheel Python version py3 Upload date Hashes View hashes
Filename, size vincenty-cuda-nns-0.1.5.tar.gz (4.7 kB) File type Source Python version None Upload date Hashes View hashes

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN SignalFx SignalFx Supporter DigiCert DigiCert EV certificate StatusPage StatusPage Status page