(57)【要約】【課題】検索処理の効率を改善する。【解決手段】本願に係る演算装置は、クエリ情報を受付ける受付部と、主記憶装置に設定された複数のページであって、検索対象情報のグラフを近傍検索の範囲として推定された領域ごとに分割した分割グラフが登録されたページのうち、前記クエリ情報と対応する分割グラフが登録されたページを示すページ情報を特定する特定部と、前記特定部により特定されたページ情報が示すページから、前記分割グラフを読み出す読出部と、前記読出部により読み出された分割グラフを用いて、前記クエリ情報と類似する情報を検索する検索部とを有することを特徴とする。【選択図】図１
2019200724.tif 000002
【特許請求の範囲】
【請求項１】
クエリ情報を受付ける受付部と、
主記憶装置に設定された複数のページであって、検索対象情報のグラフを近傍検索の範囲として推定された領域ごとに分割した分割グラフが登録されたページのうち、前記クエリ情報と対応する分割グラフが登録されたページを示すページ情報を特定する特定部と、
前記特定部により特定されたページ情報が示すページに登録された前記分割グラフを用いて、前記クエリ情報と類似する情報を検索する検索部と
を有することを特徴とする演算装置。
【請求項２】
前記特定部は、グラフラプラシアンに基づいて分割された分割グラフが登録されたページのうち、前記クエリ情報と対応する分割グラフが登録されたページを示すページ情報を特定する
ことを特徴とする請求項１に記載の演算装置。
【請求項３】
前記演算装置は、プログラムにより実行する処理を設定可能な第１演算装置と、所定の命令セットを実行する第２演算装置とを有し、
前記第１演算装置は、前記受付部と、前記特定部として動作し、
前記第２演算装置は、前記検索部として動作する
ことを特徴とする請求項１または２に記載の演算装置。
【請求項４】
グラフラプラシアンに基づいて、前記検索対象情報のグラフを複数の分割グラフに分割する分割部と、
前記分割部により分割された各分割グラフが登録された前記主記憶装置の物理ページ番号と、前記検索部が検索処理に用いる仮想ページ番号とを対応付けたページテーブルを生成する生成部と
を有し、
前記特定部は、前記ページ情報として、前記クエリ情報と対応する分割グラフが登録されたページの仮想ページ番号を特定し、
前記検索部は、前記ページテーブルを用いて、前記特定部により特定された仮想ページ番号と対応付けられた物理ページ番号を特定し、特定した物理ページ番号が示すページから読み出した前記分割グラフを用いて、前記クエリ情報と類似する情報を検索する
ことを特徴とする請求項１〜３のうちいずれか１つに記載の演算装置。
【請求項５】
演算装置が実行する検索方法であって、
クエリ情報を受付ける受付工程と、
主記憶装置に設定された複数のページであって、検索対象情報のグラフを近傍検索の範囲として推定された領域ごとに分割した分割グラフが登録されたページのうち、前記クエリ情報と対応する分割グラフが登録されたページを示すページ情報を特定する特定工程と、
前記特定工程により特定されたページ情報が示すページに登録された前記分割グラフを用いて、前記クエリ情報と類似する情報を検索する検索工程と
を含むことを特徴とする検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算装置、および検索方法に関する。
【背景技術】
【０００２】
従来、種々の情報を検索する技術が知られている。このような技術の一例として、検索対象となる情報（以下、「検索対象情報」と記載する。）が配置された多次元空間内を複数の領域に分割し、クエリ情報と類似する情報をクエリ情報と対応する領域から検索する技術が知られている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平１０−１２４５２８号公報
【非特許文献】
【０００４】
【非特許文献１】“グラフ分割と固有値問題”，川本  達郎,  日本神経回路学会誌  Ｖｏｌ．２１，Ｎｏ．４（２０１４），１６２−１６９＜インターネット＞https://www.jstage.jst.go.jp/article/jnns/21/4/21_162/_pdf（平成３０年５月１日検索）
【非特許文献２】“ページング方式”＜インターネット＞http://mt-net.vis.ne.jp/ADFE_mail/0126.htm（平成３０年５月１日検索）
【非特許文献３】“ＦＰＧＡのしくみと開発に使うソフトとハード”，丹下  昌彦＜インターネット＞http://toragi.cqpub.co.jp/Portals/0/backnumber/2009/03/p096-097.pdf（平成３０年５月１日検索）
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述した技術では、検索処理における効率を改善する余地がある。
【０００６】
例えば、グラフ構造を有する検索対象情報のうち、クエリ情報と概念が類似する検索対象情報を検索する近傍検索の技術が知られている。このような近傍検索においても、検索対象とする検索対象情報を限定することで、検索の効率を図ることができると考えられる。しかしながら、上述した技術では、単純に多次元空間を複数の領域に分割しているに過ぎないため、グラフ構造を適切に分割することが難しい。このため、必ずしも検索処理における効率を改善することができない場合がある。
【０００７】
本願は、上記に鑑みてなされたものであって、検索処理の効率を改善することを目的とする。
【課題を解決するための手段】
【０００８】
本願に係る演算装置は、クエリ情報を受付ける受付部と、主記憶装置に設定された複数のページであって、検索対象情報のグラフを近傍検索の範囲として推定された領域ごとに分割した分割グラフが登録されたページのうち、前記クエリ情報と対応する分割グラフが登録されたページを示すページ情報を特定する特定部と、前記特定部により特定されたページ情報が示すページから、前記分割グラフを読み出す読出部と、前記読出部により読み出された分割グラフを用いて、前記クエリ情報と類似する情報を検索する検索部とを有することを特徴とする。
【発明の効果】
【０００９】
実施形態の一態様によれば、検索処理の効率を改善することができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、演算装置が実行する検索処理の一例について説明する図である。
【図２】図２は、実施形態に係る分割グラフの情報の一例を示す図である。
【図３】図３は、実施形態に係る検索対象データベースに登録される情報の一例を示す図である。
【図４】図４は、ページテーブルに登録される情報の一例を示す図である。
【図５】図５は、実施形態に係る判定処理の流れの一例を説明するフローチャートである。
【発明を実施するための形態】
【００１１】
以下に、本願に係る演算装置、および検索方法を実施するための形態（以下、「実施形態」と記載する。）について図面を参照しつつ詳細に説明する。なお、この実施形態により本願に係る演算装置、および検索方法が限定されるものではない。また、以下の各実施形態において同一の部位には同一の符号を付し、重複する説明は省略される。
【００１２】
［実施形態］
〔１．演算装置の一例〕
まず、図１を用いて、演算装置が実行する検索処理の一例について説明する。なお、以下の説明では、近傍検索によりクエリ情報と類似する情報を検索する処理の一例について説明する。より具体的には、以下の説明では、検索対象情報と対応するノードを、検索対象情報同士の類似性に応じて接続したグラフを用いて、近傍検索を実行する処理の一例について説明する。
【００１３】
図１は、実施形態に係る演算装置が有する機能構成の一例を示す図である。図１では、演算装置１００は、以下に説明する検索処理を実行する演算装置である。ここで、演算装置１００は、製造後に利用者が内部の論理回路を定義あるいは変更することができる集積回路であり、所謂うＰＬＤ（Programmable  Logic  Device）である。より具体的には、演算装置１００は、ＦＰＧＡ（Field-Programmable  Gate  Array）により実現される。また、演算装置１００は、外部装置ＯＡおよび主記憶装置２００と接続されている。
【００１４】
主記憶装置２００は、各種データを記憶する記憶装置であり、例えば、ＲＡＭ（Random  Access  Memory)、フラッシュメモリ（Flash  Memory）等の半導体メモリ素子等の記憶装置によって実現される。
【００１５】
ここで、主記憶装置２００には、ページと呼ばれる複数の記憶領域が設定されており、ページ単位でデータの読出しおよび書込みが行われる。例えば、主記憶装置２００には、ページｍ１〜ページｍ４が設定されており、各ページｍ１〜ｍ４には、それぞれ、近傍検索に用いるグラフを分割した分割グラフＧ１〜Ｇ４が登録されている。また、主記憶装置２００には、分割グラフＧ１〜Ｇ４とは別に、検索対象情報が登録される検索対象データベース２０１が保持されている。
【００１６】
例えば、図２は、実施形態に係る分割グラフの情報の一例を示す図である。図２に示すように、分割グラフＧ１には、「ノードＩＤ」、「データＩＤ」、「エッジ情報」および「接続先」といった項目が含まれている。ここで、「ノードＩＤ」とは、分割グラフに含まれるノードを識別するための識別子である。また、「データＩＤ」とは、対応付けられた「ノードＩＤ」が示すノードと対応する検索対象情報を識別する識別子である。また、エッジ情報とは、ノード同士を接続するエッジを識別する識別子である。また、「接続先」とは、対応付けられた「ノードＩＤ」が示すノードとエッジにより接続された他のノードのノードＩＤである。
【００１７】
例えば、図２に示す例では、ノードＩＤ「Ｎ１」、データＩＤ「Ｄ１」、エッジ情報「Ｅ１２」および接続先「Ｎ２」といった情報が対応付けて登録されている。このような情報は、ノードＩＤ「Ｎ１」が示すノードが、検索対象情報のうちデータＩＤ「Ｄ１」が示す検索対象情報と対応するノードであり、エッジ情報「Ｅ１２」が示すエッジにより、接続先「Ｎ２」が示すノード、すなわち、ノードＩＤ「Ｎ２」が示すノードと接続されている旨を示す。
【００１８】
また、図３は、実施形態に係る検索対象データベースに登録される情報の一例を示す図である。図３に示すように、検索対象データベース２０１には、「データＩＤ」および「検索対象情報」が対応付けて登録されている。ここで、「検索対象情報」とは、検索対象情報のデータである。なお、図３に示す例では、検索対象情報として「データ＃１」といった概念的な値を記載したが、実際には、検索対象となる情報の各種データが登録される。
【００１９】
例えば、図３に示す例では、データＩＤ「Ｄ１」および検索対象情報「データ＃１」が対応付けて登録されている。このような情報は、データＩＤ「Ｄ１」が示す検索対象情報が、「データ＃１」である旨を示す。
【００２０】
図１に戻り、説明を続ける。例えば、演算装置１００は、プロセッサ１１０、入出力装置１２０、メモリコントローラ１３０、記憶部１４０およびＦＰＧＡ１５０を有する。プロセッサ１１０は、演算装置１００が有するプロセッサであり、例えば、ＡＲＭアーキテクチャやＰＯＷＥＲアーキテクチャを採用したプロセッサ若しくはマイクロプロセッサである。そして、プロセッサ１１０は、ＦＰＧＡ１５０と連携することで、各種の演算処理を実行する。
【００２１】
例えば、プロセッサ１１０は、プロセッサコア１１１とキャッシュメモリ１１２とを有する。プロセッサコア１１１は、論理演算や四則演算を実現する所謂コアであり、ＡＬＵ（Arithmetic  Logic  Unit）から構成される算術論理演算装置により実現される。キャッシュメモリ１１２は、プロセッサ１１０が有する補助記憶装置である。より具体的には、キャッシュメモリ１１２は、主記憶装置２００よりもプロセッサコア１１１が高速にアクセスすることができる記憶装置であり、所謂キャッシュメモリである。
【００２２】
入出力装置１２０は、演算装置１００と外部装置ＯＡとの間の通信を中継する装置であり、所謂Ｉ／Ｏ（Input  Output）装置である。例えば、入出力装置１２０は、ＵＳＢ（Universal  Serial  Bus）、イーサーネット、ＳＤ（Secure  Digital）、ＵＡＲＴ（Universal  Asynchronous  Receiver/Transmitter）、ＳＰＩ（Serial  Peripheral  Interface）、Ｉ２Ｃ、ＧＰＩＯ（General-purpose  input/output）等、各種の通信規格に沿って外部装置ＯＡとの間の通信を制御する各種の入出力装置により実現される。
【００２３】
メモリコントローラ１３０は、演算装置１００による主記憶装置２００へのメモリアクセスを制御する。より具体的には、メモリコントローラ１３０は、ページング方式により主記憶装置２００に格納されたデータの読み出しや書込みを行う。
【００２４】
記憶部１４０は、ＲＡＭ（Random  Access  Memory)、フラッシュメモリ（Flash  Memory）等の半導体メモリ素子等の記憶装置によって実現される。記憶部１４０は、ページテーブル１４１を有する。ページテーブル１４１には、仮想アドレスと物理アドレスとが対応付けて登録されている。
【００２５】
例えば、図４は、ページテーブルに登録される情報の一例を示す図である。図４に示すように、ページテーブル１４１には、「仮想ページ番号」と「物理ページ番号」とが対応付けて登録されている。ここで、「仮想ページ番号」とは、プロセッサコア１１１が各種演算処理の対象となるデータが登録された記憶領域を指定する際に用いる仮想アドレスである。また、「物理ページ番号」とは、主記憶装置２００が有する記憶領域を示す物理アドレスである。
【００２６】
例えば、図４に示す例では、仮想ページ番号「ページｓ１」と物理ページ番号「ページｍ１」が対応付けて登録されている。このような情報は、例えば、プロセッサコア１１１が「ページｓ１」を用いて指定する情報が、主記憶装置２００が有する記憶領域のうち、「ページｍ１」によって指定される領域に格納されている旨を示す。なお、ページテーブル１４１は、例えば、各仮想ページ番号が示す記憶領域を用いて演算処理を実行するアプリケーションの識別子が登録されていてもよい。
【００２７】
図１に戻り、説明を続ける。例えば、図１に示す構成を有する場合、プロセッサコア１１１は、キャッシュメモリ１１２にアクセスし、演算対象となるデータの取得を試行する。そして、プロセッサコア１１１は、データがキャッシュメモリ１１２に格納されていない場合（すなわち、キャッシュミス）は、メモリコントローラ１３０に対して、演算対象となるデータが格納されている記憶領域のアドレスを通知する。より具体的には、プロセッサコア１１１は、演算処理に用いる仮想アドレスをメモリコントローラ１３０に通知する。
【００２８】
このような場合、メモリコントローラ１３０は、仮想アドレスと、主記憶装置２００が有する記憶領域のうち仮想アドレスと対応する情報が格納された記憶領域を示す物理アドレスとを対応付けたページテーブル１４１を参照し、アクセス対象となる物理アドレスを特定する。そして、メモリコントローラ１３０は、主記憶装置２００が有する記憶領域のうち、特定した物理アドレスが示す記憶領域に格納されたデータを読出す。その後、メモリコントローラ１３０は、読み出したデータと仮想アドレスとを対応付けてキャッシュメモリ１１２に登録する。
【００２９】
また、メモリコントローラ１３０は、キャッシュメモリ１１２に登録されたデータを主記憶装置２００に書き戻す場合（ライトバック）は、ページテーブルを参照し、書き戻しの対象となる情報と対応付けられた仮想アドレスと対応する物理アドレスを特定する。そして、メモリコントローラ１３０は、主記憶装置２００の記憶領域のうち、特定した物理アドレスが示す記憶領域に書き戻しの対象となる情報を格納する。
【００３０】
ＦＰＧＡ１５０は、外部装置ＯＡからの指示に従って、回路構成を変更可能な演算装置である。例えば、ＦＰＧＡ１５０は、デジタル回路要素とアナログ回路要素とを含む。例えば、ＦＰＧＡ１５０には、プログラム可能な論理コンポーネントである複数の論理ブロックを有し、論理ブロック間が再構成可能な配線により相互接続されている。そして、ＦＰＧＡ１５０は、外部装置ＯＡから受付けたハードウェア記述言語（ＨＤＬ：Hardware  Description  language）により、論理コンポーネント間の配線の接続を変更することで、各種の処理をハードウェアにより実現することができる。
【００３１】
ここで、ＦＰＧＡ１５０は、外部装置ＯＡから受付けたＨＤＬに従って回路を構成することで、以下の機能構成を有する。そして、ＦＰＧＡ１５０は、以下の機能構成を用いることで、外部装置ＯＡから受付けたクエリ情報と類似する情報を検索対象情報の中から検索する処理を実行する。より具体的には、ＦＰＧＡ１５０は、以下の機能構成を用いることで、効率的な近傍検索の実行を実現する。
【００３２】
例えば、ＦＰＧＡ１５０は、分割部１６１、生成部１６２、受付部１６３、特定部１６４、および検索制御部１６５を有する。
【００３３】
分割部１６１は、グラフラプラシアンに基づいて、検索対象情報のグラフを複数の分割グラフに分割する。より具体的には、分割部１６１は、検索対象情報のグラフを、近傍検索の範囲として推定された領域ごとに分割した分割グラフに分割する。
【００３４】
例えば、分割部１６１は、入出力装置１２０を介して、検索処理の対象となる検索対象情報を受付ける。このような場合、分割部１６１は、受付けた検索対象情報を検索対象データベース２０１に登録する。なお、検索対象データベース２０１は、外部装置ＯＡから入出力装置１２０およびメモリコントローラ１３０を介して直接主記憶装置２００に登録されてもよい。
【００３５】
また、分割部１６１は、検索対象情報と対応する複数のノードを、検索対象情報の類似性に応じてエッジにより連結されたグラフを外部装置ＯＡから受付ける。すなわち、分割部１６１は、検索対象情報の類似性を示すグラフを受付ける。なお、このようなグラフは、例えば、近似ｋ最近傍グラフ等、近傍検索に用いるグラフを生成する任意のグラフ生成技術により生成されたものであってよい。
【００３６】
このような場合、分割部１６１は、グラフを複数のグラフに分割する。より具体的には、分割部１６１は、受付けたグラフを用いた近傍検索が行われる際に、近傍検索の対象となりうる範囲を推定し、推定した範囲ごとにグラフを分割した分割グラフを生成する。
【００３７】
例えば、近傍検索に用いられるグラフは、各ノード間が、各ノードと対応する検索対象情報同士の類似性に応じて連結されている。このため、類似する複数の検索対象情報と対応する複数のノード間は、エッジにより接続されやすいと考えられる。一方、適切にグラフの分割を行うため、分割グラフ感のエッジの数がなるべく小さくなり、かつ、各分割グラフの大きさ（ノードの数）がなるべく等しくなるように、グラフを複数の分割グラフに分割するための様々な手法が提案されている。このようにグラフを複数の分割グラフに分割した場合は、相互に類似する検索対象情報が同じ分割グラフに含まれやすくなると考えられる。すると、分割グラフは、近傍検索を行う際の検索範囲となる検索対象情報を示すと考えられる。
【００３８】
そこで、分割部１６１は、グラフを複数のグラフに分割する。例えば、分割部１６１は、グラフ全体を示す隣接行列を生成し、生成した隣接行列に基づいたグラフラプラシアンを設定する。そして、分割部１６１は、グラフラプラシアンを用いて検索対象情報のグラフを、推定される検索範囲ごとに分割した分割グラフを生成する（ステップＳ１）。例えば、分割部１６１は、ＲａｔｉｏＣｕｔと呼ばれる評価関数や、Ｎｃｕｔ（normalized-cut）と呼ばれる評価関数を最小化するように、グラフを複数の分割グラフに分割する。すなわち、分割部１６１は、スペクトラルクラスタリングと呼ばれる手法により、グラフを分割する。
【００３９】
例えば、分割部１６１は、上述した非特許文献１に開示された手法を用いて、グラフを複数の分割グラフに分割する。より具体的な例を挙げると、分割部１６１は、グラフを、分割グラフＧ１〜Ｇ４の４つに分割する。この結果、分割部１６１は、あるクエリ情報を取得した際に、クエリ情報と類似するか否かを判断すべき検索対象情報の範囲を示す分割グラフを生成することができる。すなわち、分割部１６１は、近傍検索の範囲を示す分割グラフを生成することができる。
【００４０】
生成部１６２は、各分割グラフが登録された主記憶装置の物理ページ番号と、検索処理に用いる仮想ページ番号とを対応付けたページテーブル１４１を生成する。例えば、生成部１６２は、検索処理を実行するアプリケーションが利用する記憶領域として、各分割グラフを登録するための記憶領域を設定するようにメモリコントローラ１３０に指示する。このような場合、メモリコントローラ１３０は、ページテーブル１４１を参照し、他のアプリケーションによって使用されていない仮想ページ番号と物理ページ番号とを特定し、特定した仮想ページ番号と物理ページ番号とを対応付けてページテーブル１４１に登録する。
【００４１】
また、生成部１６２は、メモリコントローラ１３０から割り当てられた仮想ページ番号を用いて、分割グラフを主記憶装置２００に登録する。例えば、生成部１６２は、割り当てられた仮想ページ番号と分割グラフのデータとをメモリコントローラ１３０に提供し、仮想ページ番号と対応する物理ページ番号が示す記憶領域に、分割グラフのデータを登録させる。例えば、生成部１６２は、分割グラフＧ１を物理ページ番号が「ページｍ１」となる記憶領域に登録させ、分割グラフＧ２を物理ページ番号が「ページｍ２」となる記憶領域に登録させ、分割グラフＧ３を物理ページ番号が「ページｍ３」となる記憶領域に登録させ、分割グラフＧ４を物理ページ番号が「ページｍ４」となる記憶領域に登録させる。
【００４２】
なお、生成部１６２は、１つのページに１つの分割グラフのデータを登録する必要はない。例えば、生成部１６２は、１つの分割グラフのデータのデータ長によっては、１つの分割グラフのデータを複数のページに登録してもよい。このような処理の結果、生成部１６２は、各分割グラフが登録された主記憶装置２００の記憶領域を示す物理アドレスと、各分割グラフが登録された主記憶装置２００の記憶領域を示す際にプロセッサコア１１１が用いる仮想アドレスとを対応付けたページテーブル１４１を作成することができる。
【００４３】
そして、ＦＰＧＡ１５０は、分割グラフを用いた近傍検索を実行する。例えば、受付部１６３は、クエリ情報を受付ける。より具体的には、受付部１６３は、入出力装置１２０を介して、外部装置ＯＡからクエリ情報を受付ける。このような場合、受付部１６３は、クエリ情報を特定部１６４に提供する。
【００４４】
特定部１６４は、主記憶装置に設定された複数のページであって、検索対象情報のグラフを近傍検索の範囲として推定された領域ごとに分割した分割グラフが登録されたページのうち、クエリ情報と対応する分割グラフが登録されたページを示すページ情報を特定する。すなわち、特定部１６４は、グラフラプラシアンに基づいて分割された分割グラフが登録されたページのうち、クエリ情報と対応する分割グラフが登録されたページを示すページ情報を特定する。例えば、特定部１６４は、ページ情報として、クエリ情報と対応する分割グラフが登録されたページの仮想ページ番号を特定する。
【００４５】
例えば、ＦＰＧＡ１５０においては、論理ブロックとして、ＦＰＧＡ１５０の入出力を制御する入出力ブロックと各種の演算処理を実行するロジックセルとが含まれる。このようなロジックセルは、ＬＵＴ（Look  Up  Table）とレジスタとにより構成されており、入力されたデータを、ＬＵＴに基づいて変換したデータを出力する（例えば、非特許文献３参照）。そこで、ＦＰＧＡ１５０は、ロジックセルが有するＬＵＴを書換えることで、入力されたクエリ情報と対応する分割グラフが登録されたページの仮想ページ番号を特定する。より具体的には、ＦＰＧＡ１５０は、クエリ情報のデータ列を入力した際に、検索すべき範囲の分割グラフが登録された仮想ページ番号を出力するように、ＬＵＴを書換えることで、特定部１６４を実現する。
【００４６】
例えば、生成部１６２は、分割グラフごとに、その分割グラフを用いて近傍検索を行うクエリ情報（以下、「対応クエリ情報」と記載する。）の範囲を特定する。例えば、生成部１６２は、に含まれるノードと対応する検索対象情報の範囲を、対応クエリ情報の範囲としてもよい。また、生成部１６２は、分割グラフに含まれるノードからルートノードとなるノードを選択し、選択したノードと対応する検索対象情報との類似度が所定の範囲に収まる対応クエリ情報の範囲を特定してもよい。
【００４７】
そして、生成部１６２は、ある分割グラフの対応クエリ情報の範囲が入力された際に、その分割グラフが登録された記憶領域の仮想ページ番号を出力するＬＵＴを生成する。すなわち、生成部１６２は、クエリ情報のデータを、そのクエリ情報と類似する検索対象情報と対応するノードを含む分割グラフが登録された記憶領域を示す仮想ページ番号へとデコードするためのＬＵＴを生成する。そして、生成部１６２は、特定部１６４として動作するロジックセルに設定する。このような処理の結果、特定部１６４は、入力されたクエリ情報と対応する分割グラフの仮想ページ番号を特定することができる。
【００４８】
続いて、検索制御部１６５は、プロセッサコア１１１を検索処理を実行する検索部として動作させることで、クエリ情報と類似する検索対象情報を検索させる。例えば、検索制御部１６５は、特定部１６４により特定された仮想ページ番号をプロセッサコア１１１に提供し、仮想ページ番号が示す記憶領域に登録された分割グラフを読み出させる。そして、検索制御部１６５は、分割グラフを用いて、クエリ情報と類似する検索対象情報をプロセッサコア１１１に検索させる。
【００４９】
例えば、検索制御部１６５は、特定部１６４により特定された仮想ページ番号をプロセッサコア１１１に提供する。このような場合、プロセッサコア１１１は、仮想ページ番号をメモリコントローラ１３０に提供する。すると、メモリコントローラ１３０は、仮想ページ番号と対応付けられた物理ページ番号をページテーブル１４１から特定し、特定した物理ページ番号が示す記憶領域に登録された分割グラフを読み出す。そして、メモリコントローラ１３０は、読み出した分割グラフをキャッシュメモリ１１２に登録する。
【００５０】
また、検索制御部１６５は、クエリ情報をプロセッサコア１１１に提供する。なお、検索制御部１６５は、クエリ情報をキャッシュメモリ１１２を介してプロセッサコア１１１に提供してもよい。このような場合、プロセッサコア１１１は、キャッシュメモリ１１２から分割グラフを読出し、読み出した分割グラフに含まれるノードと対応する検索対象情報のデータを検索対象データベース２０１から読み出す。そして、プロセッサコア１１１は、読み出したデータのうち、クエリ情報と類似するデータを特定し、特定したデータを、入出力装置１２０を介して、外部装置ＯＡへと送信する。
【００５１】
このように、演算装置１００は、プログラムにより実行する処理を設定可能な第１演算装置であるＦＰＧＡ１５０と、所定の命令セットを実行する第２演算装置であるプロセッサ１１０とを有する。そして、ＦＰＧＡ１５０は、受付部１６３および特定部１６４として動作し、プロセッサ１１０は、検索処理を実行する検索部として動作する。ここで、ＦＰＧＡ１５０は、検索対象情報の類似性を示すグラフを、近傍検索の範囲として推定されうる複数の分割グラフに分割し、分割グラフをそれぞれ個別のページに登録する。そして、ＦＰＧＡ１５０は、クエリ情報と対応する分割グラフを特定し、特定した分割グラフが登録されたページの情報を読み出す。
【００５２】
このような処理の結果、演算装置１００は、全検索対象情報のうち、検索範囲とすべきであると推定される検索対象情報を示す分割グラフを用いて、近傍検索を実行することができる。この結果、演算装置１００は、検索処理を効率化することができる。
【００５３】
〔２．演算装置が実行する処理の流れの一例〕
次に、図５を用いて、演算装置１００が実行する演算処理の流れの一例について説明する。図５は、実施形態に係る判定処理の流れの一例を説明するフローチャートである。まず、演算装置１００は、検索対象情報のグラフを取得する（ステップＳ１０１）。このような場合、演算装置１００は、近傍検索の範囲を推定し、推定した領域ごとに分割した分割グラフを生成する（ステップＳ１０２）。そして、演算装置１００は、主記憶装置２００の各ページに分割グラフを登録する（ステップＳ１０３）。
【００５４】
また、演算装置１００は、主記憶装置２００の物理ページ番号と、演算処理に用いる仮想ページ番号とを対応付けたページテーブル１４１を生成する（ステップＳ１０４）。そして、演算装置１００は、クエリ情報を受付けたか否かを判定し（ステップＳ１０５）、受付けていない場合は（ステップＳ１０５：Ｎｏ）、クエリ情報を受付けるまで待機する。また、演算装置１００は、クエリ情報を受付けた場合は（ステップＳ１０５：Ｙｅｓ）、クエリ情報に対応する分割グラフを特定する（ステップＳ１０６）。例えば、演算装置１００は、各分割グラフが登録された記憶領域を示す仮想ページ番号と、各分割グラフが示す検索対象情報を検索の対象とすべきクエリ情報の範囲とを対応付けたＬＵＴを用いて、クエリ情報から、対応する仮想ページ番号を特定する。
【００５５】
また、演算装置１００は、ページテーブルを用いて、対応する分割グラフを読み出す（ステップＳ１０７）。そして、演算装置１００は、読み出した分割グラフをプロセッサのキャッシュメモリに登録し（ステップＳ１０８）、近傍検索処理を実行して（ステップＳ１０９）、処理を終了する。
【００５６】
〔３．変形例〕
上記では、演算装置１０による検索処理の一例について説明した。しかしながら、実施形態は、これに限定されるものではない。以下、演算装置１０が実行する検索処理のバリエーションについて説明する。
【００５７】
〔３−１．装置構成〕
上述した例では、ＦＰＧＡ１５０を含む演算装置１００により実行される検索処理の一例について記載した。しかしながら、実施形態は、これに限定されるものではない。例えば、上述した検索処理は、ＦＰＧＡ１５０以外にも、ＣＰＵ（Central  Processing  Unit）、ＭＰＵ（Micro  Processing  Unit）等のプロセッサによって実現されてもよい。また、上述した検索処理は、ＡＳＩＣ（Application  Specific  Integrated  Circuit）等の集積回路により実現されてもよい。
【００５８】
すなわち、上述した検索処理は、プログラム可能な論理回路を有さない演算処理装置であって、ページング方式を用いる各種の演算処理装置により実現されてもよい。このような演算処理装置は、例えば、検索対象情報の類似性を示すグラフを、検索対象として推定されうる範囲ごとに分割したグラフを生成し、生成したグラフをそれぞれ個別のページに登録する。このような処理の結果、演算処理装置は、検索対象とする範囲を適切に限定するとともに、検索対象とする範囲の特定を高速化することができる。
【００５９】
また、演算装置１００は、分割部１６１を有さず、グラフの分割を行わずともよい。例えば、演算装置１００は、グラフラプラシアン等を用いて分割が行われた分割グラフを外部装置ＯＡから受付けた場合、受付けた分割グラフを主記憶装置２００の各ページに登録し、このような分割グラフを用いた検索を行ってもよい。
【００６０】
〔３−２．その他〕
また、上記実施形態において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。この他、上記文章中や図面中で示した処理手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。例えば、各図に示した各種情報は、図示した情報に限られない。
【００６１】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。
【００６２】
また、上記してきた各実施形態は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。
【００６３】
〔４．効果〕
上述したように、演算装置１００は、クエリ情報を受付けると、主記憶装置２００に設定された複数のページであって、検索対象情報のグラフを近傍検索の範囲として推定された領域ごとに分割した分割グラフが登録されたページのうち、クエリ情報と対応する分割グラフが登録されたページを示すページ情報を特定する。そして、演算装置１００は、特定されたページ情報が示すページに登録された分割グラフを用いて、クエリ情報と類似する情報を検索する。このため、演算装置１００は、検索処理における効率を改善することができる。
【００６４】
また、演算装置１００は、グラフラプラシアンに基づいて分割された分割グラフが登録されたページのうち、クエリ情報と対応する分割グラフが登録されたページを示すページ情報を特定する。このため、演算装置１００は、クエリ情報との比較対象として適切な検索対象情報の範囲を示す分割グラフを用いて、検索処理を実行することができる。
【００６５】
また、演算装置１００は、プログラムにより実行する処理を設定可能な第１演算装置であるＦＰＧＡ１５０と、所定の命令セットを実行する第２演算装置であるプロセッサ１１０とを有し、第１演算装置は、受付部１６３と、特定部１６４として動作し、第２演算装置は、検索処理を実行する検索部として動作する。このため、演算装置１００は、検索処理における効率を改善することができる。
【００６６】
また、演算装置１００は、グラフラプラシアンに基づいて、検索対象情報のグラフを複数の分割グラフに分割する。また、演算装置１００は、分割された各分割グラフが登録された主記憶装置２００の物理ページ番号と、検索処理に用いる仮想ページ番号とを対応付けたページテーブル１４１を生成する。そして、演算装置１００は、クエリ情報と対応する分割グラフが登録されたページの仮想ページ番号を特定し、ページテーブル１４１を用いて、特定された仮想ページ番号と対応付けられた物理ページ番号を特定し、特定した物理ページ番号が示すページから読み出した分割グラフを用いて、クエリ情報と類似する情報を検索する。このため、演算装置１００は、検索処理における効率を改善することができる。
【００６７】
以上、本願の実施形態のいくつかを図面に基づいて詳細に説明したが、これらは例示であり、発明の開示の欄に記載の態様を始めとして、当業者の知識に基づいて種々の変形、改良を施した他の形態で本発明を実施することが可能である。
【００６８】
また、上記してきた「部（section、module、unit）」は、「手段」や「回路」などに読み替えることができる。例えば、生成部は、生成手段や生成回路に読み替えることができる。
【符号の説明】
【００６９】
１００  演算装置
１１０  プロセッサ
１１１  プロセッサコア
１１２  キャッシュメモリ
１２０  入出力装置
１３０  メモリコントローラ
１４０  記憶部
１４１  ページテーブル
１５０  ＦＰＧＡ
１６１  分割部
１６２  生成部
１６３  受付部
１６４  特定部
１６５  検索制御部
２００  主記憶装置
２０１  検索対象データベース
Ｇ１〜Ｇ４  分割グラフ
ＯＡ  外部装置
【図１】
2019200724.tif 000003
【図２】
2019200724.tif 000004
【図３】
2019200724.tif 000005
【図４】
2019200724.tif 000006
【図５】
2019200724.tif 000007