(57)【特許請求の範囲】
【請求項１】
データベース内のコンテンツを検索する方法であって、
サイズを有するネットを構成するステップであって、前記ネットはターゲットを含み、前記ネットは検索半径を有する前記データベース内の一組のデータを含み、他のデータとの距離が少なくとも最小値であるデータを含めることにより構成するステップと、
複数の見本を選択するステップであって、各見本は前記データベース中のデータであるステップと、
距離メトリックを用いて各見本を他のすべての見本と比較するステップと、
前記比較に基づき前記ターゲットに最も近い見本を判定するステップと、
前記ネットのサイズをより小さいサイズに縮小するステップであって、サイズを縮小されたネットは前記ターゲットを含み、前記比較で最も近いものの半径の外側にあるデータを除くことにより縮小するステップと、
前記ネットのサイズが閾値内になるまで、少なくとも２回、前記選択、比較、判定、及び縮小するステップを繰り返すステップとを有する、方法。
【請求項２】
前記繰り返すステップは所定の繰り返し回数行われる、請求項１に記載の方法。
【請求項３】
前記ターゲットは、前記ネットが十分小さくなった後、別の検索方法により見つけられる、請求項１に記載の方法。
【請求項４】
データベース内のコンテンツを検索する装置であって、
サイズを有するネットを構成する回路であって、前記ネットはターゲットを含み、前記ネットは検索半径を有する前記データベース内の一組のデータを含み、他のデータとの距離が少なくとも最小値であるデータを含めることにより構成する回路と、
複数の見本を選択する回路であって、各見本は前記データベース中のデータである回路と、
距離メトリックを用いて前記見本に作用する比較回路と、
比較に基づき前記ターゲットに最も近い見本を見つける判定回路と、
前記ネットのサイズをより小さいサイズに縮小する回路であって、サイズを縮小されたネットは前記ターゲットを含み、前記比較で最も近いものの半径の外側にあるデータを除くことにより縮小する回路と、
最後のネットのサイズが閾値内になるまで、少なくとも２回、前記構成する回路、前記選択する回路、前記比較回路、前記判定回路、及び縮小する回路に、その動作を繰り返させる制御回路とを有する、
装置。
【請求項５】
前記制御回路は、前記構成する回路、前記選択する回路、前記比較回路、前記判定回路、及び縮小する回路に、最後のネットのサイズが閾値以内になるまで、その動作を繰り返させる、請求項４に記載の装置。
【請求項６】
前記制御回路は、ターゲットを、前記ネットが十分小さくなった後、別の検索方法により見つけさせる、請求項４に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本原理は比較によるインターラクティブコンテンツ検索に関する。
【背景技術】
【０００２】
比較によるコンテンツ検索は最近隣探索（ＮＮＳ）の特殊ケースである。ここに説明の原理は、距離空間に埋め込まれたオブジェクトのＮＮＳ問題を考えることにより、以前の取り組みを拡張する。埋め込みは小さな固有次元を有することを、多くの実際的研究により指示されている仮定として仮定する。以前の取り組みは、ナビゲーティングネット、すなわち複距離空間（doubling  metric  spaces）においてＮＮＳを支援する決定論的データ構造を考慮する。一定の球形充填特性を満たす空間に埋め込まれたオブジェクトに対し同様の手法も検討され、一方他の取り組みは成長制限距離に依存している。上記の仮定はすべてここで考慮される複定数に関連している。以前のすべての取り組みでは、ターゲットオブジェクト上のデマンドは均一であると仮定されている。
【０００３】
比較オラクルへのアクセスをするＮＮＳは以前研究された。以前の研究の大きな利点は、オブジェクトが距離空間中にアプリオリに埋め込まれているという仮定が無い。オブジェクト間の類似性を距離（distance  metric）により捉えることを要するが、以前の取り組みでは、任意の２つのオブジェクトが、比較オラクルにより任意のターゲットとの類似性に関してランク付けできることのみを仮定している。それにもかかわらず、これらの取り組みは、均一デマンドも仮定しており、ここに開示の原理は、比較検索の不均一性への拡張である。この点において、不均一なデマンド分布は本原理の開始点である。距離空間があり、検索アルゴリズムがそれを知っているとの仮定の下に、本原理は平均検索コストを改善する。幾つかの以前の取り組みの主な問題は、そのアプローチが無記憶であること、すなわち以前の比較を用いないことであり、一方、本原理はこの問題を、e-netデータ構造を展開することにより解決する。
【０００４】
画像間のペア比較は以前提案された。それはコンテンツ検索の場合に拡張された。比較オラクル（comparison  oracle）の利用はコンテンツ読み出し／検索のみに限定されない。個々のレーティングスケールは大きくふらつく傾向がある。また、レーティングスケールは人によって変わる。これらの理由から、ペア比較を示唆システムの基礎として用いることがより自然である。このアプローチの利点、及びかかるシステムをいかに作るかという問題を十分に説明する。
［関連出願との相互参照］
この出願は、２０１２年２月６日に出願された米国仮出願第６１／５９５，５０２号の利益を主張するものである。この文献はその全体をここに参照援用する。
【発明の概要】
【０００５】
こうした先行技術の欠点や不利な点は、本原理により解消される。本原理は比較によるインターラクティブコンテンツ検索の方法に関する。
【０００６】
本原理の一態様により、データベース内のコンテンツを検索する方法が提供される。該方法は、ターゲットを含むサイズを有するネットを構成するステップと、複数の見本を選択するステップと、各見本を他の見本と比較するステップと、前記ターゲットに最も近い見本を判定するステップと、を有する。該方法はさらに、前記ネットのサイズを前記ターゲットを含む、より小さいサイズに縮小するステップを有する。該方法はさらに、前記ターゲットを見つけるのに前記ネットのサイズが十分小さくなるまで、前記選択、比較、判定、及び縮小するステップを繰り返すステップを有する。
【０００７】
本原理の他の一態様により、データベース内のコンテンツを検索する装置が提供される。該装置は、ここに説明する方法を有するステップを実行するコンピュータよりなる。該コンピュータは、ターゲットを含むサイズを有するネットを構成する回路を有する。また、該コンピュータは、複数の見本を選択する回路を有する。
【０００８】
前記見本に作用する比較回路とを有する。また、該コンピュータは、前記ターゲットに最も近い見本を見つける判定回路と、前記ネットのサイズを前記ターゲットを含む、より小さいサイズに縮小する回路とを有する。また、該コンピュータは、終了条件が満たされていないとき、前記ネットを構成する回路と、前記見本を選択する回路と、前記比較回路と、前記判断回路と、前記ネットのサイズを縮小する回路とに、それらの動作を繰り返させる制御回路を有する。
【０００９】
本原理の上記その他の態様、特徴、及び有利性は、添付した図面を参照して読むと、実施形態の詳細な説明から明らかとなるであろう。
【図面の簡単な説明】
【００１０】
【図１】本原理によるコンテンツ検索を実行する方法の一実施形態を示す図である。
【図２】本原理によるコンテンツ検索を実行する装置を示す図である。
【図３】図２の装置を含む複数の要素の一実施形態を示す図である。
【発明を実施するための形態】
【００１１】
本原理は、比較によるインターラクティブコンテンツ検索の方法と装置に関する。この方法は「インターラクティブ（interactive）」であると言ったが、その理由は前の段階の結果と繰り返しインターラクトする段階があるからである。この方法は、比較を用いて、一定の測定可能な特性を有するオブジェクト（例えば、オブジェクト、写真、映画、記事など）のデータベースをナビゲートする。具体的に、本方法は、一度に２つのオブジェクトから、ターゲット（例えば、写真や映画や記事など）に最も近いものを決定する。ターゲットへの近さ、すなわち距離は、絶対差、絶対差の和などの複数の方法で測定できる。選択に基づき、本方法は、新しいオブジェクトペアを選択しオブジェクトペアが所望のターゲットを含むようになるまで、この過程を同様の段階で繰り返す。各段階において、比較するオブジェクトの小さいリストを提示する。リスト中の一オブジェクトを、ターゲットに最も近いオブジェクトとして選択する。以前の選択に基づき、新しいオブジェクトリストを提示する。この過程は、ターゲットが見つかり、提示されるリストにそのターゲットが含まれるまで続けられ、検索は終了する。
【００１２】
他の一実施形態では、この過程は一定反復回数だけ、または選択されるオブジェクトが所望のターゲットから閾値距離内になるまで繰り返されてもよい。また、別の方法を用いて、ネット中のすべてのオブジェクトがターゲットから閾値距離内になるようにネットを縮小してから、そのネット中のターゲットを探すこともできる。
【００１３】
本方法が必要とするものは次の通りである：
１）オブジェクトの距離埋め込み、すなわち距離空間におけるオブジェクトの、そのフィーチャを記述する表現。例えば、これは画像オブジェクトの画素値であり得る。この距離空間における距離は、オブジェクトがどれだけ「類似している」または「近い」かを捉える。
２）各段階における比較結果は、どのオブジェクトがターゲットに最も近いか示す。
【００１４】
各段階において、本方法は、新しいオブジェクトペアを生成してターゲットの可能性として提案する。
【００１５】
提案されたオブジェクトは、本方法の次の繰り返しで用いることができ、またはターゲットを含むか所望のターゲットに十分近い場合、検索を停止できる。
【００１６】
簡単に言うと、本方法は、オブジェクトを階層で整理するツリーを構成する。このツリー中の同じレベルにあるノードは、オブジェクトが表現される距離空間のおよそ同じサイズの領域を「カバー」する。本方法は、ツリーの第１レイヤー中のオブジェクトのペアを提案することにより、進行する。ツリーのこのレベル中のどのオブジェクトがターゲットに最も近いか特定することにより、階層中のこのオブジェクトの下にあるオブジェクトの選択を狭める。本方法は、このノードの子供中のオブジェクトのペアを提案することにより、再帰的に進行する。
【００１７】
提案の方法は次の特性を有する：
１）本方法は、提案のペアが少ない中で、オブジェクトを素早く見つける。
２）不均一デマンドに対しても動作することを保証する。すなわち、幾つかのオブジェクトが他のオブジェクトより選択されやすくても、動作する。
【００１８】
このエリアにおける以前の取り組みと比較すると、本方法は、保証がよく、オブジェクトをより高速に見つける。本方法は、距離空間全体の知識を必要とするが、以前の取り組みは、オブジェクトとターゲットとの間の距離の厳密な数値ではないが、その順序に関する知識を必要としていた。本方法は、オブジェクトが選択される尤度の知識は必要としないが、以前の方法は必要としていた。本方法は、この分野における以前の取り組みとは基本的に異なるアルゴリズムを実行する。
【００１９】
この種のインターラクティブナビゲーションは、実験的検索としても知られているが、実生活上の多くのアプリケーションを有する。一例は、管理下にない環境において撮影された人の写真のデータベース、例えばFickrやPicasaなどのデータベースにおけるナビゲーションである。自動化された方法では、このような写真から意味のあるフィーチャを抽出することはできない。さらに、多くの現実的な場合には、同様の低レベル記述子（例えば、ＳＩＦＴフィーチャ）を示す画像は、非常に異なるセマンティックコンテンツと、ハイレベル記述とを有し、ユーザにより異なった知覚をされる。
【００２０】
他方、特定の人の検索により、思っている人と最も似た被写体を写真リスト中から容易に選択できる。形式的に、ユーザの振る舞いはいわゆる比較オラクル（comparison  oracle）によりモデル化できる。具体的に、写真データベースは距離メトリックｄを有する集合Ｎにより表されると過程する。このメトリックは、異なる人の写真間の「距離」や「非類似性」を示す。オラクル／人は、具体的なターゲットｔ∈Ｎを考え、次のような質問に答えることができる：「Ｎ中の２つのオブジェクトｘとｙでは、メトリックｄの下ではどちらがｔに近いか？」
比較によるインターラクティブコンテンツ検索の目標は、できるだけ少ないクエリーでターゲットオブジェクトに導く、オラクル／人に対して提案されるオブジェクトペアのシーケンスを見いだすことである。
【００２１】
ここに説明の原理は、不均一デマンドのシナリオにおける問題を考慮したものである。ターゲットオブジェクトｔ∈Ｎは確率分布μからサンプリングされる。この設定において、比較によるインターラクティブコンテンツ検索は古くからの「二十の質問ゲーム」問題と強い関係を有する。具体的に、メンバーシップオラクル（membership  oracle）は、次の形式のクエリーに答えられるオラクルである：「サブセットＡ⊆Ｎが与えられたとき、ｔはＡに属するか？」
ターゲットｔを見つけるためには、メンバーシップオラクルに対して平均して少なくともＨ（μ）回のクエリーを発することが必要であり、Ｈ（μ）はμのエントロピーであることは周知である。さらに、平均でＨ（μ）＋１回のクエリーでターゲットを見つけるアルゴリズム（ハフマン符号化）がある。
【００２２】
比較によるコンテンツ検索は、上記の設定とは異なり、データベースＮにはメトリックｄがあることを仮定する。メンバーシップオラクルは比較オラクルより強い。距離メトリックｄが分かれば、比較クエリーをメンバーシップクエリーによりシミュレートできるからである。他方、メンバーシップオラクルは実装するのが難しい：Ａを簡潔に表現できなければ、ユーザは｜Ａ｜の線形時間でメンバーシップクエリーに回答する。これは、比較オラクルと対照的である。比較オラクルでは回答は一定時間で与えられる。要するに、比較による検索については我々の研究は、（ａ）実装しやすいオラクルに対する、（ｂ）データベースの構造に関する追加的仮定の下で（すなわち、距離メトリックが与えられている）、古くからの設定と同様の性能を求めるものである。
【００２３】
直感的に、比較によるオブジェクトの検索の性能は、ターゲット分布のエントロピーだけでなく、メトリックｄで記述されるターゲット集合Ｎのトポロジーにも依存する。具体的に、比較オラクルを用いてターゲットを見つけるのに、Ω（ｃＨ（μ））回のクエリーが必要であることが分かっている。ここで、ｃはメトリックｄのいわゆる倍加定数（doubling-constant）である。さらに、ターゲットをＯ（ｃ３Ｈｌｏｇ（１／μ＊））回のクエリーで見つける方式がある。ここで、μ＊はｍｉｎｘ∈Ｎμ（ｘ）である。本原理の下、ターゲットをＯ（ｃ５Ｈ（μ））回のクエリーで探すアルゴリズムを提案することにより、以前の限界に対する改善が達成される。
定義と記法
オブジェクトの集合Ｎを考える、ここで｜Ｎ｜＝ｎである。距離空間（Ｍ，ｄ）があり、Ｎ中のオブジェクトが（Ｍ，ｄ）に埋め込まれるように、すなわち、ＮからサブセットＭへの１対１マッピングがあるように、ｄ（ｘ，ｙ）がｘ，ｙ∈Ｍ間の距離を示すものと仮定する。
【００２４】
Ｎ中のオブジェクトは、例えば、データベース中の画像を表す。メトリックの埋め込みは、データベースエントリーの、一組のフィーチャ（例えば、撮影された人の年齢、その髪の毛や目の色など）へのマッピングとして考えられる。２つのオブジェクト間の距離は、２つのオブジェクトがこれらのフィーチャに関してどのくらい「類似している」かを捉えるものである。以下、物理的オブジェクト（写真）とその埋め込み（それらを特徴付ける属性）との間のには差があることを念頭に置きつつ、幾つかの記法をＮ⊆Ｍと記す。
Ａ．比較オラクル
比較オラクルは、２つのオブジェクトｘ，ｙとターゲットｔとが与えられたときに、ｔに最も近いオブジェクトを返すオラクル（oracle）である。もっと形式的に言うと、
【数１】
0006278903.tif 000002
である。
【００２５】
ｘ＝Ｏｒａｃｌｅ（ｘ，ｙ，ｔ）であるとすると、ｄ（ｘ，ｔ）≦ｄ（ｙ，ｔ）である。これは必ずしもｄ（ｘ，ｔ）＜ｄ（ｙ，ｔ）であることを示唆しない。
【００２６】
重要な留意点として、クエリーは常にあるターゲットｔに対して行われることを強調するためＯｒａｃｌｅ（ｘ，ｙ，ｔ）と記載するが、実際には、ターゲットは隠れており、オラクルのみが知っている。あるいは、「人としてのオラクル」アナロジーにしたがって、人間ユーザは、ターゲットを念頭に置き、それを用いて２つのオブジェクトを比較するが、それと共に提示されるまで決して開示しない。
Ｂ．デマンド、エントロピー及び倍加定数
Ｎ中のオブジェクトのセットにわたる確率分布μをデマンドと呼ぶ。換言すると、μはΣｔ∈Ｎμ（ｔ）＝１であるような非負関数である。一般的に、μ（ｔ）はターゲットによって異なるので、デマンドは不均一であり得る。ターゲット分布μは以下の分析において重要な役割を果たす。具体的に、説明している方式における検索の性能に影響する２つの量は、ターゲット分布のエントロピーと倍加定数である。これらの２つの記法は形式的には次のように定義される。
【００２７】
μのエントロピーは
【数２】
0006278903.tif 000003
となる。ここで、ｓｕｐｐ（μ）はμのサポートである。μの最大エントロピーは
【数３】
0006278903.tif 000004
である。オブジェクトｘ∈Ｎが与えられると、ｘの周りの半径Ｒ≧０の閉球は
【数４】
0006278903.tif 000005
となる。集合Ａ⊂Ｎについて、
＜外１＞
0006278903.tif 000006
であるとする。分布μの倍加定数ｃ（μ）は、任意のｘ∈ｓｕｐｐ（μ）と任意のＲ≧０に対して、
【数５】
0006278903.tif 000007
となる最小値ｃ＞０であると定義される。さらに、ｃ（μ）＝ｃであるとき、μはｃ倍加（c-doubling）であると言うことができる。
【００２８】
留意点として、エントロピーＨ（μ）と対照的に、倍加定数ｃ（μ）は、距離空間（Ｍ，ｄ）でのＮの埋め込みにより決まる、ｓｕｐｐ（μ）のトポロジーに依存する。
【００２９】
【表１】
0006278903.tif 000008
問題を定式化するにあたり、この分野における以前の取り組みの記法は次の通りである。比較オラクルにアクセスするとき、ターゲットオブジェクトが見つかるまでＮをナビゲートすることが望ましい。具体的に、グリーディなコンテンツ検索は次のように定義される。ｔをターゲットオブジェクトとし、ｓを開始点となるオブジェクトとする。グリーディなコンテンツ検索アルゴリズムは、オブジェクトｗを提案し、オラクルにｓまたはｗのうち、ターゲットｔに近い方のオブジェクトを選択するように依頼する。すなわち、Ｏｒａｃｌｅ（ｓ，ｗ，ｔ）である。この過程は、オラクルがｓ以外のものを返すまで、すなわち提案のオブジェクトがターゲットｔに「より類似している」ようになるまで、繰り返される。そうなると、例えば、ｗ’の提案の時点で、ｗ’≠ｔであれば、グリーディなコンテンツ検索はｗ’から同じ過程を繰り返す。いつかの時点で提案のオブジェクトがｔであれば、過程は終了する。
【００３０】
＜外２＞
0006278903.tif 000009
をオラクルの応答とし、
＜外３＞
0006278903.tif 000010
を、オラクルに与えられる最初のｋ個の入力のシーケンスであり、得られる応答であると定義する。Ｈｋは、オラクルへのｋ番目のアクセスを含むそれまでのコンテンツ検索の「履歴」である。
【００３１】
開始オブジェクトは常にオラクルに送られた最初の２つのオブジェクトの一方であり、すなわちｘ１＝ｓである。さらに、グリーディなコンテンツ検索では、
＜外４＞
0006278903.tif 000011
であり、すなわち現在のオブジェクトは、今までに送られたもののなかで常にターゲットに最も近いものである。
【００３２】
他方、提案のオブジェクトｙｋ＋１の選択は、履歴Ｈｋとオブジェクトｘｋにより決定される。具体的に、Ｈｋと現在のオブジェクトｘｋとが与えられると、
＜外５＞
0006278903.tif 000012
となるマッピング（Ｈｋ，ｘｋ）→Ｆ（Ｈｋ，ｘｋ）∈Ｎがあり、ここで、ｘ０＝ｓ∈Ｎ（開始オブジェクト）であり、Ｈ０＝０（すなわち、比較をする前であり、履歴はない）である。
【００３３】
マッピングＦはグリーディなコンテンツ検索の選択ポリシーと呼ばれる。一般的に、選択ポリシーはランダムであってもよく、この場合、Ｆ（Ｈｋ，ｘｋ）により返されるオブジェクトはランダム変数であり、その分布
【数６】
0006278903.tif 000013
は（Ｈｋ，ｘｋ）により完全に決定される。Ｆは、Ｈｋとｘｋを通じてターゲットｔに間接的に依存しているだけであることがわかる。これはｔが結局見つかった時にのみ「明らかにされる」との仮定と一貫している。
【００３４】
選択ポリシーは、ｘｋに依存するが履歴Hkには依存しないのであれば、無記憶（memoryless）であると言える。言い換えれば、ｘｋに到達する前に行われた比較にかかわらず、ｘｋ＝ｘ∈Ｎであれば、分布は同じである。
【００３５】
ｘｋ＝ｔである時、検索が有効に終了する（すなわち、これがターゲットであると人が明らかにする）と仮定すると、所望の目標は、オラクルへのアクセス回数を最小化するように、Ｆを選択することである。具体的に、ターゲットがｔであり選択ポリシーがＦであるとすると、検索コストは、ｔが見つかるまでのオラクルに対する提案数である
＜外６＞
0006278903.tif 000014
となる。これは、Ｆがランダムなので、ランダム変数である。Ｅ［ＣＦ（ｔ）］を期待値とする。比較によるコンテンツ検索は次のように確定される：
比較によるコンテンツ検索（ＣＳＴＣ）：（Ｍ，ｄ）へのＮの埋め込みとデマンド分布μ（ｔ）が与えられたとき、期待検索コスト
＜外７＞
0006278903.tif 000015
を最小化するＦを選択せよ。Ｆはランダムなので、上記の最適化問題における自由変数は分布である。
下限及び無記憶アルゴリズム
ターゲットｔを見つけるために比較オラクルに送る必要があるクエリーの期待数の下限は、発明者により以前確立された。
【００３６】
定理１．
任意の整数ＫとＤに対して、任意の選択ポリシーＦの平均検索コストが
【数７】
0006278903.tif 000016
を満たすような、エントロピーＨ（μ）＝Ｋｌｏｇ（Ｄ）及び倍加定数（doubling  constant）ｃ（μ）＝Ｄである距離空間（Ｍ，ｄ）及びターゲットメジャーμがある。
【００３７】
面白いことに、単純な無記憶選択ポリシーは、この限界のＯ（ｃ２（μ）Ｈｍａｘ（μ））内である上限を満たす。
アルゴリズム１．
無記憶コンテンツ検索
入力：ｏｒａｃｌｅ（・，・，ｔ）、デマンド分布μ、開始オブジェクトｓ
出力：ターゲットｔ
１：ｘ←ｓ
２：ｗｈｉｌｅ  ｘ≠ｔ  ｄｏ
３：確率分布
【数８】
0006278903.tif 000017
からｙ∈Ｎをサンプリング
４：ｘ←Ｏｒａｃｌｅ（ｘ，ｙ，ｆ）
５：ｅｎｄ  ｗｈｉｌｅ
定理２．  アルゴリズム１の期待検索コストはＣＦ≦６ｃ３（μ）・Ｈ（μ）・Ｈｍａｘ（μ）
上記のアルゴリズム１から面白いことがわかる。初めに、無記憶選択ポリシーは次の好ましい特性を有する。ｘから等距離にある２つのオブジェクトｙ、ｚについて、μ（ｙ）＞μ（ｚ）であれば、ｙが提案される確率が高い。２つのオブジェクトｙ、ｚが同様にターゲットでありそうなとき、ｄ（ｙ，ｘ）＜ｄ（ｚ，ｘ）であれば、ｙが提案される確率が高い。分布（８）は、両者を、ｘに近いオブジェクトに向けて、及びターゲットでありそうなオブジェクトに向けてバイアスする。
【００３８】
さらに、アルゴリズム１に概要を示したポリシーを実装するにあたり、各ｘにおいて、ランダムなｙを分布（８）からサンプリングできる。これは、分布μと埋め込みＭ（または距離メトリックｄ）が先験的に知られていることを仮定している。しかし、アルゴリズム１は、ターゲット間の実際の距離ではなく、オブジェクト間の順序関係が既知である場合にのみ、実装できる。これは重要である。後者は比較オラクルにアクセスしなければ得られないからである。具体的に、かかるすべての順序関係は、オフラインで（例えば、トレーニングフェーズ中に）、｜Ｎ｜ｌｏｇ｜Ｎ｜回オラクルにクエリーを問い合わせることにより明らかにできる。
【００３９】
定理２の上限と定理１の下限の間の主要な相違要因は、ｃ３Ｈｍａｘのオーダーである。次のセクションに現れる次の結果は、Ｏ（ｃ５）項により、倍加次元への依存性を代償として、Ｈｍａｘ項を無くす。
εネットに基づくアルゴリズム
このセクションの目的は、比較ベースの検索が、平均値ＣＦが幾つかの固定指数ｋの
＜外８＞
0006278903.tif 000018
が特定されることを確認する複数のステップＣＦにおいて確率分布μにより最初にサンプリングされたオブジェクトターゲットｔ∈Ｎの特定において競争できることを示すことである。この目的のため、中間結果を示す。
Ａ．εネット
εネットは次のように定義される：
定義１．サブセットＡ⊂Ｎのεネットは、ｄ（ｘｉ，ｘｊ）＞ε、ｉ≠ｊであるＡの点｛ｘ１，・・・、ｘｋ｝の最大コレクションである。
【００４０】
εネットを構成するために、基礎となる距離空間と、任意の２点間の距離ｄにアクセスする必要がある。ネットの構成は、Ｏ（Ｋ｜Ａ｜）時間でグリーディに行える。ここで、Ｋはεネットのサイズである。かかるネットを構成できる効率的なアルゴリズムが実際にある。
補題１．球Ｂｘ（Ｒ）⊂Ｎと整数ｌ＞０が与えられると、Ｂｘ（Ｒ）の任意の（Ｒ／２ｌ）−ｎｅｔ｛ｘ１，・・・，ｘｋ｝は、
【数９】
0006278903.tif 000019
となり、全てのｉ≠ｊに対して、
【数１０】
0006278903.tif 000020
である。
さらに、かかる（Ｒ／２ｌ）−ｎｅｔの濃度ｋは大きくてもｃｌ＋３である。
証明：
式（９）が成り立たなければ、Ｂｘ（Ｒ）中に、すべてのｉ＝１，・・・，ｋについてｄ（ｙ，ｘｉ）＞Ｒ／２ｌとなるようなｙが存在する。これは｛ｘ１，・・・，ｘｋ｝の最大性と矛盾する。
【００４１】
すべてのｉ≠ｊについて、交わりＢｘｉ（Ｒ／２ｌ＋１）∩Ｂｘｊ（Ｒ／２ｌ＋１）中のどの点ｚでも
＜外９＞
0006278903.tif 000021
である。これはｄ（ｘｉ，ｘｊ）＞Ｒ／２ｌという性質と矛盾する。よって、交わりＢｘｉ（Ｒ／２ｌ＋１）∩Ｂｘｊ（Ｒ／２ｌ＋１）は空でなければならない。
【００４２】
最後に、性質（１０）は
＜外１０＞
0006278903.tif 000022
を示唆する。他方、μがｃ−ｄｏｕｂｌｉｎｇであることをｌ＋２回適用すると、すべてのｉ＝１，・・・，ｋについて
＜外１１＞
0006278903.tif 000023
である。Ｂｘ（Ｒ）⊂Ｂｘｉ（２Ｒ）だからである。これはｘｉ∈Ｂｘ（Ｒ）から得られる。要するに、
＜外１２＞
0006278903.tif 000024
となることに留意されたい。そして、
＜外１３＞
0006278903.tif 000025
となる。上限ｋ≦ｃｌ＋３がすぐ得られる。
【００４３】
ここで、以下が必要である：
補題２．
δ∈（０，１）がδ＞１／３を満たすとする。球Ｂｘ（Ｒ）を、ｄ（ｘ、ｙ）＝Ｒかつμ（｛ｙ｝）＞０であるｙ∈Ｎがあるようにする。すると、次が成り立つ。ρ＞０をρ＜ｍｉｎ（δ，（１−δ）／２）Ｒとし、ｌ＞０を、
【数１１】
0006278903.tif 000026
となる正の整数であるとする。
【００４４】
すると、任意のｚ∈Ｂｘ（Ｒ）について
【数１２】
0006278903.tif 000027
が得られる。
【００４５】
証明：
ｚ∈Ｂｘ（Ｒ）が固定されているとする。
【００４６】
＜外１４＞
0006278903.tif 000028
とする。ρ≦δＲであると仮定すると、Ｂ’は球
＜外１５＞
0006278903.tif 000029
に含まれる。
【００４７】
仮定により、ｄ（ｘ，ｙ）＝Ｒかつμ（｛ｙ｝）＞０であるｙ∈Ｎがある。よって、ｄ（ｘ，ｚ）またはｄ（ｙ，ｚ）のいずれかはＲ／２が下限となる：実際、三角不等式により
＜外１６＞
0006278903.tif 000030
である。最初に、ｄ（ｘ，ｚ）≧Ｒ／２であると仮定する。再び三角不等式により、任意のｚ’∈Ｂ’について、
＜外１７＞
0006278903.tif 000031
となるから、
＜外１８＞
0006278903.tif 000032
が得られる。ρ＜（１−δ）・２Ｒとの仮定の下、下限Ｒ／２−ρ（１−δ）は正であることに留意されたい。言い換えると、任意のα＞０について、球Ｂ’は
＜外１９＞
0006278903.tif 000033
で定義される球Ｂ’’とは互いに素である。これにより
【数１３】
0006278903.tif 000034
となる。ここで、ｌは式（１１）を満たす整数であるとする。もっと強い理由から、ｌは、十分小さい正のαについて、
＜外２０＞
0006278903.tif 000035
となる。これから
＜外２１＞
0006278903.tif 000036
が得られる。μのｃ−ｄｏｕｂｌｉｎｇ性をｌ回適用して、この不等式からさらに
＜外２２＞
0006278903.tif 000037
が得られる。式（１３）と組み合わせると、この最後の不等式から
＜外２３＞
0006278903.tif 000038
となり、これは所望の制約（１２）である。
【００４８】
次に、ｄ（ｘ，ｚ）＜Ｒ／２であると仮定すると、必ずｄ（ｙ，ｚ）≧Ｒ／２となる。任意のｚ’∈Ｂ’について、三角不等式により、
＜外２４＞
0006278903.tif 000039
となり、ここでＢ’’’を
＜外２５＞
0006278903.tif 000040
と定義する。任意の小さいα＞０について、２つの球Ｂ’とＢ’’’は互いに素である。Ｂ’’’はＢに含まれ、任意のｚ’’’∈Ｂ’’’について、
＜外２６＞
0006278903.tif 000041
となり、仮定δ＞１／３により（３／２）Ｒ≦Ｒ／（１−δ）となる。これはＢの半径である。
【００４９】
（１３）と同様に、
＜外２７＞
0006278903.tif 000042
が得られる。ここで、ｌを、式（１１）を満たす正の整数であるとする。三角不等式を適用すると、十分小さいα＞０について、包含関係
＜外２８＞
0006278903.tif 000043
が得られる。実際、任意の点ｘ’∈Ｂについて、
＜外２９＞
0006278903.tif 000044
であり、性質（１１）により、ｘ’が対応する球Ｂｙ（２ｌ（Ｒ／２−ρ／（１−δ）−α））内にあることが保証される。最後に、μのｃ−ｄｏｕｂｌｉｎｇ性をｌ回用いることにより、μ（Ｂ）≦ｃｌμ（Ｂ’’’）であることを示せる。式（１３）と組み合わせると、前の場合のように、所望の性質（１２）が得られる。
備考１．
あるＲ＞０について、補題２の仮定は、ρ＝Ｒ／４、十分に小さいε＞０についてδ＝１／３＋ε、かつｌ＝５であるときに満たされる。実際、１／４＜１／３なので条件ρ＜ｍｉｎ（δ、（１−δ）／２）Ｒが成り立つ。任意の小さい正のε’として（１−δ）−１＝（３／２）＋ε’と書くと、条件（１１）は単純化の後、Ｒ：
＜外３０＞
0006278903.tif 000045
となる。これはｌ＝５かつε’＞０が十分小さいときに明らかに成り立つ。
Ｂ．アルゴリズムと上限
アルゴリズム２  εネットコンテンツ検索
入力：Ｏｒａｃｌｅ（・，・，ｔ）、デマンド分布μ、開始オブジェクトｓ、埋め込み（Ｍ，ｄ）
出力：ターゲットｔ
１:初期化ｘ０←ｓ
２:Ro:=supy∈Ｎｄ(x０,y)により検索半径Ｒ０を初期化
３:ｊ←０
４:while  xｊ≠t  do
５:（Ｒｊ／４）ネットを構成
６:比較オラクルを用いることにより、（Ｒｊ／４）ネット中の点とｘｊの中からターゲットｔに最も近いオブジェクトｘｊ＋１を見つける
７:検索半径
＜外３１＞
0006278903.tif 000046
を更新
８:ｊ←ｊ＋１
９:end  while
εネットに基づき本原理の下で提案されるアルゴリズムはアルゴリズム２である。端的に、検討の検索ストラテジーは段階的に進行する。これらの段階はｊ＝１，・・・，Ｓで示される。段階ｊの初めに、現在の最もよい見本（ｘｊで示す）と検索Ｒｊの現在の半径が与えられる。Ｒｊは前の段階でされた選択を考慮したものであり、検索ターゲットは球Ｂｊ：＝Ｂｘｊ（Ｒｊ）の中にある。各段階ｊにおいて、検索半径Rjは、μ（｛ｙｊ｝）＞０かつｄ（ｘｊ、ｙｊ）＝Rjとなる点ｙｊ∈Nが存在するように定める、すなわち、デマンド分布μはBjの境界に一部がある。
【００５０】
最初の段階は、任意の初期候補ｘ１∈Nを取ることにより始まる。対応する初期検索半径はＲ１：＝ｓｕｐｙ∈ｓｕｐｐ（μ）ｄ（ｘ１，ｙ）と定義される。よって、構成により、この初期球Ｂ１はその境界の質量がゼロではない。
【００５１】
任意の段階ｊの間の検索は次のように進む。現在の検索中心ｘは、Ｂｊのρｊ−ｎｅｔを形成するＢｊの追加点により完成される。ここで、ρｊ＝Ｒｊ／４である。次に、最後の選択と、ｘｊとは区別されるネットの各点との間で比較を行う。これらの比較の終了により、ｘ’ｊをユーザの最後の選択とする。明らかに、この選択はネットの点の中から行われ、検索ターゲットに最も近いものである。
【００５２】
（補題１を考慮して）ネットの点が中心であり、半径ρｊを有する球の交わりは、現在の検索グラウンドＢｊをすっぽりカバーするので、ターゲットは球Ｂｘ’ｊ（ρｊ）中になければならないことになる。
【００５３】
最後に、次の段階ｊ＋１をいかに始めるかを指定する動作が必要である。段階ｊ＋１における検索の中心はｘｊ＋１：＝ｘ’ｊと設定される。ターゲットはＢｘｊ＋１（ρｊ）内にあることが分かる。次に、検索半径Ｒｊ＋１を、μ（Ｂｘｊ＋１（Ｒ））＝μ（Ｂｘｊ＋１（ρｊ））となる最小のＲとする。このように必ず、Ｒｊ＋１≦ρｊであり、さらにＲｊ＋１の最小性は、尺度μが、結果として得られる検索球Ｂｊ＋１の境界に一部の質量を有することを示唆する。このように、この方法は、任意の段階ｊにおいて、（ａ）ターゲットが現在の球Ｂｊ中にあること、及び（ｂ）その球はその境界に被ゼロ質量のオブジェクトを含むことを、構成により保証する。
【００５４】
オラクルに送られるクエリーの数はアルゴリズム２により制限され得る。
【００５５】
アルゴリズム２は、検索履歴を用いて新しいオブジェクトを提案するグリーディなアルゴリズムである。本原理の下の方法１００の一実施形態を図１に示す。本方法は、あるサイズのネットを構成するステップ１１０を有する。このネットは、ターゲット（中に点を含む球として考える）を含むことを保証する方法で構成される。この方法は、さらに、少数の見本（exemplars）を選択するステップ１２０と、前記見本を互いに比較するステップ１３０とを有する。ステップ１４０において、ターゲットにより近い見本が選択され、ステップ１５０において、このオブジェクトの周りにサイズがより小さい他のネットが再構成される。本方法は、ターゲットがネットに含まれることを保証しなければならない。この仮定は、ステップ１６０において、ターゲットの発見などの終了条件に到達するまで、繰り返される。終了条件が満たされると、ターゲットをネット内に見つけることができ、本方法は終了する。終了条件が満たされてないと、本方法はステップ１２０に戻り、ネットサイズがより小さい見本を選択する。
【００５６】
コンテンツ検索を実行する装置２００の一実施形態を図２に示す。本装置は、方法１００を実行するコンピュータよりなる。
【００５７】
コンテンツを検索する装置２００の詳細な実施形態を図３に示す。本装置は、ネット構成回路２１０を有する。このネットは、ターゲットを含むことを保証する方法で構成される。本装置は、さらに、見本選択回路２２０を有する。本装置は、比較回路２３０も有する。比較回路２３０は、リソース及び／または時間があるかどうかにより、見本をペアで、または全部一度に比較できる。本装置は、判定回路２４０も有する。判定回路２４０は、どちらの見本がターゲットに近いか、判定する。判定は、絶対差などの一以上の様々な方法で行える。本装置は、さらに、ネット縮小回路２５０を有する。ネット縮小回路２５０は、ネットのサイズを縮小しつつ、ターゲットがネットにまだ含まれていることを保証しなければならない。この過程は、終了条件が満たされるまで、繰り返される。本装置は、制御回路２６０も含む。これは、様々な要素の動作を制御するのに用いられ、特に、終了条件に合わせてネットを縮小するために、要素が実行する繰り返し回数を制御する。終了条件は制御回路により監視される。
【００５８】
終了条件は１つの条件でもよいし、複数の条件の組み合わせでもよい。例えば、可能性のある１つの条件は、ターゲットを発見（locate）するのにネットが十分小さいことである。他の可能性のある１つの条件は、ネットのサイズが閾値内になることである。他の可能性のある１つの条件は、方法１００のループが所定回数実行されることである。他の可能性のある１つの条件は、ターゲットに最も近い見本を判定する時に、ターゲット自体が選択されることである。
【００５９】
さらに別の実施形態では、ネットのサイズは、ネットが縮小されるまでループの繰り返し動作を実行することにより、縮小でき、次に別の方法を用いて、縮小したサイズのネット内のターゲットを実際に見つける（locate）することができる。例えば、このループをより多く繰り返すよりも、別の方法で最終的な選択をした方が計算量的に効率的である場合に、この実施形態を用いてもよい。
定理３  アルゴリズム２の期待検索コストは
【数１４】
0006278903.tif 000047
により制限される。
【００６０】
各段階ｊにおいて、最後の選択と、ｘｊとは区別されるρｊ−ネットの各点との間で比較を行う。このρｊ−ｎｅｔのサイズは補題１により最大でもｃ５である。よって、最大ｃ５−１回のバイナリ比較が各段階で必要である。
【００６１】
段階ｊにおける最後の選択を、再びｘ’ｊで示す。また、半径を係数１／（１−δ）だけ拡大したあとの検索グラウンドＢｊに尺度μによる質量をπｊ：＝μ（Ｂｘｊ（Ｒｊ／（１−δ）））で示す。ここで、備考１で選択した小さいεに対し、δ＝１／３＋εである。補題２と備考１から、必ず
＜外３２＞
0006278903.tif 000048
となる。
【００６２】
また、批判的に、補題２と演繹的議論により、検索の各段階ｊにおいて
＜外３３＞
0006278903.tif 000049
が保証されることに留意されたい。次に、ターゲット要素ｚ∈Nに条件を課す。その確率μ（｛ｚ｝）とｊ段階後の検索レンジの確率に対する前の制限とを考慮すると、明らかに、検索は、
＜外３４＞
0006278903.tif 000050
を条件に、または等価的に、
＜外３５＞
0006278903.tif 000051
を条件に、ｊ段階後に完了する。段階の平均数Ｓの上限は、
＜外３６＞
0006278903.tif 000052
となる。
【００６３】
１つの段階内で、最大ｃ５−１回の比較が行われることに留意すると、上限（１４）が得られる。
【００６４】
定理３は、倍加定数ｃの指数の装置まで、下限（７）にマッチする上限を与えることに留意されたい。厳密な距離ではなくオブジェクト間の順序関係のみを用いて実施できるアルゴリズム１と対照的に、アルゴリズム２は、基礎となる距離空間に関する完全な知識が必要である。興味深いことに、アルゴリズム２は、ターゲット分布μについての知識は必要としない。アルゴリズムの全てのステップ（及び、特に、境界に被ゼロ質量を有することを保証する球Ｂｊの縮小）は、サポートｓｕｐｐ（μ）が分かれば実施できる。
結論
ここに説明した本原理は、不均一なデマンドの下における比較によるコンテンツ検索（ＣＳＴＣ）の問題に対するソリューションを提供し、性能をターゲット分布のトポロジー及びエントロピーと結びつける。アルゴリズム２で考えた検索ストラテジーは、検索の異なる段階におけるεネットの構成に依存し、検索空間（Ｍ，ｄ）のジオメトリーに関する詳細情報へのアクセスを必要とするが、デマンド分布μに関する情報は必要としない。
【００６５】
本発明の現在好ましい実施形態一以上の具体的なフィーチャと態様を有する一以上の実施形態を説明した。しかし、説明した実施形態の特徴と態様は、他の実施形態にも適合できる。例えば、これらの実施形態とフィーチャは、他のビデオデバイスやシステムにおいて用いることもできる。実施形態と特徴は、必ずしも標準で用いる必要はない。
【００６６】
明細書において、本原理の「一実施形態」等と言う場合、本発明の少なくとも１つの実施形態に含まれるその実施形態に関して説明する具体的な特徴、構造、特性などを意味する。それゆえ、本明細書を通していろいろなところに記載した「一実施形態において」等と言った場合、必ずしもすべてが同じ実施形態を参照するものではない。
【００６７】
ここで説明した実施形態は、方法またはプロセス、装置、またはソフトウェアプログラム、データストリーム、又は信号として実施できる。１つの形式の実施形態の場合で説明した（例えば、方法としてのみ説明した）場合であっても、説明した機能の実施形態は他の形式（例えば、装置やコンピュータソフトウェアプログラム）でも実施できる。装置は例えば適切なハードウェア、ソフトウェア、及びファームウェアで実施可能である。上記の方法は、例えばプロセッサ等の装置で実施可能である。プロセッサとは、処理装置一般を指し、例えばコンピュータ、マイクロプロセッサ、集積回路、プログラマブル論理デバイスなどを指す。プロセッサは、エンドユーザ間での情報通信を行う、コンピュータ、セルラー電話、ポータブル／パーソナル・デジタル・アシスタント（ＰＤＡ）などのデバイス、及びその他の通信デバイスも含む。
【００６８】
ここに説明した様々なプロセスと特徴の実施形態は、異なるいろいろな装置やアプリケーションで実施できる。かかる装置の例には、ウェブサーバ、ラップトップ、パーソナルコンピュータ、セルラー電話、ＰＤＡ、その他の通信デバイスが含まれる。言うまでもなく、上記の機器は可動なものであってもよいし、移動体に組み込まれていてもよい。
【００６９】
また、上記の方法は、プロセッサによって実行される命令で実施することができる。かかる命令（及び／又は、一実施形態で生成されるデータ値）は、例えば集積回路、ソフトウェア担体その他の記憶デバイス、例えば、ハードディスク、コンパクトディスク、ランダムアクセスメモリ（ＲＡＭ）、リードオンリーメモリ（ＲＯＭ）に記憶できる。上記の命令は、プロセッサ読み取り可能媒体上に化体されたアプリケーションプログラムであってもよい。命令は、例えば、ハードウェア、ファームウェア、ソフトウェア、又はこれらの組み合わせであってもよい。命令は、例えば、オペレーティングシステム、アプリケーション、又はこれらの組み合わせに見いだすことができる。それゆえ、プロセッサは、プロセスを実行するように構成されたデバイス、及びプロセスを実行する命令を記憶したプロセッサ読み取り可能媒体（記憶デバイスなど）を含むデバイスの両方として特徴付けられる。さらに、プロセッサ読み取り可能媒体は、命令に加えて、又は命令の替わりに、実施形態により生成されたデータ値を記憶することができる。
【００７０】
当業者には言うまでもなく、実施形態はここに説明したアプローチの全部または一部を用いることができる。実施形態には、例えば、方法を実行する命令や、説明した実施形態により生成されるデータが含まれ得る。
実施形態を説明した。しかし、言うまでもなく様々な修正を行うことができる。例えば、別の実施形態の要素を組み合わせ、補充し、修正し、または削除して、他の実施形態を形成してもよい。また、当業者には言うまでもないが、開示した構成やプロセスを他の構成やプロセスで置き換えてもよく、その結果の実施形態が少なくとも実質的に同じ機能を果たし、少なくとも実質的に同じように、開示した実施形態と実質的に同じ結果を達成する。したがって、これらの実施形態やその他の実施形態が本開示では想定されており、本開示の範囲に入る。
次の付記を記す。
（付記１）  データベース内のコンテンツを検索する方法であって、
ターゲットを含むサイズを有するネットを構成するステップと、
複数の見本を選択するステップと、
各見本を他の見本と比較するステップと、
前記ターゲットに最も近い見本を判定するステップと、
前記ネットのサイズを前記ターゲットを含む、より小さいサイズに縮小するステップと、
前記ターゲットを見つけるのに前記ネットのサイズが十分小さくなるまで、前記選択、比較、判定、及び縮小するステップを繰り返すステップとを有する、方法。
（付記２）  前記繰り返すステップは少なくとも２回繰り返される、付記１に記載の方法。
（付記３）  前記繰り返すステップは、最後のネットが閾値内になるまで、行われる、付記１に記載の方法。
（付記４）  前記繰り返すステップは所定の繰り返し回数行われる、付記１に記載の方法。
（付記５）  前記ターゲットは、前記ネットが十分小さくなった後、別の検索方法により見つけられる、付記１に記載の方法。
（付記６）  データベース内のコンテンツを検索するコンピュータであって、
ターゲットを含むサイズを有するネットを構成する回路と、
複数の見本を選択する回路と、
前記見本に作用する比較回路と、
前記ターゲットに最も近い見本を見つける判定回路と、
前記ネットのサイズを前記ターゲットを含む、より小さいサイズに縮小する回路と、
前記ターゲットを見つけるのに前記ネットのサイズが十分小さくなるまで、前記構成する回路、前記選択する回路、前記比較回路、前記判定回路、及び縮小する回路に、その動作を繰り返させる制御回路とを有する、
コンピュータ。
（付記７）  前記制御回路は、前記構成する回路、前記選択する回路、前記比較回路、前記判定回路、及び縮小する回路に、少なくとも２回の繰り返しの間にその動作を繰り返させる、付記６に記載の装置。
（付記８）  前記制御回路は、前記構成する回路、前記選択する回路、前記比較回路、前記判定回路、及び縮小する回路に、最後のネットのサイズが閾値以内になるまで、その動作を繰り返させる、付記６に記載の装置。
（付記９）  前記制御回路は、前記構成する回路、前記選択する回路、前記比較回路、前記判定回路、及び縮小する回路に、最後のネットのサイズが閾値以内になるまで、その動作を繰り返させる、付記６に記載の装置。
（付記１０）  前記制御回路は、ターゲットを、前記ネットが十分小さくなった後、別の検索方法により見つけさせる、
付記６に記載の装置。
【図１】
0006278903.tif 000053
【図２】
0006278903.tif 000054
【図３】
0006278903.tif 000055