N2: Approximate Nearest Neighbor

Lightweight approximate Nearest Neighbor algorithm library written in C++ (with Python/Go bindings).

N2 stands for two N's, which comes from 'Approximate Nearest Neighbor Algorithm'.

Why N2 Was Made

Before N2, there has been other great approximate nearest neighbor libraries such as Annoy and NMSLIB. However, each of them had different strengths and weaknesses regarding usability, performance, and etc. So, N2 has been developed aiming to bring the strengths of existing aKNN libraries and supplement their weaknesses.

Features

  • Lightweight library which runs fast with large datasets.

  • Good performance in terms of index build time, search speed, and memory usage.

  • Supports multi-core CPUs for index building.

  • Supports a mmap feature by default to efficiently process large index files.

  • Supports Python/Go bindings.

Supported Distance Metrics

Metric

Definition

\(d(\vec{p}, \vec{q})\)

"angular"

\(1 - \cos{\theta}\)

\(1 - \frac{\vec{p}\cdot\vec{q}} {||\vec{p}||\ ||\vec{q}||} = 1 - \frac{\sum_{i} {p_i q_i}} {\sqrt{\sum_{i} {p_i^2}} \sqrt{\sum_{i} {q_i^2}}}\)

"L2"

squared L2

\(\sum_{i} {(p_i - q_i)^2}\)

"dot"

dot product

\(\vec{p}\cdot\vec{q} = \sum_{i} {p_i q_i}\)

N2 supports three distance metrics. For "angular" and "L2", d (distance) is defined such that the closer the vectors are, the smaller d is. However for "dot", d is defined such that the closer the vectors are, the larger d is. You may be wondering why we defined and implemented "dot" metric as plain dot product and not as (1 - dot product). The rationale for this decision was to allow users to directly interpret the d value returned from Hnsw search function as a dot product value.

Getting Started

Benchmark

References

License

This software is licensed under the Apache 2 license, quoted below.

Copyright 2017 Kakao Corp. http://www.kakaocorp.com

Licensed under the Apache License, Version 2.0 (the “License”); you may not use this project 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.