特許ウォッチ

公開番号2025142888
公報種別公開特許公報(A)
公開日2025-10-01
出願番号2024042488
出願日2024-03-18
発明の名称管理方法およびデータベース装置
出願人キオクシア株式会社
代理人弁理士法人酒井国際特許事務所
主分類G06F 16/18 20190101AFI20250924BHJP(計算;計数)
要約【課題】ストレージデバイスにライトされるデータの量を抑制できる管理方法およびデータベース装置を提供すること。
【解決手段】ストレージデバイスに格納された第1ベクトルデータベースは、複数の第1ベクトルのそれぞれを示す第1情報片の群が記録される。複数の第1ベクトルは第1有向グラフを構成する複数のノードに対応する。管理方法は、2以上の第2ベクトルに対応する2以上のノードを含む第2有向グラフを生成しながら、揮発性メモリ内に、2以上の第2ベクトルのそれぞれを示す第3情報片の群が記録された第2ベクトルデータベースを生成することを含む。管理方法は、第1情報片の群および第3情報片の群のうちの1つの情報片を更新または設定することによって第1有向グラフと第2有向グラフとを結合して、第2ベクトルデータベースをストレージデバイスに格納することを含む。
【選択図】図7
特許請求の範囲【請求項１】
複数の第１ベクトルのそれぞれを示す第１情報片の群が記録された第１ベクトルデータベースをストレージデバイスに格納することと、前記複数の第１ベクトルは第１有向グラフを構成する複数のノードに対応し、前記第１情報片の群に含まれるそれぞれの第１情報片は前記複数の第１ベクトルのうちの１つと隣接ノードに対応するベクトルを示す第２情報片とを含み、
２以上の第２ベクトルに対応する２以上のノードを含む第２有向グラフを生成しながら、揮発性メモリ内に、前記２以上の第２ベクトルのそれぞれを示す第３情報片の群が記録された第２ベクトルデータベースを生成することと、前記第３情報片の群に含まれるそれぞれの第３情報片は前記２以上の第２ベクトルのうちの１つと隣接ノードに対応するベクトルを示す第４情報片とを含み、
前記第１情報片の群および前記第３情報片の群のうちの少なくとも１つの情報片を更新または設定することによって前記第１有向グラフと前記第２有向グラフとを結合することと、
前記第２ベクトルデータベースを前記ストレージデバイスに格納することと、
を含む管理方法。
続きを表示（約 1,500 文字）【請求項２】
前記第１有向グラフと前記第２有向グラフとを結合することは、前記第１情報片の群および前記第３情報片の群のうちの、前記第１有向グラフと前記第２有向グラフとの境界を挟んで互いに隣接する２つのノードのうちの上流側のノードに対応する情報片、を更新または設定することを含む、
請求項１に記載の管理方法。
【請求項３】
前記第２ベクトルデータベースを生成することは、前記第１有向グラフと前記第２有向グラフとを結合することを含み、
前記第２ベクトルデータベースが前記揮発性メモリに格納されているときにクエリが入力された場合、前記ストレージデバイス内の前記第１ベクトルデータベースと前記揮発性メモリ内前記第２ベクトルデータベースとに基づき、前記クエリに最も近いベクトルを探索すること、
をさらに含む、
請求項１または請求項２に記載の管理方法。
【請求項４】
前記第２ベクトルデータベースが前記揮発性メモリに格納されているときにクエリが入力された場合、
前記ストレージデバイス内の前記第１ベクトルデータベースに基づく前記クエリに最も近いベクトルの探索と、前記揮発性メモリ内前記第２ベクトルデータベースに基づく前記クエリに最も近いベクトルの探索と、を実行することと、
前記ストレージデバイス内の前記第１ベクトルデータベースに基づく探索の結果と、前記揮発性メモリ内前記第２ベクトルデータベースに基づく探索の結果と、に基づき前記クエリに最も近いベクトルを特定することと、
をさらに含む、
請求項１または請求項２に記載の管理方法。
【請求項５】
前記ストレージデバイスは、複数の単位記憶領域を備え、前記複数の単位記憶領域のそれぞれは前記ストレージデバイスにおけるデータのライトおよびリードの単位に対応し、
前記第１ベクトルデータベースをストレージデバイスに格納することは、前記複数の単位記憶領域のうちの１つ当たりに前記第１情報片の群に含まれる整数個の第１情報片を格納することを含み、
前記第２ベクトルデータベースを前記ストレージデバイスに格納することは、前記複数の単位記憶領域のうちの１つ当たりに前記第３情報片の群に含まれる整数個の第３情報片を格納することを含む、
請求項１に記載の管理方法。
【請求項６】
複数の第１ベクトルのそれぞれを示す第１情報片の群が記録された第１ベクトルデータベースが格納され、前記複数の第１ベクトルは第１有向グラフを構成する複数のノードに対応し、前記第１情報片の群に含まれるそれぞれの第１情報片は前記複数の第１ベクトルのうちの１つと隣接ノードに対応するベクトルを示す第２情報片とを含む、ストレージデバイスと、
揮発性メモリと、
２以上の第２ベクトルに対応する２以上のノードを含む第２有向グラフを生成しながら、前記揮発性メモリ内に、前記２以上の第２ベクトルのそれぞれを示す第３情報片の群が記録された第２ベクトルデータベースを生成することと、前記第３情報片の群に含まれるそれぞれの第３情報片は前記２以上の第２ベクトルのうちの１つと隣接ノードに対応するベクトルを示す第４情報片とを含み、
前記第１情報片の群および前記第３情報片の群のうちの少なくとも１つの情報片を更新または設定することによって前記第１有向グラフと前記第２有向グラフとを結合することと、
前記第２ベクトルデータベースを前記ストレージデバイスに格納することと、
を実行するように構成されたプロセッサと、
を備えるデータベース装置。

発明の詳細な説明【技術分野】
【０００１】
本実施形態は、管理方法およびデータベース装置に関する。
続きを表示（約 2,500 文字）【背景技術】
【０００２】
データをベクトル形式で管理するベクトルデータベースがある。ベクトルデータベースは、近似近傍探索（Approximate Nearest Neighbor Search : ANNS）などの探索動作を可能にする。ＡＮＮＳのアルゴリズムの一例として、ＤｉｓｋＡＮＮ（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）１４、およびバス１５を備える。プロセッサ１１、インタフェース１２、ＳＳＤ１３、およびＤＲＡＭ１４は、バス１５を介して相互に電気的に接続される。
（【００１１】以降は省略されています）

関連特許