mongdb ngt_NGT：用于高速近似最近邻居搜索的库

mongdb ngt

深度学习中使用近似最近邻（ ANN ）搜索，以在给定集合中与另一点最相似的点进行最佳猜测。 本文介绍了ANN搜索与传统搜索方法之间的区别，并介绍了NGT ，这是Yahoo!开发的性能最高的开源ANN库。 日本研究 。

最近邻居搜索高维数据

此外，向量不仅代表源数据的文本和图像特征，而且还代表产品，人类，组织等。 因此，您可以搜索相似的文档和图像，以及具有相似属性的产品，具有相似技能的人，具有相似特征的服装等。 例如， Yahoo！ 日本使用NGT提供了基于相似度的时尚商品搜索。

由于深度学习模型中的维数趋于增加，因此当搜索超过数百万个高维向量时，ANN搜索方法必不可少。 ANN搜索方法使您可以在高维空间中搜索指定查询向量的邻居。

有很多近邻搜索方法可供选择。 ANN Benchmarks评估了最著名的ANN搜索方法，包括Faiss（Facebook），Flann和Hnswlib。 根据此基准，NGT达到了顶级性能。

NGT算法

NGT索引结合了图形和树。 该结果具有非常好的搜索性能，其中图形的顶点表示可搜索的对象。 相邻的顶点通过边连接。

该动画显示了如何构造图。

在搜索过程中，可以找到指定查询的相邻顶点从图形下降。 密集连接的顶点使用户可以有效地浏览图形。

NGT提供了命令行工具，以及C，C ++和Python API。 本文重点介绍命令行工具和Python API。

在命令行工具中使用NGT

Linux安装

将NGT的最新版本下载为ZIP文件，并通过以下方式将其安装在Linux上：

unzip NGT-x.x.x.zip

cd NGT-x.x.x

mkdir build

cd build

cmake ..

make

make install

由于NGT库默认情况下安装在/ usr / local / lib（64）中，因此将目录添加到搜索路径：

export PATH = " $PATH :/opt/local/bin"

export LD_LIBRARY_PATH = " $LD_LIBRARY_PATH :/usr/local/lib"

样本数据集生成

在搜索大规模数据集之前，必须生成NGT数据集。 例如，从fastText网站 下载 fastText 数据集 ，然后使用以下命令将其转换为NGT注册格式：

curl -O https: // / fasttext / vectors-english / wiki-news-300d-1M-subword.vec.zip

unzip wiki-news-300d-1M-subword.vec.zip

tail -n + 2 wiki-news-300d-1M-subword.vec | cut -d " " -f 2 - > objects.ssv

Objects.ssv是具有100万个对象的注册文件。 文件中的一个对象被提取为查询：

head -10000 objects.ssv | tail -1 > query.ssv

指标建设

可以使用以下命令来构造ngt_index：

ngt create -d 300 -D c index objects.ssv

-d指定向量的维数。-D c表示使用余弦相似度。

近似最近邻居搜索

可以使用以下查询来查询ngt_index：

ngt search -n 10 index query.ssv

-n指定结果对象的数量。

搜索结果是：

Query No.1

Rank ID Distance

1 10000 0

2 21516 0.184495

3 60 0.240375

4 71865 0.241284

5 339589 0.267265

6 485158 0.280977

7 7961 0.283865

8 924513 0.286571

9 28870 0.286654

10 395274 0.290466

Query Time = 0.000972628 ( sec ) , 0.972628 ( msec )

Average Query Time = 0.000972628 ( sec ) , 0.972628 ( msec ) , ( 0.000972628 / 1 )

有关更多信息，请参见NGT命令行自述文件 。

从Python使用NGT

尽管NGT具有C和C ++ API，但NGT的ngtpy Python绑定是编程的最简单选择。

安装ngtpy

通过PyPI安装Python绑定（ngtpy），方法如下：

pip3 install ngt

样本数据集生成

使用以下代码从下载的样本数据集中为Python样本程序生成数据文件：

dataset_path = 'wiki-news-300d-1M-subword.vec'

with open ( dataset_path , 'r' ) as fi , open ( 'objects.tsv' , 'w' ) as fov ,

open ( 'words.tsv' , 'w' ) as fow:

n , dim = map ( int , fi. readline ( ) . split ( ) )

fov. write ( '{0}¥t{1}¥n' . format ( n , dim ) )

for line in fi:

tokens = line. rstrip ( ) . split ( ' ' )

fow. write ( tokens [ 0 ] + '¥n' )

fov. write ( '{0}¥n' . format ( '¥t' . join ( tokens [ 1 : ] ) ) )

指标建设

使用以下命令构造NGT索引：

import ngtpy

index_path = 'index'

with open ( 'objects.tsv' , 'r' ) as fin:

n , dim = map ( int , fin. readline ( ) . split ( ) )

ngtpy. create ( index_path , dim , distance_type = 'Cosine' ) # create an index

index = ngtpy. Index ( index_path ) # open the index

print ( 'inserting objects...' )

for line in fin:

object = list ( map ( float , line. rstrip ( ) . split ( '¥t' ) ) )

index. insert ( object ) # insert objects

print ( 'building objects...' )

index. build_index ( )

print ( 'saving the index...' )

index. save ( )

近似最近邻居搜索

这是ANN搜索程序的示例：

import ngtpy

print ( 'loading words...' )

with open ( 'words.tsv' , 'r' ) as fin:

words = list ( map ( lambda x: x. rstrip ( '¥n' ) , fin. readlines ( ) ) )

index = ngtpy. Index ( 'index' , zero_based_numbering = False ) # open index

query_id = 10000

query_object = index. get_object ( query_id ) # get the object for a query

result = index. search ( query_object ) # aproximate nearest neighbor search

print ( 'Query={}' . format ( words [ query_id - 1 ] ) )

print ( 'Rank¥tID¥tDistance¥tWord' )

for rank , object in enumerate ( result ) :

print ( '{}¥t{}¥t{:.6f}¥t{}' . format ( rank + 1 , object [ 0 ] , object [ 1 ] , words [ object [ 0 ] - 1 ] ) )

以下是搜索结果，与NGT命令行选项的结果相同：

loading words...

Query =Horse

Rank ID Distance Word

1 10000 0.000000 Horse

2 21516 0.184495 Horses

3 60 0.240375 Horseback

4 71865 0.241284 Horseman

5 339589 0.267265 Prancing

6 485158 0.280977 Horsefly

7 7961 0.283865 Dog

8 924513 0.286571 Horsing

9 28870 0.286654 Pony

10 395274 0.290466 Blood-Horse

有关更多信息，请参见ngtpy README 。

近似最近邻（ANN）原理是分析数据的重要功能。 学习如何在自己的项目中使用它，或了解正在分析的数据，是进行关联和解释信息的有效方法。 借助NGT，您可以根据需要使用ANN，也可以在其基础上添加自定义功能。

翻译自: /article/19/10/ngt-open-source-library

mongdb ngt

如果觉得《mongdb ngt_NGT：用于高速近似最近邻居搜索的库》对你有帮助，请点赞、收藏，并留下你的观点哦！