特許ウォッチ

公開番号2025116398
公報種別公開特許公報(A)
公開日2025-08-08
出願番号2024010798
出願日2024-01-29
発明の名称生成方法、探索方法、および生成装置
出願人キオクシア株式会社
代理人弁理士法人酒井国際特許事務所
主分類G06F 16/903 20190101AFI20250801BHJP(計算;計数)
要約【課題】メモリ使用量が少ない探索動作を可能にするインデックス情報の生成方法、当該インデックス情報を用いた探索方法、および生成装置を提供すること。
【解決手段】生成方法は、設定することと、ライトすることと、を含む。設定することは、探索範囲に含まれる複数の第1ベクトルに対応した複数の第1ノードのうちの1つを第2ノードとして設定することである。ライトすることは、第2ベクトルと、第2ノードの出隣接ノードである1以上の第3ノードのそれぞれについてIDおよび第3ノードに対応するベクトルである第3ベクトルと、を含む情報片をライトすることである。第2ベクトルは、複数の第1ベクトルのうちの第2ノードに対応した第1ベクトルである。情報片は有向グラフに対応したインデックス情報のうちの第2ノードにかかる要素である。
【選択図】図6
特許請求の範囲【請求項１】
有向グラフで表されるデータを処理するように構成されたプロセッサによる生成方法であって、
前記有向グラフに含まれるそれぞれＩＤがアサインされた複数の第１ノードであって探索範囲に含まれる複数の第１ベクトルに対応した複数の第１ノードのうちの１つを第２ノードとして設定することと、
前記複数の第１ベクトルのうちの前記第２ノードに対応した第１ベクトルである第２ベクトルと、前記複数の第１ノードのうちの前記第２ノードの全ての出隣接ノードである１以上の第３ノードのそれぞれについてＩＤおよび第３ベクトルと、を含む情報片をライトすることと、前記第３ベクトルは前記第３ノードに対応するベクトルであり、前記情報片は前記有向グラフに対応したインデックス情報のうちの前記第２ノードにかかる要素である、
を含む生成方法。
続きを表示（約 1,900 文字）【請求項２】
前記第３ベクトルは、前記第３ノードに対応する第１ベクトル、又は前記第３ノードに対応する前記第１ベクトルを圧縮することで生成されるベクトルである、
請求項１に記載の生成方法。
【請求項３】
複数回の第１動作を実行することをさらに含み、前記複数回の第１動作のそれぞれは、前記設定すること、および前記ライトすることを含み、
前記複数回の第１動作のそれぞれにおいて、前記設定することは、前記複数の第１ノードのうちのまだ前記第２ノードとして設定されていない第１ノードを設定し、
前記複数回の第１動作は、前記第２ノードとして設定されていない第１ノードがなくなるまで実行される、
請求項１に記載の生成方法。
【請求項４】
前記ライトすることは、前記第２ノードの出隣接ノードの数を前記情報片に追加することを含む、
請求項１に記載の生成方法。
【請求項５】
複数回の第１動作を実行することをさらに含み、前記複数回の第１動作のそれぞれは、前記設定すること、および前記ライトすることを含み、
前記複数回の第１動作のそれぞれにおける前記ライトすることは、複数の第１記憶領域のうちのそれぞれ異なる第１記憶領域に前記情報片をライトすることであり、
前記複数の第１記憶領域のそれぞれはストレージデバイスへのアクセスの単位に対応する、
請求項１から請求項４の何れか一項に記載の生成方法。
【請求項６】
クエリを取得することと、
インデックス情報によって規定された有向グラフに沿って前記クエリに最も近い第１ノードの候補を設定することと、前記有向グラフは探索範囲である複数の第１ベクトルに対応した複数の第１ノードを含み、前記インデックス情報がストレージデバイスに格納され、前記インデックス情報は複数の第１情報片を含み、前記複数の第１情報片のそれぞれは前記複数の第１ベクトルのうちの１つの第１ノードに対応する第１ベクトルである第２ベクトルと前記複数の第１ノードのうちの前記１つの第１ノードの全ての出隣接ノードである１以上の第２ノードのそれぞれについてＩＤおよび第３ベクトルを含み、前記第３ベクトルは前記第２ノードに対応するベクトルであり、
を含み、
前記候補を設定することは、前記候補の第１ノードである第３ノードにかかる第１情報片である第２情報片を前記ストレージデバイスへのアクセスの単位に対応する第１の記憶領域からリードして、リードされた前記第２情報片を前記ストレージデバイスよりもアクセスの動作が高速なメモリに格納することと、
前記メモリに格納された前記第２情報片に含まれる１以上の前記第３ベクトルに基づいて新たな候補の第１ノードを設定することと、
を含む探索方法。
【請求項７】
前記第３ベクトルは、前記第２ノードに対応する第１ベクトル、又は前記第２ノードに対応する前記第１ベクトルを圧縮することで生成されるベクトルである、
請求項６に記載の探索方法。
【請求項８】
前記メモリに前記第２情報片が格納された後、格納された前記第２情報片に含まれる第１ベクトルを用いて前記候補の第１ノードと前記クエリとの距離を計算することと、
前記候補として設定されたことがある複数の第１ノードのそれぞれと前記クエリとの複数の前記距離に基づいて前記クエリに最も近いベクトルを特定することと、
をさらに含む請求項６に記載の探索方法。
【請求項９】
それぞれＩＤがアサインされた複数の第１ノードを含む有向グラフおよび探索範囲に含まれる複数の第１ベクトルを受信するように構成されたインタフェース回路と、前記複数の第１ノードは前記複数の第１ベクトルに対応し、
前記複数の第１ノードのうちの１つを第２ノードとして設定することと、
前記複数の第１ベクトルのうちの前記第２ノードに対応した第１ベクトルである第２ベクトルと、前記複数の第１ノードのうちの前記第２ノードの全ての出隣接ノードである１以上の第３ノードのそれぞれについてＩＤおよび第３ベクトルと、を含む情報片をライトすることと、前記第３ベクトルは前記第３ノードに対応するベクトルであり、前記情報片は前記有向グラフに対応したインデックス情報のうちの前記第２ノードにかかる要素である、
を実行するように構成されたプロセッサと、
を備える生成装置。

発明の詳細な説明【技術分野】
【０００１】
本実施形態は、生成方法、探索方法、および生成装置に関する。
続きを表示（約 2,200 文字）【背景技術】
【０００２】
グラフベースの近似最近傍探索アルゴリズムの一つとして、ＤｉｓｋＡＮＮ（Disk-based Approximate Nearest Neighbor search）というアルゴリズムが知られている。ＤｉｓｋＡＮＮによれば、探索の範囲である多次元ベクトル群のうちのそれぞれの多次元ベクトルをノードと見なして有向グラフが作成され、この有向グラフの構造に基づいて生成されたインデックス情報がストレージデバイスに格納される。そして、ストレージデバイス内の当該インデックス情報に基づき、有向グラフに沿った探索動作が行われる。
【先行技術文献】
【非特許文献】
【０００３】
Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Krishaswamy, and Harsha Vardhan Simhadri, “DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node”, [online], November 2019, NeurIPS, [retrieved on 2022-12-11], retrieved from the Internet: <URL: https://suhasjs.github.io/files/diskann_neurips19.pdf>
【発明の概要】
【発明が解決しようとする課題】
【０００４】
一つの実施形態は、メモリ使用量が少ない探索動作を可能にするインデックス情報の生成方法、当該インデックス情報を用いた探索方法、および生成装置を提供することを目的とする。
【課題を解決するための手段】
【０００５】
一つの実施形態によれば、生成方法は、有向グラフで表されるデータを処理するように構成されたプロセッサによる生成方法である。生成方法は、設定することと、ライトすることと、を含む。設定することは、探索範囲に含まれる複数の第１ベクトルに対応した複数の第１ノードのうちの１つを第２ノードとして設定することである。複数の第１ノードは、有向グラフに含まれるそれぞれＩＤがアサインされた複数のノードである。ライトすることは、第２ベクトルと、１以上の第３ノードのそれぞれについてＩＤおよび第３ノードに対応するベクトルである第３ベクトルと、を含む情報片をライトすることである。第２ベクトルは、複数の第１ベクトルのうちの第２ノードに対応した第１ベクトルである。１以上の第３ノードは、複数の第１ノードのうちの第２ノードの全ての出隣接ノードである。情報片は有向グラフに対応したインデックス情報のうちの第２ノードにかかる要素である。
【図面の簡単な説明】
【０００６】
実施形態の探索装置の構成の一例を示す模式的な図。
実施形態にかかる有向グラフおよびインデックス情報の構成を説明するための図。
実施形態の探索装置が探索を実行する際にＳＳＤおよびＤＲＡＭに格納されている情報の一例を説明するための模式的な図。
実施形態の生成装置の構成の一例を示す模式的な図。
実施形態の生成装置が備えるプロセッサが実現する機能の一例を示す模式的な図。
実施形態の生成装置の動作の一例を示すフローチャート。
実施形態の探索装置が備えるプロセッサが実現する機能の一例を示す模式的な図。
実施形態の探索装置の動作の一例を示すフローチャート。
変形例１にかかるノード情報の構成の一例を示す図。
変形例２にかかるノード情報の構成の一例を示す図。
【発明を実施するための形態】
【０００７】
以下に添付図面を参照して、実施形態にかかる生成方法、探索方法、および生成装置を詳細に説明する。なお、これらの実施形態により本発明が限定されるものではない。
【０００８】
（実施形態）
まず、実施形態の探索方法が実行される装置（探索装置と表記する）の例を説明する。図１は、実施形態の探索装置の構成の一例を示す模式的な図である。
【０００９】
図１に示す例では、探索装置２は、プロセッサ２１、インタフェース２２、ＳＳＤ（Solid State Drive）２３、ＤＲＡＭ（Dynamic Random Access Memory）２４、およびバス２５を備える。プロセッサ２１、インタフェース２２、ＳＳＤ２３、およびＤＲＡＭ２４は、バス２５に電気的に接続される。
【００１０】
インタフェース２２は、探索装置２に対して情報を入出力するための装置である。インタフェース２２は、ネットワークを介した通信のためのインタフェース、記憶装置が接続され得るインタフェース、キーボードなどの入力装置が接続され得るインタフェース、などを含む。探索装置２は、インタフェースを介してクエリの入力を受け付けることができる。
（【００１１】以降は省略されています）

関連特許