Skip to main content

MinimalKNN: minimal package to construct k-NN Graph

Project description

A Minimal k-Nearest Neighbor Graph Construction Library

License: MIT


This package will provide a function to construct an approximated k-Nearest Neighbor graph from a list of three dimensional points. The graph construction algorithm is based on NN-descent presented in Dong, Moses, & Li (2011)[^DML2011]. The Euclidean and Manhattan metrics are implemented in the current version, while only the Euclidean one is available in Python. The algorithm efficiently constructs an approximated k-Nearest Neighbor graph. This provides a portable C++11 header and a Python interface.


The library is written in C++11 and do not depends on any library outside of the STL. The Python interface is depends on NumPy, and functional test procedures depend on Matplotlib. The library is developed on g++ version 5.4 installed in Linux Mint 18.1 (serena). The Python interface is developed on Python 3.7.1 and Numpy 1.18.1.


[^DML2011]: Wei Dong, Charikar Moses, & Kai Li, WWW'11: Proceedings of the 20th international conference on World wide web (2011), 577--586 (doi: 10.1145/1963405.1963487)

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

minimalKNN-0.9.tar.gz (66.2 kB view hashes)

Uploaded source

Built Distribution

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Huawei Huawei PSF Sponsor Microsoft Microsoft PSF Sponsor NVIDIA NVIDIA PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page