(57)【要約】【課題】一致判定処理を省略可能な多次元データの検索において、検索時間を低減する。【解決手段】検索部２００は、検索する属性集合の属性を属性順５０１に従って配置した属性列を探索木４０１上で探索することにより当該属性集合を検索するときに、新たな検索に係る属性列と過去の検索に係る属性列との間で、注目順位より前の各順位の属性が一致する場合は、過去の検索における探索で辿った当該注目順位に対応する階層のノードから、前記新たな検索に係る属性列における当該注目順位以降の属性を探索する。探索木更新部３００は、検索する属性集合の時系列に含まれる２つの属性集合に係る属性列の間で、先頭から連続して一致する属性の数が他の属性順よりも大きくなる属性順で、属性順５０１を更新し、更新された属性順５０１に従って探索木４０１を更新する。【選択図】図１
2014229106.tif 000002
【特許請求の範囲】
【請求項１】
所定数の要素の集合である検索対象を表す探索木であって、探索要素順に従って、根ノードからの各階層に前記所定数の要素を各々対応付けた探索木を記憶する探索木記憶手段と、
検索する要素集合の要素を前記探索要素順に従って配置した要素列を前記探索木上で探索することにより当該要素集合を検索するときに、新たな検索に係る要素列と過去の検索に係る要素列との間で、注目順位より前の各順位の要素が一致する場合は、前記過去の検索における探索で辿った当該注目順位に対応する階層のノードから、前記新たな検索に係る要素列における当該注目順位以降の要素を探索する検索手段と、
検索する要素集合の時系列に含まれる２つの要素集合に係る要素列の間で、先頭から連続して一致する要素の数が他の要素順よりも大きくなる要素順で、前記探索要素順を更新し、前記更新された探索要素順に従って前記探索木を更新する探索木更新手段と、
を備えた検索装置。
【請求項２】
前記探索木更新手段は、前記所定数の要素についてとりうる要素順の各々について、前記検索する要素集合の時系列に含まれる２つの要素集合に係る要素列の間で、先頭から連続して一致する要素の数の総和を算出し、当該算出した総和が他の要素順より大きい要素順で、前記探索要素順を更新する、
請求項１に記載の検索装置。
【請求項３】
前記探索木更新手段は、前記検索する要素集合の時系列に含まれる２つの要素集合の間で、同時に一致する回数が他の要素の組より大きい要素の組を抽出し、一致する回数の大きい順に当該抽出した組に含まれる要素を配置した１つの要素として統合することを繰り返し、統合した要素における要素順で、前記探索要素順を更新する、
請求項１に記載の検索装置。
【請求項４】
前記検索処理手段は、前記新たな検索に係る要素列と前記過去の検索に係る要素列との間で、所定の注目順位より前の要素列を一括して比較する、
請求項１乃至３のいずれかに記載の検索装置。
【請求項５】
所定数の要素の集合である検索対象を表す探索木であって、探索要素順に従って、根ノードからの各階層に前記所定数の要素を各々対応付けた探索木を記憶し、
検索する要素集合の要素を前記探索要素順に従って配置した要素列を前記探索木上で探索することにより当該要素集合を検索するときに、新たな検索に係る要素列と過去の検索に係る要素列との間で、注目順位より前の各順位の要素が一致する場合は、前記過去の検索における探索で辿った当該注目順位に対応する階層のノードから、前記新たな検索に係る要素列における当該注目順位以降の要素を探索し、
検索する要素集合の時系列に含まれる２つの要素集合に係る要素列の間で、先頭から連続して一致する要素の数が他の要素順よりも大きくなる要素順で、前記探索要素順を更新し、前記更新された探索要素順に従って前記探索木を更新する、
検索方法。
【請求項６】
前記探索要素順を更新する場合、前記所定数の要素についてとりうる要素順の各々について、前記検索する要素集合の時系列に含まれる２つの要素集合に係る要素列の間で、先頭から連続して一致する要素の数の総和を算出し、当該算出した総和が他の要素順より大きい要素順で、前記探索要素順を更新する、
請求項５に記載の検索方法。
【請求項７】
前記探索要素順を更新する場合、前記検索する要素集合の時系列に含まれる２つの要素集合の間で、同時に一致する回数が他の要素の組より大きい要素の組を抽出し、一致する回数の大きい順に当該抽出した組に含まれる要素を配置した１つの要素として統合することを繰り返し、統合した要素における要素順で、前記探索要素順を更新する、
請求項５に記載の検索方法。
【請求項８】
コンピュータに、
所定数の要素の集合である検索対象を表す探索木であって、探索要素順に従って、根ノードからの各階層に前記所定数の要素を各々対応付けた探索木を記憶し、
検索する要素集合の要素を前記探索要素順に従って配置した要素列を前記探索木上で探索することにより当該要素集合を検索するときに、新たな検索に係る要素列と過去の検索に係る要素列との間で、注目順位より前の各順位の要素が一致する場合は、前記過去の検索における探索で辿った当該注目順位に対応する階層のノードから、前記新たな検索に係る要素列における当該注目順位以降の要素を探索し、
検索する要素集合の時系列に含まれる２つの要素集合に係る要素列の間で、先頭から連続して一致する要素の数が他の要素順よりも大きくなる要素順で、前記探索要素順を更新し、前記更新された探索要素順に従って前記探索木を更新する、
処理を実行させるプログラム。
【請求項９】
前記探索要素順を更新する場合、前記所定数の要素についてとりうる要素順の各々について、前記検索する要素集合の時系列に含まれる２つの要素集合に係る要素列の間で、先頭から連続して一致する要素の数の総和を算出し、当該算出した総和が他の要素順より大きい要素順で、前記探索要素順を更新する、
処理を実行させる、請求項８に記載のプログラム。
【請求項１０】
前記探索要素順を更新する場合、前記検索する要素集合の時系列に含まれる２つの要素集合の間で、同時に一致する回数が他の要素の組より大きい要素の組を抽出し、一致する回数の大きい順に当該抽出した組に含まれる要素を配置した１つの要素として統合することを繰り返し、統合した要素における要素順で、前記探索要素順を更新する、
処理を実行させる、請求項８に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索装置、検索方法、及び、検索プログラムに関し、特に、木構造の探索により検索を行う検索装置、検索方法、及び、検索プログラムに関する。
【背景技術】
【０００２】
予め登録された多次元のデータ群の中から、クエリに合致する多次元データを検索する多次元データ検索装置が知られている。
【０００３】
多次元データとは、互いに独立した情報を少なくとも１つ以上含む情報である。例えば、コンテキストアウェアサービスでは、人の状態（位置や性別、年齢等）を表現するために、人を特徴付ける属性情報（属性名と属性値のペア）の集合である多次元データが利用される。この場合、例えば、（位置、新宿）、（性別、男）、（年齢、３０）がそれぞれ属性情報であり、これらの属性情報の集合「（位置、新宿）、（性別、男）、（年齢、３０）」が多次元データである。
【０００４】
このような多次元データ検索装置の一例として、トライ木構造を利用した検索装置が非特許文献１に記載されている。
【０００５】
非特許文献１に記載される検索装置は、多次元データをトライ木で管理し、検索する。トライ木では、各階層に多次元データの属性が対応付けられ、当該階層に対応する属性の一致判定を行うためのノードが配置される。各ノードは、クエリと比較を行う属性値、及び当該属性値と一致した場合に、次に辿る下層のノードへのリンクを持つ。さらに、トライ木は、最下層に検索対象の多次元データを格納する葉ノードを持つ。検索装置は、クエリが入力されると、根ノードから、各ノードの属性値とクエリの属性値が一致するかどうかの判定を、葉ノードにたどり着くまで繰り返す。
【０００６】
また、非特許文献１に記載される検索装置は、注目属性を用いて一致判定処理を省略（スキップ）する。検索装置は、検索を行うたびに、クエリと所定の注目属性に対応する階層で探索したノードとを記憶する。そして、検索装置は、新たなクエリが入力されると、過去のクエリと新たなクエリとの間で、先頭からの各属性を比較する。ここで、検索装置は、先頭から注目属性より前までの全ての属性値が等しければ、過去のクエリで探索した注目属性に対応する階層のノードから今回の探索を開始する。これにより、クエリの先頭から注目属性までの一致判定処理が省略され、検索が高速化される。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】小林他、「多属性の照合を実現する拡張トライ木方式の提案と評価」、２０１２年電子情報通信学会通信ソサイエティ大会通信講演論文集２、２０１２年、ｐ．３６５
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、非特許文献１に記載の多次元データ検索装置では、多次元データにおける属性の順序によっては、過去のクエリと新たなクエリとで、先頭から注目属性までの属性値が一致せず、一致判定処理の省略による検索の高速化の効果が得られないことがある。
【０００９】
本発明の目的は、上述の課題を解決し、一致判定処理を省略可能な多次元データの検索において、検索時間をより低減できる、検索装置、検索方法、及び、検索プログラムを提供することである。
【課題を解決するための手段】
【００１０】
本発明の一態様における検索装置は、所定数の要素の集合である検索対象を表す探索木であって、探索要素順に従って、根ノードからの各階層に前記所定数の要素を各々対応付けた探索木を記憶する探索木記憶手段と、検索する要素集合の要素を前記探索要素順に従って配置した要素列を前記探索木上で探索することにより当該要素集合を検索するときに、新たな検索に係る要素列と過去の検索に係る要素列との間で、注目順位より前の各順位の要素が一致する場合は、前記過去の検索における探索で辿った当該注目順位に対応する階層のノードから、前記新たな検索に係る要素列における当該注目順位以降の要素を探索する検索手段と、検索する要素集合の時系列に含まれる２つの要素集合に係る要素列の間で、先頭から連続して一致する要素の数が他の要素順よりも大きくなる要素順で、前記探索要素順を更新し、前記更新された探索要素順に従って前記探索木を更新する探索木更新手段と、を備える。
【００１１】
本発明の一態様における検索方法は、所定数の要素の集合である検索対象を表す探索木であって、探索要素順に従って、根ノードからの各階層に前記所定数の要素を各々対応付けた探索木を記憶し、検索する要素集合の要素を前記探索要素順に従って配置した要素列を前記探索木上で探索することにより当該要素集合を検索するときに、新たな検索に係る要素列と過去の検索に係る要素列との間で、注目順位より前の各順位の要素が一致する場合は、前記過去の検索における探索で辿った当該注目順位に対応する階層のノードから、前記新たな検索に係る要素列における当該注目順位以降の要素を探索し、検索する要素集合の時系列に含まれる２つの要素集合に係る要素列の間で、先頭から連続して一致する要素の数が他の要素順よりも大きくなる要素順で、前記探索要素順を更新し、前記更新された探索要素順に従って前記探索木を更新する。
【００１２】
本発明の一態様におけるプログラムは、コンピュータに、所定数の要素の集合である検索対象を表す探索木であって、探索要素順に従って、根ノードからの各階層に前記所定数の要素を各々対応付けた探索木を記憶し、検索する要素集合の要素を前記探索要素順に従って配置した要素列を前記探索木上で探索することにより当該要素集合を検索するときに、新たな検索に係る要素列と過去の検索に係る要素列との間で、注目順位より前の各順位の要素が一致する場合は、前記過去の検索における探索で辿った当該注目順位に対応する階層のノードから、前記新たな検索に係る要素列における当該注目順位以降の要素を探索し、検索する要素集合の時系列に含まれる２つの要素集合に係る要素列の間で、先頭から連続して一致する要素の数が他の要素順よりも大きくなる要素順で、前記探索要素順を更新し、前記更新された探索要素順に従って前記探索木を更新する、処理を実行させる。
【発明の効果】
【００１３】
本発明の効果は、一致判定処理を省略可能な多次元データの検索において、検索時間を低減できることである。
【図面の簡単な説明】
【００１４】
【図１】本発明の第１の実施の形態の特徴的な構成を示すブロック図である。
【図２】本発明の第１の実施の形態における、検索装置１００の構成を示すブロック図である。
【図３】本発明の第１の実施の形態における、検索処理を示すフローチャートである。
【図４】本発明の第１の実施の形態における、探索木更新処理を示すフローチャートである。
【図５】本発明の第１の実施の形態における、探索木４０１の例を示す図である。
【図６】本発明の第１の実施の形態における、属性順５０１の例を示す図である。
【図７】本発明の第１の実施の形態における、クエリ時系列情報６０１の例を示す図である。
【図８】本発明の第１の実施の形態における、総プレフィックス長の算出例を示す図である。
【図９】本発明の第１の実施の形態における、探索木４０１の他の例を示す図である。
【図１０】本発明の第１の実施の形態における、属性順５０１の他の例を示す図である。
【図１１】本発明の第２の実施の形態における、検索装置１００の構成を示すブロック図である。
【図１２】本発明の第２の実施の形態における、探索木更新処理を示すフローチャートである。
【図１３】本発明の第２の実施の形態における、統合属性情報７０１の生成例を示す図である。
【発明を実施するための形態】
【００１５】
（第１の実施の形態）
本発明の第１の実施の形態について説明する。
【００１６】
はじめに、本発明の第１の実施の形態の構成について説明する。
【００１７】
図２は、本発明の第１の実施の形態における、検索装置１００の構成を示すブロック図である。
【００１８】
図２を参照すると、検索装置１００は、検索部２００、探索木更新部３００、探索木記憶部４００、属性順記憶部５００、及び、クエリ記憶部６００を含む。
【００１９】
探索木記憶部４００は、多次元データを検索するための探索木４０１（トライ木）を記憶する。多次元データは、所定数の属性（属性名と値）の集合である。以下、属性のことを、要素とも記載する。
【００２０】
図５、図９は、本発明の第１の実施の形態における、探索木４０１の例を示す図である。
【００２１】
探索木４０１では、属性順５０１（探索属性順）に従って、最上位からの各階層に、多次元データの属性が順番に対応付けられる。各階層には、当該階層に対応する属性の一致判定を行うためのノードが配置される。各ノードは、属性の値、及び、検索する属性が当該値と一致した場合に、次に辿る下層のノードへのリンクを持つ。さらに、探索木４０１の最下層には、多次元データのデータ識別子を持つ葉ノードが配置される。
【００２２】
属性順記憶部５００は、属性順５０１を記憶する。
【００２３】
図６、図１０は、本発明の第１の実施の形態における、属性順５０１の例を示す図である。
【００２４】
本発明の第１の実施の形態においては、多次元データは属性「性別」、「年齢」、「位置」を有する。図５の探索木４０１では、図６の属性順５０１に従って、最上位の階層から、「位置」、「性別」、「年齢」が対応付けられている。また、図９の探索木４０１では、図１０の属性順５０１に従って、最上位の階層から、「性別」、「年齢」、「位置」が対応付けられている。
【００２５】
検索部２００は、探索木４０１上で、多次元データを検索する。
【００２６】
検索部２００は、クエリ入力部２１０、検索実行部２２０、及び、検索結果出力部２３０を含む。
【００２７】
ここで、クエリ入力部２１０は、ユーザ等から、検索する多次元データを含むクエリの入力を受け付ける。検索実行部２２０は、クエリにより指定された多次元データの属性を属性順５０１に従って配置した属性列を、探索木４０１で探索することにより、検索を実行する。検索結果出力部２３０は、検索実行部２２０による検索結果を、ユーザ等へ出力する。
【００２８】
クエリ記憶部６００は、クエリの時系列を示すクエリ時系列情報６０１を記憶する。
【００２９】
図７は、本発明の第１の実施の形態における、クエリ時系列情報６０１の例を示す図である。クエリ時系列情報６０１には、クエリで指定された多次元データが、クエリを受信した順番に格納される。
【００３０】
探索木更新部３００は、属性順５０１の更新、及び、探索木４０１の更新を行う。ここで、探索木更新部３００は、クエリ時系列情報６０１に含まれる連続する２つのクエリに係る属性列の間で、先頭から連続して一致する属性の数が他の属性順よりも大きくなるように（先頭から連続して一致する属性の数が最大となるように）、属性順５０１を更新する。
【００３１】
探索木更新部３００は、プレフィクス長算出部３１０、属性順更新部３２０、及び、更新実行部３３０を含む。
【００３２】
プレフィクス長算出部３１０は、クエリ時系列情報６０１をもとに、とりうる属性順の各々について、総プレフィクス長を算出する。属性順更新部３２０は、総プレフィクス長をもとに、属性順５０１を更新する。更新実行部３３０は、更新した属性順５０１に従って、探索木４０１を更新する。
【００３３】
なお、検索装置１００はＣＰＵ（Central Processing Unit）とプログラムを記憶した記憶媒体を含み、プログラムに基づく制御によって動作するコンピュータであってもよい。また、探索木記憶部４００と、属性順記憶部５００と、クエリ記憶部６００とは、それぞれ個別の記憶媒体でも、１つの記憶媒体によって構成されてもよい。
【００３４】
次に、本発明の第１の実施の形態の動作について説明する。
【００３５】
はじめに、本発明の第１の実施の形態における、検索処理について説明する。
【００３６】
図３は、本発明の第１の実施の形態における、検索処理を示すフローチャートである。
【００３７】
ここでは、多次元データ入力部（図示せず）により入力された検索対象の多次元データに対して、図６の属性順５０１に従って図５の探索木４０１が予め生成され、探索木記憶部４００に格納されていると仮定する。
【００３８】
はじめに、検索部２００のクエリ入力部２１０は、ユーザ等から、検索する多次元データを含むクエリの入力を受け付ける（ステップＳ１０１）。
【００３９】
例えば、クエリ入力部２１０は、多次元データ「（位置、新宿）、（性別、男）、（年齢、３０）」を含むクエリを受け付ける。
【００４０】
クエリ入力部２１０は、クエリで指定された多次元データに識別子を付与し、クエリ時系列情報６０１に格納する（ステップＳ１０２）。
【００４１】
例えば、クエリ入力部２１０は、図７のように、多次元データ「（位置、新宿）、（性別、男）、（年齢、３０）」に識別子「クエリ１」を付与し、クエリ時系列情報６０１に格納する。
【００４２】
検索実行部２２０は、探索木４０１を用いて、クエリで指定された多次元データを検索する（ステップＳ１０３）。検索実行部２２０は、探索木４０１上に、クエリで指定された多次元データが存在する場合、当該多次元データのデータ識別子を取得する。
【００４３】
ここで、検索実行部２２０は、属性順５０１に従って、多次元データの属性列を生成し、属性列の先頭から順番に、探索木４０１上の各階層のノードが持つ属性値との一致判定を行う（属性列を探索木４０１で探索する）。
【００４４】
例えば、検索実行部２２０は、クエリ識別子「クエリ１」の多次元データについて、図６の属性順５０１に従って、属性列「新宿、男、３０」を生成する。そして、検索実行部２２０は、図５の探索木４０１上で、ノード識別子「Ｎ１１１」、「Ｎ１２１」、「Ｎ１３１」、「Ｎ１４２」の順にノードを辿ることにより、データ識別子「データ２」を取得する。
【００４５】
検索結果出力部２３０は、検索結果として、取得したデータ識別子を出力する（ステップＳ１０４）。
【００４６】
また、検索実行部２２０は、ステップＳ１０３において、新たなクエリに係る属性列と前回のクエリに係る属性列との間で、注目順位より前の各順位の属性が一致する場合、前回のクエリに対して辿った注目順位に対応する階層のノードから、新たなクエリに係る属性列における注目順位以降の属性について探索を行う。
【００４７】
なお、注目順位は、管理者等により設定された所定の順位でもよい。この場合、検索実行部２２０は、新たなクエリに係る属性列と前回のクエリに係る属性列との間で、注目順位より前の属性列を一括して比較してもよい。また、検索実行部２２０は、複数の注目順位を用いてもよい。また、検索実行部２２０は、新たなクエリに係る属性列と前回のクエリに係る属性列との間で、先頭からの各順位を順番に比較し、一致しない順位に対応する階層のノードから、新たなクエリに係る属性列における当該一致しない順位以降の属性について探索を行ってもよい。
【００４８】
例えば、次のクエリとして、クエリ入力部２１０は、多次元データ「（位置、新宿）、（性別、男）、（年齢、３０）」を含むクエリを受け付け、図７のように、識別子「クエリ２」を付与し、クエリ時系列情報６０１に格納する。
【００４９】
検索実行部２２０は、クエリ識別子「クエリ２」の多次元データについて、属性列「新宿、男、３０」を生成する。ここで、注目順位が予め「順位３」に設定されていると仮定する。この場合、クエリ識別子「クエリ１」と「クエリ２」の属性列間で、順位１、順位２の属性が一致する。従って、検索実行部２２０は、図５の探索木４０１上で、ノード識別子「Ｎ１３１」、「Ｎ１４２」の順にノードを辿ることにより、データ識別子「データ２」を取得する。
【００５０】
さらに次のクエリとして、クエリ入力部２１０は、多次元データ「（位置、渋谷）、（性別、男）、（年齢、３０）」を含むクエリを受け付け、図７のように、識別子「クエリ３」を付与し、クエリ時系列情報６０１に格納する。
【００５１】
検索実行部２２０は、クエリ識別子「クエリ３」の多次元データについて、属性列「渋谷、男、３０」を生成する。この場合、クエリ識別子「クエリ２」と「クエリ３」の属性列間で、順位１、順位２の属性は一致しない。従って、検索実行部２２０は、図５の探索木４０１上で、ノード識別子「Ｎ１１１」、「Ｎ１２２」、「Ｎ１３３」、「Ｎ１４６」の順にノードを辿ることにより、データ識別子「データ６」を取得する。
【００５２】
次に、本発明の第１の実施の形態における、探索木更新処理について説明する。
【００５３】
探索木更新処理は、例えば、ユーザ等により指示されたときに実行される。また、探索木更新処理は、クエリが入力されるたびに実行されてもよい。
【００５４】
ここでは、図７のようなクエリ時系列情報６０１が、クエリ情報記憶部６００に格納されていると仮定する。
【００５５】
図４は、本発明の第１の実施の形態における、探索木更新処理を示すフローチャートである。
【００５６】
はじめに、探索木更新部３００のプレフィクス長算出部３１０は、多次元データについてとりうる属性順を全て生成する（ステップＳ２０１）。
【００５７】
図８は、本発明の第１の実施の形態における、総プレフィックス長の算出例を示す図である。
【００５８】
例えば、プレフィクス長算出部３１０は、多次元データの属性「性別」、「年齢」、「位置」について、図８のような属性順＃１〜６を生成する。
【００５９】
プレフィクス長算出部３１０は、クエリ時系列情報６０１をもとに、生成した属性順の各々についてプレフィクス長を算出し、さらに、プレフィクス長をもとに総プレフィクス長を算出する（ステップＳ２０２）。ここで、プレフィクス長は、クエリ時系列情報６０１に含まれる連続する２つのクエリに係る属性列の間で、先頭から連続して一致する属性の数である。また、総プレフィクス長は、クエリ時系列情報６０１における、連続する２つのクエリの組み合わせ全てについての、プレフィクス長の総和である。
【００６０】
プレフィクス長算出部３１０は、生成した属性順の各々について、クエリ時系列情報６０１における多次元データの時系列から、当該属性順に従った属性列の時系列を生成し、プレフィクス長、総プレフィクス長を算出する。
【００６１】
例えば、図７のクエリ時系列情報６０１において、図８の属性順＃３についてプレフィクス長を算出する場合、クエリ識別子「クエリ１」と「クエリ２」の属性列間では、先頭から属性「性別」、「位置」、「年齢」が、それぞれ一致するため、プレフィクス長は３である。また、クエリ識別子「クエリ２」と「クエリ３」の属性列間では、先頭から属性「性別」が一致するため、プレフィクス長は１である。従って、総プレフィクス長は４である。
【００６２】
プレフィクス長算出部３１０は、図８のように、属性順＃１〜６の各々について、プレフィクス長、総プレフィクス長を算出する。
【００６３】
属性順更新部３２０は、総プレフィクス長をもとに、属性順５０１を更新する（ステップＳ２０３）。ここで、属性順更新部３２０は、総プレフィクス長が他の属性順よりも大きい属性順（総プレフィクス長が最大の属性順）で、属性順５０１を更新する。
【００６４】
例えば、属性順更新部３２０は、総プレフィクス長が最大である、属性順＃４（「性別」、「年齢」、「位置」の順）を、図１０のように属性順５０１に設定する。
【００６５】
更新実行部３３０は、更新した属性順５０１に従って、探索木４０１を更新する（ステップＳ２０４）。
【００６６】
例えば、更新実行部３３０は、図１０の属性順に従って、図９のように探索木４０１を更新する。
【００６７】
次に、探索木４０１の更新後の検索処理の例について説明する。
【００６８】
例えば、探索木４０１が図９のように更新された後で、クエリ識別子「クエリ１」のクエリと同様に、多次元データ「（位置、新宿）、（性別、男）、（年齢、３０）」を含むクエリ（クエリ識別子「クエリ４」）を受け付けた場合、検索実行部２２０は、図１０の属性順５０１に従って、属性列「男、３０、新宿」を生成する。検索実行部２２０は、図９の探索木４０１上で、ノード識別子「Ｎ２１１」、「Ｎ２２１」、「Ｎ２３２」、「Ｎ２４３」の順にノードを辿ることにより、データ識別子「データ２」を取得する。
【００６９】
また、次のクエリとして、クエリ識別子「クエリ２」のクエリと同様に、多次元データ「（位置、新宿）、（性別、男）、（年齢、３０）」を含むクエリ（クエリ識別子「クエリ５」）を受け付けた場合、検索実行部２２０は、属性列「男、３０、新宿」を生成する。この場合、クエリ識別子「クエリ４」と「クエリ５」の属性列間で、順位１、順位２の属性が一致する。従って、検索実行部２２０は、図５の探索木４０１上で、ノード識別子「Ｎ２３２」、「Ｎ２４３」の順にノードを辿ることにより、データ識別子「データ２」を取得する。
【００７０】
さらに、次のクエリとして、クエリ識別子「クエリ３」のクエリと同様に、多次元データ「（位置、渋谷）、（性別、男）、（年齢、３０）」を含むクエリ（クエリ識別子「クエリ６」）を受け付けた場合、検索実行部２２０は、属性列「男、３０、渋谷」を生成する。この場合、クエリ識別子「クエリ４」と「クエリ５」の属性列間で、順位１、順位２の属性が一致する。従って、検索実行部２２０は、図５の探索木４０１上で、ノード識別子「Ｎ２３２」、「Ｎ２４４」の順にノードを辿ることにより、データ識別子「データ６」を取得する。
【００７１】
このように、探索木４０１の更新によって、クエリに含まれる連続する２つの多次元データに係る属性列間で、先頭から連続して一致する属性の数が増えるため、一致判定処理を省略できる回数が増え、検索時間がより低減される。
【００７２】
以上により、本発明の第１の実施の形態の動作が完了する。
【００７３】
なお、本発明の第１の実施の形態においては、探索木更新部３００が、クエリの時系列に含まれる連続する２つのクエリに係る属性列の間でプレフィクス長を算出したが、これに限らず、探索木更新部３００は、例えば、クエリの時系列に含まれる、連続しないクエリを含む２つのクエリ（クエリのペア）に係る属性列の間でプレフィクス長、総プレフィクス長を算出して、属性順５０１、探索木４０１を更新してもよい。この場合、探索木更新部３００は、クエリの時系列に含まれる、クエリの全ペアについて、総プレフィクス長を算出してもよい。また、探索木更新部３００は、所定期間（例えば、直近の所定期間）の時系列に含まれる、クエリのペアについて、総プレフィクス長を算出してもよい。
【００７４】
また、この場合、検索部２００は、新たなクエリに係る属性列と前回以前の過去のクエリ（例えば、過去の指定されたクエリや、前回までの連続した所定数のクエリの内のいずれか）に係る属性列との間で、注目順位より前の各順位の属性が一致する場合は、当該過去のクエリにおける探索で辿った当該注目順位に対応する階層のノードから、新たな検索に係る属性列における当該注目順位以降の属性を探索してもよい。
【００７５】
次に、本発明の第１の実施の形態の特徴的な構成を説明する。図１は、本発明の第１の実施の形態の特徴的な構成を示すブロック図である。
【００７６】
図１を参照すると、検索装置１００は、検索部２００、探索木更新部３００、及び、探索木記憶部４００を含む。
【００７７】
探索木記憶部４００は、所定数の属性（要素）の集合である検索対象を表す探索木４０１であって、属性順５０１（探索要素順）に従って、根ノードからの各階層に所定数の属性を各々対応付けた探索木４０１を記憶する。
【００７８】
検索部２００は、検索する属性集合の属性を属性順５０１に従って配置した属性列（要素列）を探索木４０１上で探索することにより当該属性集合を検索するときに、新たな検索に係る属性列と過去の検索に係る属性列との間で、注目順位より前の各順位の属性が一致する場合は、過去の検索における探索で辿った当該注目順位に対応する階層のノードから、新たな検索に係る属性列における当該注目順位以降の属性を探索する。
【００７９】
探索木更新部３００は、検索する属性集合の時系列に含まれる２つの属性集合に係る属性列の間で、先頭から連続して一致する属性の数が他の属性順よりも大きくなる属性順で、属性順５０１を更新し、更新された属性順５０１に従って探索木４０１を更新する。
【００８０】
本発明の第１の実施の形態によれば、一致判定処理を省略可能な多次元データの検索において、検索時間をより低減できる。その理由は、探索木更新部３００が、クエリの時系列に含まれる２つのクエリに係る属性列の間で、先頭から連続して一致する属性の数が他の属性順よりも大きくなる属性順で、属性順５０１を更新し、更新された属性順５０１に従って探索木４０１を更新するためである。
【００８１】
（第２の実施の形態）
次に、本発明の第２の実施の形態について説明する。
【００８２】
本発明の第２の実施の形態においては、属性のペアを１つの属性（統合属性）として統合することを繰り返すことにより、属性順５０１を決定する点で、本発明の第１の実施の形態と異なる。
【００８３】
はじめに、本発明の第２の実施の形態の構成について説明する。
【００８４】
図１１は、本発明の第２の実施の形態における、検索装置１００の構成を示すブロック図である。
【００８５】
図１１を参照すると、本発明の第２の実施の形態における探索木更新部３００は、本発明の第１の実施の形態におけるプレフィクス長算出部３１０、属性順更新部３２０の代わりに、属性統合部３４０、属性順更新部３５０を含む。
【００８６】
属性統合部３４０は、クエリ時系列情報６０１をもとに、多次元データの属性を統合して、統合属性情報７０１（例えば、後述する統合属性情報７０１ａ〜ｃ）を生成する。
【００８７】
属性順更新部３５０は、統合属性情報７０１をもとに、属性順５０１を決定する。
【００８８】
次に、本発明の第２の実施の形態の動作について説明する。
【００８９】
本発明の第２の実施の形態における検索処理は、本発明の第１の実施の形態の検索処理（図３）と同様となる。
【００９０】
次に、本発明の第２の実施の形態における、探索木更新処理について説明する。
【００９１】
ここでは、図７のようなクエリ時系列情報６０１が、クエリ情報記憶部６００に格納されていると仮定する。
【００９２】
図１２は、本発明の第２の実施の形態における、探索木更新処理を示すフローチャートである。
【００９３】
はじめに、探索木更新部３００の属性統合部３４０は、クエリ時系列情報６０１をもとに、統合属性情報７０１を生成する（ステップＳ３０１）。
【００９４】
図１３は、本発明の第２の実施の形態における、統合属性情報７０１の生成例を示す図である。統合属性情報７０１は、多次元データの属性を統合した統合属性、各統合属性に含まれる属性数、各統合属性の連続する２つのクエリ間での一致状態（一致（ＴＲＵＥ）／不一致（ＦＡＬＳＥ））を含む。
【００９５】
ここで、属性統合部３４０は、多次元データの各属性を統合属性とし、連続する２つのクエリに間での統合属性の一致状態を判定することにより、統合属性情報７０１を生成する。
【００９６】
例えば、図７のクエリ時系列情報６０１において、クエリ識別子「クエリ１」と「クエリ２」の属性列間では、属性「位置」、「性別」、「年齢」が、それぞれ一致する。また、クエリ識別子「クエリ２」と「クエリ３」の属性列間では、属性「性別」、「年齢」が、それぞれ一致する。従って、属性統合部３４０は、図１３に示すように、統合属性情報７０１ａを生成する。
【００９７】
属性統合部３４０は、統合属性情報７０１においてとりうる統合属性の全ペアの各々について、ペアプレフィクス長を算出する。ここで、ペアプレフィクス長は、ペアの両統合属性の一致状態が同時にＴＲＵＥを示した数と両統合属性の属性数の合計との積である（ステップＳ３０２）。
【００９８】
属性統合部３４０は、ステップＳ３０２で算出したペアプレフィクス長が他のペアよりも大きい統合属性のペア（ペアプレフィクス長が最大の統合属性のペア）を抽出する（ステップＳ３０３）。
【００９９】
例えば、属性統合部３４０は、統合属性情報７０１ａについて、図１３に示すように、ペアプレフィクス長を算出し、ペアプレフィクス長が最大である、統合属性のペア「性別」、「年齢」を抽出する。
【０１００】
属性統合部３４０は、ステップＳ３０３で抽出した統合属性のペアを統合して、新たな１つの統合属性として統合し、統合属性情報７０１を更新する（ステップＳ３０４）。ここで、属性統合部３４０は、ペアの各統合属性について、一致状態がＴＲＵＥを示した数と属性数との積を算出し、算出した値が大きい順に統合属性を配置したものを新たな統合属性と定義する。算出した値が同じ場合は、どちらの統合属性を先に配置してもよい。
【０１０１】
例えば、図１３の統合属性情報７０１ａにおいて、一致状態ＴＲＵＥの数と属性数との積は、統合属性「性別」、「年齢」のどちらも２である。従って、属性統合部３４０は、図１３に示すように、統合属性を「性別」、「年齢」の順で配置した「（「性別」、「年齢」）」を、統合属性情報７０１ｂの新たな統合属性に設定する。
【０１０２】
また、属性統合部３４０は、ペアの両統合属性の属性数の合計値を、新たな統合属性の属性数に設定する。また、属性統合部３４０は、両統合属性の一致状態がＴＲＵＥの場合、新たな統合属性の一致状態にＴＲＵＥを、そうでない場合、ＦＡＬＳＥを設定する。
【０１０３】
例えば、属性統合部３４０は、図１３に示すように、統合属性情報７０１ｂの新たな統合属性「（「性別」、「年齢」）」に対する、属性数、一致状態を設定する。
【０１０４】
属性統合部３４０は、統合属性の数が１つになるまで、ステップＳ３０２〜Ｓ３０４の処理を繰り返す（ステップＳ３０５）。
【０１０５】
例えば、属性統合部３４０は、統合属性情報７０１ｂについて、図１３に示すように、ペアプレフィクス長を算出し、ペアプレフィクス長が最大である、統合属性のペア「位置」、「（「性別」、「年齢」）」を抽出する。
【０１０６】
統合属性情報７０１ｂにおいて、一致状態ＴＲＵＥの数と属性数との積は、統合属性「位置」について１、統合属性「（「性別」、「年齢」）」について４である。従って、属性統合部３４０は、図１３に示すように、統合属性を「（「性別」、「年齢」）」、「位置」の順で配置した「（「（「性別」、「年齢」）」、「位置」）」を、統合属性情報７０１ｃの新たな統合属性に設定する。
【０１０７】
次に、属性順更新部３５０は、統合属性をもとに、属性順５０１を更新する（ステップＳ３０６）。ここで、属性順更新部３５０は、統合属性における属性の順番で、属性順５０１を更新する。
【０１０８】
例えば、属性順更新部３５０は、統合属性情報７０１ｃの統合属性「（「（「性別」、「年齢」）」、「位置」）」における属性の順番（「性別」、「年齢」、「位置」の順）を、図１０のように属性順５０１に設定する。
【０１０９】
更新実行部３３０は、決定した属性順５０１に従って、探索木４０１を更新する（ステップＳ３０７）。
【０１１０】
例えば、更新実行部３３０は、図１０の属性順５０１に従って、図９のように探索木４０１を更新する。
【０１１１】
以上により、本発明の第２の実施の形態の動作が完了する。
【０１１２】
なお、本発明の第２の実施の形態においては、探索木更新部３００が、クエリの時系列に含まれる連続する２つのクエリの間の属性ペアが同時に一致する回数をもとに、属性ペアを統合したが、これに限らず、探索木更新部３００は、例えば、クエリの時系列に含まれる、連続しないクエリを含む２つのクエリ（クエリのペア）の間の属性ペアが同時に一致する回数をもとに、属性ペアを統合して、属性順５０１、探索木４０１を更新してもよい。この場合、探索木更新部３００は、クエリの時系列に含まれる、クエリの全ペアについて、属性ペアが同時に一致する回数を算出してもよい。また、探索木更新部３００は、所定期間（例えば、直近の所定期間）の時系列に含まれる、クエリのペアについて、属性ペアが同時に一致する回数を算出してもよい。
【０１１３】
また、本発明の第２の実施の形態では、探索木更新部３００が、同時に一致する回数が他の属性ペアより大きい属性ペアを統合することを繰り返したが、これに限らず、探索木更新部３００は、同時に一致する回数が他の属性の組（複数の属性の組）より大きい属性の組を統合することを繰り返してもよい。
【０１１４】
本発明の第２の実施の形態によれば、本発明の第１の実施の形態に比べて少ない計算量で、属性順５０１を決定できる。その理由は、探索木更新部３００が、とりうる全ての属性順についてプレフィックス長を算出するのではなく、２つのクエリの間で、同時に一致する回数が他の属性ペアより大きい属性ペアを抽出し、一致する回数の大きい順に当該抽出したペアに含まれる属性を配置した１つの属性として統合することを繰り返し、統合した属性における属性順で、属性順５０１を更新するためである。
【０１１５】
これにより、属性順５０１を更新するための計算量は、本発明の第１の実施の形態では、Ｏ（Ｎ！）であったのに対し、本発明の第２の実施の形態では、Ｏ（Ｎ＾３）となる。
【０１１６】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【産業上の利用可能性】
【０１１７】
本発明は、データベースから任意のコンテキストに合致するユーザを検索するユーザ検索装置に適用できる。また、本発明は、多次元データにメッセージの選択条件を登録することにより、多次元データ形式のメッセージから所望のメッセージを抽出するような、publish/subscribe型のメッセージフィルタリング装置にも適用できる。
【符号の説明】
【０１１８】
１００    検索装置
２００    検索部
２１０    クエリ入力部
２２０    検索実行部
２３０    検索結果出力部
３００    探索木更新部
３１０    プレフィクス長算出部
３２０    属性順更新部
３３０    更新実行部
３４０    属性統合部
３５０    属性順更新部
４００    探索木記憶部
４０１    探索木
５００    属性順記憶部
５０１    属性順
６００    クエリ情報記憶部
６０１    クエリ時系列情報
７０１    統合属性情報
【図１】
2014229106.tif 000003
【図２】
2014229106.tif 000004
【図３】
2014229106.tif 000005
【図４】
2014229106.tif 000006
【図５】
2014229106.tif 000007
【図６】
2014229106.tif 000008
【図７】
2014229106.tif 000009
【図８】
2014229106.tif 000010
【図９】
2014229106.tif 000011
【図１０】
2014229106.tif 000012
【図１１】
2014229106.tif 000013
【図１２】
2014229106.tif 000014
【図１３】
2014229106.tif 000015