新开源项目 Hora, 一个基于 Rust 🦀 的高速近似最近邻搜索 (ANN)算法库 🚀 ,欢迎围观与参与 (≧∇≦)ノ

2021-08-07 16:55:46 +08:00
 aljun

Hora 是一个近似最近邻搜索算法 (wiki) 库

Hora 完全基于 Rust🦀 实现,事实证明,Rust 确实非常非常快,完全可以媲美 C++ ,且Hora使用 SIMD进行了加速,速度非常快⚡️⚡️⚡️,具体速度可以参考下面的 benchmark.

Hora ,日语为 「ほら」,读法像 [hōlə] ,意思是 Wow, You see! , Look at that! 。 这个名字的灵感来自日本著名歌曲 「小さな恋のうた」

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

主页: https://horasearch.com/

Python 库: https://github.com/hora-search/horapy

Javascript 库: https://github.com/hora-search/hora-wasm

Hora 定位上是Rust实现的 ANN 算法库,希望能基于 Rust 本身的优势,能够提供多个安全的语言库,且能部署在任何地方。目前已经能在Linux, macOSWindows以及WebAssembly部署,未来还会支持AndroidIOS以及 嵌入式设备


Demo

这是 Hora 的在线演示(可以在这里找到它,强烈推荐试试速度!! https://horasearch.com/)

👩 Face-Match [online demo], have a try!

🍷 Dream wine comments search [online demo], have a try!

benchmark

Hora 非常快,bench (与 Faiss 和 Annoy 相比)

Usage

安装极为简单: Rust

[dependencies]
hora = "0.1.1"

Python

$ pip install horapy

Javascript (WebAssembly)

$ npm i horajs

Building from source

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

使用上 API 也非常简单:

Python example [more info]

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

我们很欢迎任何参与,欢迎任何贡献,包括文档和测试。 我们使用 GitHub 问题来跟踪 Issue 和 bug,你可以在 github 上进行 Pull Requests 、Issue

最后如果觉得这个项目做的还不错,或者比较感兴趣,或者你们想用的,欢迎在 github 上 star 或者给我们提 issue

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

Python 库: https://github.com/hora-search/horapy

Javascript 库: https://github.com/hora-search/hora-wasm

3017 次点击
所在节点    程序员
30 条回复
3dwelcome
2021-08-07 17:13:02 +08:00
强啊,有了 wasm 后,JS 就是羞涩的少女,感觉任何语言都能插入到 JS 里。

好奇以后 rust 开发 web 网页效果会如何,运行速度肯定很快。
aljun
2021-08-07 17:18:01 +08:00
@3dwelcome 我还是踩了不少坑的,最典型的就是多线程支持了,毕竟是个算法库,速度还是比较重要的,但是 wasm 以及 rust-wasm 的多线程支持明显还是不成熟的

不过 wasm 比 js 快还是应该的(虽然 V8 快到不行),主要还是这块是个方向,可以借着方向发展,一起快
aljun
2021-08-07 17:34:47 +08:00
貌似在 v2 不是很叫座🤔 ?
jdhao
2021-08-07 17:37:32 +08:00
用到是哪个 ANN 算法,PQ 还是 HNSW?
aljun
2021-08-07 17:45:00 +08:00
@jdhao 实现了多个,目前的:

* Hierarchical Navigable Small World Graph Index (HNSWIndex) (details)
* Satellite System Graph (SSGIndex) (details)
* Product Quantization Inverted File(PQIVFIndex) (details)
* Random Projection Tree(RPTIndex) (LSH, WIP)
* BruteForce (BruteForceIndex) (naive implementation with SIMD)
aljun
2021-08-07 17:45:51 +08:00
@aljun 复制的 readme 。。。详情可以看看 github readme 😂
jdhao
2021-08-07 17:46:07 +08:00
@aljun 都是一个人搞定的吗,牛逼
aljun
2021-08-07 17:48:30 +08:00
@jdhao 算法是我和另一个朋友一起搞的,感兴趣的话可以一起实现,还有很多算法未实现,目前是 **0.1.0** 挺早期的
jdhao
2021-08-07 17:52:32 +08:00
目前定位是怎么样的呢,像 FAISS 一样准备长期维护,还是说只是尝试实现一下,个人兴趣。

可以和 [ANN benchmark]( https://github.com/erikbern/ann-benchmarks) 里面其他算法也对比一下
aljun
2021-08-07 17:55:13 +08:00
@jdhao
在 github readme 我应该有写和其他项目的 comparison,其实主要是这么几点不同,我们可能希望未来能部署在各个地方,同时提供多个语言包,尽可能充分压榨 Rust 的潜力,Faiss 现在越来越偏向 GPU 了,看 pr (同时我的文档应该比 Faiss 强 hhh

另外 ANN bench 是有跑的,上面不就有跑出来的 bench 图嘛,不过目前 search 速度是和 Faiss 无差,但 build 速度还是比 Faiss 的实现慢了一点点,之后会优化,感兴趣一起来搞呀 (≧∇≦)ノ
jdhao
2021-08-07 18:03:06 +08:00
@aljun ANN benchmarks 里面有个 NGT,速度似乎挺快的,没看到和 NGT 的对比。我主要是平时会使用到 ANN 搜索库,没有开发能力 😄,目前用到的是 vearch (底层还是 FAISS)。
aljun
2021-08-07 18:59:28 +08:00
@aljun - -
aljun
2021-08-07 20:34:27 +08:00
没有人关注么😢
aljun
2021-08-07 22:49:55 +08:00
@aljun 😢
messense
2021-08-08 01:05:53 +08:00
👍
LeeReamond
2021-08-08 04:31:43 +08:00
近期最近搜索应该怎么理解?是如同 demo 中只能对图像进行搜索?还是一种普遍适用的算法?
aljun
2021-08-08 11:21:35 +08:00
@messense 感激🙏
aljun
2021-08-08 11:26:55 +08:00
@LeeReamond 是一种普遍算法,我的文档应该有写清楚这是个什么问题 ( https://horasearch.com/doc/#introduction)

拿图像检索举个例子,一个图像可以提供模型输出一个定长(dimension)的 embedding,我们可以通过 embedding 的距离(比如 euclidean distance )找到距离最小的 k 个 embedding,对应的对象也就最相近(比如图片最相近),但这样最基本你要 O( n * d)暴力穷举一遍,当你 N 和 dimension 都比较大的时候,这个就很慢了,可以看看上图,上了 SIMD 的穷举( bruteforce )速度大概要慢其他算法千倍
aljun
2021-08-08 12:07:08 +08:00
@LeeReamond 可以体验下我 homepage 的 demo,是用 actix-web 搭的应用,底层跑了这个算法,反应应该是毫秒级的,其他的体感相关的耗时就只有 nginx 的静态文件 serving 速度了

我这边体感速度应该是非常快的,可以试试

http://horasearch.com/
aljun
2021-08-08 12:08:02 +08:00
@messense 说起来,maturin 我在发布 pypi 时还遇到了一些 bug,我这两天提个 patch😂😂

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/794292

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX