NGT: Nearest Neighbor Search with Neighborhood Graph and Tree

栏目: IT技术 · 发布时间: 3年前

内容简介:Neighborhood Graph and Tree for Indexing High-dimensional Data

NGT: Nearest Neighbor Search with Neighborhood Graph and Tree

Neighborhood Graph and Tree for Indexing High-dimensional Data

Home / Installation / Command / License / Publications / About Us / 日本語

NGTprovides commands and a library for performing high-speed approximate nearest neighbor searches against a large volume of data (several million to several 10 million items of data) in high dimensional vector data space (several ten to several thousand dimensions).

News

  • 11/04/2019 NGT tutorial has been released.
  • 06/26/2019 Jaccard distance is available. (v1.7.6)
  • 06/10/2019 PyPI NGT package v1.7.5 is now available.
  • 01/17/2019 Python NGT can be installed via pip from PyPI. (v1.5.1)
  • 12/14/2018 NGTQ (NGT with Quantization) is now available. (v1.5.0)
  • 08/08/2018 ONNG is now available. (v1.4.0)

Key Features

  • Supported operating systems: Linux and macOS
  • Object additional registration and removal are available.
  • Objects beyond the memory size can be handled using the shared memory (memory mapped file) option .
  • Supported distance functions: L1, L2, Cosine similarity, Angular, Hamming, and Jaccard
  • Data Types: 4 byte floating point number and 1 byte unsigned integer
  • Supported languages: Python , Ruby , Go , C, and C++
  • Distributed servers: ngtd and vald
  • NGTQ can handle billions of objects.

Documents

Installation

Downloads

Pre-Built

On macOS

$ brew install ngt

Build

On Linux

$ unzip NGT-x.x.x.zip
  $ cd NGT-x.x.x
  $ mkdir build
  $ cd build
  $ cmake ..
  $ make
  $ make install
  $ ldconfig /usr/local/lib

On macOS using homebrew

$ /usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"
  $ brew install cmake
  $ brew install gcc@9
  $ export CXX=/usr/local/bin/g++-9
  $ export CC=/usr/local/bin/gcc-9
  $ unzip NGT-x.x.x.zip
  $ cd NGT-x.x.x
  $ mkdir build
  $ cd build
  $ cmake ..
  $ make
  $ make install

Shared memory use

The index can be placed in shared memory with memory mapped files. Using shared memory can reduce the amount of memory needed when multiple processes are using the same index. In addition, it can not only handle an index with a large number of objects that cannot be loaded into memory, but also reduce time to open it. Since changes become necessary at build time, please add the following parameter when executing "cmake" in order to use shared memory.

$ cmake -DNGT_SHARED_MEMORY_ALLOCATOR=ON ..

Note: Since there is no lock function, the index should be used only for reference when multiple processes are using the same index.

Large-scale data use

When you insert more than about 5 million objects, please add the following parameter to improve the search time.

$ cmake -DNGT_LARGE_DATASET=ON ..

Utilities

Supported Programming Languages

Benchmark Results

The followings are the results of ann benchmarks on an AWS c5.4xlarge instance for NGT v1.7.5.

glove-100-angular

NGT: Nearest Neighbor Search with Neighborhood Graph and Tree

gist-960-euclidean

NGT: Nearest Neighbor Search with Neighborhood Graph and Tree

fashion-mnist-784-euclidean

NGT: Nearest Neighbor Search with Neighborhood Graph and Tree

nytimes-256-angular

NGT: Nearest Neighbor Search with Neighborhood Graph and Tree

sift-128-euclidean

NGT: Nearest Neighbor Search with Neighborhood Graph and Tree

License

Copyright (C) 2015-2020 Yahoo Japan Corporation

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this software except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Yahoo Japan Corporation has acquired several patents on the technologies utilized in this software. However, the patent rights shall not be exercised under Apache License Version 2.0, only when the patented techniques are used with this software.

Contributor License Agreement

This project requires contributors to accept the terms in the Contributor License Agreement (CLA) .

Please note that contributors to the NGT repository on GitHub ( https://github.com/yahoojapan/NGT ) shall be deemed to have accepted the CLA without individual written agreements.

Contact Person

masajiro

Publications

ONNG

  • Iwasaki, M., Miyazaki, D.: Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity. arXiv:1810.07355 [cs] (2018). ( pdf )

PANNG

  • Iwasaki, M.: Pruned Bi-directed K-nearest Neighbor Graph for Proximity Search. Proc. of SISAP2016 (2016) 20-33. ( pdf )
  • Sugawara, K., Kobayashi, H. and Iwasaki, M.: On Approximately Searching for Similar Word Embeddings. Proc. of ACL2016 (2016) 2265-2275. ( pdf )

ANNGT

  • Iwasaki, M.: Applying a Graph-Structured Index to Product Image Search (in Japanese). IIEEJ Journal 42(5) (2013) 633-641. ( pdf )
  • Iwasaki, M.: Proximity search using approximate k nearest neighbor graph with a tree structured index (in Japanese). IPSJ Journal 52(2) (2011) 817-828. ( pdf )

ANNG

  • Iwasaki, M.: Proximity search in metric spaces using approximate k nearest neighbor graph (in Japanese). IPSJ Trans. on Database 3(1) (2010) 18-28. ( pdf )

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

百度SEM竞价推广

百度SEM竞价推广

马明泽 / 电子工业出版社 / 2017-5 / 59

竞价推广已成为企业昀主要的网络营销方式,《百度SEM竞价推广:策略、方法、技巧与实战》以百度竞价推广为基础,全面阐述了整个竞价推广过程中的重要环节,涉及大量账户操作实战技巧,以及解决各类难点的方法,其中包括搜索引擎营销基础、百度搜索推广介绍、账户结构搭建技巧、关键词与创意的使用技巧、质量度优化与提升、账户工具的使用、百度推广客户端的使用、企业搜索推广方案制作、百度网盟推广、着陆页分析、效果优化与数......一起来看看 《百度SEM竞价推广》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

URL 编码/解码
URL 编码/解码

URL 编码/解码

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器