V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
aljun
V2EX  ›  程序员

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

  •  4
     
  •   aljun · 2021-08-07 16:55:46 +08:00 · 2997 次点击
    这是一个创建于 1205 天前的主题,其中的信息可能已经有所发展或是发生改变。

    brand

    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! demo3

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

    benchmark

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

    demo3

    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

    30 条回复    2022-06-09 21:47:03 +08:00
    3dwelcome
        1
    3dwelcome  
       2021-08-07 17:13:02 +08:00   ❤️ 2
    强啊,有了 wasm 后,JS 就是羞涩的少女,感觉任何语言都能插入到 JS 里。

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

    不过 wasm 比 js 快还是应该的(虽然 V8 快到不行),主要还是这块是个方向,可以借着方向发展,一起快
    aljun
        3
    aljun  
    OP
       2021-08-07 17:34:47 +08:00
    貌似在 v2 不是很叫座🤔 ?
    jdhao
        4
    jdhao  
       2021-08-07 17:37:32 +08:00 via Android
    用到是哪个 ANN 算法,PQ 还是 HNSW?
    aljun
        5
    aljun  
    OP
       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
        6
    aljun  
    OP
       2021-08-07 17:45:51 +08:00
    @aljun 复制的 readme 。。。详情可以看看 github readme 😂
    jdhao
        7
    jdhao  
       2021-08-07 17:46:07 +08:00 via Android
    @aljun 都是一个人搞定的吗,牛逼
    aljun
        8
    aljun  
    OP
       2021-08-07 17:48:30 +08:00
    @jdhao 算法是我和另一个朋友一起搞的,感兴趣的话可以一起实现,还有很多算法未实现,目前是 **0.1.0** 挺早期的
    jdhao
        9
    jdhao  
       2021-08-07 17:52:32 +08:00
    目前定位是怎么样的呢,像 FAISS 一样准备长期维护,还是说只是尝试实现一下,个人兴趣。

    可以和 [ANN benchmark]( https://github.com/erikbern/ann-benchmarks) 里面其他算法也对比一下
    aljun
        10
    aljun  
    OP
       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
        11
    jdhao  
       2021-08-07 18:03:06 +08:00   ❤️ 1
    @aljun ANN benchmarks 里面有个 NGT,速度似乎挺快的,没看到和 NGT 的对比。我主要是平时会使用到 ANN 搜索库,没有开发能力 😄,目前用到的是 vearch (底层还是 FAISS)。
    aljun
        12
    aljun  
    OP
       2021-08-07 18:59:28 +08:00
    @aljun - -
    aljun
        13
    aljun  
    OP
       2021-08-07 20:34:27 +08:00 via iPhone
    没有人关注么😢
    aljun
        14
    aljun  
    OP
       2021-08-07 22:49:55 +08:00 via iPhone
    @aljun 😢
    messense
        15
    messense  
       2021-08-08 01:05:53 +08:00
    👍
    LeeReamond
        16
    LeeReamond  
       2021-08-08 04:31:43 +08:00 via Android
    近期最近搜索应该怎么理解?是如同 demo 中只能对图像进行搜索?还是一种普遍适用的算法?
    aljun
        17
    aljun  
    OP
       2021-08-08 11:21:35 +08:00
    @messense 感激🙏
    aljun
        18
    aljun  
    OP
       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
        19
    aljun  
    OP
       2021-08-08 12:07:08 +08:00
    @LeeReamond 可以体验下我 homepage 的 demo,是用 actix-web 搭的应用,底层跑了这个算法,反应应该是毫秒级的,其他的体感相关的耗时就只有 nginx 的静态文件 serving 速度了

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

    http://horasearch.com/
    aljun
        20
    aljun  
    OP
       2021-08-08 12:08:02 +08:00
    @messense 说起来,maturin 我在发布 pypi 时还遇到了一些 bug,我这两天提个 patch😂😂
    messense
        21
    messense  
       2021-08-08 12:13:49 +08:00
    @aljun 好嘞,也可以先提一下 issue
    timpaik
        22
    timpaik  
       2021-08-08 13:16:11 +08:00 via Android
    aljun
        23
    aljun  
    OP
       2021-08-08 13:31:15 +08:00
    @timpaik 感谢🙏
    honkki
        24
    honkki  
       2021-08-08 15:35:05 +08:00
    rust🦀 针不戳
    aljun
        25
    aljun  
    OP
       2021-08-08 15:43:50 +08:00
    @honkki 其实还是不少坑,比如 Rust 现在的 SIMD 支持就不能算很完善,所以严格来说我 bench 实在 SIMD + nightly ( llvm12 )开启的情况下,才比 Faiss ( openmp + BLAS )有更快的水平(具体速度可以参考上面的 benchmark 图)
    zzl22100048
        26
    zzl22100048  
       2021-09-13 16:39:02 +08:00
    index 怎么做持久化呢
    aljun
        27
    aljun  
    OP
       2021-09-15 00:34:19 +08:00
    @zzl22100048 我看你貌似提了个 issue,应该已经找到了对吧
    zzl22100048
        28
    zzl22100048  
       2021-09-15 08:32:34 +08:00 via iPhone
    @aljun 找到了持久化的方法。
    build 索引的时候没有进度条,100 多万的 200 维向量花了 8 个小时才构建完,有没有什么加速的方法
    aljun
        29
    aljun  
    OP
       2021-09-20 17:01:48 +08:00
    @zzl22100048 好的,感谢建议,我们会完善这块的建设
    rpman
        30
    rpman  
       2022-06-09 21:47:03 +08:00
    原来作者居然混 v2 ,惊了
    想知道 ANN 里有没有适合 online 场景 (vector db 存在一定的 CRUD)
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   926 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 34ms · UTC 19:42 · PVG 03:42 · LAX 11:42 · JFK 14:42
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.