Hora

[主页] [文档] [示例]

Hora搜索无处不在！

Hora是一个 近似最近邻搜索算法 (维基百科) 库。我们使用Rust🦀进行所有代码实现，以确保可靠性、高级抽象和与C++相当的高速度。

Hora，日语中的“ほら”，发音类似于 [hōlə]，意为 哇，你看到了吗？ 或 看那里！ 这个名字灵感来源于一首著名的日本歌曲 「小さな恋のうた」。

演示

👩 人脸匹配 [在线演示]，试试看！

🍷 梦想葡萄酒评论搜索 [在线演示]，试试看！

功能

• 高性能 ⚡️

  • SIMD加速 (packed_simd)
  • 稳定的算法实现
  • 多线程设计

• 支持多种语言 ☄️

  • Python
  • Javascript
  • Java
  • Go (WIP)
  • Ruby (WIP)
  • Swift (WIP)
  • R (WIP)
  • Julia (WIP)
  • 也可用作服务

• 支持多种索引 🚀

  • 层次导航小世界图索引 (HNSWIndex) (详情)
  • 卫星系统图 (SSGIndex) (详情)
  • 产品量化倒排索引(PQIVFIndex) (详情)
  • 随机投影树(RPTIndex) (LSH, WIP)
  • 暴力搜索(BruteForceIndex) (使用SIMD的简单实现)

• 便携 💼

  • 支持 WebAssembly
  • 支持 Windows，Linux 和 OS X
  • 支持 IOS 和 Android (WIP)
  • 支持 no_std (WIP，部分)
  • 无重量级依赖，如 BLAS

• 可靠性 🔒

  • Rust 编译器确保所有代码的安全性
  • 所有语言库（如 Python's）的内存由 Rust 管理
  • 广泛的测试覆盖

• 支持多种距离 🧮

  • 点积距离
    • 
  • 欧几里得距离
    • 
  • 曼哈顿距离
    • 
  • 余弦相似度
    • 

• 高效 ⭐

  • 文档齐全
  • 优雅、简单且易于学习的API

安装

Rust

在 Cargo.toml

[dependencies]
hora = "0.1.1"

Python

$ pip install horapy

Javascript(WebAssembly)

$ npm i horajs

从源码构建

$ git clone https://github.com/hora-search/hora
$ cargo build

基准测试

由 aws t2.medium (CPU: Intel(R) Xeon(R) CPU E5-2686 v4 @ 2.30GHz) 更多信息

示例

Rust 示例 [更多信息]

use hora::core::ann_index::ANNIndex;
use rand::{thread_rng, Rng};
use rand_distr::{Distribution, Normal};

pub fn demo() {
    let n = 1000;
    let dimension = 64;

    // make sample points
    let mut samples = Vec::with_capacity(n);
    let normal = Normal::new(0.0, 10.0).unwrap();
    for _i in 0..n {
        let mut sample = Vec::with_capacity(dimension);
        for _j in 0..dimension {
            sample.push(normal.sample(&mut rand::thread_rng()));
        }
        samples.push(sample);
    }

    // init index
    let mut index = hora::index::hnsw_idx::HNSWIndex::<f32, usize>::new(
        dimension,
        &hora::index::hnsw_params::HNSWParams::<f32>::default(),
    );
    for (i, sample) in samples.iter().enumerate().take(n) {
        // add point
        index.add(sample, i).unwrap();
    }
    index.build(hora::core::metrics::Metric::Euclidean).unwrap();

    let mut rng = thread_rng();
    let target: usize = rng.gen_range(0..n);
    // 523 has neighbors: [523, 762, 364, 268, 561, 231, 380, 817, 331, 246]
    println!(
        "{:?} has neighbors: {:?}",
        target,
        index.search(&samples[target], 10) // search for k nearest neighbors
    );
}

Python 示例 [更多信息]

import numpy as np
from horapy import HNSWIndex

dimension = 50
n = 1000

# init index instance
index = HNSWIndex(dimension, "usize")

samples = np.float32(np.random.rand(n, dimension))
for i in range(0, len(samples)):
    # add node
    index.add(np.float32(samples[i]), i)

index.build("euclidean")  # build index

target = np.random.randint(0, n)
# 410 in Hora ANNIndex <HNSWIndexUsize> (dimension: 50, dtype: usize, max_item: 1000000, n_neigh: 32, n_neigh0: 64, ef_build: 20, ef_search: 500, has_deletion: False)
# has neighbors: [410, 736, 65, 36, 631, 83, 111, 254, 990, 161]
print("{} in {} \nhas neighbors: {}".format(
    target, index, index.search(samples[target], 10)))  # search

JavaScript 示例 [更多信息]

import * as horajs from "horajs";

const demo = () => {
    const dimension = 50;
    var bf_idx = horajs.BruteForceIndexUsize.new(dimension);
    // var hnsw_idx = horajs.HNSWIndexUsize.new(dimension, 1000000, 32, 64, 20, 500, 16, false);
    for (var i = 0; i < 1000; i++) {
        var feature = [];
        for (var j = 0; j < dimension; j++) {
            feature.push(Math.random());
        }
        bf_idx.add(feature, i); // add point 
    }
    bf_idx.build("euclidean"); // build index
    var feature = [];
    for (var j = 0; j < dimension; j++) {
        feature.push(Math.random());
    }
    console.log("bf result", bf_idx.search(feature, 10)); //bf result Uint32Array(10) [704, 113, 358, 835, 408, 379, 117, 414, 808, 826]
}

(async () => {
    await horajs.default();
    await horajs.init_env();
    demo();
})();

Java 示例 [更多信息]

public void demo() {
    final int dimension = 2;
    final float variance = 2.0f;
    Random fRandom = new Random();

    BruteForceIndex bruteforce_idx = new BruteForceIndex(dimension); // init index instance

    List<float[]> tmp = new ArrayList<>();
    for (int i = 0; i < 5; i++) {
        for (int p = 0; p < 10; p++) {
            float[] features = new float[dimension];
            for (int j = 0; j < dimension; j++) {
                features[j] = getGaussian(fRandom, (float) (i * 10), variance);
            }
            bruteforce_idx.add("bf", features, i * 10 + p); // add point
            tmp.add(features);
          }
    }
    bruteforce_idx.build("bf", "euclidean"); // build index

    int search_index = fRandom.nextInt(tmp.size());
    // nearest neighbor search
    int[] result = bruteforce_idx.search("bf", 10, tmp.get(search_index));
    // [main] INFO com.hora.app.ANNIndexTest  - demo bruteforce_idx[7, 8, 0, 5, 3, 9, 1, 6, 4, 2]
    log.info("demo bruteforce_idx" + Arrays.toString(result));
}

private static float getGaussian(Random fRandom, float aMean, float variance) {
    float r = (float) fRandom.nextGaussian();
    return aMean + r * variance;
}

路线图

• 完整的测试覆盖
• 实现 EFANNA 算法以实现更快的KNN图构建
• Swift 支持和 iOS/macOS 部署示例
• 支持 R
• 支持 mmap

相关项目和比较

• Faiss，Annoy，ScaNN

  • Hora 的实现受到这些库的强烈启发。
  • Faiss 更侧重于 GPU 环境，而 Hora 比Faiss更轻量（无重量级依赖）。
  • Hora 预期将支持更多语言，且与性能相关的一切都将由Rust🦀实现。
  • Annoy 只支持 LSH (随机投影) 算法。
  • ScaNN 和 Faiss 更不友好（例如，缺乏文档）。
  • Hora 是 完全使用 Rust 🦀。

• Milvus、Vald、Jina AI

  • Milvus 和 Vald 也支持多种语言，但作为服务而非库使用
  • Milvus 建立在诸如 Faiss 的库之上，而 Hora 是一个实现了所有算法的库

git clone https://github.com/hora-search/hora

cargo build

cargo test --lib

cd examples
cargo run