百科.dev
全部条目在线工具AI 编程趋势榜开源项目技术资讯提交条目
登录
< 返回工具列表
K

kgraph

> 编程语言
开源

一个用于 k 最近邻搜索的库

387 stars0 点赞0 次浏览
访问官网GitHub

工具介绍

一个用于 k 最近邻搜索的库

KGraph: A Library for Approximate Nearest Neighbor Search

Introduction

KGraph is a library for k-nearest neighbor (k-NN) graph construction and online k-NN search using a k-NN Graph as index. KGraph implements heuristic algorithms that are extremely generic and fast:

  • KGraph works on abstract objects. The only assumption it makes is that a similarity score can be computed on any pair of objects, with a user-provided function.
  • KGraph is among the fastest of libraries for k-NN search according to recent benchmark.

For best generality, the C++ API should be used. A python wrapper is provided under the module name kgraph, which supports Euclidean and Angular distances on rows of NumPy matrices.

!!!pykgraph has been renamed to kgraph.

Building and Installation

KGraph depends on a recent version of GCC with C++11 support, cmake and the Boost library. The package can be built and installed with

bash
cmake -DCMAKE_BUILD_TYPE=release .
make
sudo make install

A Makefile.plain is also provided in case cmake is not available.

The Python API can be installed with

bash
python setup.py install

Python Quick Start

python
from numpy import random
import kgraph

dataset = random.rand(1000000, 16)
query = random.rand(1000, 16)

index = kgraph.KGraph(dataset, 'euclidean')  # another option is 'angular'
index.build(reverse=-1)                        #
index.save("index_file");
# load with index.load("index_file");

knn = index.search(query, K=10)                       # this uses all CPU threads
knn = index.search(query, K=10, threads=1)            # one thread, slower
knn = index.search(query, K=1000, P=100)              # search for 1000-nn, no need to recompute index.

Both index.build and index.search supports a number of optional keywords arguments to fine tune the performance. The default values should work reasonably well for many datasets. One exception is that reverse=-1 should be added if the purpose of building index is to speedup search, which is the typical case, rather than to obtain the k-NN graph itself.

Two precautions should be taken:

  • Although matrices of both float32 and float64 are supported, the latter is not optimized. It is recommened that matrices be converted to float32 before being passed into kgraph.
  • The dimension (columns of matrices) should be a multiple of 4. If not, zeros must be padded.

For performance considerations, the Python API does not support user-defined similarity function, as the callback function is invoked in such a high frequency that, if written in Python, speedup will inevitably be brought down. For the full generality, the C++ API should be used.

C++ Quick Start

The KGraph C++ API is based on two central concepts: the index oracle and the search oracle. (Oracle is a fancy way of calling a user-defined callback function that behaves like a black box.) KGraph works solely with object IDs from 0 to N-1, and relies on the oracles to map the IDs to actual data objects and to compute the similarity. To use KGraph, the user has to extend the following two abstract classes

…

Note that the search API does not directly imply nearest neighbor search. Rather it is a generic API for minimizing a function on top of a graph, and finds the K nodes where the function assumes minimal values.

More Documentation

Oracles for Common Tasks

KGraph provides a number of efficient oracle implementation for common tasks.

Parameter Tuning

Doxygen Documentation

Issues· 0 开放

查看全部 Issues在 GitHub 打开

暂无开放 Issues,或尚未同步最近议题。

> 标签

C++

暂无评论,来聊聊你的看法吧

> 工具信息

发布日期2026年8月1日
最后更新2026年9月17日
分类编程语言
定价开源

> 相关工具

T
TypeScript
JavaScript 的超集,为前端与全栈提供静态类型
P
Python
通用编程语言,广泛用于 Web、数据与 AI
G
Go
Google 推出的简洁高效系统语言