(57)【要約】【課題】  条件にマッチするobjectを特定し、該objectのIPアドレスを特定する。【解決手段】  本発明は、登録要求パケット内の多属性情報からobjectの属性ベクトルを生成する属性ベクトル生成手段と、検索要求パケット内の各属性に対する条件指定からクエリベクトルを生成するクエリベクトル生成手段と、を有するリゾルバと、リゾルバからobjectの属性ベクトルを取得し、各並び替えパタンに対して先頭のＫ個を抽出してＫ次元ベクトルを生成し、objectのアドレスと共に、Ｋ次元ベクトルＤＢに格納する登録手段と、クエリベクトルから並び替えパタンを用いてＳ通りのＫ次元ベクトルを生成する検索用ベクトル生成手段と、Ｋ次元ベクトルのｋ番目の要素で指定されている属性に対するレンジを用いてｑのスコアを算出するスコア算出手段と、スコアが最も小さいＫ次元ベクトルに基づいてＫ次元ベクトルデータベースを検索し、各オブジェクトに対するアドレスを特定する検索手段と、を有するobject管理サーバを有する。【選択図】  図１
2014215806.tif 000002
【特許請求の範囲】
【請求項１】
情報通信ネットワークに接続されているobjectが、複数の属性に対する値を有し、該属性の値の組み合わせにより条件指定を行うことでobjectを検索し、該objectのアドレスを特定するアドレス解決システムであって、
前記情報通信ネットワークに接続されるリゾルバとobject管理サーバを有し、
前記リゾルバは、
登録要求パケットを取得して、該登録要求パケット内のobjectのアドレス、多属性情報を抽出し、該多属性情報から該objectの属性ベクトルを生成し、前記object管理サーバに送信する属性ベクトル生成手段と、
検索要求パケットを取得して、該検索要求パケット内の各属性に対する条件指定からクエリベクトルを生成し、前記object管理サーバに送信するクエリベクトル生成手段と、
を有し、
前記object管理サーバは、
前記情報通信ネットワークに接続され、前記リゾルバから前記objectの属性ベクトルを取得し、属性i（i=1〜d）の並び替えパタンをＳ個用意し、各並び替えパタンに対して先頭のＫ個（Ｋ<d）を抽出してＫ次元ベクトルを生成し、objectのアドレスと共に、Ｋ次元ベクトルデータベースに格納する登録手段と、
前記リゾルバから前記クエリベクトルqを取得し、前記登録手段の前記並び替えパタンを用いてＳ通りのＫ次元ベクトルPermsK(q)を生成する検索用ベクトル生成手段と、
前記Ｋ次元ベクトルPermsK(q)のｋ番目の要素で指定されている属性に対するレンジを用いてｑのスコアCs(q)を算出するスコア算出手段と、
前記スコアが最も小さいsに対するＫ次元ベクトルPermsK(q)に基づいて前記Ｋ次元ベクトルデータベースを検索し、特定された各オブジェクトに対するアドレスを特定する検索手段と、
を有することを特徴とするアドレス解決システム。
【請求項２】
前記スコア算出手段は、
全object集合に対する属性iに関する累積分布関数Fi (x)=P[objectの属性iの値≦xi]を作成しておき、クエリpermsK(q)における属性skについてのレンジ指定が、xlowsk〜xhighskの場合、前記スコアを
【数１４】
2014215806.tif 000017
により求める（ここで、λ１，λ２は予め定めるパラメータであり、As(q)，R s(q)はそれぞれ2K次元のベクトルであり、
【数１５】
2014215806.tif 000018
とし、Lは予め定める正の整数、r[x]はxの小数点以下を四捨五入して整数値に変換する関数、
【数１６】
2014215806.tif 000019
とする（pは予め定めるパラメータでp>1））手段を含む
請求項１記載のアドレス解決システム。
【請求項３】
前記スコア算出手段は、
ツリー型のデータ構造treesの木の高さをLmとし、treesの各ノードは、探索空間（K次元空間）の部分空間を担当しているとし、あるノードは、ある次元に関して自身の担当空間を２分割して左の子と右の子にそれぞれ分岐するような２分岐ツリーを構成しているとき、permsに対するスコアを、
【数１７】
2014215806.tif 000020
より計算する（但し、
【数１８】
2014215806.tif 000021
（a,bは正の整数でa≦bの場合。ただしa>bは\Pi{j=a}b=1と定義する）mod[l/K]は、lをKで割った剰余、ceil[x]は、xの少数点以下を切り上げた整数の値、floor[x]は、xの小数点以下を切り捨てた整数の値、j=1からKまでの添え字jは、perm sで指定された属性s1からsKまでを指す）手段を含む
請求項１記載のアドレス解決システム。
【請求項４】
前記スコア算出手段は、
属性に対するスコアf(s' k)として、前記累積分布関数Fを用いて
【数１９】
2014215806.tif 000022
を計算する手段を含む請求項２記載のアドレス解決システム。
【請求項５】
情報通信ネットワークに接続されているobjectが、複数の属性に対する値を有し、該属性の値の組み合わせにより条件指定を行うことでobjectを検索し、該objectのアドレスを特定するアドレス解決方法であって、
前記情報通信ネットワークに接続されるリゾルバとobject管理サーバを有するシステムにおいて、
前記リゾルバが、
登録要求パケットを取得して、該登録要求パケット内のobjectのアドレス、多属性情報を抽出し、該多属性情報から該objectの属性ベクトルを生成し、前記object管理サーバに送信する属性ベクトル生成ステップと、
検索要求パケットを取得して、該検索要求パケット内の各属性に対する条件指定からクエリベクトルを生成し、前記object管理サーバに送信するクエリベクトル生成ステップと、を行い、
前記object管理サーバが、
前記情報通信ネットワークに接続され、前記リゾルバから前記objectの属性ベクトルを取得し、属性i（i=1〜d）の並び替えパタンをＳ個用意し、各並び替えパタンに対して先頭のＫ個（Ｋ<d）を抽出してＫ次元ベクトルを生成し、objectのアドレスと共に、Ｋ次元ベクトルデータベースに格納する登録ステップと、
前記リゾルバから前記クエリベクトルqを取得し、前記登録ステップにおける前記並び替えパタンを用いてＳ通りのＫ次元ベクトルPermsK(q)を生成する検索用ベクトル生成ステップと、
前記Ｋ次元ベクトルPermsK(q)のｋ番目の要素で指定されている属性に対するレンジを用いてｑのスコアCs(q)を算出するスコア算出ステップと、
前記スコアが最も小さいsに対するＫ次元ベクトルPermsK(q)に基づいて前記Ｋ次元ベクトルデータベースを検索し、特定された各オブジェクトに対するアドレスを特定する検索ステップと、
を行うことを特徴とするアドレス解決方法。
【請求項６】
前記スコア算出ステップにおいて、
全object集合に対する属性iに関する累積分布関数Fi (x)=P[objectの属性iの値≦xi]を作成しておき、クエリpermsK (q)における属性skについてのレンジ指定が、xlowsk〜xhighskの場合、前記スコアを
【数２０】
2014215806.tif 000023
により求める（ここで、λ１，λ２は予め定めるパラメータであり、As(q)，R s(q)はそれぞれ2K次元のベクトルであり、
【数２１】
2014215806.tif 000024
とし、Lは予め定める正の整数、r[x]はxの小数点以下を四捨五入して整数値に変換する関数、
【数２２】
2014215806.tif 000025
とする（pは予め定めるパラメータでp>1））
請求項５記載のアドレス解決方法。
【請求項７】
前記スコア算出ステップにおいて、
ツリー型のデータ構造treesの木の高さをLmとし、treesの各ノードは、探索空間（K次元空間）の部分空間を担当しているとし、あるノードは、ある次元に関して自身の担当空間を２分割して左の子と右の子にそれぞれ分岐するような２分岐ツリーを構成しているとき、permsに対するスコアを、
【数２３】
2014215806.tif 000026
より計算する（但し、
【数２４】
2014215806.tif 000027
（a,bは正の整数でa≦bの場合。ただしa>bは\Pi{j=a}b=1と定義する）mod[l/K]は、lをKで割った剰余、ceil[x]は、xの少数点以下を切り上げた整数の値、floor[x]は、xの小数点以下を切り捨てた整数の値、j=1からKまでの添え字jは、perm sで指定された属性s1からsKまでを指す）
請求項５記載のアドレス解決方法。
【請求項８】
前記スコア算出ステップにおいて、
属性に対するスコアf(s' k)として、前記累積分布関数Fを用いて
【数２５】
2014215806.tif 000028
を計算する
請求項６記載のアドレス解決方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アドレス解決システム及び方法に係り、特に、情報通信ネットワークにおいて、いくつかの条件指定によって、ネットワークに接続されているobject（通信機能を持つ家電品や端末などを指す）を特定し、通信できるようにするためのアドレス解決システム及び方法に関する。
【背景技術】
【０００２】
従来の情報通信ネットワークは、論理空間上のアドレスにより通信対象を指定している、固定電話では電話番号、インターネットではIPアドレスがそれにあたり、これらはネットワーク上の位置とも対応しているのでその位置に接続することで通信が可能となる。
【０００３】
一方で、携帯電話の電話番号やインターネットでのURLは、より上位の論理アドレスまたは名前と解釈できる。つまり、これらは通信相手や情報の論理位置を示すが、ネットワーク上の接続位置は示していないため、前者ではLR（ロケーションレジスタ）、後者ではDNS（ドメインネームサーバ）により、ネットワーク上の接続位置を示すアドレスへの変換（いわゆる名前解決）が必要となる。後者の場合であれば、URLから変換後のIPアドレスを用い、接続する（例えば、非特許文献１，２参照）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】弓場英明監修、未来ねっと技術シリーズ  ユビキタスネットワーク技術、電気通信協会、2003.
【非特許文献２】http://www.nic.ad.jp/ja/newsletter/No22/080.html
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところで、今後、非常に多数のobjectがネットワークに接続されるようになったときに、個々のobjectに一意に付与された名前をユーザが把握した上で通信を行う代わりに、例えば、ユーザが、目の前で落し物をした自転車に乗っている人と通信したい、あるいは、ある地域である時間帯に温度が２０度以上を示したセンサと通信したい、といったユーザの通信要求条件（様々な属性に対する検索条件の組み合わせ）を直接指定することでobjectを特定して通信できるようにしたい場合が想定される。
【０００６】
しかし、既存のシステムでは、個々のobjectに一意に付与された名前をユーザが把握した上でその名前を指定して通信を行う。例えば携帯電話であれば電話番号をユーザが指定することで通信を行う。そのため、上述のような利用形態を実現することは困難である。
【０００７】
本発明は、上記の点に鑑みなされたもので、objectが有する様々な属性（物理空間上の位置、時刻情報やその他の属性（色）など）に対する条件指定を行うことで、条件にマッチするobjectを特定し、該objectのIPアドレスを特定可能なアドレス解決システム及び方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記の課題を解決するため、本発明（請求項１）は、情報通信ネットワークに接続されているobjectが、複数の属性に対する値を有し、該属性の値の組み合せにより条件指定を行うことでobjectを検索し、該objectのアドレスを特定するアドレス解決システムであって、
前記情報通信ネットワークに接続されるリゾルバとobject管理サーバを有し、
前記リゾルバは、
登録要求パケットを取得して、該登録要求パケット内のobjectのアドレス、多属性情報を抽出し、該多属性情報から該objectの属性ベクトルを生成し、前記object管理サーバに送信する属性ベクトル生成手段と、
検索要求パケットを取得して、該検索要求パケット内の各属性に対する条件指定からクエリベクトルを生成し、前記object管理サーバに送信するクエリベクトル生成手段と、
を有し、
前記object管理サーバは、
前記情報通信ネットワークに接続され、前記リゾルバから前記objectの属性ベクトルを取得し、属性i（i=1〜d）の並び替えパタンをＳ個用意し、各並び替えパタンに対して先頭のＫ個（Ｋ<d）を抽出してＫ次元ベクトルを生成し、objectのアドレスと共に、Ｋ次元ベクトルデータベースに格納する登録手段と、
前記リゾルバから前記クエリベクトルqを取得し、前記登録手段の前記並び替えパタンを用いてＳ通りのＫ次元ベクトルPermsK(q)を生成する検索用ベクトル生成手段と、
前記Ｋ次元ベクトルPermsK(q)のｋ番目の要素で指定されている属性に対するレンジを用いてｑのスコアCs(q)を算出するスコア算出手段と、
前記スコアが最も小さいsに対するＫ次元ベクトルPermsK(q)に基づいて前記Ｋ次元ベクトルデータベースを検索し、特定された各オブジェクトに対するアドレスを特定する検索手段と、を有する。
【０００９】
また、本発明（請求項２）は、前記スコア算出手段において、
全object集合に対する属性iに関する累積分布関数Fi(x)=P[objectの属性iの値≦xi]を作成しておき、クエリpermsK (q)における属性skについてのレンジ指定が、xlowsk〜xhighskの場合、前記スコアを
【００１０】
【数１】
2014215806.tif 000003
により求める（ここで、λ１，λ２は予め定めるパラメータであり、As(q)，R s(q)はそれぞれ2K次元のベクトルであり、
【００１１】
【数２】
2014215806.tif 000004
とし、Lは予め定める正の整数、r[x]はxの小数点以下を四捨五入して整数値に変換する関数、
【００１２】
【数３】
2014215806.tif 000005
とする（pは予め定めるパラメータでp>1））手段を含む。
【００１３】
また、本発明（請求項３）は、前記スコア算出手段において、
ツリー型のデータ構造treesの木の高さをLmとし、treesの各ノードは、探索空間（K次元空間）の部分空間を担当しているとし、あるノードは、ある次元に関して自身の担当空間を２分割して左の子と右の子にそれぞれ分岐するような２分岐ツリーを構成しているとする。このとき、permsに対するスコアを、
【００１４】
【数４】
2014215806.tif 000006
より計算する（但し、\sum{l=1}{Lm}Xl = X1 + X2+…+XLmを意味し、
【００１５】
【数５】
2014215806.tif 000007
（a,bは正の整数でa≦bの場合。ただしa>bは\Pi{j=a}b=1と定義する）mod[l/K]は、lをKで割った剰余、ceil[x]は、xの少数点以下を切り上げた整数の値、floor[x]は、xの小数点以下を切り捨てた整数の値、j=1からKまでの添え字jは、perm sで指定された属性s1からsKまでを指す）手段を含む。
【００１６】
また、本発明（請求項４）は、前記スコア算出手段において、
属性に対するスコアf(s'k)として、前記累積分布関数Fを用いて
【００１７】
【数６】
2014215806.tif 000008
を計算する手段を含む。
【発明の効果】
【００１８】
以上説明したように、本発明によれば、objectが有する様々な属性（物理空間上の位置や、色）に対する条件指定を行うことで、条件にマッチするobjectを特定し、該objectのIPアドレスを特定可能なアドレス解決を提供することが可能となる。
【図面の簡単な説明】
【００１９】
【図１】本発明の第１の実施の形態におけるシステム構成図である。
【図２】本発明の第１の実施の形態におけるリゾルバの構成図である。
【図３】本発明の第１の実施の形態におけるobject管理サーバの構成図である。
【図４】本発明の第１の実施の形態における２次元データ（x1,x2）の木構造の例である。
【図５】本発明の第１の実施の形態における次元数を変えたときの処理対象ノード数を示す図である。
【図６】本発明の第１の実施の形態における次元数を変えたときの処理対象ノード数の数値計算例である。
【図７】本発明の第１の実施の形態における登録時処理のフローチャートである。
【図８】本発明の第１の実施の形態における検索時処理のフローチャートである。
【発明を実施するための形態】
【００２０】
以下、図面と共に本発明の実施の形態を説明する。
【００２１】
［第１の実施の形態］
図１は、本発明の第１の実施の形態におけるＩＰネットワークの基本構成を示す。同図に示すシステムは、ＩＰネットワーク１にobject１０、リゾルバ２０、object管理サーバ３０が接続されている。なお、ここではIPネットワーク１を例に記載しているが、IPアドレス以外の論理アドレスを用いた他のネットワークであってもよい（つまり、論理アドレスがネットワーク上の位置を指し、かつその論理アドレスを指定すれば所望の宛先までデータやパケットを転送することが可能であれば他のネットワークであってもよい）。ここで、object１０は、当該object１０を識別するID、IPアドレスに加え、多属性情報（位置情報、色、時刻情報等）を有するとする。
【００２２】
本発明の第１の方法を用いた場合のリゾルバの構成例を図２に、object管理サーバの構成例を図３に示す。
【００２３】
リゾルバ２０は、登録・検索要求受付部２１、object・クエリベクトル生成部２２を有し、object・クエリベクトル生成部２２はobject管理サーバ３０に接続されている。
【００２４】
object管理サーバ３０は、object・クエリベクトル受付部３１、Ｋ次元ベクトル作成部３２、スコア計算部３３、Ｋ次元ベクトルデータベース３４を有する。
【００２５】
本実施の形態では、情報通信ネットワーク（ＩＰネットワーク１）に接続されているobject１０（例：通信機能をもつ家電品や端末、センサなどを指し、IPアドレス=IP#Aを持つとする）が、複数の属性（例えば、時間や位置、端末の色、センサの気温など）に対する値（例えば、時刻=10:00，位置=緯度XXX，経度YYY，色=赤，気温=20度など）を有するものとし、これら複数属性:値の組み合わせにより条件指定を行うことでobject１０を検索し、該object１０のアドレスIP#Aを特定することを考える。
【００２６】
このような、複数の属性に関して、レンジを指定することで条件にマッチするobjectを探索する方法として、R-tree（例えば、非特許文献３（A. Guttman, "R-Trees: A Dynamic Index Structure for Spatial Searching," ACM SIGMOD 1984.）、非特許文献４（L. Arge et al., "The Priority R-tree: a practically efficient and worst-case optimal R-tree," SIGMOD 2004.）や非特許文献５（http://en.wikipedia.org/wiki/K-dtree]やKD-tree）と呼ばれるツリー型のデータ構造を用いる方法が一般的である。
【００２７】
図４に２次元データ(x1,x 2)に対する具体例を示す。本図に示すように、各次元の値に対する範囲をいくつかの区間に分割し、それぞれの区間を担当する子ノードを用意する。例えば、本図のrootノードAにおいて、[0-1,0-1]と記載しているが、これは、本ノードの担当する範囲が1次元目、２次元目とも0から1であることを意味する。ノードBは[0-0.5,0-1]の範囲を担当している。各子ノードは自身の担当する区間を分割し、各分割区間に対応する子ノードを用意する。
【００２８】
（１）リゾルバ２０によるobjectの登録時には、自身の値(x1,x 2)を担当するleafノード（図４の最下位層のノード）にobjectをobject管理サーバ３０にエントリする。
【００２９】
（２）object管理サーバ３０によるobjectの検索時には、指定されたレンジに対応する子ノードを辿ることで、対象objectを特定する。例えば、0.1<x1<0.3, 0.1<x2<0.25を満たすobjectを探索する場合、rootノードA→ノードB→leafノードDと辿って、object=(0.2,0.2)を見つける。
【００３０】
しかしながら、属性の数（＝次元数）が大きくなると、このようなツリー型のデータ構造を用いた検索では、全ノード探索に近づく問題が指摘されている（次元の呪いとよばれる）（例えば、非特許文献６（C. B¨ohm et al.,"Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases," ACM Computing Surveys, 2001.）参照）。
【００３１】
以下では、上記の次元の呪いに対処する方法を述べている。
【００３２】
属性iがi=1からdまで存在するとし（以下で、属性iを次元i、属性数dを次元数dとよぶ場合がある）、属性iにおける属性値の取りうる範囲を[0,mi]とする。属性が色のような数値でない場合は数値に対応付けることにする（例えば24色で表現するとして、mi=24にし、色が白=1、黄=2、という対応付を行う）。object管理サーバ３０のK次元ベクトル作成部３２は、各object#jの各属性iに対する属性値x(j) iが与えられているとし、object#jの属性ベクトルv(j)を、
v(j)=[x(j)１, x(j)２, …, x(j)i, …, x(j)ｄ]
として生成しておく。
【００３３】
ここで、属性i=1からdの並び替えのパタンをS個用意し、それぞれの並び替えパタンに対して先頭のK個（K<d）を抽出して、K次元ベクトルを作成する。例えばd=5とし、並び替えのパタンをS=3個用意するとして、
perm1=[3,4,2,1,5],
perm2=[2,5,1,3,4], 
perm3=[5,4,2,1,3]
を生成する。各perms の先頭K(=2とする)個を抽出し、perm１K=[3,4], perm2 K=[2,5], perm3K =[5,4]というS個のK次元ベクトルを作成する。
【００３４】
permsKで指定された属性の順に、オブジェクトv(j)の要素を並び替える。この操作をpermsK (v(j))と記載する。例えば、
v(j)=[x(j)1, x(j)2, …, x(j)i, …,x(j)5]
に対して、
perm1K (v(j))=[x(j)3, x(j)4]
となる。以上を各objectに対して実施する。R-treeやkd-treeと呼ばれる多次元データに対するツリー型のデータ構造をs=1からS個用意しておき（これをtreesと呼ぶ）、permsK (v(j))をs番目のtreesにエントリする。これを各object１０に対して実施しておく。
【００３５】
一方、検索を行う際には、各属性iに対して、検索条件を指定する。例えば属性iが気温とし、気温の値xiが20度≦xi≦25度というようにレンジ指定で検索を行う。具体的には、Ｋ次元ベクトル作成部３２において、属性iのレンジ指定がxlowi≦xi≦xhighiの場合、クエリベクトルqを
q=[xlow１〜xhigh１, xlow２〜xhigh２ ..., xlowi〜xhighi, …, xlowｄ〜xhighｄ]
として生成する。
【００３６】
検索時には、クエリベクトルqに対してpermsKの操作を行う。例えば
q=[xlow1〜xhigh1, xlow2〜xhigh2, ..., xlowi〜xhighi, …, xlow5〜xhigh5]
に対して、
perm1K(q)=[xlow3〜xhigh3，xlow4〜xhigh4]
となる。
【００３７】
スコア計算部３３は、permsK (q)のk番目の要素（k=1からK）で指定されている属性sk に対するレンジ[xlowsk, xhighsk]を用いて、permｓに対するクエリベクトルqのスコアCs(q)を計算する。スコアはobject探索コストやobject特定精度と関連する尺度とし、スコアが小さいほど良い指標とする。Cs(q)を各s=1〜Sについて計算し、スコアが最も小さいsを選択し、該sに対するtree sにおいて、permsK(q)で指定されたレンジを満たすobjectをK次元ベクトルデータベース３４を探索して取得する。 
このように、object管理サーバ３０のＫ次元ベクトル作成部３２では、Kを次元数dよりも小さい値に設定することで、objectベクトルv(j)を、低次元（K次元）ベクトルへ変換し、K次元空間上で探索することで次元の呪いを回避している。
【００３８】
ツリー型のデータ構造を用いてレンジ検索を行う際、ツリーを構成するノードの担当範囲が、クエリでの指定範囲に包含されている場合は、該ノード配下のobjectは全て条件にマッチすると判定できるが、ノードの範囲とクエリでの指定範囲の一部が重なる場合には、該ノード配下のobjectが本当に条件を満たすかを調べる必要があり、探索に時間を要することになる。簡単な例として、１次元の場合と２次元の場合を比較する（図５-(a)と(b)）。ここでは、探索空間を１６個の区間に分割している場合を示している。このとき、レンジ長が全区間の半分であるクエリがあったとする。一次元の場合（図５−(a)）、該クエリの指定範囲とノードの範囲の一部が重なるノード数は２ノード（ノード１と９）となる。それに対して、２次元の場合（図５−(b)）、該クエリの指定範囲とノードの範囲の一部が重なるノード数は８ノード（ノード５，６，７，９，１１，１３，１４，１５）となる。このように次元が大きい方が一部と重なるケースが大きくなると考えられる。
【００３９】
図６は、探索空間を232個に分割したときに、各leafノードの担当範囲がクエリの指定範囲の一部と重なるようなleafノードの数Nnonoverlapを数値計算で計算した結果である。X軸は次元数d、Y軸はNnonoverlap/232としてプロットしている。これより、次元が小さいと該ノード数が少なくて済むことが分かる。
【００４０】
なお、object管理サーバ３０のK次元空間での探索においては、一部の属性のみを対象に検索することとなるため、誤検出の可能性がある。誤検出率をなるべく小さくするために、スコアを導入している。スコア計算部３３のスコアの計算方法は後述する。
【００４１】
object管理サーバ３０において、treesを探索する際、クエリpermsK(q)の探索がtreesにおけるleafノード（本ツリーの最下位層に位置するノード）まで到達した際に、leafノード配下に属するobjectがpermsK(q)の条件を満たすかチェックする代わりに、以下を実施する。
【００４２】
permsKで指定されている属性を除いた属性の集合UsKを用意する。もしpermsK=[3,4]，全属性の集合が[1,2,3,4,5]であれば、UsK=[1,2,5]となる。スコア計算部３３は、UsKにおける(d-K)個の属性
【００４３】
【数７】
2014215806.tif 000009
に対してスコアf(s'k)を計算する（スコアの具体的な計算方法は後述する）。Ｋ次元ベクトル作成部３２は、本スコアについて昇順に並び替え、上位K2個の属性を調べる。その上位K2個の属性s'kそれぞれについて、leafノード配下に属するobjectが、クエリqの属性s' kに対する指定条件を満たすかチェックし、K2個全てについて条件を満たしたobjectを抽出する。
【００４４】
この手順について補足説明をする。図５-(b)の１６個の分割空間が、それぞれツリーのleafノードに対応するとする。また、クエリの範囲は点線の矩形だったとする。このとき、leafノード10は、クエリの範囲に完全に包含されているため、該leafノード配下のobjectはクエリの条件を満たすと判定できる。一方、一部重なるleafノード5,6,7,9,11,13,14,15は、それぞれの配下のobjectがクエリの条件を満たすか、調べる必要がある。その際、各objectに対し、最悪ケースで次元数分のチェックが必要となる。また、leafノードの範囲の一部と重なっていることから、該leafノード配下のobjectはクエリの条件を満たす可能性が高いため、次元数分のチェックが必要になる確率も高くなる。（逆に、クエリの条件を満たす可能性が低いobjectに対してであれば、例えば最初の次元をチェックしただけで，クエリの条件を満たさないobjectだと判定できる可能性がある。）そこで、（通常のツリー型データ構造での探索のように）leafノードでpermsK(q)の条件を満たすかチェックすることをせずに、本ツリー以外の属性（次元）に関する条件について調べることで、objectの更なる絞り込みを効率的に行っている。本発明の効果については、評価結果を後程示す。
【００４５】
図７は、本発明の第１の実施の形態におけるobject登録時のフローチャートである。
【００４６】
ステップ１０１）  object１０がネットワーク（ＩＰネットワーク１）に接続されたら、object登録要求パケットをリゾルバ２０内の登録・検索要求受付部２１に送信する。その際、object１０は、自身のIPアドレス、objectID(=j)，多属性情報（位置情報，色，時刻情報等）を通知する。
【００４７】
ステップ１０２）object１０からの登録要求パケットがリゾルバ２０へ到着したら、リゾルバ２０の登録・検索要求受付部２１は、当該object１０の各種情報を読み出し、object・クエリベクトル生成部２２に通知する。object・クエリベクトル生成部２２では、多属性情報から該object#jの属性ベクトルv(j)を生成する。具体的な手順は以下の通りである。
【００４８】
属性iがi=1からdまで存在するとし（以下で、属性iを次元i、属性数dを次元数dと呼ぶ場合がある）、属性iにおける属性値の取りうる範囲を[0,mi]とする。属性が色のような数値でない場合は数値に対応付けることにする（例えば24色で表現するとして、mi=24にし、色が白=1、黄=2、という対応付を行う）。各object#jの各属性iに対する属性値x(j) iが与えられているとし、object#jの属性ベクトルv(j)を、v(j)=[x(j)1, x(j) 2, …, x(j)i, …, x(j)d]として生成する。
【００４９】
生成したv(j)とIPアドレス(IP#A)の組を、object管理サーバ３０へ通知する。
【００５０】
ステップ１０３）  objectベクトルv(j)とIP#Aの組をobject管理サーバ３０内のobject・クエリベクトル受付部３１にて受信したら、それをK次元ベクトル作成部３２に通知する。K次元ベクトル作成部３２では、以下の手順により、S通りのK次元ベクトル
permsK(v(j))
を生成する。
【００５１】
属性i=1からdの並び替えのパタンをS個用意し、それぞれの並び替えパタンに対して先頭のK個（K<d）を抽出して、K次元ベクトルを作成する。例えばd=5とし、並び替えのパタンをS=3個用意するとして、
perm1=[3,4,2,1,5], perm2=[2,5,1,3,4], perm3=[5,4,2,1,3]
を生成する。各perms の先頭K(=2とする)個を抽出し、
perm1K=[3,4], perm2K=[2,5], perm3K=[5,4]
というS個のK次元ベクトルを作成する。permsKで指定された属性の順に、オブジェクトv(j)の要素を並び替える。この操作をpermsK (v(j))と記載する。例えば、
v(j)=[x(j)1, x(j)2, …, x(j)i, …,  x(j)5]
に対して、
perm1k(v(j))=[x(j)3, x(j)4]
となる。
【００５２】
ステップ１０４）  Ｋ次元ベクトル作成部３２は、K次元ベクトルとIP#Aの組をK次元ベクトルデータベース３４に格納する。具体的には、permsK(v(j))⇔objectID#jの対応、ならびに、objectID#j⇔IP#Aの対応をエントリする。（あるいは，permsK(v(j))⇔IP#AのようにIPアドレスと直接対応付けてもよい．）なお、permsK(v(j))⇔objectID#jの対応は、R-treeやkd-treeと呼ばれる多次元データに対するツリー型のデータ構造をs=1からS個用意しておき（これをtreesとよぶ）、permsK(v(j))をs番目のtreesにエントリする。これを各objectに対して実施しておく。
【００５３】
次にobject検索時の処理フローについて図８を用いて説明する。
【００５４】
ステップ２０１）  ユーザは各属性に関する条件指定をした情報（例えば、位置が○○の範囲、時刻が△△の範囲、色＝赤など）を検索要求パケットとしてリゾルバ２０に送信する。
【００５５】
ステップ２０２）  リゾルバ２０内の登録・検索要求受付部２１にて検索要求パケットを受信したら、各属性に対する条件指定を読み出し、object・クエリベクトル生成部２２へ通知する。object・クエリベクトル生成部２２では、以下の手順により、クエリベクトルqを生成する。属性iのレンジ指定がxlowi≦xi≦xhighiの場合、クエリベクトルqを、
q=[xlow1〜xhigh1, xlow2〜xhigh2 ..., xlowi〜xhighi…, xlowd〜xhighd]
として生成する。生成したqを、object管理サーバ３０へ通知する。
【００５６】
ステップ２０３）  object管理サーバ３０内のobject・クエリベクトル受付部３１にてクエリベクトルqを受信したら、それをK次元ベクトル作成部３２に通知する。K次元ベクトル作成部３２では、以下の手順により、S通りのK次元ベクトルpermsK (q)を生成する。
【００５７】
object登録時に用いた、属性i=1からdの並び替えのパタンpermsK（s=1からS）を用いてpermsK (q)を生成する。例えば、object登録時のステップ１０３に準備した
perm1=[3,4,2,1,5], perm2=[2,5,1,3,4], perm3=[5,4,2,1,3]
を用いる。この場合、例えばs=1に対しては、
perm1K(q)=[xlow3〜xhigh3, xlow4〜xhigh4]
となる。
【００５８】
ステップ２０４）  K次元ベクトル作成部３２は、生成したpermsK (q)をスコア計算部３３に通知する。スコア計算部３３では、permsK (q)のk番目の要素（k=1からK）で指定されている属性skに対するレンジ[xlowsk, xhighsk]を用いて、qのスコアCs (q)を計算する。スコアはobject探索コストやobject特定精度と関連する尺度とし、スコアが小さいほど良い指標とする。
【００５９】
ここでは、以下の手順でスコアを計算する。まず、スコア計算のために、全object集合に対する属性iに関する累積分布関数Fi (x)=P[objectの属性iの≦xi]を作成しておく。クエリpermsK (q)における属性skについてのレンジ指定がxlowsk〜xhighskの場合、スコアとして、
【００６０】
【数８】
2014215806.tif 000010
を用いる。ここで、λ１、λ２は予め定めるパラメータであり，As(q)，R s(q)はそれぞれ2K次元のベクトルであり、
【００６１】
【数９】
2014215806.tif 000011
とする。Lは予め定める正の整数、r[x]はxの小数点以下を四捨五入して整数値に変換する関数である。また、
【００６２】
【数１０】
2014215806.tif 000012
とする（pは予め定めるパラメータでp>1）。
【００６３】
ステップ２０５）  C s (q)を各s=1からSについて計算し、スコアが最も小さいsを選択し、そのsの値をK次元ベクトル作成部に返す。K次元ベクトル作成部３２は、該sに対するperm sK(q)をK次元ベクトルデータベース３４に通知する。K次元ベクトルデータベース３４では、本データベース３４上で管理されているtree sにおいて、perm sK(q)で指定されたレンジを満たすobjectを探索する。
【００６４】
tree sを探索する際、クエリpermsK(q)の探索がtree sにおけるleafノード（本ツリーの最下位層に位置するノード）まで到達した際に、leafノード配下に属するobjectがpermsK(q)の条件を満たすかチェックする代わりに、以下を実施する。permsK(q)で指定されている属性を除いた属性の集合UsKを用意する。もしpermsK=[3,4]、全属性の集合が[1,2,3,4,5]であれば、UsK=[1,2,5]となる。UsKにおける(d-K)個の属性s'1, s'2, …s'k, …, s' {d-K}に対してスコアf(s'k)を計算する。
【００６５】
スコア計算部３３のスコア計算として、以下の手順を用いる。
【００６６】
累積分布関数Fを用いて
【００６７】
【数１１】
2014215806.tif 000013
を計算する。本スコアについて昇順に並び替え、上位K2個の属性を調べる。その上位K2個の属性s'kそれぞれについて、leafノード配下に属するobjectが、クエリqの属性s'kに対する指定条件を満たすかチェックし、K2個全てについて条件を満たしたobjectを抽出する。
【００６８】
本検索により特定された各object#jに対するIP#Aを読み出し、その結果をリゾルバ２０に通知する。
【００６９】
＜評価結果＞
本実施の形態を用いたときの数値計算による評価結果について述べる。
【００７０】
全属性数d=100, object数N=240, 特定すべきobject（つまり、クエリqの条件をすべて満たすobject）の数の期待値をH=100個とする。本実験ではKを何パターンか振らせる。
【００７１】
S=floor[d/K]（floor()は括弧内の値の小数点以下を切り捨て）
とし、s=1からSに対して、
perm sK =[K×(s-1)+1, K×(s-1)+2, …, K×s]
とする。また、K2=10，λ1=1, λ2=0とする。object１０は各属性に関して一様に分布しているとする。各属性iについて、検索範囲を設定する次元をd2=25個選択する。その際、Zipf分布に従って属性iを選択する。また、選択されたd2個の属性各々について、クエリの範囲を以下のように設定する。
【００７２】
・平均Tavg=(H/N)(1/d2)，標準偏差Tsd=min(Tavg/2,(1-Tavg)/2)の正規分布に従う乱数の値をレンジ長Tlenとする。それをさらにTlen←min(0.001,max(1,Tlen))とする。
【００７３】
・xlowを、[0,1-Tlen]の間の一様分布に従う乱数の値とし、xhigh=xlow+Tlenとする。
【００７４】
このときの評価結果を表１に示す。
【００７５】
【表１】
2014215806.tif 000014
ここで２カラム目のfprとは、本来特定すべきobject（つまり、クエリqの条件をすべて満たすobject）ではないobjectが誤って検出される確率を指す。３カラム目のcost ratioは，tree sの各階層において、クエリの範囲とその階層のノードの担当範囲の一部のみ重複したためにさらにその子ノードを調査する必要があったノードの数を、全階層について数え上げたものと、leafノードにおいてその配下にあるobjectに対して探索処理を行った回数の和である（その値をd次元ツリーを用いた場合の探索コストで正規化している）。
【００７６】
これより、例えばK=10とすると、d次元ツリー探索時に比べてコストを約0.0055程度に抑えつつ、誤検出率を1.45E-08とできていることが分かる。
【００７７】
[第２の実施の形態]
本実施の形態では、object管理サーバ３０のスコア計算部３３の他の計算方法について説明する。
【００７８】
上記の第１の実施の形態におけるtreesに対するスコア計算手順（図８のステップ２０４）を以下のように変更してもよい。
【００７９】
treesの木の高さをLmとし、treesの各ノードは、探索空間（K次元空間）の部分空間を担当しているとし、あるノードは、ある次元に関して自身の担当空間を２分割して左の子と右の子にそれぞれ分岐するような２分岐ツリーを構成しているとする。このとき、permsに対するスコアとして
【００８０】
【数１２】
2014215806.tif 000015
を計算する。ここで、
【００８１】
【数１３】
2014215806.tif 000016
（a,bは正の整数でa≦bの場合。ただしa>bは\Pi{j=a}b=1と定義する）mod[l/K]は、lをKで割った剰余、ceil[x]は、xの少数点以下を切り上げた整数の値、floor[x]は、xの小数点以下を切り捨てた整数の値、j=1からKまでの添え字jは、perm sで指定された属性s1からsKまでを指すとする。以上のスコアを、第１の実施の形態のスコアC s(q)に追加してもよいし、C s(q)の第１項目、あるいは第二項目の代わりに用いてもよい。
【００８２】
なお、上記の図２に示すリゾルバ２０及び図３に示すobject管理サーバ３０の各構成要素の動作をプログラムとして構築し、リゾルバ、object管理サーバとして利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００８３】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００８４】
１  ＩＰネットワーク
１０  object
２０  リゾルバ
２１  登録・検索要求受付部
２２  object・クエリベクトル生成部
３０  object管理サーバ
３１  object・クエリベクトル受付部
３２  K次元ベクトル作成部
３３  スコア計算部
３４  Ｋ次元ベクトルデータベース
【図１】
2014215806.tif 000029
【図２】
2014215806.tif 000030
【図３】
2014215806.tif 000031
【図４】
2014215806.tif 000032
【図５】
2014215806.tif 000033
【図６】
2014215806.tif 000034
【図７】
2014215806.tif 000035
【図８】
2014215806.tif 000036