Upgrade to Pro — share decks privately, control downloads, hide ads and more …

近似最近傍探索とVector DBの理論的背景

Yusuke Matsui
November 20, 2023

近似最近傍探索とVector DBの理論的背景

UTokyo ARC 第3回サロン
https://sites.google.com/g.ecc.u-tokyo.ac.jp/utokyoarc/schedule?authuser=0

2023年11月21日(火) 11:00~12:00
工学部2号館2階222講義室 および オンライン

松井 勇佑(東京大学)https://yusukematsui.me/

Yusuke Matsui

November 20, 2023
Tweet

More Decks by Yusuke Matsui

Other Decks in Research

Transcript

  1. スライド:https://bit.ly/49WgRfs
    1
    近似最近傍探索とVector DBの
    理論的背景
    松井勇佑
    情報理工学系研究科 電子情報学専攻 講師
    UTokyo ARC 第3回サロン 2023/11/21

    View full-size slide

  2. スライド:https://bit.ly/49WgRfs
    2
    松井勇佑
    ✓ コンピュータビジョン
    ✓ 大規模探索
    ✓ データ構造+機械学習
    http://yusukematsui.me
    東京大学 情報理工学系研究科 電子情報学専攻 講師
    @utokyo_bunny
    ARM 4-bit PQ
    [Matsui+, ICASSP 22]
    Relative NN-Descent
    [Ono & Matsui, ACMMM 23]
    @matsui528
    Fast Partitioned Learned Bloom Filter
    [Sato & Matsui, NeurIPS 23]

    View full-size slide

  3. スライド:https://bit.ly/49WgRfs
    3
    ➢ 導入:埋め込み+探索+LLMのデモ
    ➢ 近傍探索・Vector DBの理論
    ➢ 今後の展望

    View full-size slide

  4. スライド:https://bit.ly/49WgRfs
    4
    ➢ 導入:埋め込み+探索+LLMのデモ
    ➢ 近傍探索・Vector DBの理論
    ➢ 今後の展望

    View full-size slide

  5. スライド:https://bit.ly/49WgRfs
    5
    Texts are from: https://github.com/openai/openaicookbook/blob/main/examples/Question_answering_using_embeddings.ipynb Icon credit: https://ja.wikipedia.org/wiki/ChatGPT
    "Who won curling
    gold at the 2022
    Winter Olympics?"
    ChatGPT 3.5
    (trained in 2021)
    “I'm sorry, but as an AI language
    model, I don't have information
    about the future events.”
    Ask

    LLMへ知識を追加したい

    View full-size slide

  6. スライド:https://bit.ly/49WgRfs
    6
    埋め込み+探索+LLM(RAG; Retrieval Augmented Generation)
    Texts are from: https://github.com/openai/openaicookbook/blob/main/examples/Question_answering_using_embeddings.ipynb Icon credit: https://ja.wikipedia.org/wiki/ChatGPT
    "Who won curling
    gold at the 2022
    Winter Olympics?"
    ChatGPT 3.5
    (trained in 2021)

    View full-size slide

  7. スライド:https://bit.ly/49WgRfs
    7
    Texts are from: https://github.com/openai/openaicookbook/blob/main/examples/Question_answering_using_embeddings.ipynb Icon credit: https://ja.wikipedia.org/wiki/ChatGPT
    "Who won curling
    gold at the 2022
    Winter Olympics?"
    ChatGPT 3.5
    (trained in 2021)
    “Damir Sharipzyanov¥n¥n=Career…”
    “Lviv bid for the 2022 Winter…”

    “Chinami Yoshida¥n¥n==Personal…”
    埋め込み+探索+LLM(RAG; Retrieval Augmented Generation)

    View full-size slide

  8. スライド:https://bit.ly/49WgRfs
    8
    𝒙1
    ,
    Texts are from: https://github.com/openai/openaicookbook/blob/main/examples/Question_answering_using_embeddings.ipynb Icon credit: https://ja.wikipedia.org/wiki/ChatGPT
    "Who won curling
    gold at the 2022
    Winter Olympics?"
    ChatGPT 3.5
    (trained in 2021)
    “Damir Sharipzyanov¥n¥n=Career…”
    “Lviv bid for the 2022 Winter…”

    “Chinami Yoshida¥n¥n==Personal…”
    Text
    Encoder
    埋め込み+探索+LLM(RAG; Retrieval Augmented Generation)

    View full-size slide

  9. スライド:https://bit.ly/49WgRfs
    9
    𝒙1
    , 𝒙2
    ,
    Texts are from: https://github.com/openai/openaicookbook/blob/main/examples/Question_answering_using_embeddings.ipynb Icon credit: https://ja.wikipedia.org/wiki/ChatGPT
    "Who won curling
    gold at the 2022
    Winter Olympics?"
    ChatGPT 3.5
    (trained in 2021)
    “Damir Sharipzyanov¥n¥n=Career…”
    “Lviv bid for the 2022 Winter…”

    “Chinami Yoshida¥n¥n==Personal…”
    Text
    Encoder
    埋め込み+探索+LLM(RAG; Retrieval Augmented Generation)

    View full-size slide

  10. スライド:https://bit.ly/49WgRfs
    10
    𝒙1
    , 𝒙2
    , … , 𝒙𝑁
    Texts are from: https://github.com/openai/openaicookbook/blob/main/examples/Question_answering_using_embeddings.ipynb Icon credit: https://ja.wikipedia.org/wiki/ChatGPT
    "Who won curling
    gold at the 2022
    Winter Olympics?"
    ChatGPT 3.5
    (trained in 2021)
    “Damir Sharipzyanov¥n¥n=Career…”
    “Lviv bid for the 2022 Winter…”

    “Chinami Yoshida¥n¥n==Personal…”
    Text
    Encoder
    埋め込み+探索+LLM(RAG; Retrieval Augmented Generation)

    View full-size slide

  11. スライド:https://bit.ly/49WgRfs
    11
    0.23
    3.15
    0.65
    1.43
    𝒙1
    , 𝒙2
    , … , 𝒙𝑁
    Texts are from: https://github.com/openai/openaicookbook/blob/main/examples/Question_answering_using_embeddings.ipynb Icon credit: https://ja.wikipedia.org/wiki/ChatGPT
    "Who won curling
    gold at the 2022
    Winter Olympics?"
    ChatGPT 3.5
    (trained in 2021)
    “Damir Sharipzyanov¥n¥n=Career…”
    “Lviv bid for the 2022 Winter…”

    Text
    Encoder
    “Chinami Yoshida¥n¥n==Personal…”
    Text
    Encoder
    埋め込み+探索+LLM(RAG; Retrieval Augmented Generation)

    View full-size slide

  12. スライド:https://bit.ly/49WgRfs
    12
    0.23
    3.15
    0.65
    1.43
    0.20
    3.25
    0.72
    1.68
    argmin 𝒒 − 𝒙𝑛 2
    2
    Result
    𝒙1
    , 𝒙2
    , … , 𝒙𝑁
    Texts are from: https://github.com/openai/openaicookbook/blob/main/examples/Question_answering_using_embeddings.ipynb Icon credit: https://ja.wikipedia.org/wiki/ChatGPT
    "Who won curling
    gold at the 2022
    Winter Olympics?"
    ChatGPT 3.5
    (trained in 2021)
    Search
    “Damir Sharipzyanov¥n¥n=Career…”
    “Lviv bid for the 2022 Winter…”

    Text
    Encoder
    “Chinami Yoshida¥n¥n==Personal…”
    Text
    Encoder
    “List of 2022 Winter
    Olympics medal winners…”
    埋め込み+探索+LLM(RAG; Retrieval Augmented Generation)

    View full-size slide

  13. スライド:https://bit.ly/49WgRfs
    13
    0.23
    3.15
    0.65
    1.43
    0.20
    3.25
    0.72
    1.68
    argmin 𝒒 − 𝒙𝑛 2
    2
    Result
    𝒙1
    , 𝒙2
    , … , 𝒙𝑁
    Texts are from: https://github.com/openai/openaicookbook/blob/main/examples/Question_answering_using_embeddings.ipynb Icon credit: https://ja.wikipedia.org/wiki/ChatGPT
    "Who won curling
    gold at the 2022
    Winter Olympics?"
    Search
    Update
    “Damir Sharipzyanov¥n¥n=Career…”
    “Lviv bid for the 2022 Winter…”

    Text
    Encoder
    “Chinami Yoshida¥n¥n==Personal…”
    Text
    Encoder
    “Who won curling gold at the
    2022 Winter Olympics?
    Use the bellow articles: List of
    2022 Winter Olympics medal
    winners…”
    “List of 2022 Winter
    Olympics medal winners…”
    ChatGPT 3.5
    (trained in 2021)
    埋め込み+探索+LLM(RAG; Retrieval Augmented Generation)

    View full-size slide

  14. スライド:https://bit.ly/49WgRfs
    14
    0.23
    3.15
    0.65
    1.43
    0.20
    3.25
    0.72
    1.68
    argmin 𝒒 − 𝒙𝑛 2
    2
    Result
    𝒙1
    , 𝒙2
    , … , 𝒙𝑁
    Texts are from: https://github.com/openai/openaicookbook/blob/main/examples/Question_answering_using_embeddings.ipynb Icon credit: https://ja.wikipedia.org/wiki/ChatGPT
    "Who won curling
    gold at the 2022
    Winter Olympics?"
    “Niklas Edin, Oskar
    Eriksson, …”
    Search
    Update

    “Damir Sharipzyanov¥n¥n=Career…”
    “Lviv bid for the 2022 Winter…”

    Text
    Encoder
    “Chinami Yoshida¥n¥n==Personal…”
    Text
    Encoder
    “Who won curling gold at the
    2022 Winter Olympics?
    Use the bellow articles: List of
    2022 Winter Olympics medal
    winners…”
    “List of 2022 Winter
    Olympics medal winners…”
    ChatGPT 3.5
    (trained in 2021)
    埋め込み+探索+LLM(RAG; Retrieval Augmented Generation)

    View full-size slide

  15. スライド:https://bit.ly/49WgRfs
    15
    0.23
    3.15
    0.65
    1.43
    0.20
    3.25
    0.72
    1.68
    argmin 𝒒 − 𝒙𝑛 2
    2
    Result
    𝒙1
    , 𝒙2
    , … , 𝒙𝑁
    Texts are from: https://github.com/openai/openaicookbook/blob/main/examples/Question_answering_using_embeddings.ipynb Icon credit: https://ja.wikipedia.org/wiki/ChatGPT
    "Who won curling
    gold at the 2022
    Winter Olympics?"
    “Niklas Edin, Oskar
    Eriksson, …”
    Search
    Update

    “Damir Sharipzyanov¥n¥n=Career…”
    “Lviv bid for the 2022 Winter…”

    Text
    Encoder
    “Chinami Yoshida¥n¥n==Personal…”
    Text
    Encoder
    “Who won curling gold at the
    2022 Winter Olympics?
    Use the bellow articles: List of
    2022 Winter Olympics medal
    winners…”
    “List of 2022 Winter
    Olympics medal winners…”
    ChatGPT 3.5
    (trained in 2021)
    埋め込み+探索はLLMに知識を追加
    するもっとも簡単な方法
    埋め込み+探索+LLM(RAG; Retrieval Augmented Generation)

    View full-size slide

  16. スライド:https://bit.ly/49WgRfs
    16
    DEMO1: OpenAI Playground (OpenAIに全投げのウェブサービス)
    https://platform.openai.com/playground?assistant

    View full-size slide

  17. スライド:https://bit.ly/49WgRfs
    17
    DEMO1: OpenAI Playground (OpenAIに全投げのウェブサービス)
    検索をオン
    オリンピック情報をアップロード
    https://platform.openai.com/playground?assistant

    アップした情報を参照している

    View full-size slide

  18. スライド:https://bit.ly/49WgRfs
    18
    DEMO1: OpenAI Playground (OpenAIに全投げのウェブサービス)
    検索をオン
    オリンピック情報をアップロード
    https://platform.openai.com/playground?assistant

    アップした情報を参照している

    View full-size slide

  19. スライド:https://bit.ly/49WgRfs
    19
    DEMO2: 手元でやる(疑似コード)
    # Embed knowledge
    texts = [
    "Chinami Yoshida¥n¥n==Persona...",
    "Lviv bid for the 2022 Winter...",
    ...
    ]
    features = encode(texts)
    # Embed a question
    question =
    "2022のオリンピックでカーリングで金メダルをとったのは誰?"
    query_feature = encode(question)
    # Search
    ids = search(query_feature, features)
    # Add results to the question
    question += "以下の情報を使っていいです。"
    for id in ids:
    question += texts[id]
    # Ask LLM
    result = LLM.ask(question)
    https://github.com/openai/openai-cookbook/blob/main/examples/Question_answering_using_embeddings.ipynb を参考

    View full-size slide

  20. スライド:https://bit.ly/49WgRfs
    20
    DEMO2: 手元でやる(疑似コード)
    # Embed knowledge
    texts = [
    "Chinami Yoshida¥n¥n==Persona...",
    "Lviv bid for the 2022 Winter...",
    ...
    ]
    features = encode(texts)
    # Embed a question
    question =
    "2022のオリンピックでカーリングで金メダルをとったのは誰?"
    query_feature = encode(question)
    # Search
    ids = search(query_feature, features)
    # Add results to the question
    question += "以下の情報を使っていいです。"
    for id in ids:
    question += texts[id]
    # Ask LLM
    result = LLM.ask(question)
    https://github.com/openai/openai-cookbook/blob/main/examples/Question_answering_using_embeddings.ipynb を参考
    ➢ エンコーダはなんでもいい
    ➢ 古典方式(BM25とか)もアリ
    ➢ モダン方式でもいい(がGPUいる)
    ➢ OpenAI APIでもいい(GPUいらない
    がお金かかる)
    ➢ エンコーダはなんでもいい
    ➢ 古典方式(BM25とか)もアリ
    ➢ モダン方式でもいい(がGPUいる)
    ➢ OpenAI APIでもいい(GPUいらない
    がお金かかる)
    ここをどう準備
    するか?
    探索はCPUでもGPUでもいい
    (精度 vs 速度 vs メモリ vs お金)
    手元でやるならGPU必要。利用可能なモデルを準備(e.g., LLaMa)
    OpenAI APIならGPUいらないがお金かかる

    View full-size slide

  21. スライド:https://bit.ly/49WgRfs
    21
    DEMO2: 手元でやる(疑似コード)
    # Embed knowledge
    texts = [
    "Chinami Yoshida¥n¥n==Persona...",
    "Lviv bid for the 2022 Winter...",
    ...
    ]
    features = encode(texts)
    # Embed a question
    question =
    "2022のオリンピックでカーリングで金メダルをとったのは誰?"
    query_feature = encode(question)
    # Search
    ids = search(query_feature, features)
    # Add results to the question
    question += "以下の情報を使っていいです。"
    for id in ids:
    question += texts[id]
    # Ask LLM
    result = LLM.ask(question)
    https://github.com/openai/openai-cookbook/blob/main/examples/Question_answering_using_embeddings.ipynb を参考
    ➢ エンコーダはなんでもいい
    ➢ 古典方式(BM25とか)もアリ
    ➢ モダン方式でもいい(がGPUいる)
    ➢ OpenAI APIでもいい(GPUいらない
    がお金かかる)
    ➢ エンコーダはなんでもいい
    ➢ 古典方式(BM25とか)もアリ
    ➢ モダン方式でもいい(がGPUいる)
    ➢ OpenAI APIでもいい(GPUいらない
    がお金かかる)
    ここをどう準備
    するか?
    探索はCPUでもGPUでもいい
    (精度 vs 速度 vs メモリ vs お金)
    手元でやるならGPU必要。利用可能なモデルを準備(e.g., LLaMa)
    OpenAI APIならGPUいらないがお金かかる
    ➢ 埋め込み+探索部分は古典的
    エンジニアリングみが強い
    ➢ APIコールとの兼ね合い
    ✓ 簡単だが毎度お金かかる
    ✓ 研究で使う場合の再現性?

    View full-size slide

  22. スライド:https://bit.ly/49WgRfs
    22
    ➢ 導入:埋め込み+探索+LLMのデモ
    ➢ 近傍探索・Vector DBの理論
    ➢ 今後の展望

    View full-size slide

  23. スライド:https://bit.ly/49WgRfs
    23
    0.23
    3.15
    0.65
    1.43
    0.20
    3.25
    0.72
    1.68
    argmin 𝒒 − 𝒙𝑛 2
    2
    Result
    𝒙1
    , 𝒙2
    , … , 𝒙𝑁
    Texts are from: https://github.com/openai/openaicookbook/blob/main/examples/Question_answering_using_embeddings.ipynb Icon credit: https://ja.wikipedia.org/wiki/ChatGPT
    "Who won curling
    gold at the 2022
    Winter Olympics?"
    “Niklas Edin, Oskar
    Eriksson, …”
    Search
    Update

    “Damir Sharipzyanov¥n¥n=Career…”
    “Lviv bid for the 2022 Winter…”

    Text
    Encoder
    “Chinami Yoshida¥n¥n==Personal…”
    Text
    Encoder
    “Who won curling gold at the
    2022 Winter Olympics?
    Use the bellow articles: List of
    2022 Winter Olympics medal
    winners…”
    “List of 2022 Winter
    Olympics medal winners…”
    ChatGPT 3.5
    (trained in 2021)
    埋め込み+探索はLLMに知識を追加
    するもっとも簡単な方法
    埋め込み+探索+LLM(RAG; Retrieval Augmented Generation)

    View full-size slide

  24. スライド:https://bit.ly/49WgRfs
    24
    0.23
    3.15
    0.65
    1.43
    0.20
    3.25
    0.72
    1.68
    argmin 𝒒 − 𝒙𝑛 2
    2
    Result
    𝒙1
    , 𝒙2
    , … , 𝒙𝑁
    Texts are from: https://github.com/openai/openaicookbook/blob/main/examples/Question_answering_using_embeddings.ipynb Icon credit: https://ja.wikipedia.org/wiki/ChatGPT
    "Who won curling
    gold at the 2022
    Winter Olympics?"
    “Niklas Edin, Oskar
    Eriksson, …”
    Search
    Update

    “Damir Sharipzyanov¥n¥n=Career…”
    “Lviv bid for the 2022 Winter…”

    Text
    Encoder
    “Chinami Yoshida¥n¥n==Personal…”
    Text
    Encoder
    “Who won curling gold at the
    2022 Winter Olympics?
    Use the bellow articles: List of
    2022 Winter Olympics medal
    winners…”
    “List of 2022 Winter
    Olympics medal winners…”
    ChatGPT 3.5
    (trained in 2021)
    埋め込み+探索はLLMに知識を追加
    するもっとも簡単な方法
    埋め込み+探索+LLM(RAG; Retrieval Augmented Generation)
    ➢ (近似)最近傍探索問題そのもの
    ➢ 速度・精度・メモリのトレードオフ
    ➢ Vector DB??

    View full-size slide

  25. スライド:https://bit.ly/49WgRfs
    25
    技術を議論する際の3つのレベル
    Milvus
    Pinecone
    Qdrant
    ScaNN (4-bit PQ)
    [Guo+, ICML 2020]
    アルゴリズム
    ➢ 科学技術論文
    ➢ 数学の話(が多い)
    ➢ 多くの場合、by 研究者
    ライブラリ
    ➢ アルゴリズムの実装
    ➢ 普通、探索機能のみ
    ➢ By 研究者、開発者、など
    サービス (例: vector DB)
    ➢ ライブラリ + (メタデータ扱い、
    サービング、スケーリング、
    IO、CRUD、など)
    ➢ 普通、by 会社
    Product Quantization +
    Inverted Index (PQ, IVFPQ)
    [Jégou+, TPAMI 2011]
    Hierarchical Navigable
    Small World (HNSW)
    [Malkov+, TPAMI 2019]
    Weaviate
    Vertex AI
    Matching Engine
    faiss
    NMSLIB
    hnswlib
    Vald
    ScaNN
    jina

    View full-size slide

  26. スライド:https://bit.ly/49WgRfs
    26
    技術を議論する際の3つのレベル
    Milvus
    Pinecone
    Qdrant
    ScaNN (4-bit PQ)
    [Guo+, ICML 2020]
    アルゴリズム
    ➢ 科学技術論文
    ➢ 数学の話(が多い)
    ➢ 多くの場合、by 研究者
    ライブラリ
    ➢ アルゴリズムの実装
    ➢ 普通、探索機能のみ
    ➢ By 研究者、開発者、など
    サービス (例: vector DB)
    ➢ ライブラリ + (メタデータ扱い、
    サービング、スケーリング、
    IO、CRUD、など)
    ➢ 普通、by 会社
    Weaviate
    Vertex AI
    Matching Engine
    NMSLIB
    hnswlib
    Vald
    ScaNN
    jina
    1つのライブラリは複数の
    アルゴを実装することもある
     “faissは速い”
    ☺ “faissのPQは速い”
    Product Quantization +
    Inverted Index (PQ, IVFPQ)
    [Jégou+, TPAMI 2011]
    Hierarchical Navigable
    Small World (HNSW)
    [Malkov+, TPAMI 2019]
    faiss

    View full-size slide

  27. スライド:https://bit.ly/49WgRfs
    27
    技術を議論する際の3つのレベル
    Milvus
    Pinecone
    Qdrant
    ScaNN (4-bit PQ)
    [Guo+, ICML 2020]
    アルゴリズム
    ➢ 科学技術論文
    ➢ 数学の話(が多い)
    ➢ 多くの場合、by 研究者
    ライブラリ
    ➢ アルゴリズムの実装
    ➢ 普通、探索機能のみ
    ➢ By 研究者、開発者、など
    サービス (例: vector DB)
    ➢ ライブラリ + (メタデータ扱い、
    サービング、スケーリング、
    IO、CRUD、など)
    ➢ 普通、by 会社
    Product Quantization +
    Inverted Index (PQ, IVFPQ)
    [Jégou+, TPAMI 2011]
    Weaviate
    Vertex AI
    Matching Engine
    Vald
    ScaNN
    jina
    1つのアルゴリズムは複数のライブラリに
    実装されていることがある
    Hierarchical Navigable
    Small World (HNSW)
    [Malkov+, TPAMI 2019]
    faiss
    NMSLIB
    hnswlib

    View full-size slide

  28. スライド:https://bit.ly/49WgRfs
    28
    技術を議論する際の3つのレベル
    Milvus
    Pinecone
    Qdrant
    アルゴリズム
    ➢ 科学技術論文
    ➢ 数学の話(が多い)
    ➢ 多くの場合、by 研究者
    ライブラリ
    ➢ アルゴリズムの実装
    ➢ 普通、探索機能のみ
    ➢ By 研究者、開発者、など
    サービス (例: vector DB)
    ➢ ライブラリ + (メタデータ扱い、
    サービング、スケーリング、
    IO、CRUD、など)
    ➢ 普通、by 会社
    Product Quantization +
    Inverted Index (PQ, IVFPQ)
    [Jégou+, TPAMI 2011]
    Hierarchical Navigable
    Small World (HNSW)
    [Malkov+, TPAMI 2019]
    Weaviate
    Vertex AI
    Matching Engine
    faiss
    NMSLIB
    hnswlib
    Vald
    jina
    1ライブラリ=1アルゴ もよくある
    ScaNN (4-bit PQ)
    [Guo+, ICML 2020]
    ScaNN

    View full-size slide

  29. スライド:https://bit.ly/49WgRfs
    29
    技術を議論する際の3つのレベル
    Pinecone
    Qdrant
    ScaNN (4-bit PQ)
    [Guo+, ICML 2020]
    アルゴリズム
    ➢ 科学技術論文
    ➢ 数学の話(が多い)
    ➢ 多くの場合、by 研究者
    ライブラリ
    ➢ アルゴリズムの実装
    ➢ 普通、探索機能のみ
    ➢ By 研究者、開発者、など
    サービス (例: vector DB)
    ➢ ライブラリ + (メタデータ扱い、
    サービング、スケーリング、
    IO、CRUD、など)
    ➢ 普通、by 会社
    Product Quantization +
    Inverted Index (PQ, IVFPQ)
    [Jégou+, TPAMI 2011]
    Vertex AI
    Matching Engine
    NMSLIB
    Vald
    ScaNN
    jina
    1つのサービスは複数のライブラリを
    使うことがある
    … また、アルゴリズムを
    フルスクラッチすること
    もある (例: Goで書き直す)
    Hierarchical Navigable
    Small World (HNSW)
    [Malkov+, TPAMI 2019]
    faiss
    hnswlib
    Milvus
    Weaviate

    View full-size slide

  30. スライド:https://bit.ly/49WgRfs
    30
    技術を議論する際の3つのレベル
    Milvus
    Pinecone
    Qdrant
    ScaNN (4-bit PQ)
    [Guo+, ICML 2020]
    アルゴリズム
    ➢ 科学技術論文
    ➢ 数学の話(が多い)
    ➢ 多くの場合、by 研究者
    ライブラリ
    ➢ アルゴリズムの実装
    ➢ 普通、探索機能のみ
    ➢ By 研究者、開発者、など
    サービス (例: vector DB)
    ➢ ライブラリ + (メタデータ扱い、
    サービング、スケーリング、
    IO、CRUD、など)
    ➢ 普通、by 会社
    Product Quantization +
    Inverted Index (PQ, IVFPQ)
    [Jégou+, TPAMI 2011]
    Hierarchical Navigable
    Small World (HNSW)
    [Malkov+, TPAMI 2019]
    Weaviate
    Vertex AI
    Matching Engine
    faiss
    NMSLIB
    hnswlib
    Vald
    ScaNN
    jina
    どのようなアルゴリズムが
    あるか?

    View full-size slide

  31. スライド:https://bit.ly/49WgRfs
    31
    𝑁
    109
    106
    billion-scale
    million-scale
    Locality Sensitive Hashing (LSH)
    Tree / Space Partitioning
    Graph traversal
    0.34
    0.22
    0.68
    0.71
    0
    1
    0
    0
    ID: 2
    ID: 123
    0.34
    0.22
    0.68
    0.71
    Space partition Data compression
    ➢ k-means
    ➢ PQ/OPQ
    ➢ Graph traversal
    ➢ etc…
    ➢ Raw data
    ➢ Scalar quantization
    ➢ PQ/OPQ
    ➢ etc…
    Look-up-based
    Hamming-based
    Linear-scan by
    Asymmetric Distance

    Linear-scan by
    Hamming distance
    Inverted index + data compression
    For raw data: Acc. ☺, Memory:  For compressed data: Acc. , Memory: ☺

    View full-size slide

  32. スライド:https://bit.ly/49WgRfs
    32
    𝑁
    109
    106
    billion-scale
    million-scale
    Locality Sensitive Hashing (LSH)
    Tree / Space Partitioning
    Graph traversal
    0.34
    0.22
    0.68
    0.71
    0
    1
    0
    0
    ID: 2
    ID: 123
    0.34
    0.22
    0.68
    0.71
    Space partition Data compression
    ➢ k-means
    ➢ PQ/OPQ
    ➢ Graph traversal
    ➢ etc…
    ➢ Raw data
    ➢ Scalar quantization
    ➢ PQ/OPQ
    ➢ etc…
    Look-up-based
    Hamming-based
    Linear-scan by
    Asymmetric Distance

    Linear-scan by
    Hamming distance
    Inverted index + data compression
    For raw data: Acc. ☺, Memory:  For compressed data: Acc. , Memory: ☺
    最も使われる。少し紹介します

    View full-size slide

  33. スライド:https://bit.ly/49WgRfs
    33
    グラフ探索
    ➢ データが全部メモリに載るなら、デファクトの方式
    ➢ 実データに対し高速で高精度
    ➢ billion級(メモリに載らない)でもやはり重要
    ✓ グラフ探索アルゴリズムはbillion級探索システムの
    ビルディングブロック
    Images are from [Malkov+, Information Systems, 2013]
    ➢ クエリに向かってグラフを辿る
    ➢ 直感的に見えるが、結構ムズい
    ➢ アルゴリズムを詳細に見ます

    View full-size slide

  34. スライド:https://bit.ly/49WgRfs
    34
    探索 Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    ➢ クエリが来る
    Candidates
    (size = 3)
    Close to the query
    説明のため、ノードに
    アルファベットを振りました

    View full-size slide

  35. スライド:https://bit.ly/49WgRfs
    35
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    探索
    ➢ クエリが来る
    ➢ エントリポイント(例: )から始める。
    M

    View full-size slide

  36. スライド:https://bit.ly/49WgRfs
    36
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    ➢ クエリが来る
    ➢ エントリポイント(例: )から始める。qまでの距離を記録
    Candidates
    (size = 3)
    Close to the query
    M
    M 23.1
    探索

    View full-size slide

  37. スライド:https://bit.ly/49WgRfs
    37
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    23.1
    M
    探索

    View full-size slide

  38. スライド:https://bit.ly/49WgRfs
    38
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    M 23.1
    探索
    1st iteration

    View full-size slide

  39. スライド:https://bit.ly/49WgRfs
    39
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    M 23.1
    Best
    Best
    探索
    ➢ 未チェックの最良候補を選ぶ( )
    M

    View full-size slide

  40. スライド:https://bit.ly/49WgRfs
    40
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    M 23.1
    Best
    Best
    check!
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    M

    View full-size slide

  41. スライド:https://bit.ly/49WgRfs
    41
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    23.1
    Best
    Best
    M
    check!
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    M

    View full-size slide

  42. スライド:https://bit.ly/49WgRfs
    42
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    23.1
    Best
    N
    M
    check!
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    ➢ qへの距離を記録
    M

    View full-size slide

  43. スライド:https://bit.ly/49WgRfs
    43
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    Best
    N
    J 11.1
    N 15.3
    K 19.4
    M 23.1
    check!
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    ➢ qへの距離を記録
    M

    View full-size slide

  44. スライド:https://bit.ly/49WgRfs
    44
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    Best
    N
    J 11.1
    N 15.3
    K 19.4
    M 23.1
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    ➢ qへの距離を記録
    M

    View full-size slide

  45. スライド:https://bit.ly/49WgRfs
    45
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    Best
    N
    J 11.1
    N 15.3
    K 19.4
    M 23.1
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    ➢ qへの距離を記録
    ➢ 候補を調整 (size=3)
    M

    View full-size slide

  46. スライド:https://bit.ly/49WgRfs
    46
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    Best
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    ➢ qへの距離を記録
    ➢ 候補を調整 (size=3)
    N
    M
    J 11.1
    N 15.3
    K 19.4
    探索

    View full-size slide

  47. スライド:https://bit.ly/49WgRfs
    47
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    J 11.1
    N 15.3
    K 19.4
    探索

    View full-size slide

  48. スライド:https://bit.ly/49WgRfs
    48
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    J 11.1
    N 15.3
    K 19.4
    探索
    2nd iteration

    View full-size slide

  49. スライド:https://bit.ly/49WgRfs
    49
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    J 11.1
    N 15.3
    K 19.4
    Best
    Best
    探索
    ➢ 未チェックの最良候補を選ぶ( )
    J

    View full-size slide

  50. スライド:https://bit.ly/49WgRfs
    50
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    J 11.1
    N 15.3
    K 19.4
    Best
    Best
    check!
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    J

    View full-size slide

  51. スライド:https://bit.ly/49WgRfs
    51
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    J 11.1
    N 15.3
    K 19.4
    Best
    Best
    check!
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    J

    View full-size slide

  52. スライド:https://bit.ly/49WgRfs
    52
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    J 11.1
    N 15.3
    K 19.4
    Best
    13.2
    9.7
    check!
    Already
    visited
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    ➢ qへの距離を記録
    J

    View full-size slide

  53. スライド:https://bit.ly/49WgRfs
    53
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    Best
    13.2
    9.7
    J 11.1
    N 15.3
    B 2.3
    G 3.5
    I 9.7
    F 10.2
    L 13.2
    check!
    Already
    visited
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    ➢ qへの距離を記録
    J

    View full-size slide

  54. スライド:https://bit.ly/49WgRfs
    54
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    Best J 11.1
    N 15.3
    B 2.3
    G 3.5
    I 9.7
    F 10.2
    L 13.2
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    ➢ qへの距離を記録
    J

    View full-size slide

  55. スライド:https://bit.ly/49WgRfs
    55
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    Best J 11.1
    N 15.3
    B 2.3
    G 3.5
    I 9.7
    F 10.2
    L 13.2
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    ➢ qへの距離を記録
    ➢ 候補を調整 (size=3)
    J

    View full-size slide

  56. スライド:https://bit.ly/49WgRfs
    56
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    Best
    B 2.3
    G 3.5
    I 9.7
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    ➢ qへの距離を記録
    ➢ 候補を調整 (size=3)
    J

    View full-size slide

  57. スライド:https://bit.ly/49WgRfs
    57
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    B 2.3
    G 3.5
    I 9.7
    探索

    View full-size slide

  58. スライド:https://bit.ly/49WgRfs
    58
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    B 2.3
    G 3.5
    I 9.7
    探索
    3rd iteration

    View full-size slide

  59. スライド:https://bit.ly/49WgRfs
    59
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    B 2.3
    G 3.5
    I 9.7
    Best
    Best
    探索
    ➢ 未チェックの最良候補を選ぶ( )
    B

    View full-size slide

  60. スライド:https://bit.ly/49WgRfs
    60
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    B 2.3
    G 3.5
    I 9.7
    Best
    Best
    check!
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    B

    View full-size slide

  61. スライド:https://bit.ly/49WgRfs
    61
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    B 2.3
    G 3.5
    I 9.7
    Best
    Best
    check!
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    B

    View full-size slide

  62. スライド:https://bit.ly/49WgRfs
    62
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    B 2.3
    G 3.5
    I 9.7
    Best
    0.5
    2.1
    check!
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    ➢ qへの距離を記録
    B

    View full-size slide

  63. スライド:https://bit.ly/49WgRfs
    63
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    Best
    0.5
    2.1
    C 0.5
    D 2.1
    A 3.6
    B 2.3
    G 3.5
    I 9.7
    check!
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    ➢ qへの距離を記録
    B

    View full-size slide

  64. スライド:https://bit.ly/49WgRfs
    64
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    A 3.6
    B 2.3
    G 3.5
    I 9.7
    Best
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    ➢ qへの距離を記録
    B

    View full-size slide

  65. スライド:https://bit.ly/49WgRfs
    65
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    A 3.6
    B 2.3
    G 3.5
    I 9.7
    Best
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    ➢ qへの距離を記録
    ➢ 候補を調整 (size=3)
    B

    View full-size slide

  66. スライド:https://bit.ly/49WgRfs
    66
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    B 2.3
    Best
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    ➢ qへの距離を記録
    ➢ 候補を調整 (size=3)
    B

    View full-size slide

  67. スライド:https://bit.ly/49WgRfs
    67
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    B 2.3
    探索

    View full-size slide

  68. スライド:https://bit.ly/49WgRfs
    68
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    B 2.3
    探索
    4th iteration

    View full-size slide

  69. スライド:https://bit.ly/49WgRfs
    69
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    B 2.3
    Best
    Best
    探索
    ➢ 未チェックの最良候補を選ぶ( )
    C

    View full-size slide

  70. スライド:https://bit.ly/49WgRfs
    70
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    B 2.3
    Best
    Best
    check!
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    C

    View full-size slide

  71. スライド:https://bit.ly/49WgRfs
    71
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    B 2.3
    Best
    Best
    check!
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    C

    View full-size slide

  72. スライド:https://bit.ly/49WgRfs
    72
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    B 2.3
    Best
    check!
    Already
    visited
    Already
    visited
    Already
    visited
    Already
    visited
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    ➢ qへの距離を記録
    C

    View full-size slide

  73. スライド:https://bit.ly/49WgRfs
    73
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    B 2.3
    Best
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    ➢ qへの距離を記録
    ➢ 候補を調整 (size=3)
    C

    View full-size slide

  74. スライド:https://bit.ly/49WgRfs
    74
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    B 2.3
    探索

    View full-size slide

  75. スライド:https://bit.ly/49WgRfs
    75
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    B 2.3
    探索
    5th iteration

    View full-size slide

  76. スライド:https://bit.ly/49WgRfs
    76
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    B 2.3
    Best
    Best
    探索
    ➢ 未チェックの最良候補を選ぶ( )
    D

    View full-size slide

  77. スライド:https://bit.ly/49WgRfs
    77
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    B 2.3
    Best
    Best
    check!
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    D

    View full-size slide

  78. スライド:https://bit.ly/49WgRfs
    78
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    B 2.3
    Best
    Best
    check!
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    D

    View full-size slide

  79. スライド:https://bit.ly/49WgRfs
    79
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    B 2.3
    Best
    check!
    Already
    visited
    Already
    visited
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    ➢ qへの距離を記録
    D

    View full-size slide

  80. スライド:https://bit.ly/49WgRfs
    80
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    B 2.3
    Best
    check!
    Already
    visited
    Already
    visited
    H 3.9
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    ➢ qへの距離を記録
    D

    View full-size slide

  81. スライド:https://bit.ly/49WgRfs
    81
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    B 2.3
    Best
    H 3.9
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    ➢ qへの距離を記録
    D

    View full-size slide

  82. スライド:https://bit.ly/49WgRfs
    82
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    B 2.3
    Best
    H 3.9
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    ➢ qへの距離を記録
    ➢ 候補を調整 (size=3)
    D

    View full-size slide

  83. スライド:https://bit.ly/49WgRfs
    83
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    B 2.3
    Best
    探索
    ➢ 未チェックの最良候補を選ぶ( ) チェック!
    ➢ 隣接点を探す
    ➢ qへの距離を記録
    ➢ 候補を調整 (size=3)
    D

    View full-size slide

  84. スライド:https://bit.ly/49WgRfs
    84
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    B 2.3
    ➢ 全候補はチェック済み。終わり。
    ➢ ここでは がクエリ( )に一番近い
    C
    探索

    View full-size slide

  85. スライド:https://bit.ly/49WgRfs
    85
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    B 2.3
    ➢ 全候補はチェック済み。終わり。
    ➢ ここでは がクエリ( )に一番近い
    C
    探索
    最終出力1:候補集合
    ➢ ここからtopkを選択

    View full-size slide

  86. スライド:https://bit.ly/49WgRfs
    86
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    B 2.3
    ➢ 全候補はチェック済み。終わり。
    ➢ ここでは がクエリ( )に一番近い
    C
    探索
    最終出力1:候補集合
    ➢ ここからtopkを選択
    最終出力2:チェックノード
    ➢ つまり、探索経路

    View full-size slide

  87. スライド:https://bit.ly/49WgRfs
    87
    Images are from [Malkov+, Information Systems, 2013]
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    N M
    Candidates
    (size = 3)
    Close to the query
    N
    C 0.5
    D 2.1
    B 2.3
    ➢ 全候補はチェック済み。終わり。
    ➢ ここでは がクエリ( )に一番近い
    C
    探索
    最終出力1:候補集合
    ➢ ここからtopkを選択
    最終出力2:チェックノード
    ➢ つまり、探索経路
    最終出力3:訪問フラグ
    ➢ それぞれのノードに対し、
    訪れたかどうか

    View full-size slide

  88. スライド:https://bit.ly/49WgRfs
    88
    基本的特性:速度
    ➢ アイテム比較は𝑂 𝐷
    ➢ 全体の計算量 ~ #item_comparison
    ∼ length_of_search_path * average_outdegree
    𝒒 ∈ ℝ𝐷
    𝒙13
    ∈ ℝ𝐷
    start
    query
    start
    query
    start
    query
    1st path 2nd path 3rd path
    2.1
    1.9
    outdegree = 1 outdegree = 2 outdegree = 2
    #item_comparison = 3 * (1 + 2 + 2)/3 = 5
    2.4

    View full-size slide

  89. スライド:https://bit.ly/49WgRfs
    89
    基本的特性:速度
    ➢ アイテム比較は𝑂 𝐷
    ➢ 全体の計算量 ~ #item_comparison
    ∼ length_of_search_path * average_outdegree
    𝒒 ∈ ℝ𝐷
    𝒙13
    ∈ ℝ𝐷
    start
    query
    start
    query
    start
    query
    1st path 2nd path 3rd path
    2.1
    1.9
    outdegree = 1 outdegree = 2 outdegree = 2
    #item_comparison = 3 * (1 + 2 + 2)/3 = 5
    2.4
    探索を高速化するには、、、
    (1) 探索経路を短くする?
    ➢ 例:たまに長いエッジ(ショートカット)
    ➢ 例:階層構造
    (2) グラフを疎にする?
    ➢ 例:冗長エッジを削る

    View full-size slide

  90. スライド:https://bit.ly/49WgRfs
    90
    A
    D
    C
    B
    query
    基本的特性:候補サイズ
    E
    start
    Candidates
    (size = 1)
    C
    A
    D
    C
    B
    query
    E
    start
    Candidates
    (size = 3)
    C
    D
    E
    size = 1: Greedy search size > 1: Beam search
    ➢ 候補サイズが大きい➡精度良いが遅い
    ➢ トレードオフを担うオンラインパラメータ
    ➢ HNSWでは“ef”と呼ばれる
    速いが、局所解
    遅いが、より良い解

    View full-size slide

  91. スライド:https://bit.ly/49WgRfs
    91
    グラフ探索方式
    Images are from an excellent survey paper [Wang+, VLDB 2021]
    ➢ めちゃくちゃたくさんある
    ➢ 基本的な構造:良いグラフを設計 + ビームサーチ(先ほど述べたアルゴ)
    ➢ 有名どころ:HNSW, NSG, NGT

    View full-size slide

  92. スライド:https://bit.ly/49WgRfs
    92
    ただの探索?Vector DB?
    ➢ Vector DBの会社は「Vector DBはイケてる!」と言ってます
    ➢ 自分の考え:
    ➢ どのvector DB? ➡ まだ結論無し(みんな戦っている)
    ✓ https://weaviate.io/blog/vector-library-vs-vector-database
    ✓ https://codelabs.milvus.io/vector-database-101-what-is-a-vector-database/index#2
    ✓ https://zilliz.com/learn/what-is-vector-database
    一番単純なnumpy
    only探索を試す
    遅い?
    HNSW in faissのような
    速いANNを試す
    Try Vector DB
    速度のみが問題であれば、
    単にライブラリを使えばいい

    View full-size slide

  93. スライド:https://bit.ly/49WgRfs
    93
    ➢ 導入:埋め込み+探索+LLMのデモ
    ➢ 近傍探索・Vector DBの理論
    ➢ 今後の展望

    View full-size slide

  94. スライド:https://bit.ly/49WgRfs
    94
    現状の探索+LLM(RAG)についての心構え
    ➢ 探索が活きる場面についての基本的思想
    ✓ 難しい問題を大規模だが単純な探索問題に落とし込めるとき
    ✓ 例:複雑な画像認識器 vs 単純kNN認識
    ✓ 例:LLM + fine-tuning vs LLM + embedding
    ➢ 「どうやってLLMに情報を入れるか」という意味でfine-tuneとの対比
    ✓ RAGで論文を書けばfine-tuneとの比較を要求され、fine-tuneで論文
    を書けばRAGとの比較を要求されるかも。。。
    ➢ 現状のRAGは、ML部分をブラックボックス or APIコールと割り切り、
    残りは古典的(非ML的)エンジニアリングでやる、ともとれる
    ✓ 例:LLM自身はありもの
    ✓ 例:Encoderはblack box特徴量抽出器

    View full-size slide

  95. スライド:https://bit.ly/49WgRfs
    95
    RAGにおける探索をもっと賢くする近年動向
    ➢ ただの埋め込み&ただの探索はナイーブすぎる?
    ✓ 「質問文に似ている知識」が良い情報とは全然限らない
    ➢ より賢い探索が良いかもしれない
    ✓ 古典探索技術がRevisitされている現状!
    ✓ 例:クエリ拡張。古典技術だったクエリ拡張を画像検索に
    適用した[Chum+, ICCV 2007]を思い出す。Revisitは繰り返す!
    ➢ 進む方向
    ✓ 機械学習的に解決するか?
    (例:特別な埋め込み空間を学習する)
    ✓ データ構造・アルゴリズム的に解決するか?
    (例:特殊な操作に対応した探索データ構造)

    View full-size slide

  96. スライド:https://bit.ly/49WgRfs
    96
    RAGにおける探索をもっと賢くする近年動向
    ➢ ただの埋め込み&ただの探索はナイーブすぎる?
    ✓ 「質問に似ている知識」が良い情報とは全然限らない
    ➢ より賢い探索が追求されている
    ✓ 古典探索技術がRevisitされている現状!
    ✓ 例:クエリ拡張。古典技術だったクエリ拡張を画像検索に
    適用した[Chum+, ICCV 2007]を思い出す。Revisitは繰り返す!
    ➢ 進む方向
    ✓ 機械学習的に解決するか?
    (例:特別な埋め込み空間を学習する)
    ✓ データ構造・アルゴリズム的に解決するか?
    (例:特殊な操作に対応した探索データ構造)

    View full-size slide

  97. スライド:https://bit.ly/49WgRfs
    97
    RAGにおける探索をもっと賢くする近年動向
    ➢ ただの埋め込み&ただの探索はナイーブすぎる?
    ✓ 「質問に似ている知識」が良い情報とは全然限らない
    ➢ より賢い探索が追求されている
    ✓ 古典探索技術がRevisitされている現状!
    ✓ 例:クエリ拡張。古典技術だったクエリ拡張を画像検索に
    適用した[Chum+, ICCV 2007]を思い出す。Revisitは繰り返す!
    ➢ 進む方向
    ✓ 機械学習的に解決するか?
    (例:特別な埋め込み空間を学習する)
    ✓ データ構造・アルゴリズム的に解決するか?
    (例:特殊な操作に対応した探索データ構造)

    View full-size slide

  98. スライド:https://bit.ly/49WgRfs
    98
    近傍探索の観点から考えるべきこと
    ➢ CPUなのか?GPUなのか?マネージドサービスなのか?
    ✓ 全てはトレードオフ
    ✓ NVIDIAはGPU探索を推してきている
    (RAFT&CAGRA [Ootomo+, arXiv 23])
    ✓ 探索部分にお金をかけられるかどうか?
    ➢ グラフ探索アルゴリズムの『次』
    ✓ 近年のグラフ探索論文はかなりエンジニアリング色が強い
    (例:並列性の追求。ディスクの考慮。)
    ✓ 全く新しいブレイクスルーが待たれる
    ➢ 地味だが重要:ベクトルの次元が100ぐらいから1000ぐらいに
    ✓ 100以上ならPCAして100にしろ、とよく言われていた
    ✓ LLMのAPI側の制約により、1000でやるしかない状況が生まれる

    View full-size slide

  99. スライド:https://bit.ly/49WgRfs
    99
    これからの最適化問題:LLMを要素技術として使う時代
    ➢ 疑似コード内で、LLMを関数として用いる時代はもう来ている
    ➢ ある処理を手元でやるか?APIコールにするか?
    というこれまでになかった選択
    ➢ LLM時代・API時代の「再現性」をどう考えるか
    ➢ ある問題について、どういう解決方式があり、どういうコストを
    かけると、何が得られるか、おおざっぱに見積もれる必要
    オンプレ自前サーバ クラウド(例:ABCI, mdx) APIコール
    ☺使い放題
    初期投資
    維持費
    ☺バランス
    クラウドの
    調子に依存?
    ☺激安かも
    大量処理は不向き
    通信?会社依存?
    新しいパラダイムも

    View full-size slide

  100. スライド:https://bit.ly/49WgRfs
    100
    参考資料
    ➢ 近傍探索技術全体のまとめ
    ➢ 日本語:MIRU19チュートリアル
    ➢ 英語:CVPR20チュートリアル
    ➢ グラフ系探索のまとめ
    ➢ 日本語:YANS23チュートリアル
    ➢ 英語:CVPR23チュートリアル
    ➢ RAGに関するおすすめ
    チュートリアル
    [Asai+, ACL 2023 Tutorial]

    View full-size slide

  101. スライド:https://bit.ly/49WgRfs
    101
    ◼ [Jégou+, TPAMI 2011] H. Jégou+, “Product Quantization for Nearest Neighbor Search”, IEEE TPAMI 2011
    ◼ [Guo+, ICML 2020] R. Guo+, “Accelerating Large-Scale Inference with Anisotropic Vector Quantization”, ICML 2020
    ◼ [Malkov+, TPAMI 2019] Y. Malkov+, “Efficient and Robust Approximate Nearest Neighbor search using Hierarchical
    Navigable Small World Graphs,” IEEE TPAMI 2019
    ◼ [Malkov+, IS 13] Y, Malkov+, “Approximate Nearest Neighbor Algorithm based on Navigable Small World Graphs”,
    Information Systems 2013
    ◼ [Fu+, VLDB 19] C. Fu+, “Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graphs”, 2019
    ◼ [Wang+, VLDB 21] M. Wang+, “A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate
    Nearest Neighbor Search”, VLDB 2021
    ◼ [Iwasaki+, arXiv 18] M. Iwasaki and D. Miyazaki, “Optimization if Indexing Based on k-Nearest Neighbor Graph for
    Proximity Search in High-dimensional Data”, arXiv 2018
    ◼ [Ootomo+, arXiv 23] H. Ootomo+, “CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor
    Search for GPUs”, arXiv 2023
    ◼ [Chum+, ICCV 07] O. Chum+, “Total Recall: Automatic Query Expansion with a Generative Feature Model for Object
    Retrieval”, ICCV 2007
    ◼ [Pinecone] https://www.pinecone.io/
    ◼ [Milvus] https://milvus.io/
    ◼ [Qdrant] https://qdrant.tech/
    ◼ [Weaviate] https://weaviate.io/
    ◼ [Vertex AI Matching Engine] https://cloud.google.com/vertex-ai/docs/matching-engine
    ◼ [Vald] https://vald.vdaas.org/
    ◼ [Modal] https://modal.com/
    Reference

    View full-size slide