特許ウォッチ

公開番号2025043131
公報種別公開特許公報(A)
公開日2025-03-28
出願番号2023150461
出願日2023-09-15
発明の名称情報処理装置、情報処理システム、及び情報処理方法
出願人キオクシア株式会社
代理人弁理士法人鈴榮特許綜合事務所
主分類G06F 16/908 20190101AFI20250321BHJP(計算;計数)
要約【課題】探索精度の劣化を抑制し、かつレイテンシを低減する。
【解決手段】実施形態の情報処理装置は、クエリベクトルを受信する回路と、回路を介して受信したクエリベクトルと、複数のポスティングリストそれぞれに関連付けられた複数の代表ベクトルのそれぞれとの距離に基づいて、第1数の選択ポスティングリストを決定し、複数の探索用データのうち、第1数の選択ポスティングリストそれぞれに関連する第1数の選択データを受信し、第1数の選択データが、圧縮されたポスティングリストを含む場合に、圧縮されたポスティングリストの解凍を実行し、第1数の選択データに対応する第1数の選択ポスティングリストに含まれる複数のベクトルのそれぞれとクエリベクトルとの距離に基づいて、第1数の選択ポスティングリストに含まれる複数のベクトルのうち少なくとも1つのベクトルを回答として出力するように構成された第1プロセッサと、を備える。
【選択図】図6
特許請求の範囲【請求項１】
複数の探索用データを記憶するように構成されたストレージを利用して、クエリベクトルに対する回答を出力するように構成された情報処理装置であって、
前記複数の探索用データはそれぞれ、各々が複数のベクトルを格納するポスティングリストに関連し、前記複数の探索用データの各々は、圧縮されていないポスティングリスト、又は圧縮されたポスティングリストであり、
前記クエリベクトルを受信する回路と、
前記回路を介して受信した前記クエリベクトルと、複数のポスティングリストそれぞれに関連付けられた複数の代表ベクトルのそれぞれとの距離に基づいて、前記複数のポスティングリストから第１数の選択ポスティングリストを決定し、
前記複数の探索用データのうち、前記第１数の選択ポスティングリストそれぞれに関連する第１数の選択データを受信し、
前記第１数の選択データが、前記圧縮されたポスティングリストを含む場合に、前記圧縮されたポスティングリストの解凍を実行し、
前記第１数の選択データに対応する前記第１数の選択ポスティングリストに含まれる複数のベクトルのそれぞれと前記クエリベクトルとの距離に基づいて、前記第１数の選択ポスティングリストに含まれる前記複数のベクトルのうち少なくとも１つのベクトルを前記回答として出力する、ように構成された第１プロセッサと、
を備える、
情報処理装置。
続きを表示（約 2,200 文字）【請求項２】
前記ストレージは、記憶している前記複数の探索用データのうち前記圧縮されたポスティングリストに関する圧縮アルゴリズム情報をさらに記憶するように構成され、
前記第１プロセッサは、前記圧縮アルゴリズム情報に基づいて、前記圧縮された選択ポスティングリストを解凍する、
請求項１記載の情報処理装置。
【請求項３】
前記第１プロセッサは、前記複数の代表ベクトルを格納する探索用グラフに基づいて、前記複数のポスティングリストから複数の選択ポスティングリストを決定する、
請求項１記載の情報処理装置。
【請求項４】
前記代表ベクトルは、前記複数のポスティングリストのうち関連付けられたポスティングリストに含まれた前記複数のベクトルの重心に基づくベクトル、前記複数のポスティングリストのうち関連付けられたポスティングリストに含まれるベクトル、又は、前記複数のポスティングリストのうち関連付けられたポスティングリストに含まれないベクトル、である、
請求項１記載の情報処理装置。
【請求項５】
前記複数のベクトルを用いて前記複数のポスティングリストを生成し、前記複数のポスティングリストに基づいて生成された前記複数の探索用データを前記ストレージに出力する第２プロセッサをさらに備える、
請求項１乃至請求項４のいずれか一項記載の情報処理装置。
【請求項６】
前記ストレージを更に備える、
請求項１乃至請求項４のいずれか一項記載の情報処理装置。
【請求項７】
請求項１乃至請求項４のいずれか一項記載の前記情報処理装置と、
前記ストレージと、
前記複数のベクトルを用いて前記複数のポスティングリストを生成し、前記複数のポスティングリストに基づいて生成された前記複数の探索用データを前記ストレージに出力する装置と、
を備える、
情報処理システム。
【請求項８】
ストレージを利用してクエリに対する回答を探索するために用いられるデータを、前記ストレージに出力するように構成された情報処理装置であって、
前記ストレージと通信するように構成された回路と、
複数のベクトルに基づいて複数の代表ベクトルを生成し、
生成された前記複数の代表ベクトルに基づいて、前記複数のベクトルを、前記複数の代表ベクトルそれぞれに対応する複数のポスティングリストに分類し、
前記複数のポスティングリストそれぞれを、圧縮の対象である対象ポスティングリスト、又は圧縮の対象でない非対象ポスティングリストに設定し、
前記対象ポスティングリストの圧縮を実行可能であり、
圧縮された前記対象ポスティングリストを含む複数の探索用データを前記回路を介して前記ストレージに送信する、ように構成されたプロセッサと、
を備える、
情報処理装置。
【請求項９】
複数の探索用データを記憶するように構成されたストレージを利用して、クエリベクトルに対する回答を出力する情報処理方法であって、
前記複数の探索用データはそれぞれ、各々が複数のベクトルを格納するポスティングリストに関連し、前記複数の探索用データの各々は、圧縮されていないポスティングリスト、又は圧縮されたポスティングリストであり、
前記クエリベクトルを受信することと、
受信した前記クエリベクトルと、複数のポスティングリストそれぞれに関連付けられた複数の代表ベクトルのそれぞれとの距離に基づいて、前記複数のポスティングリストから第１数の選択ポスティングリストを決定し、
前記複数の探索用データのうち、前記第１数の選択ポスティングリストそれぞれに関連する第１数の選択データを受信し、
前記第１数の選択データが、前記圧縮されたポスティングリストを含む場合に、前記圧縮されたポスティングリストの解凍を実行し、
前記第１数の選択データに対応する前記第１数の選択ポスティングリストに含まれる複数のベクトルのそれぞれと前記クエリベクトルとの距離に基づいて、前記第１数の選択ポスティングリストに含まれる前記複数のベクトルのうち少なくとも１つのベクトルを前記回答として出力することと、
を備える、
情報処理方法。
【請求項１０】
ストレージを利用してクエリに対する回答を探索するために用いられるデータを、前記ストレージに出力する情報処理方法であって、
複数のベクトルに基づいて複数の代表ベクトルを生成し、
生成された前記複数の代表ベクトルに基づいて、前記複数のベクトルを、前記複数の代表ベクトルそれぞれに対応する複数のポスティングリストに分類し、
前記複数のポスティングリストそれぞれを、圧縮の対象である対象ポスティングリスト、又は圧縮の対象でない非対象ポスティングリストに設定し、
前記対象ポスティングリストが設定された場合に、
前記対象ポスティングリストの少なくとも一つの圧縮を実行し、
圧縮された前記対象ポスティングリストを含む複数の探索用データを前記ストレージに送信する、
情報処理方法。

発明の詳細な説明【技術分野】
【０００１】
実施形態は、情報処理装置、情報処理システム、及び情報処理方法に関する。
続きを表示（約 2,600 文字）【背景技術】
【０００２】
ＩＴ技術を利用した業務効率化などを目的として、非構造化データの重要性が高まっている。非構造化データのデータ量は、構造化データのデータ量に比べて、大量になる傾向がある。このような大量の非構造化データから所望のデータを検索する技術として、近似最近傍探索と呼ばれる技術が知られている。近似最近傍探索では、メモリ上に置かれた複数の検索データから、入力データであるクエリに近いデータを、複数の検索データそれぞれに関連付けられたベクトル情報に基づいて検索する。近似最近傍探索では、クエリに対する厳密な近傍点を求めることは行われず、クエリに基づくクエリベクトルと、複数の検索データそれぞれのベクトル情報との間の距離を計算することで、クエリベクトルの近傍のベクトル情報が探索される。以上のような近似最近傍探索において、検索データ量、及びメモリコストの増大に伴い、一部の検索データが、メモリよりも大容量のストレージ装置に格納された状態で実行される技術が提案されている。
【先行技術文献】
【特許文献】
【０００３】
国際公開第２０１５／０４９７３２号パンフレット
国際公開第２０２１／０４４５１９号パンフレット
【非特許文献】
【０００４】
ＱｉＣｈｅｎ，外７名，“SPANN:Highly-efficient Billion-scale Approximate Nearest Neighbor Search”，［Online］，令和３年１２月８日，ＮｅｕｒＩＰＳ２０２１，[令和５年７月６日検索]，インターネット＜ＵＲＬ：https://www.microsoft.com/en-us/research/uploads/prod/2021/11/SPANN_finalversion1.pdf＞
【発明の概要】
【発明が解決しようとする課題】
【０００５】
探索精度の劣化を抑制し、かつレイテンシを低減する情報処理装置、情報処理システム、及び情報処理方法を提供する。
【課題を解決するための手段】
【０００６】
実施形態の情報処理装置は、複数の探索用データを記憶するように構成されたストレージ装置を利用して、クエリベクトルに対する回答を出力するように構成された情報処理装置であって、上記複数の探索用データはそれぞれ、各々が複数のベクトルを格納するポスティングリストに関連し、上記複数の探索用データの各々は、圧縮されていないポスティングリスト、又は圧縮されたポスティングリストであり、上記クエリベクトルを受信する回路と、上記回路を介して受信した上記クエリベクトルと、複数のポスティングリストそれぞれに関連付けられた複数の代表ベクトルのそれぞれとの距離に基づいて、上記複数のポスティングリストから第１数の選択ポスティングリストを決定し、上記複数の探索用データのうち、上記第１数の選択ポスティングリストそれぞれに関連する第１数の選択データを受信し、上記第１数の選択データが、上記圧縮されたポスティングリストを含む場合に、上記圧縮されたポスティングリストの解凍を実行し、上記第１数の選択データに対応する上記第１数の選択ポスティングリストに含まれる複数のベクトルのそれぞれと上記クエリベクトルとの距離に基づいて、上記第１数の選択ポスティングリストに含まれる上記複数のベクトルのうち少なくとも１つのベクトルを上記回答として出力する、ように構成された第１プロセッサと、を備える。
【図面の簡単な説明】
【０００７】
ストレージ装置の利用を前提とした近似最近傍探索の概要を示す概略図。
実施形態に係る情報処理システムの構成の一例を示すブロック図。
実施形態に係る情報処理システムが備える情報処理装置のハードウェア構成の一例を示すブロック図。
実施形態に係る情報処理システムが備えるストレージ装置のハードウェア構成の一例を示すブロック図。
実施形態に係る情報処理システムの機能構成の一例を説明するためのブロック図。
実施形態に係る情報処理システムの機能構成の他の一例を説明するためのブロック図。
実施形態に係る情報処理システムにおける近似最近傍探索の全体の流れを説明するためのフローチャート。
実施形態に係る情報処理システムの近似最近傍探索におけるインデックス生成処理の一例を示すフローチャート。
実施形態に係る情報処理システムの近似最近傍探索におけるインデックス生成処理におけるポスティングリストの圧縮の一例を説明するための図。
実施形態に係る情報処理システムの近似最近傍探索におけるインデックス生成処理におけるポスティングリストの圧縮の他の一例を説明するための図。
実施形態に係る情報処理システムの近似最近傍探索におけるインデックス生成処理におけるポスティングリストの圧縮の更に他の一例を説明するための図。
実施形態に係る情報処理システムの近似最近傍探索における探索処理の処理シーケンスの一例を示すシーケンス図。
実施形態に係る情報処理システムの近似最近傍探索における探索処理の一例を示すフローチャート。
【発明を実施するための形態】
【０００８】
以下に、実施形態について図面を参照して説明する。なお、図面は、模式的又は概念的なものである。略同一の機能及び構成を有する構成要素には、同一の符号が付加されている。参照符号に付加された数字やアルファベットなどは、同じ参照符号により参照され、かつ類似した要素同士を区別するために使用される。
【０００９】
１実施形態
実施形態に係る情報処理装置、情報処理システム、及び情報処理方法は、ストレージ装置の利用を前提とした近似最近傍探索を好適に実行可能に構成される。
【００１０】
１．１実施形態におけるストレージ装置の利用を前提とした近似最近傍探索の概要
まず、実施形態におけるストレージ装置の利用を前提とした近似最近傍探索の概要について、図１を用いて説明する。図１は、ストレージ装置の利用を前提とした近似最近傍探索の概要を示す概略図である。
（【００１１】以降は省略されています）

関連特許