(57)【要約】【課題】膨大な量のデータからの検索を高速化すること。【解決手段】対象データの識別情報を記憶する領域を有する一次判定テーブルと、対象データの識別情報をリスト構造で記憶する二次判定テーブルとを備え、対象データの識別情報を第１のハッシュ関数でハッシュ化したハッシュ値に対応する一次判定テーブルのアドレスに、識別情報の登録の有無を判定し、識別情報が登録されていないと判定された場合に、所定の処理を行うこととして、一次判定テーブルのアドレスに対象データの識別情報を登録し、対象データの識別情報が登録されていると判定された場合に、対象データに関する所定の処理を不要と判定し、登録判定部により二次判定テーブルに識別情報が登録されていると判定された場合、対象データの識別情報を第２のハッシュ関数でハッシュ化したハッシュ値をキーとして二次判定テーブルを参照し、所定の処理の要否を判定する。【選択図】図１
2018049315.tif 000002
【特許請求の範囲】
【請求項１】
対象データに対する所定の処理の要否を判定するデータ管理装置であって、
前記対象データの識別情報を記憶する領域を有する一次判定テーブルと、
前記対象データの識別情報をリスト構造で記憶する二次判定テーブルと、
前記対象データの識別情報を第１のハッシュ関数でハッシュ化したハッシュ値に対応する前記一次判定テーブルのアドレスに、識別情報の登録の有無を判定し、
識別情報が登録されていないと判定された場合に、前記所定の処理を行うこととして、前記一次判定テーブルのアドレスに前記対象データの識別情報を登録し、
前記対象データの識別情報が登録されていると判定された場合に、前記対象データに関する前記所定の処理を不要と判定し、
前記登録判定部により前記二次判定テーブルに識別情報が登録されていると判定された場合、前記対象データの識別情報を第２のハッシュ関数でハッシュ化したハッシュ値をキーとして前記二次判定テーブルを参照し、前記所定の処理の要否を判定するデータ管理部と、
を備えるデータ管理装置。
【請求項２】
前記データ管理部は、前記一次判定テーブルに格納された、前記二次判定テーブルに識別情報が格納されているか否かを示すフラグを参照し、前記二次判定テーブルに識別情報が登録されているか否かを判定する、
請求項１記載のデータ管理装置。
【請求項３】
前記データ管理部は、前記対象データの識別情報を前記第２のハッシュ関数でハッシュ化したハッシュ値に対応する前記二次判定テーブルのアドレスに格納されたポインタの示すアドレスを順に辿ることにより、前記二次判定テーブルに前記対象データの識別情報が登録されているか否かを判定する、
請求項１または２記載のデータ管理装置。
【請求項４】
前記データ管理部は、前記二次判定テーブルに前記対象データの識別情報が登録されている場合に、前記所定の処理が必要であると判定する、
請求項３記載のデータ管理装置。
【請求項５】
前記第１のハッシュ関数によって得られるハッシュ値のとり得る値の数は、前記第２のハッシュ関数によって得られるハッシュ値のとり得る値の数よりも多い、
請求項１から４のうちいずれか１項記載のデータ管理装置。
【請求項６】
前記第１のハッシュ関数は、入力データのバイナリ列の下位ｎビットをハッシュ値とする関数である、
請求項１から５のうちいずれか１項記載のデータ管理装置。
【請求項７】
前記一次判定テーブルは、前記一次元の配列構造を複数有する、
請求項１から６のうちいずれか１項記載のデータ管理装置。
【請求項８】
前記所定の処理は、グラフ構造のデータを用いたデータ検索処理において、前記対象データを検索対象のノードとして、クエリに対応するノードとの距離を計算する処理である、
請求項１から７のうちいずれか１項に記載のデータ管理装置。
【請求項９】
前記一次判定テーブルの配列数は、前記検索対象のノードの数の１／１０程度の値に設定される、
請求項８記載のデータ管理装置。
【請求項１０】
対象データの識別情報を記憶する領域を有する一次判定テーブルと、前記対象データの識別情報をリスト構造で記憶する二次判定テーブルと、を有し、前記対象データに対する所定の処理の要否を判定するデータ管理装置が、
前記対象データの識別情報を第１のハッシュ関数でハッシュ化したハッシュ値に対応する前記一次判定テーブルのアドレスに、識別情報の登録の有無を判定し、
識別情報が登録されていないと判定された場合に、前記所定の処理を行うこととして、前記アドレスに前記対象データの識別情報を登録し、
前記対象データの識別情報が登録されていると判定された場合に、前記対象データに関する前記所定の処理を不要と判定し、
前記二次判定テーブルに識別情報が登録されていると判定された場合、前記対象データの識別情報を第２のハッシュ関数でハッシュ化したハッシュ値をキーとして前記二次判定テーブルを参照し、前記所定の処理の要否を判定する、
データ管理方法。
【請求項１１】
対象データの識別情報を記憶する領域を有する一次判定テーブルと、前記対象データの識別情報をリスト構造で記憶する二次判定テーブルと、を有し、前記対象データに対する所定の処理の要否を判定するデータ管理装置に、
前記対象データの識別情報を第１のハッシュ関数でハッシュ化したハッシュ値に対応する前記一次判定テーブルのアドレスに、識別情報の登録の有無を判定させ、
識別情報が登録されていないと判定された場合に、前記所定の処理を行うこととして、前記アドレスに前記対象データの識別情報を登録させ、
前記対象データの識別情報が登録されていると判定された場合に、前記対象データに関する前記所定の処理を不要と判定させ、
前記二次判定テーブルに識別情報が登録されていると判定された場合、前記対象データの識別情報を第２のハッシュ関数でハッシュ化したハッシュ値をキーとして前記二次判定テーブルを参照し、前記所定の処理の要否を判定させる、
データ管理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ管理装置、データ管理方法、およびデータ管理プログラムに関する。
【背景技術】
【０００２】
従来、ウェブブラウザやメールソフトウェアなどにおいて、膨大な量のデータから所望のデータを検索する技術が利用されている（例えば、特許文献１参照）。このような技術では、検索対象のデータごとに検索済みまたは未検索といった情報をテーブルによって管理している。例えば、検索対象のデータに対して一対一に対応したビット配列のテーブルを用意しておき、検索対象のデータが既に検索したデータであるのか否かを評価する手法が知られている。また、Ｃ言語などで実装された既存のハッシュテーブルに検索したデータの識別子を登録することで、検索対象のデータが既に検索したデータであるのか否かを評価する手法が知られている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００９−２１１２６３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従来の技術では、例えばビット配列のテーブルを利用する場合、検索対象のデータ数が増加するのに応じて、検索開始時にテーブルを初期化するのに要する時間が増加してしまう。
【０００５】
一方で、既存のハッシュテーブルを利用する場合、データの識別子同士をポインタで関連付けて管理するリスト構造のデータ構造を利用するため、データの取得に時間がかかってしまう。
【０００６】
本発明は、上記の課題に鑑みてなされたものであって、膨大な量のデータからの検索を高速化することを目的としている。
【課題を解決するための手段】
【０００７】
本発明の一態様は、対象データに対する所定の処理の要否を判定するデータ管理装置であって、前記対象データの識別情報を記憶する領域を有する一次判定テーブルと、前記対象データの識別情報をリスト構造で記憶する二次判定テーブルと、前記対象データの識別情報を第１のハッシュ関数でハッシュ化したハッシュ値に対応する前記一次判定テーブルのアドレスに、識別情報の登録の有無を判定し、識別情報が登録されていないと判定された場合に、前記所定の処理を行うこととして、前記一次判定テーブルのアドレスに前記対象データの識別情報を登録し、前記対象データの識別情報が登録されていると判定された場合に、前記対象データに関する前記所定の処理を不要と判定し、前記登録判定部により前記二次判定テーブルに識別情報が登録されていると判定された場合、前記対象データの識別情報を第２のハッシュ関数でハッシュ化したハッシュ値をキーとして前記二次判定テーブルを参照し、前記所定の処理の要否を判定するデータ管理部と、を備えるデータ管理装置である。
【発明の効果】
【０００８】
本発明の一態様によれば、膨大な量のデータからの検索を高速化することができる。
【図面の簡単な説明】
【０００９】
【図１】第１の実施形態におけるデータ管理装置１００を中心とした構成図である。
【図２】既存データオブジェクト１３２の内容の一例を示す図である。
【図３】グラフインデックス１３４のデータ構成の一例を示す図である。
【図４】インデックス検索部１１４による検索処理の内容を模式的に示す図である。
【図５】一次判定テーブル１２２のデータ構造の一例を示す図である。
【図６】二次判定テーブル１２４のデータ構造の一例を示す図である。
【図７】インデックス検索部１１４により実行される、新規オブジェクトとの距離を計算したか否かを判定する処理の流れの一例を示すフローチャートである。
【図８】インデックス検索部１１４により実行される、新規オブジェクトとの距離を計算したか否かを判定する処理の流れの一例を示すフローチャートである。
【図９】一次判定テーブル１２２の他の例を示す図である。
【発明を実施するための形態】
【００１０】
以下、本発明を適用したデータ管理装置、データ管理方法、およびデータ管理プログラムを、図面を参照して説明する。
【００１１】
［概要］
データ管理装置は、一以上のプロセッサによって実現される。データ管理装置は、例えば、インターネット検索においてユーザが所望するデータを検索する際に、既に探索したデータとそうでないデータとを判別するためのデータ管理を行う装置である。
【００１２】
（第１の実施形態）
［全体構成］
図１は、第１の実施形態におけるデータ管理装置１００を中心とした構成図である。第１の実施形態におけるデータ管理装置１００は、一以上のクライアント端末１０とネットワークＮＷを介して接続される。クライアント端末１０は、パーソナルコンピュータ、スマートフォンなどの携帯電話、タブレット端末などである。ネットワークＮＷは、無線基地局、公衆回線、専用回線、プロバイダ端末、インターネットなどを含む。ネットワークＮＷは、無線基地局、公衆回線、専用回線、プロバイダ端末、インターネットなどを含む。
【００１３】
データ管理装置１００は、クライアント端末１０からクエリデータを受信すると、クエリデータに類似するデータを検索し、検索結果のデータをクライアント端末１０に返信する。クエリデータは、例えば、クライアント端末１０において実行されるウェブブラウザの検索窓に入力されたキーワードや、データの検索条件を記述したデータなどである。データ管理装置１００が返信するデータは、データそのもの（例えば拡張子がｊｐｇなどの画像データ）であってもよいし、データを参照するための識別子（例えばＵＲＬ（Uniform Resource Locator）など）であってもよい。また、クエリデータや検索の対象データは、画像データ、音声データ、テキストデータなど、如何なる種類のデータであってもよい。
【００１４】
データ管理装置１００は、例えば、ネットワークインターフェース１０２と、入出力装置１０４と、制御部１１０と、記憶部１２０と、データサーバ１３０とを備える。ネットワークインターフェース１０２は、例えば、ＮＩＣ（Network Interface Card）である。
【００１５】
入出力装置１０４は、データ管理装置１００の管理者による入力操作を受け付ける。例えば、入出力装置１０４は、マウスやキーボード、タッチパネルなどの入力装置と、ＬＣＤ（Liquid Crystal Display）や有機ＥＬ（Electroluminescence）表示装置、スピーカなどの出力装置とを含む。
【００１６】
［制御部］
制御部１１０は、例えば、データオブジェクト生成部１１２と、インデックス検索部（データ管理部の一例）１１４とを備える。これらの制御部１１０の構成要素は、例えば、ＣＰＵ（Central Processing Unit）などのプロセッサがプログラムを実行することにより実現される。また、これらの構成要素のうち一部または全部は、ＬＳＩ（Large Scale Integration）、ＡＳＩＣ（Application Specific Integrated Circuit）、またはＦＰＧＡ（Field-Programmable Gate Array）などのハードウェアによって実現されてもよいし、ソフトウェアとハードウェアが協働して実現されてもよい。なお、制御部１１０は、一つのプロセッサにより実現される必要はなく、機能ごとに分散処理を行ってもよい。例えば、データオブジェクト生成部１１２およびインデックス検索部１１４は、それぞれ別体のプロセッサにより実現されてもよい。
【００１７】
データオブジェクト生成部１１２は、例えば、クライアント端末１０などから受信した入力データに基づいて、入力データのオブジェクトを生成する。入力データが画像である場合、オブジェクトは、例えば、局所特徴量やＢｏＦ（Bag of Features）、色のヒストグラムなど、或いはこれらの組み合わせである。また、入力データがテキストデータである場合、オブジェクトは、例えば、単語の出現頻度のベクトルデータ、ニューラルネットワークを用いて抽出した意味ベクトル、或いは、他の単語と共に出現する頻度その他の相対関係に基づくベクトルなどである。オブジェクトは、オブジェクト間の距離が定義可能であれば、如何なるデータであってもよい。
【００１８】
インデックス検索部１１４は、データサーバ１３０を検索し、データオブジェクト生成部１１２により生成されたオブジェクト（以下、新規オブジェクトと称する）に類似するオブジェクトを、既存データオブジェクト１３２から抽出する。データサーバ１３０には、例えば、既存データオブジェクト１３２と、グラフインデックス１３４とが格納される。グラフインデックス１３４は、オブジェクトを高速に検索するためのインデックスであり、エッジとオブジェクト（ノード）で構成されるグラフ構造のデータである。
【００１９】
データサーバ１３０は、ＨＤＤやフラッシュメモリなどの記憶装置により実現される。また、データサーバ１３０は、データ管理装置１００からネットワークＮＷを介してアクセス可能なＮＡＳ（Network Attached Storage）装置などの外部記憶装置により実現されてもよい。
【００２０】
データサーバ１３０には、既存データオブジェクト１３２と、グラフインデックス１３４とが格納される。既存データオブジェクト１３２やグラフインデックス１３４は、データサーバ１３０からＲＡＭ（Random Access Memory）などの高速アクセス可能なメモリに展開（ロード）されて使用される。既存データオブジェクト１３２は、検索対象となるデータから生成されたオブジェクトである。既存データオブジェクト１３２には、その既存データオブジェクト１３２を生成する元となったデータ、或いはデータを参照する識別子が対応付けられている。データ管理装置１００は、新規オブジェクトをクエリとして得られた既存オブジェクト、すなわち新規オブジェクトに類似するオブジェクトに対応付けられたデータ、或いはそのデータを参照する識別子をクライアント端末１０に送信する。
【００２１】
図２は、既存データオブジェクト１３２の内容の一例を示す図である。図示するように、既存データオブジェクト１３２は、オブジェクトの識別情報（図中、オブジェクトＩＤ）に対して、オブジェクト（図ではベクトルデータ）、およびそのオブジェクトを生成する元となったデータ、或いはデータを参照する識別子が対応付けられたデータである。
【００２２】
グラフインデックス１３４は、複数の既存ベクトルデータ１３２を接続するエッジに関する情報であり、既存ベクトルデータ１３４のうち任意の二つを接続する複数のエッジにより形成されるグラフ構造のデータである。グラフインデックス１３４に含まれるエッジは、例えば、双方向のエッジ（無向エッジ）である。図３は、グラフインデックス１３４の内容の一例を示す図である。図示するように、グラフインデックス１３４は、各エッジの識別情報であるエッジＩＤに対して、そのエッジが接続する両端の既存オブジェクトのオブジェクトＩＤが対応付けられたデータである。なお、オブジェクトは、双方向のエッジに代えて、一方向のエッジ（有向エッジ）で接続されてもよい。
【００２３】
以下、インデックス検索部１１４の処理について、より詳細に説明する。インデックス検索部１１４は、グラフインデックス１３４により規定されたエッジによって辿ることのできるオブジェクトのうち、新規オブジェクトに対する距離が短いものから順に所定数のオブジェクトを、新規オブジェクトに類似するオブジェクトとして抽出する。なお、グラフインデックス１３４が有向エッジで構成されている場合、インデックス検索部１１４は、参照元のオブジェクトから参照先のオブジェクトへの向きに従って辿ることのできるオブジェクトのうち、新規オブジェクトに対する距離が短いものから順に所定数のオブジェクトを、新規オブジェクトに類似するオブジェクトとして抽出する。オブジェクト間の距離とは、例えば、オブジェクトがベクトルである場合、ベクトル要素間の差分についてＬｐノルム（ｐ＝１、２、…）を求めたものと定義される。
【００２４】
また、インデックス検索部１１４は、グラフインデックス１３４により規定されたエッジによって辿ることのできるオブジェクトのうち、新規オブジェクトに対して既定の距離以内にあるオブジェクトを、新規オブジェクトに類似するオブジェクトとして抽出してもよい。そして、インデックス検索部１１４は、既存データオブジェクト１３２において、抽出したオブジェクトに対応付けられているデータまたはその識別子を、ネットワークインターフェース１０２およびネットワークＮＷを介してクライアント端末１０に送信する。
【００２５】
図４は、インデックス検索部１１４による検索処理の内容を模式的に示す図である。まず、インデックス検索部１１４は、グラフ構造（グラフインデックス）Ｇ、新規オブジェクトｑ、検索範囲ｒを入力する（Ｓ１００）。次に、インデックス検索部１１４は、グラフ構造Ｇからランダムにオブジェクトの集合Ｓを生成する（Ｓ１０２）。
【００２６】
次に、インデックス検索部１１４は、出力データとなる集合Ｒをクリアする（Ｓ１０４）。次に、インデックス検索部１１４は、集合Ｓに含まれるオブジェクトのうち、最も新規オブジェクトｑに近いオブジェクトを選択し、オブジェクトｓとし（Ｓ１０６）、集合Ｓからオブジェクトｓを除外する（Ｓ１０８）。
【００２７】
次に、インデックス検索部１１４は、オブジェクトｓと新規オブジェクトｑとの距離が検索半径ｒを超えるか否かを判定する（Ｓ１１０）。オブジェクトｓと新規オブジェクトｑとの距離が検索半径ｒを超えない場合、インデックス検索部１１４は、オブジェクトｓの近傍オブジェクト集合Ｎ（Ｇ，ｓ）からオブジェクトを一つ選択し、オブジェクトｏとする（Ｓ１１２）。そして、インデックス検索部１１４は、オブジェクトｏが集合Ｃに含まれるか否かを判定する（Ｓ１１４）。集合Ｃは、重複選択を回避するために設定される集合であり、このフローチャートの処理の開始時または終了時にデータが削除される。
【００２８】
オブジェクトｏが集合Ｃに含まれない場合、インデックス検索部１１４は、オブジェクトｏと新規オブジェクトｑとの距離が検索半径ｒ以下であるか否かを判定する（Ｓ１１８）。オブジェクトｏと新規オブジェクトｑとの距離が検索半径ｒ以下である場合、オブジェクトｏを集合Ｓと集合Ｒのそれぞれに入れる（Ｓ１２０）。オブジェクトｏと新規オブジェクトｑとの距離が検索半径ｒを超える場合、Ｓ１２０の処理はスキップされる。また、Ｓ１１４においてオブジェクトｏが集合Ｃに含まれると判定された場合、Ｓ１１６〜Ｓ１２０の処理はスキップされる。
【００２９】
次に、インデックス検索部１１４は、オブジェクトｓの近傍オブジェクト集合Ｎ（Ｇ，ｓ）から全てのオブジェクトを選択したか否かを判定する（Ｓ１２２）。オブジェクトｓの近傍オブジェクト集合Ｎ（Ｇ，ｓ）から全てのオブジェクトを選択していない場合、Ｓ１１２に処理が戻される。
【００３０】
オブジェクトｓの近傍オブジェクト集合Ｎ（Ｇ，ｓ）から全てのオブジェクトを選択した場合、インデックス検索部１１４は、集合Ｓが空集合であるか否かを判定する（Ｓ１２４）。集合Ｓが空集合でない場合、Ｓ１０６に処理が戻される。
【００３１】
Ｓ１２４において集合Ｓが空集合であると判定された場合、またはＳ１１０においてオブジェクトｓとｑの距離が検索半径ｒを超えると判定された場合、インデックス検索部１１４は、集合Ｒを出力する（Ｓ１２６）。この集合Ｒに含まれるオブジェクトが、新規オブジェクトに類似するオブジェクトである。なお、ここで説明した検索処理の内容は、あくまで一例であり、他の手法により検索処理が行われてもよい。
【００３２】
ここで、インデックス検索部１１４は、Ｓ１１４において、Ｓ１１６で集合Ｃに入れ、且つＳ１１８で距離を計算したオブジェクトであるか否かを判定するために、記憶部１２０に格納された一次判定テーブル１２２および二次判定テーブルを使用して、「既に距離を計算したオブジェクト」であるか否かを判定する。記憶部１２０は、例えば、ＲＡＭやフラッシュメモリなどの読み書き可能なメモリによって実現される。
【００３３】
図５は、一次判定テーブル１２２のデータ構造の一例を示す図である。一次判定テーブル１２２は、一次元の配列構造を有するテーブルであり、メモリ領域における固定アドレスに格納されるテーブルである。一次判定テーブル１２２を分割した各領域には、それぞれ、オブジェクトＩＤを第１のハッシュ関数でハッシュ化して得られるハッシュ値が対応付けられている。図では、各領域を代表して示す情報として、開始アドレスを例示している。それぞれのハッシュ値に対応する領域には、ハッシュ値の元となったオブジェクトのオブジェクトＩＤと、二次判定テーブル１２４にデータが格納されているか否かを示すフラグとが格納される。第１のハッシュ関数は、例えば、オブジェクトＩＤを２ｎで除算した剰余を求める関数である。これを実現するために、インデックス検索部１１４は、例えば、入力データのバイナリ列の下位ｎビットをハッシュ値として利用することで、実際に演算を行うよりも高速に処理を行うことができる。第１のハッシュ関数がオブジェクトＩＤを２ｎで除算した剰余を求める関数である場合、図中のＮ＝２ｎである。例えば、Ｎが、既存ベクトルデータ１３２の全データ数の１／１０程度の値に設定されると好適である。
【００３４】
インデックス検索部１１４は、既に距離を計算したか否かを判断する対象として着目するオブジェクト（以下、着目オブジェクト）について「新規オブジェクトとの距離を計算したか否か」を判定する際に、まず、着目オブジェクトのオブジェクトＩＤ（以下、着目ＩＤ）をハッシュ化したハッシュ値に対応するアドレスに、着目ＩＤが格納されている（登録されている）か否かを判定する。着目ＩＤが格納されている場合、インデックス検索部１１４は、着目オブジェクトについて「新規オブジェクトとの距離を計算した」と判定する。
【００３５】
着目ＩＤが格納されていない場合、インデックス検索部１１４は、着目オブジェクトからのハッシュ値に対応するアドレスに、他のオブジェクトのオブジェクトＩＤが格納されているか否かを判定する。他のオブジェクトのオブジェクトＩＤが格納されていない場合（すなわち何も格納されていない場合）、インデックス検索部１１４は、着目オブジェクトについて「新規オブジェクトとの距離を計算していない」と判定する。この場合、インデックス検索部１１４は、着目オブジェクトと新規オブジェクトとの距離を計算すると共に、着目ＩＤを、着目オブジェクトからのハッシュ値に対応するアドレスに書き込む。
【００３６】
一方、インデックス検索部１１４は、着目オブジェクトからのハッシュ値に対応するアドレスに、他のオブジェクトのオブジェクトＩＤが格納されている場合、一次判定テーブル１２２のフラグを参照し、二次判定テーブル１２４に、第１のハッシュ関数によって同じハッシュ値が導出される（ハッシュ衝突する）一つ以上のオブジェクトＩＤが格納されているか否かを判定する。例えば、フラグ値が１であれば、一つ以上のオブジェクトＩＤが二次判定テーブル１２４に格納されている（ハッシュ衝突が起こっている）ことを示し、フラグ値が０であれば、オブジェクトＩＤが格納されていない（ハッシュ衝突が起こっていない）ことを示す。
【００３７】
従って、フラグ値が０であれば、インデックス検索部１１４は、着目オブジェクトについて「新規オブジェクトとの距離を計算していない」と判定する。この場合、インデックス検索部１１４は、着目オブジェクトと新規オブジェクトとの距離を計算すると共に、二次判定テーブル１２４における着目ＩＤを第２のハッシュ関数（後述）でハッシュ化したハッシュ値に対応した領域に、着目ＩＤを書き込む。また、フラグ値が１であれば、インデックス検索部１１４は、二次判定テーブル１２４を参照して、着目オブジェクトについて「新規オブジェクトとの距離を計算したか否か」を判定する。
【００３８】
図６は、二次判定テーブル１２４のデータ構造の一例を示す図である。二次判定テーブル１２４は、第２のハッシュ関数により導出されるハッシュ値のとり得る値分の一次元の配列構造のデータ格納領域（図中、配列部分）を有すると共に、リスト構造のデータ格納領域（図中、リスト部分）を有する。配列部分には、リスト部分の先頭のアドレス（リンク先）が格納されている。第２のハッシュ関数は、例えば、入力データから、Ｎよりも十分に小さいＭ個のハッシュ値のいずれかを導出する関数である。なお、第２のハッシュ関数は、例えば、オブジェクトＩＤのバイナリ列の下位ｍビットをハッシュ値として利用する関数である（ｎ＞ｍ）。
【００３９】
二次判定テーブル１２４のリスト部分には、オブジェクトＩＤが順次登録されていく。リスト部分にオブジェクトＩＤが登録されている場合、例えば、配列部分におけるオブジェクトＩＤに続く末尾部分には、次に参照すべきリスト部分のアドレスが格納されている。この関係を、ポインタによって次に参照すべきアドレスが示されていると称する。図中、矢印はポインタを示している。
【００４０】
インデックス検索部１１４は、二次判定テーブル１２４を参照し、ポインタを辿りながら着目ＩＤが格納されているか否かを判定する。いずれかの時点で着目ＩＤが格納されている場合、インデックス検索部１１４は、着目オブジェクトについて「新規オブジェクトとの距離を計算した」と判定する。
【００４１】
一方、ポインタを辿って最後の領域まで到達した場合、インデックス検索部１１４は、着目オブジェクトについて「新規オブジェクトとの距離を計算していない」と判定する。なお、インデックス検索部１１４は、次に参照すべきリスト部分のアドレスが格納されていないデータが出現した場合に、「最後の領域まで到達した」と判定する。この場合、インデックス検索部１１４は、着目オブジェクトのオブジェクトＩＤを任意のアドレスに格納すると共に、直前の領域に対して、着目オブジェクトのオブジェクトＩＤを格納したアドレスを示すポインタを追加する。
【００４２】
図７および図８は、インデックス検索部１１４により実行される、新規オブジェクトとの距離を計算したか否かを判定する処理の流れの一例を示すフローチャートである。
【００４３】
まず、インデックス検索部１１４は、一次判定テーブル１２２と二次判定テーブル１２４のデータを消去（クリア）する（Ｓ２００）。
【００４４】
次に、インデックス検索部１１４は、着目ＩＤを第１のハッシュ関数でハッシュ化する（Ｓ２０２）。次に、インデックス検索部１１４は、一次判定テーブル１２２を参照し（Ｓ２０４）、Ｓ２０２で求めたハッシュ値に対応するアドレスにデータが登録されているか否かを判定する（Ｓ２０６）。Ｓ２０２で求めたハッシュ値に対応するアドレスにデータが登録されていない場合、一次判定テーブルに着目ＩＤを登録し（Ｓ２０８）、着目オブジェクトについて「新規オブジェクトとの距離を計算していない」と判定し（Ｓ２１０）、本フローチャートの処理を終了する。
【００４５】
Ｓ２０６において、Ｓ２０２で求めたハッシュ値に対応するアドレスにデータが格納されていると判定した場合、インデックス検索部１１４は、Ｓ２０２で求めたハッシュ値に対応するアドレスに着目ＩＤが登録されているか否かを判定する（Ｓ２１２）。Ｓ２０２で求めたハッシュ値に対応するアドレスに着目ＩＤが登録されている場合、インデックス検索部１１４は、着目オブジェクトについて「新規オブジェクトとの距離を計算した」と判定し（Ｓ２１４）、本フローチャートの処理を終了する。
【００４６】
Ｓ２０２で求めたハッシュ値に対応するアドレスに着目ＩＤが登録されていない場合、（以下、図８）インデックス検索部１１４は、一次判定テーブル１２２における、Ｓ２０２で求めた第１のハッシュ関数によるハッシュ値に対応する領域に付与されたフラグが１であるか０であるかを判定する（Ｓ２１６）。フラグが０である場合、インデックス検索部１１４は、着目ＩＤを第２のハッシュ関数でハッシュ化し（Ｓ２１８）、二次判定テーブル１２４に着目ＩＤを登録する（Ｓ２２４）。この際に、インデックス検索部１１４は、二次判定テーブル１２４の配列部分における、Ｓ２１８で得られたハッシュ値に対応する領域に、着目ＩＤを登録したアドレスを示すポインタを付与しておく。そして、インデックス検索部１１４は、（以下、図７）着目オブジェクトについて「新規オブジェクトとの距離を計算していない」と判定して（Ｓ２１０）、本フローチャートの処理を終了する。
【００４７】
一方、フラグが１である場合、インデックス検索部１１４は、着目ＩＤを第２のハッシュ関数でハッシュ化し（Ｓ２２０）、Ｓ２２０で求めたハッシュ値に対応するアドレスからポインタを順次辿った先に着目ＩＤが登録されているか否かを判定する（Ｓ２２２）。ポインタを順次辿った先に着目ＩＤが登録されていない場合、インデックス検索部１１４は、Ｓ２２４以下の処理を行う。ポインタを順次辿った先に着目ＩＤが登録されている場合、インデックス検索部１１４は、（以下、図７）着目オブジェクトについて「新規オブジェクトとの距離を計算した」と判定し（Ｓ２１４）、本フローチャートの処理を終了する。
【００４８】
以上説明した第１の実施形態によれば、一次元の配列構造を有する一次判定テーブル１２２と、一次元の配列構造およびリスト構造を有する二次判定テーブル１２４とが格納される記憶部１２０と、着目オブジェクト（対象データ）について新規オブジェクトとの距離を計算したか否かを判定する際に、一次判定テーブル１２２における、着目ＩＤを第１のハッシュ関数でハッシュ化したハッシュ値に対応するアドレスに、着目ＩＤまたは他のオブジェクトのオブジェクトＩＤが登録されているか否かを判定し、それらのいずれかが登録されていない場合、そのアドレスに着目ＩＤを登録し、着目ＩＤが登録されている場合、着目オブジェクトについて新規オブジェクトとの距離を計算したと判定し、他のオブジェクトのオブジェクトＩＤが登録されている場合、着目オブジェクトのオブジェクトＩＤを第２のハッシュ関数でハッシュ化したハッシュ値をキーとして二次判定テーブル１２２を参照するインデックス検索部１２２と、を備えることにより、高速処理を実現することができる。
【００４９】
ここで、配列構造のみ、またはリスト構造のみで上記と同様の判定を行うものとの比較について説明する。
【００５０】
仮に、一次判定テーブル１２２の配列数を、例えば既存データオブジェクト１３２に含まれるオブジェクトの数と同じだけ用意した場合、リスト構造においてポインタを辿る処理が不要となる。このため、新規オブジェクトを既に選択したか否かを判定する処理自体は高速に行うことができるが、図７のＳ２００で示した「データを消去する処理」に要する時間が長くなってしまい、検索処理全体に要する時間が長くなってしまう。
【００５１】
一方、リスト構造のみで同様の判定を行う場合、ハッシュ衝突が起きていないオブジェクトについてもポインタを辿る処理が発生するため、一つ一つの判定処理に要する時間が長くなってしまう。また、ハッシュ衝突が起きる度にポインタが追加されるので、判定処理に要する時間が更に長くなってしまう。
【００５２】
通常、検索処理の対象となる範囲（探索範囲）は、グラフインデックス１３４全体に対して限られた範囲内である。従って、探索範囲に相当する配列数の配列構造を設定しておけば、判定処理に要する時間は十分に短縮することができる。この部分が一次判定テーブル１２２に相当する。二次判定テーブル１２４を使用することで処理時間は長くなってしまうが、一次判定テーブル１２２の配列数に余裕を持たせておけば、ハッシュ衝突の起きる可能性を小さくすることができ、全体として検索処理を高速化することができる。
【００５３】
なお、一次判定テーブル１２２は、一段の配列構造を有するものとして説明したが、多段の配列構造を有するようにしてもよい。図９は、一次判定テーブル１２２の他の例を示す図である。この場合、オブジェクトＩＤは、一段目が空いていれば一段目に、一段目が空いておらず二段目が空いていれば二段目に格納され、二段目も空いていない場合に二次判定テーブル１２４が参照される。
【００５４】
また、「一次判定テーブル１２２のそれぞれのエントリに、二次判定テーブル１２４にデータが格納されているか否かを示すフラグを付与する」ものとしたが、このフラグの付与を省略し、インデックス検索部１１４は、一次判定テーブル１２２に着目ＩＤ以外のオブジェクトのＩＤが格納されている場合、二次判定テーブル１２４の最初のデータを参照して、二次判定テーブル１２４にデータが格納されているか否かを確認してもよい。
【００５５】
また、データ管理装置１００が既に実行したか否かを判定する「所定の処理」は、グラフ構造のデータを用いたデータ検索処理において、対象データを検索対象のノードとして、クエリに対応するノード（新規オブジェクト）との距離を計算する処理に限らず、他の種類の処理であってもよい。
【００５６】
以上、本発明を実施するための形態について実施形態を用いて説明したが、本発明はこうした実施形態に何ら限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々の変形及び置換を加えることができる。
【符号の説明】
【００５７】
１０…クライアント端末、１００…データ管理装置、１０２…ネットワークインターフェース、１０４…入出力装置、１１０…制御部、１１２…データオブジェクト生成部、１１４…インデックス検索部、１２０…記憶部、１２２…一次判定テーブル、１２４…二次判定テーブル、１３０…データサーバ、１３２…既存ベクトルデータ、１３４…グラフインデックス
【図１】
2018049315.tif 000003
【図２】
2018049315.tif 000004
【図３】
2018049315.tif 000005
【図４】
2018049315.tif 000006
【図５】
2018049315.tif 000007
【図６】
2018049315.tif 000008
【図７】
2018049315.tif 000009
【図８】
2018049315.tif 000010
【図９】
2018049315.tif 000011