loveheaven / nndescent Public

forked from TatsuyaShirakawa/nndescent

Notifications You must be signed in to change notification settings
Fork 0
Star 1

Implementation of Efficient K-NN Graph Construction Algorithm NN-Descent in C++

1 star 4 forks Branches Tags Activity

Notifications

Name		Name	Last commit message	Last commit date
Latest commit History 4 Commits
example		example
include		include
.gitignore		.gitignore
CMakeLists.txt		CMakeLists.txt
LICENSE		LICENSE
README.md		README.md
main.cpp		main.cpp

Repository files navigation

nndescent

This code implements following paper:

Wei Dong et al., "Efficient K-Nearest Neighbor Graph Construction for Generic Similarity Measures", WWW11

Some additional join algorithms are added:

join the center node to its nbd nodes
random join (join random nodes)
randomly break the tie

Build Requirements

C++ compiler (needed support for C++11 or later)
Python3 with matplotlib

Examples

I use main.cpp to generate 100 points and draw images for each step:

image for initial 100 points
image for initial graph with random neighbours
image after iteration1 by nndescent
image after iteration2 by nndescent
image after iteration3 by nndescent
image after iteration4 by nndescent
image after iteration5 by nndescent
image after iteration6 by nndescent
image after iteration7 by nndescent

About

Implementation of Efficient K-NN Graph Construction Algorithm NN-Descent in C++

Report repository

Releases

No releases published

Packages

No packages published

Languages

C++ 99.5%
CMake 0.5%