データベースをサーチする方法、索引構造を生成するナビゲーションデバイスおよび方法
【課題】索引構造を用いてナビゲーションデバイスデータベースにおいて類似性サーチを行う方法を提供すること。
【解決手段】上記方法において、データベースは、複数のオブジェクトを含み、索引構造は、複数のノードを含む。方法は、クエリーオブジェクトを受信することと、複数のオブジェクトのうちの少なくとも１つのオブジェクトに関連付けられる索引構造のノードにアクセスすることと、ノードに関連付けられた少なくとも１つのオブジェクトの各々のオブジェクトに対して、それぞれ、クエリーオブジェクトとオブジェクトとの間の距離を決定することであって、距離は、それぞれ、距離メトリックに従って決定される、ことと、決定された距離に基づいて、索引構造の別のノードに選択的にアクセスすることとを含む。
【解決手段】上記方法において、データベースは、複数のオブジェクトを含み、索引構造は、複数のノードを含む。方法は、クエリーオブジェクトを受信することと、複数のオブジェクトのうちの少なくとも１つのオブジェクトに関連付けられる索引構造のノードにアクセスすることと、ノードに関連付けられた少なくとも１つのオブジェクトの各々のオブジェクトに対して、それぞれ、クエリーオブジェクトとオブジェクトとの間の距離を決定することであって、距離は、それぞれ、距離メトリックに従って決定される、ことと、決定された距離に基づいて、索引構造の別のノードに選択的にアクセスすることとを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
（技術分野）
本発明は、ナビゲーションデバイスにおける使用のためのデータベースサーチ方法およびデバイスに関する。特に、本発明は、索引構造を用いてナビゲーションデバイスデータベースをサーチする方法と、ナビゲーションデバイスと、索引構造を生成する方法とに関する。
【背景技術】
【０００２】
（背景）
ナビゲーションデバイスは公知であり、２つの場所の間のルートサーチのような機能を行う。現代のナビゲーションデバイスは、また、要求がある場合、ポイントオブインタレスト（ＰＯＩ）に関する情報を出力するトラベルガイドとして機能するようなさらなる機能性を提供し得る。そのような情報は、通りの名称またはＰＯＩを含み得るが、さらなるテキスト情報またはマルチメディア情報を含む場合もある。例示として、いくつかのナビゲーションデバイスは、オブジェクトに関する詳細な説明を、テキストおよび／またはマルチメディア形態で出力するトラベルガイド機能性を含み得る。
【０００３】
現代のナビゲーションデバイスにおいて用いられるデータベースのサイズに起因して、データベースにおいてサーチを行うことは、かなりの難問である。特に、テキストストリング、音素ストリング、マルチメディアオブジェクトまたはユークリッド空間において規定されない他のオブジェクトに対してサーチが行われる場合、このことは当てはまる。２Ｄまたは３Ｄ空間において規定されるオブジェクトの幾何学的座標は、オブジェクトが座標ベースサーチに対して座標に基づき索引付けられることを可能にし得る。そのような索引付けは、テキストストリング、音素ストリング、マルチメディアオブジェクトまたはユークリッド空間において規定されない他のオブジェクトのようなオブジェクトに対して、より難問である。
【０００４】
さらに、サーチがテキストストリング、音素ストリングまたはマルチメディアオブジェクトのようなオブジェクトに対して行われた場合、ユーザーは、正確なヒットを得ることのみに興味があるわけではない場合がある。むしろ、ユーザーは、クエリーに類似するサーチ結果に関する情報を得ることに興味を有し得、必ずしも、クエリーと同一ではない。ルートサーチに対して、開始場所および目的場所、中間ポイントまたは経由ポイントを入力することまたはＰＯＩを入力することのような多くの用途に対して、ユーザーは、正しいテキスト表示の名称に気付いていない場合がある。ストリングの最初の文字に従うデータベースにおける正確な一致に対してサーチを行う従来技術は、それらの最初の文字内にスペルミスがある場合、失敗し得る。
【０００５】
さらに、ナビゲーションデバイスにおいて、記憶スペース制限によって課される制約、利用可能な計算時間に関する限界が、フォルトトレラントな効率的なサーチを実装することを特に難問にしている。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
（要約）
従って、フォールトトレラントサーチが実行されることを可能にする方法およびナビゲーションデバイスを提供するニーズがある。特に、フォールトトレラントサーチが効率的に行われることを可能にする方法およびナビゲーションデバイスに対するニーズがある。
【課題を解決するための手段】
【０００７】
このニーズは、独立請求項に記載されるようなデバイスおよび方法によって的にされる。従属請求項は、実施形態を規定する。
【０００８】
側面に従って、ナビゲーションデバイスデータベースにおいて類似性サーチを行う方法が提供される。類似性サーチは、メトリック索引構造を用いて行われる。データベースは、複数のオブジェクトを含み、索引構造は、複数のノードを含む。クエリーオブジェクトが受信される。複数のオブジェクトのうちの少なくとも１つのオブジェクトに関連付けられる索引構造のノードがアクセスされる。アクセスされたノードのうちの少なくとも１つのオブジェクトに対して、クエリーオブジェクトとオブジェクトとの間の距離は、距離メトリックに従って決定される。決定された距離に基づいて、索引構造の別のノードが選択的にアクセスされる。
【０００９】
方法は、類似性サーチを使用する。これは、ファジィサーチが実装されることを可能にし、ファジィサーチは、正確なマッチについての情報を提供するだけではなく、データベースにおいて最も類似なオブジェクトについての情報も検索する。方法において、クエリーオブジェクトと索引構造のノードのオブジェクトとの距離は、アクセスされるべきである他のノードを識別するように決定される。これは、サーチが効率的に行われることを可能にする。クエリーオブジェクトから閾値より大きな距離を有するオブジェクトを含むかまたは指すアクセスノードが必要とされない。距離メトリックに従って決定された距離を使用することによって、クエリーオブジェクトと索引構造に含まれるオブジェクトとの間の類似または相違が、量的に評価される。
【００１０】
索引構造は、ナビゲーションデバイスの記憶デバイスに格納され得る。
【００１１】
索引構造は、メトリック索引構造であり得る。従来の専門用語に従って、メトリック索引構造は、索引を区分するために、オブジェクトよりむしろ多重次元の空間のそれらの座標の間の相対的距離のみを考慮する索引である。索引構造は、特に、Ｍツリー、ｖａｎｔａｇｅポイントツリーまたは距離メトリックに従って組織化された任意の他のツリー構造であり得る。索引構造は、サーチを行うことにおけるクエリーオブジェクトとオブジェクトとの間の距離を決定するのに使用される距離と同じである距離関数に従って組織化される。
【００１２】
従来の専門用語を用いて、「距離メトリック」または「メトリック」は、本明細書において、反射の公準、対称性および三角不等式を満たす距離関数をさすように理解される。
【００１３】
従来の専門用語を用いて、用語「類似性サーチ」は、本明細書において、クエリーオブジェクトに対する例示または相違に関して所与の基準を満たす、オブジェクトに対するサーチをさすように使用される。実施例は、距離メトリックに従う距離のように測定された、固定の閾値より少ない相違を有するオブジェクトに対するサーチ、または距離メトリックに従う距離のように測定された、索引されたオブジェクトの中のクエリーオブジェクトから最も小さい相違を有するオブジェクトに対するサーチを含む。
【００１４】
クエリーオブジェクトと、サーチに訪問されたノードによって表される全部のオブジェクトとの間の正確な距離を決定することが、可能であるが、必要とされない。索引構造を通るパスに沿うノードのうちの少なくともいくつかに対して、クエリーオブジェクトと索引構造のそれぞれのオブジェクトとの距離の下限を決定するのは、十分であり得る。
【００１５】
オブジェクトは、ストリング、特に音素ストリングまたはテキストストリングであり得る。対応して、クエリーオブジェクトは、音素ストリングまたはテキストストリングであり得る。これは、音素ストリングまたはテキストストリングに対してフォールトトレラントサーチが行われることを可能にする。このようなサーチは、開始場所および目的地場所を入力する場合、データベース内にＰＯＩをサーチする場合、データベースに格納されるテキストまたはマルチメディアデータをサーチする場合、または類似な場合に有用であり得る。
【００１６】
ストリングであるオブジェクトに対する距離メトリックは、複数の利用可能なストリングメトリックのうちの任意の１つから選択され得る。例として、距離メトリックは、Ｌｅｖｅｎｓｈｔｅｉｎ距離に基づき得る。距離関数はまた、Ｄａｍｅｒａｕ−Ｌｅｖｅｎｓｈｔｅｉｎ距離、Ｊａｒｏ−Ｗｉｎｋｌｅｒ距離、Ｈａｍｍｉｎｇ距離、Ｓｏｕｎｄｅｘ距離メトリックに従って決定される距離、Ｎｅｅｄｌｅｍａｎ−Ｗｕｎｓｃｈ距離、Ｇｏｔｏｈ距離、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ−Ｇｏｔｏｈ距離、Ｐ≧１を有するＬｐ距離または反射の公準、対称性および三角不等式に従う任意の他のストリングメトリックのうちの任意の１つであり得る。
【００１７】
テキスト入力が受信され得、テキスト−音素変換は、テキスト入力からクエリーオブジェクトを生成するように行われ得る。代替的に、またはさらに、クエリーオブジェクトは、音声入力から生成される音素ストリングであり得る。
【００１８】
索引構造はさらに、アクセスされたノードに含まれる少なくとも１つのオブジェクトと、索引構造の他のオブジェクトと距離についての距離情報を含み得る。距離情報は、親オブジェクトを有する任意のノードに対して、ノードのオブジェクトとその親オブジェクトとの間の距離を含み得る。この距離情報は、索引構造に格納され得る。代替的に、またはさらに、別のノードを指し、すなわち、リーフノードにない任意のオブジェクトに対して、距離情報は、オブジェクトと、このオブジェクトに関連付けられる索引構造のサブツリーに含まれる任意のオブジェクトとの間の距離の上限を含み得る。距離に対するこの上限はまた、それが、そのサブツリーの全オブジェクトが配置されるオブジェクトの周りの距離を表すために、カバレッジ半径と呼ばれ得る。このような距離情報を索引構造に含むことによって、距離情報は、類似性サーチの間にそれが計算される必要があらず、ランタイムにおいて使用され得る。従って、サーチパフォーマンスが増強され得る。
【００１９】
アクセスする別のノードは、クエリーオブジェクトとアクセスされたノードの間の距離に基づいて、そして距離情報に基づいて選択的に行われ得る。閾値比較が行われ得る。閾値比較に基づいて、サーチ索引のサブツリーがサーチされなければならないか否かが決定され得る。代替的に、またはさらに、閾値比較に基づいて、クエリーオブジェクトと、索引構造のオブジェクトとの間の正確な距離を計算する必要があるか否かが決定され得る。
【００２０】
クエリーオブジェクトとノードに含まれるオブジェクトと間の距離は、カバレッジ半径とサーチ半径との総計と比較され得る。閾値比較が、クエリーオブジェクトとノードに含まれるオブジェクトと間の距離が総計より大きいであることを示す場合に、オブジェクトが指す索引構造のサブツリーにアクセスする必要とされない。サーチ半径が、固定され得、または類似性サーチが進行するので、変化するように作られ得る。
【００２１】
ノードは、いくつかのオブジェクトを含み得る。索引構造は、いくつかのオブジェクトの各々に対して、それぞれのオブジェクトと、それぞれのオブジェクトを指す索引構造のサブツリーに含まれる任意のオブジェクトとの間の距離の上限を含み得る。
【００２２】
オブジェクトは、決定された距離に基づいて類似性サーチから選択的に取り除かれ得る。取り除くことは、クエリーオブジェクトとノードのオブジェクトとの間の決定された距離に基づいて、そしてオブジェクトのカバレッジ半径に基づいて行われ得る。
【００２３】
距離を決定するステップと、別のノードに選択的にアクセスするステップとが、反復して繰り返され得る。これらのステップが繰り返される場合に、クエリーオブジェクトとノードに含まれるオブジェクトとの間の距離は、ノードのオブジェクトのうちの各々に対して計算されることが必要とされない。クエリーオブジェクトとノードに含まれるオブジェクトとの間の距離は、基準に基づいて選択的に計算され得、基準は、それが、新しい距離が計算される必要とされないようである。他のノードが索引構造のリーフノードである場合に、距離を計算することと、別のノードに選択的にアクセスすることとが、終了され得る。
【００２４】
アクセスされた他のノードがリーフノードである場合に、方法はさらに、閾値比較の結果に基づいて、リーフノードのオブジェクトとクエリーオブジェクトとの間の距離を選択的に決定することを含み得る。リーフノードの所与のオブジェクトとクエリーオブジェクトとの間の距離は、閾値比較の結果に基づいて選択的に決定され得る。閾値比較は、第１の距離と第２の距離との差異の係数と閾値を比較することを含み得る。第１の距離は、クエリーオブジェクトとのリーフノードの親オブジェクトとの距離であり得る。第２の距離は、リーフノードの親オブジェクトとリーフノードのそれぞれの所与のオブジェクトとの間の距離であり得る。リーフノードの任意の所与のオブジェクトに対して、それぞれの所与のオブジェクトとのクエリーオブジェクトとの間の距離は、このような閾値比較の結果に基づいて選択的に計算され得る。それによって、サーチ時間がさらに減少され得る。
【００２５】
サーチにおいて、クエリーオブジェクトからの所定の距離内に配置された全部のオブジェクトが識別され得る。この距離は、距離メトリックに従って規定される。これは、所与の閾値を超過しない、クエリーオブジェクトへの相違を有する全部のオブジェクトが識別され、かつユーザーに出力されることを可能にする。
【００２６】
代替的に、またはさらに、距離メトリックに従って決定された、索引構造のクエリーオブジェクトのｋ個の最も近い近傍点を表す整数個（ｋ＞１）のオブジェクトが識別され得る。これは、距離メトリックに基づいてクエリーオブジェクトの最も類似であるｋ個のオブジェクトが識別され、かつユーザーに出力されることを可能にする。
【００２７】
識別されたオブジェクトは、クエリーオブジェクトとそれぞれの識別されたオブジェクトとの間の距離に基づいて出力され得る。識別されたオブジェクトを出力する場合に、オブジェクトは、クエリーオブジェクトとそれぞれに識別されたオブジェクトとの間の距離に従って格納され得る。例として、光学出力ユニットを介して出力することに対して、クエリーオブジェクトからの最も近い距離を有するオブジェクトは、最も上の位置または最も左の位置において出力され得、他のオブジェクトは、クエリーオブジェクトからの距離を増加する順序で出力され得る。同様に、オーディオ出力ユニットを介して出力することに対して、クエリーオブジェクトからの最も近い距離を有するオブジェクトが最初に出力され得、他のオブジェクトは、その後、クエリーオブジェクトからの距離を増加する順序で連続して出力され得る。
【００２８】
もう１つの側面に従って、ナビゲーションデバイスが提供される。ナビゲーションデバイスは、規則デバイスと処理デバイスとを含む。記憶デバイスは、複数のオブジェクトを含むデータベースに対して索引構造を格納し、索引構造は、複数のノードを含む。処理デバイスは、記憶デバイスに結合される。クエリーオブジェクトに対して類似性サーチを行うために、処理デバイスは、複数のオブジェクトのうちの少なくとも１つのオブジェクトに関連付けられた索引構造のノードにアクセスするように構成される。処理デバイスはさらに、距離メトリックに従って、クエリーオブジェクトと少なくとも１つのオブジェクトとの間の距離を決定するように構成される。処理デバイスはさらに、決定された距離に基づいて、索引構造の別のノードに選択的にアクセスするように構成される。
【００２９】
このようなナビゲーションデバイスは、ファジィサーチが実装されることを可能にし、ファジーサーチは、正確なマーチについての情報を提供するだけではなく、データベースの最も類似なオブジェクトについての情報も検索する。ナビゲーションデバイスにおいて、クエリーオブジェクトと索引構造のノードのオブジェクトとの距離は、アクセスされるべきである他のノードを識別するために決定される。これは、サーチが効率的に行われることを可能にする。クエリーオブジェクトから閾値より大きな距離を有するオブジェクトを含むかまたは指すアクセスノードが必要とされない。距離メトリックに従って決定された距離を使用することによって、クエリーオブジェクトと索引構造に含まれるオブジェクトとの間の類似または相違が、量的に評価される。
【００３０】
オブジェクトは、音素ストリングおよび／またはテキストストリングであり得る。
【００３１】
索引構造は、メトリック索引構造であり得る。
【００３２】
ナビゲーションデバイスは、入力ユニットを含み得る。処理デバイスは、入力ユニットからクエリーオブジェクトを受信するように、または入力ユニットで受信された入力に基づいてクエリーオブジェクトを生成するように、入力ユニットと結合され得る。処理デバイスは、クエリーオブジェクトを生成するために、テキスト−音素変換を行うように構成され得る。
【００３３】
ナビゲーションデバイスは、出力ユニットを含み得る。処理デバイスは、類似性サーチにおいて見つけられた複数のオブジェクトが出力ユニットを介して出力されるように、出力ユニットを制御するように構成され得る。処理デバイスは、出力オブジェクトがクエリーオブジェクトとそれぞれの出力オブジェクトとの距離に従って格納されるように、出力ユニットを制御するように構成され得る。
【００３４】
処理デバイスは、距離メトリックに従って決定された、クエリーオブジェクトからの固定のサーチ半径より近い距離を有する全部のオブジェクトを識別するように構成され得る。処理デバイスは、代替的に、またはさらに、クエリーオブジェクトのｋ個の最も近い近傍点であるｋ＞１個のオブジェクトを識別するように構成され得る。
【００３５】
処理デバイスは、任意の側面または実施形態に従って類似性サーチ方法を行うように構成され得る。
【００３６】
もう１つの側面に従って、ナビゲーションデバイスデータベースに対してメトリック索引構造を生成する方法が提供される。データベースは、複数のオブジェクトを含む。方法において、索引構造の他のノードへのポインターを含む索引構造のディレクトリノードと索引構造のリーフノードとが生成される。ノードを生成することは、複数組のオブジェクトに対して、オブジェクトと組のオブジェクトのオブジェクトとの間の距離をそれぞれに決定し、それによって複数の距離を決定することを含む。距離は、それぞれ、距離メトリックに従って決定される。複数の距離に基づいて、ディレクトリノードに含まれるべきであるオブジェクトとリーフノードに含まれるべきであるオブジェクトとが識別される。
【００３７】
この方法を用いて、索引構造が生成され、類似性サーチ方法において、そして任意の側面および実施形態のナビゲーションデバイスにおいて使用され得る。生成されたメトリック構造は、オブジェクトの間の相対的距離である決定された複数の距離に従って組織化される。これは、また多重次元の空間の座標によって規定されないオブジェクトに対して、メトリック索引構造がセットアップされることを可能する。
【００３８】
オブジェクトは、音素ストリングまたはアルファベットや数値のストリングであり得る。
【００３９】
索引構造を生成する場合に、距離メトリックは、ストリングメトリックに対する複数の距離定義のうちの任意の１つから選択され得る。例として、距離メトリックは、Ｌｅｖｅｎｓｈｔｅｉｎ距離に基づき得る。距離関数はまた、Ｄａｍｅｒａｕ−Ｌｅｖｅｎｓｈｔｅｉｎ距離、Ｊａｒｏ−Ｗｉｎｋｌｅｒ距離、Ｈａｍｍｉｎｇ距離、Ｓｏｕｎｄｅｘ距離メトリックに従って決定される距離、Ｎｅｅｄｌｅｍａｎ−Ｗｕｎｓｃｈ距離、Ｇｏｔｏｈ距離、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ−Ｇｏｔｏｈ距離、Ｐ≧１を有するＬｐ距離または反射の公準、対称性および三角不等式に従う任意の他のストリングメトリックのうちの任意の１つであり得る。
【００４０】
方法は、ディレクトリノードに含まれるオブジェクトに対して、それぞれのオブジェクトとオブジェクトを指す索引構造のサブツリーに含まれる任意のオブジェクトとの距離の上限を格納することを含み得る。この上限、またはカバレッジ半径は、索引構造内に格納され得る。
【００４１】
方法は、代替的に、またはさらに、親オブジェクトを有するノードに含まれるオブジェクトに対して、それぞれのオブジェクトとその親オブジェクトとの距離を格納することを含み得る。
【００４２】
方法において、索引構造は、反復のやり方で成長され得る。方法は、ノードに追加のオブジェクトを挿入することを含み得る。そのために、オブジェクトが挿入されるべきであるノードが識別され得る。ノードを識別することは、挿入されるべきであるオブジェクトと索引構造のディレクトリノードのオブジェクトとの距離を決定することを含み得る。
【００４３】
方法はさらに、ノードを分割することを含み得る。そのために、オブジェクトの挿入の後に、ノードのオブジェクトの数は、オブジェクトの固定の最大の数より大きいか否かが決定され得る。数が最大の数を超える場合に、ノードが分割される。ノードを分割することは、新しいディレクトリノードに含まれるべきであるノードからのオブジェクトを選択することと、オブジェクトを２つの新しいリーフノードのうちの１つに割り当てることとを含み得る。ノードを分割することは、新しいディレクトリノードの２つのオブジェクトの２つのカバレッジエリアの間のオーバーラップが閾値以下に減少され、または最小化されるように行われ得る。
【００４４】
もう１つの側面に従って、ナビゲーションデバイスデータベースのためのメトリック索引構造が提供される。メトリック索引構造は、索引構造の他のノードへのポインターを含むディレクトリノードとリーフノードとを含む。ノードのうちの少なくともいつくかは、メトリックに従って決定された、索引構造のオブジェクトの間の距離についての情報を表す距離情報を含み得る。少なくともディレクトリノードは、ディレクトリノードのオブジェクトと、それぞれのオブジェクトに対する索引構造のサブツリーに含まれる任意のオブジェクトとの距離の上限を含み得る。
【００４５】
前述の特徴と以下に説明されるべきであるそれとは、示されるそれぞれの組み合わせだけではなく、他の組み合わせまたは単独に使用され得ることが理解されるべきである。
【００４６】
本発明は、例えば以下の項目を提供する。
（項目１）
索引構造（１０；７０）を用いてナビゲーションデバイスデータベースにおいて類似性サーチを行う方法であって、該データベースは、複数のオブジェクトを含み、該索引構造（１０；７０）は、複数のノード（１１−１７；７１−７５）を含み、
該方法は、
クエリーオブジェクト（５１）を受信することと、
該複数のオブジェクトのうちの少なくとも１つのオブジェクト（５２，５５，５９，６０）に関連付けられる該索引構造（１０；７０）のノード（１１−１３；７１−７３）にアクセスすることと、
該ノード（１１−１３；７１−７３）に関連付けられた該少なくとも１つのオブジェクト（５２，５５，５９，６０）の各々のオブジェクトに対して、それぞれ、該クエリーオブジェクト（５１）と該オブジェクトとの間の距離（６５，６６）を決定することであって、該距離（６５，６６）は、それぞれ、距離メトリックに従って決定される、ことと、
該決定された距離（６５，６６）に基づいて、該索引構造（１０；７０）の別のノード（１２−１７；７２−７５）に選択的にアクセスすることと
を含む、方法。
（項目２）
上記クエリーオブジェクト（５１）は、音素ストリングまたはテキストストリングである、上記項目のいずれかに記載の方法。
（項目３）
上記クエリーオブジェクト（５１）を受信することは、テキスト入力を受信することと、テキスト−音素変換を行うこととを含む、上記項目のいずれかに記載の方法。
（項目４）
上記索引構造（１０；７０）は、上記少なくとも１つのオブジェクト（５２，５５，５９，６０）と該索引構造（１０；７０）の他のオブジェクトとの間の距離についての距離情報をさらに含み、
該他のノード（１２−１７；７２−７５）は、該距離情報と、上記決定された距離（６５，６６）とに基づいて選択的にアクセスされる、上記項目のいずれかに記載の方法。
（項目５）
上記ノード（１１−１３；７１−７３）は、いくつかのオブジェクト（５２，５５）に関連付けられ、
上記距離情報は、該いくつかのオブジェクト（５２，５５）の各々に対して、該それぞれのオブジェクト（５２，５５）と、該それぞれのオブジェクト（５２，５５）に関連付けられた上記索引構造（１０；７０）のサブツリーに含まれる任意のオブジェクト（５９−６４）との間の距離の上限（５３，５６）を含む、上記項目のいずれかに記載の方法。
（項目６）
上記クエリーオブジェクト（５１）は、音素ストリングまたはテキストストリングであり、
該クエリーオブジェクト（５１）を受信することは、テキスト入力を受信することと、テキスト−音素変換を行うこととを含む、上記項目のいずれかに記載の方法。
（項目７）
オブジェクトは、上記決定された距離（６５，６６）に基づいて、上記類似性サーチから選択的に取り除かれる、上記項目のいずれかに記載の方法。
（項目８）
上記他のノード（１２−１７；７２−７５）が上記索引構造（１０；７０）のリーフノード（１４−１７；７４，７５）である場合に、上記距離（６５，６６）を決定することと、上記別のノード（１２−１７；７２−７５）に選択的にアクセスすることとが終了される、上記項目のいずれかに記載の方法。
（項目９）
上記距離メトリックに従って決定された、上記クエリーオブジェクト（５１）からの所定の距離（５８）内に配置された全てのオブジェクトが識別される、上記項目のいずれかに記載の方法。
（項目１０）
１より大きい整数ｋ個のオブジェクトが識別され、該ｋ個のオブジェクトは、上記距離メトリックに従って決定された、上記クエリーオブジェクト（５１）のｋ個の最も近い近傍点を表す、上記項目のいずれかに記載の方法。
（項目１１）
上記識別されたオブジェクトは、上記クエリーオブジェクト（５１）と、それぞれの識別されたオブジェクトとの間の距離に基づいて決定された順序で出力される、上記項目のいずれかに記載の方法。
（項目１２）
ナビゲーションデバイスであって、該ナビゲーションデバイスは、
複数のオブジェクトを含むデータベースに対する索引構造（１０；７０）を格納する記憶デバイス（３）であって、該索引構造（１０；７０）は、複数のノード（１１−１７；７１−７５）を含む、記憶デバイス（３）と、
該記憶デバイス（３）に結合された処理デバイス（２）と
を含み、該処理デバイス（２）は、クエリーオブジェクト（５１）に対して類似性サーチを行うために、
該複数のオブジェクトのうちの少なくとも１つのオブジェクト（５２，５５，５９，６０）に関連付けられた該索引構造（１０；７０）のノード（１１−１３；７１−７３）にアクセスすることと、
距離メトリックに従って、該クエリーオブジェクト（５１）と該少なくとも１つのオブジェクト（５２，５５，５９，６０）との間の距離（６５，６６）を決定することと、
該決定された距離（６５，６６）に基づいて、該索引構造（１０；７０）の別のノード（１２−１７；７２−７５）に選択的にアクセスすることと
を行うように構成される、ナビゲーションデバイス。
（項目１３）
上記処理デバイス（２）は、上記項目のいずれかに記載の方法を行うように構成される、上記項目のいずれかに記載のナビゲーションデバイス。
（項目１４）
複数のオブジェクトを含むナビゲーションデバイスデータベースのためのメトリック索引構造（１０；７０；１１０）を生成する方法であって、該方法は、該索引構造（１０；７０；１１０）の他のノードへのポインターを含む該索引構造のディレクトリノード（１１−１３；７１−７３；１１１，１１４）を生成することと、該索引構造のリーフノード（１４−１７；７４；７５；１１３，１１５，１１６）を生成することとを含み、
該ディレクトリノード（１１−１３；７１−７３；１１１，１１４）と該リーフノード（１４−１７；７４；７５；１１３，１１５，１１６）とを生成することは、
該オブジェクトの複数の組に対して、それぞれ、該オブジェクトの組のオブジェクト間の距離を決定することによって複数の距離を決定することであって、該距離は、それぞれ、距離メトリックに従って決定される、ことと、
該複数の距離に基づいて、ディレクトリノード（１１−１３；７１−７３；１１１，１１４）に含まれるべきであるオブジェクトと、リーフノード（１４−１７；７４；７５；１１３，１１５，１１６）に含まれるべきであるオブジェクトとを識別することと
を含む、方法。
（項目１５）
上記オブジェクトは、音素ストリングまたはテキストストリングである、上記項目のいずれかに記載の方法。
（項目１６）
上記ディレクトリノードおよび／または上記リーフノードにおいて、上記複数の距離から導かれた距離情報を格納することを含む、上記項目のいずれかに記載の方法。
【００４７】
（摘要）
ナビゲーションデバイスデータベースにおいて類似性サーチを行う方法は、メトリック索引構造を使用する。索引構造は、複数のノードを含む。クエリーオブジェクト（５１）が受信される場合に、少なくとも１つのオブジェクト（５２，５５，５９，６０）に関連付けられる索引構造のノードがアクセスされる。クエリーオブジェクト（５１）と少なくとも１つのオブジェクト（５２，５５，５９，６０）との間の距離（６５，６６）は、距離メトリックに従って決定される。決定された距離に基づいて、索引構造の別のノードが選択的にアクセスされる。
【００４８】
実施形態の先述および他の特徴は、添付の図面に関して読まれた場合、実施形態の以下の詳細な説明から、より明らかとなる。図面において、類似した参照数字は、類似した要素を指す。
【図面の簡単な説明】
【００４９】
【図１】図１は、ナビゲーションデバイスの概略ブロック図である。
【図２】図２は、索引構造の概略表示である。
【図３】図３は、索引構造のノードにおけるデータエントリの概略表示である。
【図４】図４は、索引構造のノードにおけるデータエントリの概略表示である。
【図５】図５は、類似性サーチを用いる方法のフローチャートである。
【図６】図６は、類似性サーチを行う方法のフローチャートである。
【図７】図７は、図６の方法を説明するためのデータベースオブジェクトの概略表示である。
【図８】図８は、図６の方法を説明するための索引構造の概略表示である。
【図９】図９は、類似性サーチを用いる方法のフローチャートである。
【図１０】図１０は、索引構造を生成する方法のフローチャートである。
【図１１】図１１は、図１０の方法を説明するための索引構造の概略表示である。
【図１２】図１２は、図１０の方法を説明するための索引構造の概略表示である。
【発明を実施するための形態】
【００５０】
（詳細な説明）
図１は、実施形態に従う乗り物のナビゲーションデバイス１を概略的に例示する。ナビゲーションデバイス１は、例えば、メモリに記憶される制御命令に従って、ナビゲーションデバイス１の動作を制御する処理デバイス２を含む。処理デバイス２は、例えば、１つ以上のマイクロプロセッサ、デジタルシグナルプロセッサまたは特定用途向け集積回路の形態の中央処理デバイスを含み得る。ナビゲーションデバイス１は、記憶デバイス３をさらに含む。記憶デバイス３は、揮発性または不揮発性記憶媒体またはメモリであり得る。記憶デバイス３は、ランダムアクセスメモリ、フラッシュメモリまたはハードドライブのようなさまざまなタイプの記憶またはメモリ媒体のうちのいずれか１つ、またはいずれかの組み合わせを含み得るが、コンパクトディスク（ＣＤ）、ＤＶＤ、メモリカードなどのようなリムーバルメモリも含み得る。ナビゲーションデバイス１は、また、情報をユーザーに出力する出力インターフェース４を含む。出力インターフェース４は、光学出力デバイス、オーディオ出力デバイスまたはそれらの組み合わせを含み得る。ナビゲーションデバイス１は、また、入力インターフェース５を含み、入力インターフェース５は、ユーザーが情報を入力することを可能にする。特に、入力インターフェース５は、ユーザーがテキスト情報または音声情報を入力することを可能にし得る。
【００５１】
ナビゲーションデバイスは、位置センサーおよび／またはワイヤレス受信器および／または乗り物のインターフェースのようなさらなるコンポーネントを含み得る。位置センサーは、ナビゲーションデバイス１がインストールされている乗り物の現在の位置を決定するように適合され得る。位置センサーは、ＧＰＳ（全地球測位システム）センサー、ガリレオセンサー、モバイル通信網に基づく位置センサーなどを含み得る。ワイヤレス受信器は、記憶デバイス３に記憶されたデータベースを更新するための情報を受信するように構成され得る。乗り物のインターフェースは、処理ユニット２が情報を他の乗り物システムから得ることを可能にし得るか、または乗り物状態情報を乗り物のインターフェースを介して得ることを可能にし得る。例えば、乗り物のインターフェースは、ＣＡＮ（コントローラーエリアネットワーク）またはＭＯＳＴ（メディアオリエンテッドデバイストランスポート）インターフェースを含み得る。
【００５２】
記憶デバイス３は、複数のオブジェクトを含むデータベースを記憶する。複数のオブジェクトは、テキストストリングまたは音素ストリングを含み得る。例示として、データベースは、道路名称を表すオブジェクト、ポイントオブインタレスト（ＰＯＩ）の名称を表すオブジェクトおよび／または道路またはＰＯＩに関してさらなる情報を表すオブジェクトを含み得る。そのような情報は、形態を有し得るか、またはテキストストリングまたは音素ストリングまたはマルチメディアオブジェクトを含み得る。
【００５３】
記憶デバイス３は、データベースに対して索引構造を記憶する。ナビゲーションデバイス１の使用において、プロセッサ２は、索引構造を用いて類似性サーチを行う。プロセッサ２は、入力インターフェース５において受信された入力をクエリーオブジェクトとして用い得るか、または入力に関するさらなる動作を行い得ることによってクエリーオブジェクトを生成する。次いで、プロセッサ２は、クエリーオブジェクトに対して索引構造を用いて類似性サーチを行う。類似性サーチは、クエリーオブジェクトと、データベースに記憶されたオブジェクトとの間の距離を計算することを含む。本明細書において用いられた場合、「計算する」は、さまざまな方法によって実装され得、ルックアップ動作を含む。距離は、クエリーオブジェクトと索引構造におけるオブジェクトとの相違に対する量的測定値を提供する。サーチにおいて見つかったいくつかの非常に類似したオブジェクトがユーザーに出力インターフェース４を介して出力される。例示として、プロセッサ２は、光学出力インターフェース４上にリストを生成し得る。光学出力インターフェース４において、クエリーオブジェクトから最も小さい距離を有する索引構造のオブジェクトが、クエリーオブジェクトからの距離によって決定された順番に羅列される。
【００５４】
索引構造は、論理的にデータベースから分離している。あるいは、データベースは、索引構造と結合し得る。
【００５５】
索引構造は、いずれか適切な技術を用いて実装され得る。限定としてよりも、むしろ例示として、索引構造は、ＳＱ Ｌｉｔｅを用いて実装され得る。索引構造は、ユーザー定義の索引構造としてデータベースシステム、特にリレーショナルデータベースシステムに実装され得る。リレーショナルデータベースは、テキストストリングまたは音素ストリングのためのテーブルもしくは対のテキストストリングと対の音素ストリングとの間の距離のための別のテーブルを含み得る。
【００５６】
データベースのための索引構造は、索引ツリーとして組織化され得る。索引構造は、複数のノードを含み得、ノードの少なくとも一部は、他のノードへのポインターを含むディレクトリノードであり、少なくとも一部の他のノードは、他のノードへのポインターを含まないリーフノードである。ノードの各々は、少なくとも１つおよび一般的な複数のオブジェクトに関連付けられ得る。ディレクトリノードは、ディレクトリノードに含まれるオブジェクトに対して、それらのオブジェクトの各々に関連付けられたそれぞれのサブツリーのルートへのポインターを記憶し得る。
【００５７】
記憶デバイス３に記憶された索引構造は、メトリック索引構造であり、メトリック索引構造は、距離メトリックを用いてサーチされ得る。さらに、索引構造は、また、距離メトリックに従って組織化される。つまり、索引構造は、距離メトリックに従って、決定されたデータベースのオブジェクトの間の相対的な距離に基づいてサブツリーに区分される。
【００５８】
一般的な用語に従って、本明細書における「距離メトリック」または「メトリック」は、以下の条件を満たす空でないセットＭのオブジェクトに対して規定された距離測定値を指す：
反射性（不可識別者同一とも呼ばれる）：
∀ｘ，ｙ∈Ｍ： ｘ＝ｙの場合かつｘ＝ｙの場合のみｄ（ｘ，ｙ）＝０； （１）
対称性：
∀ｘ，ｙ∈Ｍ： ｄ（ｘ，ｙ）＝ｄ（ｙ，ｘ） （２）
三角不等式：
∀ｘ，ｙ，ｚ∈Ｍ： ｄ（ｘ，ｙ）≦ｄ（ｘ，ｙ）＋ｄ（ｙ，ｚ） （３）
上の公準（１）〜（３）が満たされた場合、距離も正値性公準を満たすことになる：
∀ｘ，ｙ∈Ｍ： ｄ（ｘ，ｙ）≧０ （４）
セットＭおよびメトリックｄのタプル（Ｍ，ｄ）は、メトリック空間とも呼ばれる。
【００５９】
メトリック（このメトリックに従って、索引構造が組織化される）（また、索引構造におけるサーチを行うために用いられる）は、とりわけデータベースにおけるオブジェクトに応じて、さまざまな定義から選択され得る。例示として、テキストストリングまたは音素ストリングであるオブジェクトに対して、Ｌｅｖｅｎｓｈｔｅｉｎ距離がメトリックを規定する。Ｌｅｖｅｎｓｈｔｅｉｎ距離は、索引構造を作成するときと、索引構造において類似性サーチを行うときとの両方で用いられ得る。Ｌｅｖｅｎｓｈｔｅｉｎ距離は、編集距離とも呼ばれる。２つのストリングの間のＬｅｖｅｎｓｈｔｅｉｎ距離は、１つのストリングを他のストリングに変形させるために必要な編集の最小数として規定され、許容可能な編集動作は、単一の文字の挿入、削除または交換である。他のメトリックも索引構造を組織化することと、索引構造において類似性サーチが行われた場合に距離を計算することとのために用いられ得る。
【００６０】
他のメトリックが用いられ得る。例示として、距離機能がＤａｍｅｒａｕ−Ｌｅｖｅｎｓｈｔｅｉｎ距離、Ｊａｒｏ−Ｗｉｎｋｌｅｒ距離、Ｈａｍｍｉｎｇ距離、Ｓｏｕｎｄｅｘ距離メトリックに従って決定された距離、Ｎｅｅｄｌｅｍａｎ−Ｗｕｎｓｃｈ距離、Ｇｏｔｏｈ距離、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ−Ｇｏｔｏｈ距離、ｐ≧１を有するＬｐ距離または反射性、対称性、三角不等式の公準を用いてコンパイルする任意の他のストリングメトリックからのいずれか１つとなるように選択され得る。
【００６１】
記憶媒体３に記憶された索引構造は、オブジェクトおよびサーチツリーを規定する他のノードへのポインターを含み得るだけでなく、さらに索引構造におけるオブジェクト間の距離を示す距離情報も含み得る。そのような距離情報は、サーチを行う場合、索引構造から検索され得る。そのような距離情報は、下でさらに詳細に説明されるように、特に、オブジェクトまたはノードを類似性サーチから取り除くために用いられ得る。
【００６２】
図２は、索引構造１０の概略的表示である。図２においてツリーのような構造として示されるが、索引構造は、一般的にいずれか適切なフォーマットで記憶され得、例えば、リレーショナルデータベースにおけるユーザー定義の索引構造として記憶され得る。
【００６３】
索引構造は、ディレクトリノード１１〜１３およびリーフノード１４〜１７を含む。ディレクトリノード１１〜１３の各々は、他のノードへのポインターを含む。各ポインターは、それぞれのノードに含まれるオブジェクトにそれぞれ関連付けられ得る。例示として、ルートノード１１は、第１のオブジェクトに関連付けられたデータエントリ２１および第２のオブジェクトに関連付けられたデータエントリ２２を含み得る。データエントリ２１は、ディレクトリノード１２へのポインターを含み得る。ディレクトリノード１２は、第１のオブジェクトのサブツリーのルートである。データエントリ２２は、ディレクトリノード１３へのポインターを含み得、ディレクトリノード１３は、第２のオブジェクトのサブツリーのルートである。
【００６４】
ディレクトリノード１２は、データベースの他のオブジェクトに関連付けられたデータエントリ２３、２４を含み得る。データエントリ２３、２４は、それぞれ、別のノードへのポインターを含み得る。図２において例示される構造において、データエントリ２３、２４は、それぞれ、リーフノード１４、１５へのポインターを含む。ディレクトリノードのより大きい階層が実装され得る。同様に、ディレクトリノード１３は、データベースの他のオブジェクトに関連付けられたデータエントリ２５、２６を含み得る。データエントリ２５、２６は、それぞれ、リーフノード１６、１７のような別のノードへのポインターをそれぞれ含み得る。
【００６５】
リーフノード１４〜１７は、データベースの１つまたは複数のオブジェクトに関連付けられたデータエントリをそれぞれ含み得る。例示として、リーフノード１４は、データベースの３つのオブジェクトに関連付けられたデータエントリ２７〜２９を含んで示される。
【００６６】
索引構造において、サーチツリーは、距離メトリックに従って区分される。この目的のために、データ２１によって表される第１のオブジェクトおよびデータ２２によって表される第２のオブジェクトは、ルートノード１２を有する第１のサブツリーに含まれる全てのオブジェクトが第１のオブジェクトの周りに第１のカバレッジ半径を有するカバレッジエリア内に配置され、ルートノード１３を有する第２のサブツリーに含まれる全てのオブジェクトが第２のオブジェクトの周りに第２のカバレッジ半径を有するカバレッジエリア内に配置されるように、選択され得る。換言すると、第１のカバレッジ半径は、データエントリ２１によって表されるオブジェクトからのノード１２、１４および１５のうちのいずれか１つによって表される任意のオブジェクト間の距離の最大であり得る。データエントリ２１は、このサブツリーの親である。第２のカバレッジ半径は、データエントリ２２によって表されるオブジェクトからのノード１３、１６および１７のうちのいずれか１つによって表される任意のオブジェクト間の距離の最大であり得る。データエントリ２２は、このサブツリーの親である。
【００６７】
ルートノード１１における第１のオブジェクトおよび第２のオブジェクトならびに関連付けられたサブツリーにおけるオブジェクトは、第１および第２のカバレッジエリアが好ましくは可能な限り小さい重複を有するように選択される。さらに、ルートノード１１における第１のオブジェクトおよび第２のオブジェクトならびに関連付けられたサブツリーにおけるオブジェクトは、第１のオブジェクトとルート１２を有するサブツリーに含まれるいずれかのオブジェクトとの間の第１の最大距離および第２のオブジェクトとルート１３を有するサブツリーに含まれるいずれかのオブジェクトとの第２の最大距離が可能な限り小さいままであるように選択され得る。したがって、索引構造は、距離メトリックに従って決定されたオブジェクト間の近接に従って区分される。
【００６８】
上の索引構造を組織化するために概説された基準は、ルートノード１１に当てはまるだけでなく、いずれかのディレクトリノード１２、１３にも当てはまる。つまり、オブジェクトは、ディレクトリノードにおける異なるオブジェクトのカバレッジエリアの重複を減少させるため、さらに、カバレッジエリアのサイズを減少させるためにディレクトリおよびリーフノードに組織化される。そのような索引構造を生成するための体系的なアプローチは、図１０〜１２を参照して下で説明される。
【００６９】
いくつかの実施形態において、索引構造のディレクトリノードは、索引構造に含まれるオブジェクト間の距離に関する情報を含み得る。ディレクトリノードにおけるデータエントリ２１〜２６は、それぞれ、オブジェクトと、このオブジェクトが指すサブツリーに含まれるいずれかのオブジェクトとの間の距離の上限を含み得る。上限は、これらの距離の最大であり得る。例示として、データエントリ２１は、データエントリ２１によって表される第１のオブジェクトと、ノード１２、１４および１５におけるいずれかのオブジェクトとの間の距離の上限を含み得る。データエントリ２２は、データエントリ２２によって表される第２のオブジェクトと、ノード１３、１６および１７におけるいずれかのオブジェクトとの間の距離の上限を含み得る。データエントリ２３は、データ２３によって表されるオブジェクトと、ノード１４などにおけるオブジェクトのうちのいずれか１つとの間の距離の上限を含み得る。この上限に基づいて、除外が類似性サーチにおいて行われ得る。
【００７０】
親オブジェクトを有する全てのノードにおけるデータは、それぞれのノードにおけるいずれかのオブジェクトに対して、オブジェクトと、その親オブジェクトとの間の距離に関する情報をさらに含み得る。この情報も類似性サーチにおける距離を推定するために用いられ得る。
【００７１】
索引構造は、Ｐ．Ｃｉａｃｃｉａ、Ｍ．ＰａｔｅｌｌａおよびＰ．Ｚｅｚｕｌａによって発展されたＭツリーとして特に組織化され得る。距離メトリックに従って組織化される他の索引構造も用いられ得る。例示として、索引構造は、ｖａｎｔａｇｅポイントツリーであり得る。
【００７２】
図３は、ディレクトリノードに含まれるオブジェクトに関連付けられたデータエントリ３１に対する例示的データ構造を示す。Ｍツリーにおいて用いられる例示的データエントリが例示される。データエントリ３１は、オブジェクトＯｒを含む。あるいは、オブジェクトの特徴量がデータ３１に含まれ得る。あるいは、オブジェクトの識別子が、データ３１に含まれ得る。
【００７３】
データエントリ３１は、オブジェクトＯｒに対するサブツリーのルートノードへのポインターｐｔｒ（Ｔ（Ｏｒ））をさらに含む。
【００７４】
ディレクトリノードが索引構造のルートノードでない場合、データエントリ３１は、オブジェクトＯｒとその親オブジェクトＰ（Ｏｒ）との間の距離ｄ（Ｏｒ；Ｐ（Ｏｒ））をさらに含み得る。そのような索引構造への距離を含むことによって、値ｄ（Ｏｒ；Ｐ（Ｏｒ））は、距離を推定するためか、および／またはサーチを取り除くために用いられ得る。類似性サーチの効率は、ランタイムにおいて向上され得る。
【００７５】
データエントリ３１は、オブジェクトＯｒと、ルートノードＴ（Ｏｒ）を有するサブツリーにおけるいずれかのオブジェクトとの間の距離の上限である半径ｒ（Ｏｒ）をさらに含み得る。半径ｒ（Ｏｒ）は、そのような距離の最大であることが規定され得る：
ｒ（Ｏｒ）＝ｍａｘｊ ｄ（Ｏｊ；Ｏｒ） （５）
ここで、最大は、ポインターｐｔｒ（Ｔ（Ｏｒ））が指すサブツリーにおける全てのオブジェクトＯｊに対して決定される。
【００７６】
図４は、索引構造のリーフノードに含まれるオブジェクトに関連付けられたデータエントリ３２に対する例示的データ構造を示す。Ｍツリーにおいて用いられる例示的データエントリが例示される。データエントリ３２は、オブジェクトＯｊを含む。あるいは、オブジェクトの特徴量がデータ３２に含まれ得る。あるいは、オブジェクトの識別子がデータ３２に含まれ得る。
【００７７】
データエントリ３２は、それぞれのオブジェクトＯｊとその親オブジェクトＰ（Ｏｊ）との間の距離ｄ（Ｏｊ；Ｐ（Ｏｊ））をさらに含み得る。そのような索引構造への距離を含むことによって、値ｄ（Ｏｊ；Ｐ（Ｏｊ））は、サーチ中に距離が計算されることを要求せずに、距離を推定するためか、および／またはサーチを取り除くために用いられ得る。
【００７８】
他のデータ構造が用いられ得る。例示として、データエントリ３１またはデータエントリ３２において示されるさまざまなフィールドエントリは、互いに近接して記憶される必要はない。リレーショナルデータベースにおけるユーザー定義の索引構造は、索引構造の記憶のために用いられ得る。
【００７９】
図５は、プロセッサ２によって索引構造を用いて行われ得る方法３３のフローチャートである。
【００８０】
３４において、入力が受信される。入力は、入力インターフェース４を介して受信されたユーザー入力であり得る。あるいは、入力は、プロセッサ２へ乗り物の他のシステムまたはデバイスによって提供され得るか、または乗り物の外側から受信され得る。入力はテキストストリングであり得る。
【００８１】
３５において、テキスト−音素変換が行われる。結果の音素ストリングは、クエリーオブジェクトとして機能する。
【００８２】
３６において、類似性サーチが索引構造を用いて行われる。索引構造は、距離メトリックに従って組織化されたメトリック索引構造である。索引構造は、図２〜４を参照して上で説明されたように構成され得る。類似性サーチを行うために、クエリーオブジェクトと、索引構造におけるオブジェクトとの間の距離が距離メトリックに従って決定される。
【００８３】
３７において、サーチにおいて見つかる最も関連するオブジェクトが出力される。最も関連するオブジェクトは、クエリーオブジェクトのｋ＞１個の最も近い近傍点であり得る。つまり、索引付けされたオブジェクトの中で、クエリーオブジェクトから最も小さい距離を有するｋ個のオブジェクトであり、距離は、距離メトリックに従って決定される。あるいは、最も関連するオブジェクトは、所定の閾値より小さいクエリーオブジェクトからある距離を有する索引構造における全てのオブジェクトであり得る。
【００８４】
３７における出力は、複数のオブジェクトが出力されるように行われ得る。オブジェクトは、クエリーオブジェクトからのそれぞれの距離によって決定された順序で出力され得る。
【００８５】
図５は、類似性サーチを行う方法４０のフローチャートである。方法４０は、プロセッサ２によって行われ得る。類似性サーチは、距離メトリックｄ（・；・）に従って組織化された索引構造を用いて行われる。オブジェクトのタイプに応じて、さまざまな距離メトリックのうちのいずれか１つが上で説明されたように選択され得る。索引構造は、図２〜４を参照して説明されたように構成され得る。
【００８６】
４１において、クエリーオブジェクトが受信される。クエリーオブジェクトを受信することは、テキスト−音素変換を行うような入力の処理をすることを含み得る。
【００８７】
４２において、索引構造のノードＮがアクセスされる。方法４０のステップは、ツリーを通るパスに沿って反復的に繰り返され得る。第１の反復において、ノードＮは、索引構造のルートノードであり得る。続く反復において、ノードＮは、索引構造のディレクトリノードであり得る。
【００８８】
４３において、ノードＮにおけるオブジェクトＯｒが選択される。異なるオブジェクトＯｒは、異なるオブジェクトＯｒがノードＮに含まれる順序で選択され得る。
【００８９】
４４において、クエリーオブジェクトＱと、ノードＮにおいて選択されたオブジェクトＯｒとの間の距離ｄ（Ｏｒ；Ｑ）が決定される。テキストまたは音素ストリングに対して、距離を決定することは、Ｌｅｖｅｎｓｈｔｅｉｎ距離またはいずれか他のストリングメトリックに従う距離を計算することを含み得る。４４における距離は、距離メトリックを用いて決定され、距離メトリックに従って、索引構造が区分される。
【００９０】
４５において、距離ｄ（Ｏｒ；Ｑ）がオブジェクトＯｒのカバレッジ半径ｒ（Ｏｒ）とサーチ半径Ｒとの総計より大きいか否かが決定される。サーチ半径Ｒは、固定された半径であり得る。あるいは、サーチ半径Ｒは、また、類似性サーチが継続するとダイナミックに調節され得る。例示として、サーチ半径Ｒは、Ｒがクエリーオブジェクトと、それまでに検索されたｋ番目の最も近い近傍点との間の距離に対応するように、ｋ個の最も近い近傍点サーチにおいて調節され得る。
【００９１】
距離ｄ（Ｏｒ；Ｑ）がカバレッジ半径ｒ（Ｏｒ）とサーチ半径Ｒとの総計より大きいことが決定された場合、方法は４５から４６へ進む。
【００９２】
４６において、オブジェクトＯｒに対するサブツリーにおける全てのオブジェクトがサーチから取り除かれる。サブツリーにおけるいずれかのオブジェクトと、オブジェクトＯｒとの間の距離の上限であるカバレッジ半径ｒ（Ｏｒ）の定義によって、オブジェクトＯｒに対するサブツリーにおけるオブジェクトは、距離ｄ（Ｏｒ；Ｑ）がｒ（Ｏｒ）とＲとの総計より大きい場合、クエリーオブジェクトＱからのサーチ半径Ｒより小さいか、または等しい距離を有し得ない。サーチを取り除くことによって、不要なサーチステップが避けられ得る。
【００９３】
距離ｄ（Ｏｒ；Ｑ）がカバレッジ半径ｒ（Ｏｒ）とＲとの総計より大きくないことが決定された場合、方法は４５から４７に進む。
【００９４】
４７において、サーチは、オブジェクトＯｒに対するサブツリーにおいて継続される。この目的のために、オブジェクトＯｒに対するサブツリーのルートノードＴ（Ｏｒ）がアクセスされる。ルートノードは、４５においてテストされた条件に基づいて選択的にアクセスされる。このサブツリーにおけるサーチを継続するために、ステップ４２〜４８がサブツリー内でリーフノードに達するまで繰り返され得る。索引構造のルートからリーフノードまでのパスに沿って、４５において試験された条件がこのパスに沿って横切ったいずれかのオブジェクトＯｒに対して満たされていない場合のみ、リーフノードに達する。
【００９５】
４７においてリーフノードに達した場合、リーフノードにおけるオブジェクトＯｊと、クエリーオブジェクトＱとの間の距離ｄ（Ｏｊ；Ｑ）が決定され得る。
ｄ（Ｏｊ；Ｑ）＜Ｒ （６）
の場合、オブジェクトＯｊは、続く出力に対して関連する索引付けられたオブジェクトのリストに含まれ得る。ｋ個の最も近い近傍点サーチが行われた場合、サーチ半径Ｒが更新され得る。つまり、式（６）が満たされ、オブジェクトＯｊが索引構造において識別された関連するオブジェクトのリストに含まれた場合、サーチ半径Ｒは、減少され得る。リーフノード（リーフノードに対して式（６）が満たされる）において、オブジェクトが見つからなかった場合、方法は４８に進む。
【００９６】
４８において、別のオブジェクトＯｒがノードＮにあるか否かが決定される。別のオブジェクトがある場合、オブジェクトＯｒのうちの別の１つが選択される４３に方法は戻る。
【００９７】
他のオブジェクトがノードＮにないことが決定された場合、方法は４９に進む。４９において、識別されたオブジェクトが出力される。出力は、複数のオブジェクトが出力されるように行われ得る。類似性サーチにおいて見つかったオブジェクトは、クエリーオブジェクトＱからのそれぞれの距離によって決定された順序で出力され得る。この距離は、ステップ４４またはステップ４７において先に決定されているので、距離は、識別されたオブジェクトを続く出力に対して順序付けられたリストにおいて組織化するために用いられ得る。あるいは、サーチ中に決定された距離は、クエリーオブジェクトＱからの距離に従うオブジェクトの続く選別のために登録され得る。
【００９８】
方法４０において、類似性サーチがクエリーオブジェクトと索引付けられたオブジェクトとの間の距離に基づいて行われる。このことは、クエリーオブジェクトおよび索引付けられたオブジェクトがユークリッド空間において規定されない場合ですら、サーチが行われることを可能にする。類似性サーチ４０は、多次元ベクトル空間において規定されたオブジェクトに対しても行われ得る。フォルトトレラントなサーチは、メトリック索引構造において、類似性サーチを用いて実装される。
【００９９】
方法において、サーチは、クエリーオブジェクトと、索引構造のオブジェクトとの間の距離に基づいて選択的に取り除かれ得る。取り除くことは、方法４０のステップ４５において確認された条件に基づくか、もしくは下で説明される代替の条件またはさらなる条件に基づいて行われ得る。
【０１００】
さらなる例示として、図７および図８への参照がなされる。図７は、オブジェクトの概略的表示５０であり、図８は、索引構造７０の概略的表示である。
【０１０１】
図７において示されるオブジェクトは、索引構造のルートノードに含まれるオブジェクト５２および５５を含む。オブジェクト５２に対するサブツリーに配置されるオブジェクトは、オブジェクト５２からのカバレッジ半径５３より小さいか、または等しい距離に配置される。オブジェクト５３に対するサブツリーに配置されるオブジェクトは、オブジェクト５５からのカバレッジ半径５６より小さいか、または等しい距離に配置される。概略的に例示されるように、オブジェクト５２に対するサブツリーにおけるオブジェクトは、第１のカバレッジエリア５４に配置される。オブジェクト５５に対するサブツリーにおけるオブジェクトは、第２のカバレッジエリア５７に配置される。索引構造は、カバレッジエリア５４および５７が小さい重複を有するように組織化される。オブジェクト５２に関連付けられたサブツリーにおけるオブジェクトは、オブジェクト５２の周りに集められ、オブジェクト５５に関連付けられたサブツリーにおけるオブジェクトは、オブジェクト５５の周りに集められる。
【０１０２】
オブジェクト５２に対するサブツリーのルートノードは、オブジェクト５９および６０を含む。オブジェクト５９および６０を含むノードは、ディレクトリノードである。オブジェクト５９に関連付けられたポインターは、オブジェクト６１のようなオブジェクト５９の近接にオブジェクトを含むリーフノードを指す。オブジェクト６０に関連付けられたポインターは、オブジェクト６２のようなオブジェクト６０の近接にオブジェクトを含むリーフノードを指す。
【０１０３】
オブジェクト６３、６４は、オブジェクト５５に関連付けられたサブツリーに含まれる。
【０１０４】
図８は、図７の表示に対応する索引構造７０を例示する。図８において、オブジェクトは、Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ、Ｈ、Ｉ、Ｊとラベル付けされる。
【０１０５】
索引構造は、オブジェクトＡおよびＢを有するルートノード７１を含む。ルートノード７１におけるオブジェクトＡは、例えば、図７の５２において示されたオブジェクトに対応する。ルートノード７１におけるオブジェクトＢは、例えば、図７の５５において示されたオブジェクトに対応する。
【０１０６】
索引構造は、オブジェクトＡに関連付けられたサブツリーに対するルートノードであるディレクトリノード７２を含む。ノード７２は、オブジェクトＣおよびＤを含む。ノード７２におけるオブジェクトＣは、例えば、図７の５９において示されたオブジェクトに対応する。ノード７２におけるオブジェクトＤは、例えば、図７の６０において示されたオブジェクトに対応する。
【０１０７】
索引構造は、オブジェクトＣを親ノードとして有するリーフノード７４を含む。ノード７４は、オブジェクトＧおよびＨを含む。ノード７４におけるオブジェクトＧは、例えば、図７の６１において示されたオブジェクトに対応する。索引構造は、オブジェクトＤを親ノードとして有するリーフノード７５を含む。ノード７５は、オブジェクトＩおよびＪを含む。ノード７５におけるオブジェクトＩは、例えば、図７の６２において示されたオブジェクトに対応する。
【０１０８】
索引構造は、オブジェクトＢに関連付けられたサブツリーにさらなるノード７３を含む。
【０１０９】
近接サーチがクエリーオブジェクト５１に対して行われると想定すると、サーチは、クエリーオブジェクトと索引におけるそれぞれのオブジェクトＡ〜Ｊとの間の距離を索引構造に含まれる距離情報と組み合わせて用いて、取り除かれ得る。サーチ半径Ｒは、図７の５８において概略的に示される。
【０１１０】
サーチ方法４０が開始された場合、索引構造のルートノード７１がアクセスされる。６６において示されるクエリーオブジェクトＱとオブジェクトＢとの間の距離ｄ（Ｑ；Ｂ）は、サーチ半径５８とカバレッジ半径５６との総計よりも大きい。そのため、オブジェクトＢに対するサブツリーにおいてサーチは行われない。
【０１１１】
クエリーオブジェクトＱと、６５において示されたオブジェクトＡとの間の距離ｄ（Ｑ；Ａ）は、５８において示されたサーチ半径と、５３において示されたオブジェクトＡに対するカバレッジ半径との総計より小さい。そのため、サーチは、オブジェクトＡに対するサブツリーにおいて継続される。方法４０のステップ４２〜４９をルートノード７２を有するサブツリーに対して繰り返すことによって、クエリーオブジェクト５１からのサーチ半径より小さいか、または等しい距離に配置されるオブジェクトＧ（図７においてシンボル６１によって表される）およびＩ（図７においてシンボル６２によって表される）が識別される。
【０１１２】
これらのオブジェクトを識別することによって、距離メトリックに従って測定して、クエリーオブジェクトとの相違が最も小さいオブジェクトを戻すフォルトトレラントなサーチが実装される。
【０１１３】
類似性サーチは、サーチをカバレッジ半径に基づいて取り除くことによって効率的に行われ得る。索引構造に含まれるさらなるデータは、サーチ効率をさらに向上させるために用いられ得る。例示として、オブジェクトと、それぞれの親オブジェクトとの間の距離が索引構造に記憶される場合、この情報は、ランタイムにおいて行われる必要がある距離計算の数を減少させるために用いられ得る。
【０１１４】
例示として、方法４０のステップ４２においてアクセスされたノードＮは、索引構造のルートノードではないディレクトリノードである場合、Ｐ（Ｏｒ）がノードオブジェクトＯｒの親を意味する
｜ｄ（Ｑ；Ｐ（Ｏｒ））―ｄ（Ｏｒ；Ｐ（Ｑｒ））｜≦ｒ（Ｏｒ）＋Ｒ （７）
である場合のみ、ステップ４４〜４７は、選択的に行われ得る。距離ｄ（，）はメトリックであり、三角不等式は、オブジェクトＯｒに対するサブツリーにおけるオブジェクトがＲの距離を有さないか、または式（７）が満たされない場合、クエリーオブジェクトＱからより短い距離を有さないことを確実にする。式（７）が満たされない場合、オブジェクトＯｒに対するサブツリーは、取り除かれ得る。
【０１１５】
式（７）は、いずれかのさらなる距離計算を要求せずに、確認され得る。量ｄ（Ｑ；Ｐ（Ｏｒ））は、親ノードに対する方法４０の先行する反復において決定された。量ｄ（Ｏｒ；Ｐ（Ｏｒ））は、索引構造から読まれ得る。式（７）の条件が満たされたか否かに応じて、方法４０のステップ４４における計算を選択的に行うことによって、計算コストがかかるランタイムにおける距離決定の数が減少され得る。
【０１１６】
さらなる例示として、リーフノードが方法４０のステップ４７においてアクセスされた場合、リーフノードにおけるオブジェクトＯｊとクエリーオブジェクトＱとの間の距離は、Ｏｊが含まれるリーフノードの親をＰ（Ｏｊ）が意味する
｜ｄ（Ｑ；Ｐ（Ｏｊ）−ｄ（Ｏｊ；Ｐ（Ｏｊ））｜≦Ｒ （８）
である場合のみ、選択的に決定され得る。ｄ（，）はメトリックなので、三角不等式は、ＯｊおよびクエリーオブジェクトＱは、Ｒの距離を有することができないか、または式（８）が満たされない場合、より短い距離を有することができないことを確実にする。式（８）が満たされない場合、ｄ（Ｑ；Ｏｊ）を決定することは要求されない。
【０１１７】
式（８）は、いずれかのさらなる距離計算を要求せずに確認され得る。量ｄ（Ｑ；Ｐ（Ｏｊ））は、親ノードに対する方法４０の先行するステップにおいて決定された。量（Ｏｊ；Ｐ（Ｏｊ））は、索引構造から読まれ得る。式（８）の条件が満たされた場合のみｄ（Ｑ；Ｐ（Ｏｊ））を選択的に計算することによって、計算コストがかかるランタイムにおける距離決定の数が減少され得る。
【０１１８】
図１〜８を参照して上で説明された実施形態に従う類似性サーチを行うデバイスおよび方法は、オブジェクトがテキストストリング、音素ストリングまたはマルチメディアオブジェクトである場合、特に用いられ得る。デバイスおよび方法は、音素ストリングとの最も小さい相違を有する索引構造におけるオブジェクトを識別するために用いられ得る。索引構造は、音素ストリングに対するフィルターとして用いられ得る。
【０１１９】
図９は、類似性サーチが用いられ得る方法８０のフローチャート表示である。
【０１２０】
８１において、認識器が入力に基づいて音素ストリングを決定する。入力は、テキストストリングであり得る。音素ストリングへの変換は、クラスターにおける音素間の距離（距離メトリックを用いて決定される）が閾値より下という意味で、互いに類似する音素に対応する異なる音素クラスターに基づき得る。
【０１２１】
８２において、音素ストリングは、索引構造を用いてフィルタリングされる。音素ストリングは、図１〜８のうちのいずれか１つを参照して上で説明された索引構造において、類似性サーチを行うことによってフィルタリングされ得る。いくつかの実装において、閾値より小さいか、または等しいクエリーオブジェクトからの距離を有するオブジェクトが決定され得る。代替の実装において、クエリーオブジェクトのｋ個の最も近い近傍点オブジェクトが決定され得る。
【０１２２】
８３において、音素フィルタリングの結果がスペルマッチャーに提供される。
【０１２３】
類似性サーチを行う方法のうちのいずれか１つおよび上で説明されたナビゲーションデバイスのうちのいずれか１つにおいて、索引構造はメトリック索引構造であり得る。類似性サーチを行う方法のうちのいずれか１つおよび上で説明されたナビゲーションデバイスのうちのいずれか１つにおいて、索引構造は、平衡サーチツリーに対応し得る。類似性サーチを行う方法のうちのいずれか１つ、および上で説明されたナビゲーションデバイスのうちのいずれか１つにおいて、索引構造は、ディレクトリノード毎およびリーフノード毎のエントリの数が固定されるように構成され得る。
【０１２４】
図１０〜１２を参照して、これらのプロパティーを有する索引構造を生成する方法が説明される。
【０１２５】
図１０は、索引構造を生成する方法９０のフローチャートである。方法９０は、類似性サーチとは別個に行われ得る。特に、方法９０は、ナビゲーションデバイスのためにデータを前処理する場合、行われ得る。索引構造は、サーバーコンピュータによってセントラルサイトにおいて構築され得、次いで、複数のナビゲーションデバイスに配備され得る。
【０１２６】
方法９０は、索引構造をボトムアップ態様で構築し得、さらなるオブジェクトが続いて索引構造に加えられる。索引構造は、類似性サーチを行う場合にも続いて用いられる距離メトリックを用いて構築される。
【０１２７】
挿入されたオブジェクトは、ストリングであり得、特に音素ストリングまたはテキストストリングであり得る。
【０１２８】
方法９０において、索引構造は、オブジェクトを挿入することと、オーバーフロー状態がノードにおいて生じた場合、ノードを分割することとによって構築される。ノードが分割された場合、新たなディレクトリノードが生成される。
【０１２９】
９１において、索引構造に挿入されるオブジェクトＯｉが検索される。オブジェクトは、音素ストリングまたはテキストストリングであり得る。
【０１３０】
９２において、索引構造のノードＮがアクセスされる。１つしかノードがない場合、このノードがアクセスされる。索引構造が既にディレクトリノードを含んでいる場合、最も高いディレクトリノード（つまり、構造のルートノード）がアクセスされる。
【０１３１】
９３において、ノードＮがリーフノードか否かが決定される。ノードがリーフノードである場合、方法は９８において継続する。そうでない場合、方法は、９４において継続する。
【０１３２】
９４において、距離ｄ（Ｏｋ；Ｏｉ）は、挿入されるオブジェクトＯｉと、ノードに含まれる全てのオブジェクトＯｋとの間で決定される。距離は、それぞれ、距離メトリックに従って決定される。
【０１３３】
９５において、ノードＮに含まれるオブジェクトＯｋが決定され、オブジェクトＯｋに対してｄ（Ｏｋ；Ｏｉ）は、最小となる。
【０１３４】
９６において、新たなノードＮが選択され、ノードＮは、オブジェクトＯｋに対するサブツリーのルートノードである。ノードＮがアクセスされる。
【０１３５】
９７において、ノードＮはリーフノードであるか否かが決定される。ノードＮがリーフノードでない場合、方法は９４に戻る。そうでない場合、方法は、９８において継続する。
【０１３６】
９８において、オブジェクトの挿入後のノードＮのサイズが、許容されたノードのエントリの最大数に対応する閾値を超えるか否かが決定される。エントリの許容された最大数が超えられないことが決定された場合、オブジェクトＯｉが９９においてノードに挿入される。次いで、方法は９１に戻る。
【０１３７】
ノードＮが既に許容されたエントリの最大数を有していることが９８において決定された場合、方法は、９９において継続する。９９において、ノードＮは、１対のノードに分割される。ノードＮを分割することによって、２つの新たなリーフノードが生成される。同時に、ディレクトリノードが生成され、２つの新たなリーフノードへのポインターを有する２つのオブジェクトを含む。オブジェクトＯｉは、２つの新たなリーフノードのうちの１つか、または新たなディレクトリノードに挿入され得る。次いで、方法は９１に戻る。
【０１３８】
図１１および図１２は、ノードにおける許容されたエントリの最大数に達した場合のリーフノードの分割を例示する。
【０１３９】
図１１は、オブジェクトＡおよびＢを有するディレクトリノード１１１と、オブジェクトＣ、Ｄ、Ｇを有するリーフノード１１２と、オブジェクトＥおよびＦを有する別のリーフノード１１３とを有する索引構造１１０を示す。
【０１４０】
新たなオブジェクトＩ（新たなオブジェクトＩに対して、ｄ（Ａ；Ｉ）＜ｄ（Ｂ；Ｉ））が挿入されることを想定して、方法９０は、オブジェクトがリーフノード（ノードＡから到達することが可能である）に挿入されることを決定する。ノードに対して許容されたエントリの最大数が３つのオブジェクトに対応する場合、オブジェクトは、単にノード１１２に挿入することができない。この場合、ノード１１２は分割される。
【０１４１】
図１２は、ノード１１２が分割された後の索引構造１１０を示す。２つの新たなリーフノード１１５および１１６が生成される。さらに、新たなディレクトリノード１１４が生成される。リーフノード１１２に含まれるオブジェクトＣおよびＤは、ディレクトリノードにおけるオブジェクトにレベルが上げられる。Ｍツリーの専門用語において、オブジェクトＣおよびＤは、ルーティングオブジェクトにレベル上げされる。オブジェクトＧは、オブジェクトＣを親として有するリーフノード１１５に加えられる。オブジェクトＩは、オブジェクトＤを親として有するリーフノード１１６に加えられる。
【０１４２】
ノードが方法９０でステップ１００において分割された場合、さまざまな技術が用いられ得、ディレクトリノードへレベル上げされるオブジェクトを選択する。例えば、Ｍツリーに対して、以下の実装が用いられ得る：
一実装において、ディレクトリノードにレベル上げされるオブジェクトが無作為に選択され得る。
【０１４３】
別の実装において、サンプリングがディレクトリノードにレベル上げされた複数対のオブジェクトに対して行われる。複数対のうちのいずれか１つに対して、ノードに含まれる他のノードが２つの新たなリーフノードに区分される。オブジェクトは、新たなリーフノードのうちの１つに割り当てられる。新たなリーフノードのうちの１つに対して、オブジェクトとリーフノードの親との間の距離は、より小さい。区分が完了したとき、結果の包含半径が決定される。包含半径が式（５）に従って決定される。ディレクトリノードにレベル上げされた異なる対のオブジェクトに対して、異なる包含半径が生じる。次いで、ノードは、サンプリングされた対のオブジェクトのうちの１つがディレクトリノードに加えられるように分割され得る。ディレクトリノードに対して、２つの包含範囲の最大は、サンプリングされた対のレベル上げされたオブジェクトの中の最小値を有する。
【０１４４】
別の実装において、サンプリングは、全ての可能な対のオブジェクトＯ１およびＯ２に対して行われる。オブジェクトＯ１およびＯ２は、ノードに含まれ、原則的にはディレクトリノードに加えられ得る。分割の前にノードに含まれる他のオブジェクトは、上で説明されたように区分される。つまり、オブジェクトは、新たなリーフノードのうちの１つに割り当てられ得る。新たなリーフノードに対して、オブジェクトとリーフノードの親との間の距離は、より小さい。可能な対のオブジェクトのうちのいずれか１つに対して、包含半径ｒ（Ｏ１）＋ｒ（Ｏ２）の総計が決定される。次いで、包含半径の最小総計になる対のオブジェクトがディレクトリノードに加えられ得る。他のオブジェクトは、新たなリーフノードのうちの１つにそれぞれ割り当てられ得る。新たなリーフノードに対して、オブジェクトとリーフノードの親との間の距離は、より小さい。
【０１４５】
別の実装において、サンプリングは、全ての可能な対のオブジェクトＯ１およびＯ２に対して行われる。オブジェクトＯ１およびＯ２は、ノードに含まれ、原則的にはディレクトリノードに加えられ得る。分割の前にノードに含まれる他のオブジェクトは、上で説明されたように区分される。つまり、オブジェクトは、新たなリーフノードのうちの１つに割り当てられ得る。新たなリーフノードに対して、オブジェクトとリーフノードの親との間の距離は、より小さい。レベル上げされる可能な対のオブジェクトのうちのいずれか１つに対して、２つの包含半径ｍａｘ（ｒ（Ｏ１），ｒ（Ｏ２））の最大が決定される。次いで、包含半径の最大に対して最小値になる対のオブジェクトがディレクトリノードに加えられ得る。他のオブジェクトは、それぞれ、新たなリーフノードのうちの１つに割り当てられ得る。新たなリーフノードに対して、オブジェクトとリーフノードの親との間の距離は、それぞれ、より小さい。
【０１４６】
別の実装において、挿入されるオブジェクトから最も大きい距離ｄ（Ｏｋ；Ｏｉ）を有するリーフノードにおけるオブジェクトＯｋが決定される。次いで、このオブジェクトＯｋおよび新たなオブジェクトＯｉがディレクトノードにレベル上げされ得る。他のオブジェクトは、それぞれ、新たなリーフノードのうちの１つに割り当てられ得る。新たなリーフノードに対して、オブジェクトとリーフノードの親との間の距離は、より小さい。
【０１４７】
Ｍツリーとして構成される索引構造を生成する方法が図１０〜図１２を参照して、上で説明されたが、同じものを構築する他のメトリック索引構造および方法が他の実施形態において用いられ得る。例えば、ｖａｎｔａｇｅポイントツリーが用いられ得る。
【０１４８】
実施形態に従うデバイスおよび方法が詳細に説明されたが、改変が他の実施形態において実装され得る。例示として、包含半径、または親オブジェクトと子オブジェクトとの間の距離のような距離情報が索引データに記憶され得るが、そのようなデータは、また、ランタイムにおいて計算され得る。
【０１４９】
さらなる例示として、索引ツリーおよびそのノードの例示的構造が説明されたが、いずれか適切なデータ構造が索引ツリーを実装するために用いられ得る。例示として、索引ツリーは、リレーショナルデータベースにおけるユーザー定義の構造として記憶され得る。この場合、１つのテーブルが提供され得、テキストストリングまたは音素ストリングを含む。別のテーブルが提供され得、対のテキストストリングまたは音素ストリングの間の距離を含む。
【０１５０】
さらなる例示として、索引構造が「索引構造におけるオブジェクト」のような表現を用いて説明されたが、そのようなオブジェクトは、索引構造に組み込まれる必要はない。むしろ、索引構造は、オブジェクト自体よりも、オブジェクトへの識別子またはポインターを含み得る。
【０１５１】
さらなる例示として、類似性サーチが、クエリーオブジェクトからの固定されたサーチ半径内に配置されたオブジェクトに対するサーチに関連して説明されたか、またはｋ個の最も近い近傍点に対するサーチに関連して説明されたが、他の類似性サーチもメトリック索引構造を用いて実装され得る。いくつかのサーチが音素またはテキストストリングに対するサーチのような特定の距離メトリックまたは特定の適用に関連して説明されたが、実施形態は、それらに限定されない。
【０１５２】
発明の実施形態は、乗り物のナビゲーションデバイスに対して用いられ得る。
【符号の説明】
【０１５３】
１０、７０ 索引構造
５１ クエリーオブジェクト
１１〜１７、７１〜７５ ノード
【技術分野】
【０００１】
（技術分野）
本発明は、ナビゲーションデバイスにおける使用のためのデータベースサーチ方法およびデバイスに関する。特に、本発明は、索引構造を用いてナビゲーションデバイスデータベースをサーチする方法と、ナビゲーションデバイスと、索引構造を生成する方法とに関する。
【背景技術】
【０００２】
（背景）
ナビゲーションデバイスは公知であり、２つの場所の間のルートサーチのような機能を行う。現代のナビゲーションデバイスは、また、要求がある場合、ポイントオブインタレスト（ＰＯＩ）に関する情報を出力するトラベルガイドとして機能するようなさらなる機能性を提供し得る。そのような情報は、通りの名称またはＰＯＩを含み得るが、さらなるテキスト情報またはマルチメディア情報を含む場合もある。例示として、いくつかのナビゲーションデバイスは、オブジェクトに関する詳細な説明を、テキストおよび／またはマルチメディア形態で出力するトラベルガイド機能性を含み得る。
【０００３】
現代のナビゲーションデバイスにおいて用いられるデータベースのサイズに起因して、データベースにおいてサーチを行うことは、かなりの難問である。特に、テキストストリング、音素ストリング、マルチメディアオブジェクトまたはユークリッド空間において規定されない他のオブジェクトに対してサーチが行われる場合、このことは当てはまる。２Ｄまたは３Ｄ空間において規定されるオブジェクトの幾何学的座標は、オブジェクトが座標ベースサーチに対して座標に基づき索引付けられることを可能にし得る。そのような索引付けは、テキストストリング、音素ストリング、マルチメディアオブジェクトまたはユークリッド空間において規定されない他のオブジェクトのようなオブジェクトに対して、より難問である。
【０００４】
さらに、サーチがテキストストリング、音素ストリングまたはマルチメディアオブジェクトのようなオブジェクトに対して行われた場合、ユーザーは、正確なヒットを得ることのみに興味があるわけではない場合がある。むしろ、ユーザーは、クエリーに類似するサーチ結果に関する情報を得ることに興味を有し得、必ずしも、クエリーと同一ではない。ルートサーチに対して、開始場所および目的場所、中間ポイントまたは経由ポイントを入力することまたはＰＯＩを入力することのような多くの用途に対して、ユーザーは、正しいテキスト表示の名称に気付いていない場合がある。ストリングの最初の文字に従うデータベースにおける正確な一致に対してサーチを行う従来技術は、それらの最初の文字内にスペルミスがある場合、失敗し得る。
【０００５】
さらに、ナビゲーションデバイスにおいて、記憶スペース制限によって課される制約、利用可能な計算時間に関する限界が、フォルトトレラントな効率的なサーチを実装することを特に難問にしている。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
（要約）
従って、フォールトトレラントサーチが実行されることを可能にする方法およびナビゲーションデバイスを提供するニーズがある。特に、フォールトトレラントサーチが効率的に行われることを可能にする方法およびナビゲーションデバイスに対するニーズがある。
【課題を解決するための手段】
【０００７】
このニーズは、独立請求項に記載されるようなデバイスおよび方法によって的にされる。従属請求項は、実施形態を規定する。
【０００８】
側面に従って、ナビゲーションデバイスデータベースにおいて類似性サーチを行う方法が提供される。類似性サーチは、メトリック索引構造を用いて行われる。データベースは、複数のオブジェクトを含み、索引構造は、複数のノードを含む。クエリーオブジェクトが受信される。複数のオブジェクトのうちの少なくとも１つのオブジェクトに関連付けられる索引構造のノードがアクセスされる。アクセスされたノードのうちの少なくとも１つのオブジェクトに対して、クエリーオブジェクトとオブジェクトとの間の距離は、距離メトリックに従って決定される。決定された距離に基づいて、索引構造の別のノードが選択的にアクセスされる。
【０００９】
方法は、類似性サーチを使用する。これは、ファジィサーチが実装されることを可能にし、ファジィサーチは、正確なマッチについての情報を提供するだけではなく、データベースにおいて最も類似なオブジェクトについての情報も検索する。方法において、クエリーオブジェクトと索引構造のノードのオブジェクトとの距離は、アクセスされるべきである他のノードを識別するように決定される。これは、サーチが効率的に行われることを可能にする。クエリーオブジェクトから閾値より大きな距離を有するオブジェクトを含むかまたは指すアクセスノードが必要とされない。距離メトリックに従って決定された距離を使用することによって、クエリーオブジェクトと索引構造に含まれるオブジェクトとの間の類似または相違が、量的に評価される。
【００１０】
索引構造は、ナビゲーションデバイスの記憶デバイスに格納され得る。
【００１１】
索引構造は、メトリック索引構造であり得る。従来の専門用語に従って、メトリック索引構造は、索引を区分するために、オブジェクトよりむしろ多重次元の空間のそれらの座標の間の相対的距離のみを考慮する索引である。索引構造は、特に、Ｍツリー、ｖａｎｔａｇｅポイントツリーまたは距離メトリックに従って組織化された任意の他のツリー構造であり得る。索引構造は、サーチを行うことにおけるクエリーオブジェクトとオブジェクトとの間の距離を決定するのに使用される距離と同じである距離関数に従って組織化される。
【００１２】
従来の専門用語を用いて、「距離メトリック」または「メトリック」は、本明細書において、反射の公準、対称性および三角不等式を満たす距離関数をさすように理解される。
【００１３】
従来の専門用語を用いて、用語「類似性サーチ」は、本明細書において、クエリーオブジェクトに対する例示または相違に関して所与の基準を満たす、オブジェクトに対するサーチをさすように使用される。実施例は、距離メトリックに従う距離のように測定された、固定の閾値より少ない相違を有するオブジェクトに対するサーチ、または距離メトリックに従う距離のように測定された、索引されたオブジェクトの中のクエリーオブジェクトから最も小さい相違を有するオブジェクトに対するサーチを含む。
【００１４】
クエリーオブジェクトと、サーチに訪問されたノードによって表される全部のオブジェクトとの間の正確な距離を決定することが、可能であるが、必要とされない。索引構造を通るパスに沿うノードのうちの少なくともいくつかに対して、クエリーオブジェクトと索引構造のそれぞれのオブジェクトとの距離の下限を決定するのは、十分であり得る。
【００１５】
オブジェクトは、ストリング、特に音素ストリングまたはテキストストリングであり得る。対応して、クエリーオブジェクトは、音素ストリングまたはテキストストリングであり得る。これは、音素ストリングまたはテキストストリングに対してフォールトトレラントサーチが行われることを可能にする。このようなサーチは、開始場所および目的地場所を入力する場合、データベース内にＰＯＩをサーチする場合、データベースに格納されるテキストまたはマルチメディアデータをサーチする場合、または類似な場合に有用であり得る。
【００１６】
ストリングであるオブジェクトに対する距離メトリックは、複数の利用可能なストリングメトリックのうちの任意の１つから選択され得る。例として、距離メトリックは、Ｌｅｖｅｎｓｈｔｅｉｎ距離に基づき得る。距離関数はまた、Ｄａｍｅｒａｕ−Ｌｅｖｅｎｓｈｔｅｉｎ距離、Ｊａｒｏ−Ｗｉｎｋｌｅｒ距離、Ｈａｍｍｉｎｇ距離、Ｓｏｕｎｄｅｘ距離メトリックに従って決定される距離、Ｎｅｅｄｌｅｍａｎ−Ｗｕｎｓｃｈ距離、Ｇｏｔｏｈ距離、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ−Ｇｏｔｏｈ距離、Ｐ≧１を有するＬｐ距離または反射の公準、対称性および三角不等式に従う任意の他のストリングメトリックのうちの任意の１つであり得る。
【００１７】
テキスト入力が受信され得、テキスト−音素変換は、テキスト入力からクエリーオブジェクトを生成するように行われ得る。代替的に、またはさらに、クエリーオブジェクトは、音声入力から生成される音素ストリングであり得る。
【００１８】
索引構造はさらに、アクセスされたノードに含まれる少なくとも１つのオブジェクトと、索引構造の他のオブジェクトと距離についての距離情報を含み得る。距離情報は、親オブジェクトを有する任意のノードに対して、ノードのオブジェクトとその親オブジェクトとの間の距離を含み得る。この距離情報は、索引構造に格納され得る。代替的に、またはさらに、別のノードを指し、すなわち、リーフノードにない任意のオブジェクトに対して、距離情報は、オブジェクトと、このオブジェクトに関連付けられる索引構造のサブツリーに含まれる任意のオブジェクトとの間の距離の上限を含み得る。距離に対するこの上限はまた、それが、そのサブツリーの全オブジェクトが配置されるオブジェクトの周りの距離を表すために、カバレッジ半径と呼ばれ得る。このような距離情報を索引構造に含むことによって、距離情報は、類似性サーチの間にそれが計算される必要があらず、ランタイムにおいて使用され得る。従って、サーチパフォーマンスが増強され得る。
【００１９】
アクセスする別のノードは、クエリーオブジェクトとアクセスされたノードの間の距離に基づいて、そして距離情報に基づいて選択的に行われ得る。閾値比較が行われ得る。閾値比較に基づいて、サーチ索引のサブツリーがサーチされなければならないか否かが決定され得る。代替的に、またはさらに、閾値比較に基づいて、クエリーオブジェクトと、索引構造のオブジェクトとの間の正確な距離を計算する必要があるか否かが決定され得る。
【００２０】
クエリーオブジェクトとノードに含まれるオブジェクトと間の距離は、カバレッジ半径とサーチ半径との総計と比較され得る。閾値比較が、クエリーオブジェクトとノードに含まれるオブジェクトと間の距離が総計より大きいであることを示す場合に、オブジェクトが指す索引構造のサブツリーにアクセスする必要とされない。サーチ半径が、固定され得、または類似性サーチが進行するので、変化するように作られ得る。
【００２１】
ノードは、いくつかのオブジェクトを含み得る。索引構造は、いくつかのオブジェクトの各々に対して、それぞれのオブジェクトと、それぞれのオブジェクトを指す索引構造のサブツリーに含まれる任意のオブジェクトとの間の距離の上限を含み得る。
【００２２】
オブジェクトは、決定された距離に基づいて類似性サーチから選択的に取り除かれ得る。取り除くことは、クエリーオブジェクトとノードのオブジェクトとの間の決定された距離に基づいて、そしてオブジェクトのカバレッジ半径に基づいて行われ得る。
【００２３】
距離を決定するステップと、別のノードに選択的にアクセスするステップとが、反復して繰り返され得る。これらのステップが繰り返される場合に、クエリーオブジェクトとノードに含まれるオブジェクトとの間の距離は、ノードのオブジェクトのうちの各々に対して計算されることが必要とされない。クエリーオブジェクトとノードに含まれるオブジェクトとの間の距離は、基準に基づいて選択的に計算され得、基準は、それが、新しい距離が計算される必要とされないようである。他のノードが索引構造のリーフノードである場合に、距離を計算することと、別のノードに選択的にアクセスすることとが、終了され得る。
【００２４】
アクセスされた他のノードがリーフノードである場合に、方法はさらに、閾値比較の結果に基づいて、リーフノードのオブジェクトとクエリーオブジェクトとの間の距離を選択的に決定することを含み得る。リーフノードの所与のオブジェクトとクエリーオブジェクトとの間の距離は、閾値比較の結果に基づいて選択的に決定され得る。閾値比較は、第１の距離と第２の距離との差異の係数と閾値を比較することを含み得る。第１の距離は、クエリーオブジェクトとのリーフノードの親オブジェクトとの距離であり得る。第２の距離は、リーフノードの親オブジェクトとリーフノードのそれぞれの所与のオブジェクトとの間の距離であり得る。リーフノードの任意の所与のオブジェクトに対して、それぞれの所与のオブジェクトとのクエリーオブジェクトとの間の距離は、このような閾値比較の結果に基づいて選択的に計算され得る。それによって、サーチ時間がさらに減少され得る。
【００２５】
サーチにおいて、クエリーオブジェクトからの所定の距離内に配置された全部のオブジェクトが識別され得る。この距離は、距離メトリックに従って規定される。これは、所与の閾値を超過しない、クエリーオブジェクトへの相違を有する全部のオブジェクトが識別され、かつユーザーに出力されることを可能にする。
【００２６】
代替的に、またはさらに、距離メトリックに従って決定された、索引構造のクエリーオブジェクトのｋ個の最も近い近傍点を表す整数個（ｋ＞１）のオブジェクトが識別され得る。これは、距離メトリックに基づいてクエリーオブジェクトの最も類似であるｋ個のオブジェクトが識別され、かつユーザーに出力されることを可能にする。
【００２７】
識別されたオブジェクトは、クエリーオブジェクトとそれぞれの識別されたオブジェクトとの間の距離に基づいて出力され得る。識別されたオブジェクトを出力する場合に、オブジェクトは、クエリーオブジェクトとそれぞれに識別されたオブジェクトとの間の距離に従って格納され得る。例として、光学出力ユニットを介して出力することに対して、クエリーオブジェクトからの最も近い距離を有するオブジェクトは、最も上の位置または最も左の位置において出力され得、他のオブジェクトは、クエリーオブジェクトからの距離を増加する順序で出力され得る。同様に、オーディオ出力ユニットを介して出力することに対して、クエリーオブジェクトからの最も近い距離を有するオブジェクトが最初に出力され得、他のオブジェクトは、その後、クエリーオブジェクトからの距離を増加する順序で連続して出力され得る。
【００２８】
もう１つの側面に従って、ナビゲーションデバイスが提供される。ナビゲーションデバイスは、規則デバイスと処理デバイスとを含む。記憶デバイスは、複数のオブジェクトを含むデータベースに対して索引構造を格納し、索引構造は、複数のノードを含む。処理デバイスは、記憶デバイスに結合される。クエリーオブジェクトに対して類似性サーチを行うために、処理デバイスは、複数のオブジェクトのうちの少なくとも１つのオブジェクトに関連付けられた索引構造のノードにアクセスするように構成される。処理デバイスはさらに、距離メトリックに従って、クエリーオブジェクトと少なくとも１つのオブジェクトとの間の距離を決定するように構成される。処理デバイスはさらに、決定された距離に基づいて、索引構造の別のノードに選択的にアクセスするように構成される。
【００２９】
このようなナビゲーションデバイスは、ファジィサーチが実装されることを可能にし、ファジーサーチは、正確なマーチについての情報を提供するだけではなく、データベースの最も類似なオブジェクトについての情報も検索する。ナビゲーションデバイスにおいて、クエリーオブジェクトと索引構造のノードのオブジェクトとの距離は、アクセスされるべきである他のノードを識別するために決定される。これは、サーチが効率的に行われることを可能にする。クエリーオブジェクトから閾値より大きな距離を有するオブジェクトを含むかまたは指すアクセスノードが必要とされない。距離メトリックに従って決定された距離を使用することによって、クエリーオブジェクトと索引構造に含まれるオブジェクトとの間の類似または相違が、量的に評価される。
【００３０】
オブジェクトは、音素ストリングおよび／またはテキストストリングであり得る。
【００３１】
索引構造は、メトリック索引構造であり得る。
【００３２】
ナビゲーションデバイスは、入力ユニットを含み得る。処理デバイスは、入力ユニットからクエリーオブジェクトを受信するように、または入力ユニットで受信された入力に基づいてクエリーオブジェクトを生成するように、入力ユニットと結合され得る。処理デバイスは、クエリーオブジェクトを生成するために、テキスト−音素変換を行うように構成され得る。
【００３３】
ナビゲーションデバイスは、出力ユニットを含み得る。処理デバイスは、類似性サーチにおいて見つけられた複数のオブジェクトが出力ユニットを介して出力されるように、出力ユニットを制御するように構成され得る。処理デバイスは、出力オブジェクトがクエリーオブジェクトとそれぞれの出力オブジェクトとの距離に従って格納されるように、出力ユニットを制御するように構成され得る。
【００３４】
処理デバイスは、距離メトリックに従って決定された、クエリーオブジェクトからの固定のサーチ半径より近い距離を有する全部のオブジェクトを識別するように構成され得る。処理デバイスは、代替的に、またはさらに、クエリーオブジェクトのｋ個の最も近い近傍点であるｋ＞１個のオブジェクトを識別するように構成され得る。
【００３５】
処理デバイスは、任意の側面または実施形態に従って類似性サーチ方法を行うように構成され得る。
【００３６】
もう１つの側面に従って、ナビゲーションデバイスデータベースに対してメトリック索引構造を生成する方法が提供される。データベースは、複数のオブジェクトを含む。方法において、索引構造の他のノードへのポインターを含む索引構造のディレクトリノードと索引構造のリーフノードとが生成される。ノードを生成することは、複数組のオブジェクトに対して、オブジェクトと組のオブジェクトのオブジェクトとの間の距離をそれぞれに決定し、それによって複数の距離を決定することを含む。距離は、それぞれ、距離メトリックに従って決定される。複数の距離に基づいて、ディレクトリノードに含まれるべきであるオブジェクトとリーフノードに含まれるべきであるオブジェクトとが識別される。
【００３７】
この方法を用いて、索引構造が生成され、類似性サーチ方法において、そして任意の側面および実施形態のナビゲーションデバイスにおいて使用され得る。生成されたメトリック構造は、オブジェクトの間の相対的距離である決定された複数の距離に従って組織化される。これは、また多重次元の空間の座標によって規定されないオブジェクトに対して、メトリック索引構造がセットアップされることを可能する。
【００３８】
オブジェクトは、音素ストリングまたはアルファベットや数値のストリングであり得る。
【００３９】
索引構造を生成する場合に、距離メトリックは、ストリングメトリックに対する複数の距離定義のうちの任意の１つから選択され得る。例として、距離メトリックは、Ｌｅｖｅｎｓｈｔｅｉｎ距離に基づき得る。距離関数はまた、Ｄａｍｅｒａｕ−Ｌｅｖｅｎｓｈｔｅｉｎ距離、Ｊａｒｏ−Ｗｉｎｋｌｅｒ距離、Ｈａｍｍｉｎｇ距離、Ｓｏｕｎｄｅｘ距離メトリックに従って決定される距離、Ｎｅｅｄｌｅｍａｎ−Ｗｕｎｓｃｈ距離、Ｇｏｔｏｈ距離、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ−Ｇｏｔｏｈ距離、Ｐ≧１を有するＬｐ距離または反射の公準、対称性および三角不等式に従う任意の他のストリングメトリックのうちの任意の１つであり得る。
【００４０】
方法は、ディレクトリノードに含まれるオブジェクトに対して、それぞれのオブジェクトとオブジェクトを指す索引構造のサブツリーに含まれる任意のオブジェクトとの距離の上限を格納することを含み得る。この上限、またはカバレッジ半径は、索引構造内に格納され得る。
【００４１】
方法は、代替的に、またはさらに、親オブジェクトを有するノードに含まれるオブジェクトに対して、それぞれのオブジェクトとその親オブジェクトとの距離を格納することを含み得る。
【００４２】
方法において、索引構造は、反復のやり方で成長され得る。方法は、ノードに追加のオブジェクトを挿入することを含み得る。そのために、オブジェクトが挿入されるべきであるノードが識別され得る。ノードを識別することは、挿入されるべきであるオブジェクトと索引構造のディレクトリノードのオブジェクトとの距離を決定することを含み得る。
【００４３】
方法はさらに、ノードを分割することを含み得る。そのために、オブジェクトの挿入の後に、ノードのオブジェクトの数は、オブジェクトの固定の最大の数より大きいか否かが決定され得る。数が最大の数を超える場合に、ノードが分割される。ノードを分割することは、新しいディレクトリノードに含まれるべきであるノードからのオブジェクトを選択することと、オブジェクトを２つの新しいリーフノードのうちの１つに割り当てることとを含み得る。ノードを分割することは、新しいディレクトリノードの２つのオブジェクトの２つのカバレッジエリアの間のオーバーラップが閾値以下に減少され、または最小化されるように行われ得る。
【００４４】
もう１つの側面に従って、ナビゲーションデバイスデータベースのためのメトリック索引構造が提供される。メトリック索引構造は、索引構造の他のノードへのポインターを含むディレクトリノードとリーフノードとを含む。ノードのうちの少なくともいつくかは、メトリックに従って決定された、索引構造のオブジェクトの間の距離についての情報を表す距離情報を含み得る。少なくともディレクトリノードは、ディレクトリノードのオブジェクトと、それぞれのオブジェクトに対する索引構造のサブツリーに含まれる任意のオブジェクトとの距離の上限を含み得る。
【００４５】
前述の特徴と以下に説明されるべきであるそれとは、示されるそれぞれの組み合わせだけではなく、他の組み合わせまたは単独に使用され得ることが理解されるべきである。
【００４６】
本発明は、例えば以下の項目を提供する。
（項目１）
索引構造（１０；７０）を用いてナビゲーションデバイスデータベースにおいて類似性サーチを行う方法であって、該データベースは、複数のオブジェクトを含み、該索引構造（１０；７０）は、複数のノード（１１−１７；７１−７５）を含み、
該方法は、
クエリーオブジェクト（５１）を受信することと、
該複数のオブジェクトのうちの少なくとも１つのオブジェクト（５２，５５，５９，６０）に関連付けられる該索引構造（１０；７０）のノード（１１−１３；７１−７３）にアクセスすることと、
該ノード（１１−１３；７１−７３）に関連付けられた該少なくとも１つのオブジェクト（５２，５５，５９，６０）の各々のオブジェクトに対して、それぞれ、該クエリーオブジェクト（５１）と該オブジェクトとの間の距離（６５，６６）を決定することであって、該距離（６５，６６）は、それぞれ、距離メトリックに従って決定される、ことと、
該決定された距離（６５，６６）に基づいて、該索引構造（１０；７０）の別のノード（１２−１７；７２−７５）に選択的にアクセスすることと
を含む、方法。
（項目２）
上記クエリーオブジェクト（５１）は、音素ストリングまたはテキストストリングである、上記項目のいずれかに記載の方法。
（項目３）
上記クエリーオブジェクト（５１）を受信することは、テキスト入力を受信することと、テキスト−音素変換を行うこととを含む、上記項目のいずれかに記載の方法。
（項目４）
上記索引構造（１０；７０）は、上記少なくとも１つのオブジェクト（５２，５５，５９，６０）と該索引構造（１０；７０）の他のオブジェクトとの間の距離についての距離情報をさらに含み、
該他のノード（１２−１７；７２−７５）は、該距離情報と、上記決定された距離（６５，６６）とに基づいて選択的にアクセスされる、上記項目のいずれかに記載の方法。
（項目５）
上記ノード（１１−１３；７１−７３）は、いくつかのオブジェクト（５２，５５）に関連付けられ、
上記距離情報は、該いくつかのオブジェクト（５２，５５）の各々に対して、該それぞれのオブジェクト（５２，５５）と、該それぞれのオブジェクト（５２，５５）に関連付けられた上記索引構造（１０；７０）のサブツリーに含まれる任意のオブジェクト（５９−６４）との間の距離の上限（５３，５６）を含む、上記項目のいずれかに記載の方法。
（項目６）
上記クエリーオブジェクト（５１）は、音素ストリングまたはテキストストリングであり、
該クエリーオブジェクト（５１）を受信することは、テキスト入力を受信することと、テキスト−音素変換を行うこととを含む、上記項目のいずれかに記載の方法。
（項目７）
オブジェクトは、上記決定された距離（６５，６６）に基づいて、上記類似性サーチから選択的に取り除かれる、上記項目のいずれかに記載の方法。
（項目８）
上記他のノード（１２−１７；７２−７５）が上記索引構造（１０；７０）のリーフノード（１４−１７；７４，７５）である場合に、上記距離（６５，６６）を決定することと、上記別のノード（１２−１７；７２−７５）に選択的にアクセスすることとが終了される、上記項目のいずれかに記載の方法。
（項目９）
上記距離メトリックに従って決定された、上記クエリーオブジェクト（５１）からの所定の距離（５８）内に配置された全てのオブジェクトが識別される、上記項目のいずれかに記載の方法。
（項目１０）
１より大きい整数ｋ個のオブジェクトが識別され、該ｋ個のオブジェクトは、上記距離メトリックに従って決定された、上記クエリーオブジェクト（５１）のｋ個の最も近い近傍点を表す、上記項目のいずれかに記載の方法。
（項目１１）
上記識別されたオブジェクトは、上記クエリーオブジェクト（５１）と、それぞれの識別されたオブジェクトとの間の距離に基づいて決定された順序で出力される、上記項目のいずれかに記載の方法。
（項目１２）
ナビゲーションデバイスであって、該ナビゲーションデバイスは、
複数のオブジェクトを含むデータベースに対する索引構造（１０；７０）を格納する記憶デバイス（３）であって、該索引構造（１０；７０）は、複数のノード（１１−１７；７１−７５）を含む、記憶デバイス（３）と、
該記憶デバイス（３）に結合された処理デバイス（２）と
を含み、該処理デバイス（２）は、クエリーオブジェクト（５１）に対して類似性サーチを行うために、
該複数のオブジェクトのうちの少なくとも１つのオブジェクト（５２，５５，５９，６０）に関連付けられた該索引構造（１０；７０）のノード（１１−１３；７１−７３）にアクセスすることと、
距離メトリックに従って、該クエリーオブジェクト（５１）と該少なくとも１つのオブジェクト（５２，５５，５９，６０）との間の距離（６５，６６）を決定することと、
該決定された距離（６５，６６）に基づいて、該索引構造（１０；７０）の別のノード（１２−１７；７２−７５）に選択的にアクセスすることと
を行うように構成される、ナビゲーションデバイス。
（項目１３）
上記処理デバイス（２）は、上記項目のいずれかに記載の方法を行うように構成される、上記項目のいずれかに記載のナビゲーションデバイス。
（項目１４）
複数のオブジェクトを含むナビゲーションデバイスデータベースのためのメトリック索引構造（１０；７０；１１０）を生成する方法であって、該方法は、該索引構造（１０；７０；１１０）の他のノードへのポインターを含む該索引構造のディレクトリノード（１１−１３；７１−７３；１１１，１１４）を生成することと、該索引構造のリーフノード（１４−１７；７４；７５；１１３，１１５，１１６）を生成することとを含み、
該ディレクトリノード（１１−１３；７１−７３；１１１，１１４）と該リーフノード（１４−１７；７４；７５；１１３，１１５，１１６）とを生成することは、
該オブジェクトの複数の組に対して、それぞれ、該オブジェクトの組のオブジェクト間の距離を決定することによって複数の距離を決定することであって、該距離は、それぞれ、距離メトリックに従って決定される、ことと、
該複数の距離に基づいて、ディレクトリノード（１１−１３；７１−７３；１１１，１１４）に含まれるべきであるオブジェクトと、リーフノード（１４−１７；７４；７５；１１３，１１５，１１６）に含まれるべきであるオブジェクトとを識別することと
を含む、方法。
（項目１５）
上記オブジェクトは、音素ストリングまたはテキストストリングである、上記項目のいずれかに記載の方法。
（項目１６）
上記ディレクトリノードおよび／または上記リーフノードにおいて、上記複数の距離から導かれた距離情報を格納することを含む、上記項目のいずれかに記載の方法。
【００４７】
（摘要）
ナビゲーションデバイスデータベースにおいて類似性サーチを行う方法は、メトリック索引構造を使用する。索引構造は、複数のノードを含む。クエリーオブジェクト（５１）が受信される場合に、少なくとも１つのオブジェクト（５２，５５，５９，６０）に関連付けられる索引構造のノードがアクセスされる。クエリーオブジェクト（５１）と少なくとも１つのオブジェクト（５２，５５，５９，６０）との間の距離（６５，６６）は、距離メトリックに従って決定される。決定された距離に基づいて、索引構造の別のノードが選択的にアクセスされる。
【００４８】
実施形態の先述および他の特徴は、添付の図面に関して読まれた場合、実施形態の以下の詳細な説明から、より明らかとなる。図面において、類似した参照数字は、類似した要素を指す。
【図面の簡単な説明】
【００４９】
【図１】図１は、ナビゲーションデバイスの概略ブロック図である。
【図２】図２は、索引構造の概略表示である。
【図３】図３は、索引構造のノードにおけるデータエントリの概略表示である。
【図４】図４は、索引構造のノードにおけるデータエントリの概略表示である。
【図５】図５は、類似性サーチを用いる方法のフローチャートである。
【図６】図６は、類似性サーチを行う方法のフローチャートである。
【図７】図７は、図６の方法を説明するためのデータベースオブジェクトの概略表示である。
【図８】図８は、図６の方法を説明するための索引構造の概略表示である。
【図９】図９は、類似性サーチを用いる方法のフローチャートである。
【図１０】図１０は、索引構造を生成する方法のフローチャートである。
【図１１】図１１は、図１０の方法を説明するための索引構造の概略表示である。
【図１２】図１２は、図１０の方法を説明するための索引構造の概略表示である。
【発明を実施するための形態】
【００５０】
（詳細な説明）
図１は、実施形態に従う乗り物のナビゲーションデバイス１を概略的に例示する。ナビゲーションデバイス１は、例えば、メモリに記憶される制御命令に従って、ナビゲーションデバイス１の動作を制御する処理デバイス２を含む。処理デバイス２は、例えば、１つ以上のマイクロプロセッサ、デジタルシグナルプロセッサまたは特定用途向け集積回路の形態の中央処理デバイスを含み得る。ナビゲーションデバイス１は、記憶デバイス３をさらに含む。記憶デバイス３は、揮発性または不揮発性記憶媒体またはメモリであり得る。記憶デバイス３は、ランダムアクセスメモリ、フラッシュメモリまたはハードドライブのようなさまざまなタイプの記憶またはメモリ媒体のうちのいずれか１つ、またはいずれかの組み合わせを含み得るが、コンパクトディスク（ＣＤ）、ＤＶＤ、メモリカードなどのようなリムーバルメモリも含み得る。ナビゲーションデバイス１は、また、情報をユーザーに出力する出力インターフェース４を含む。出力インターフェース４は、光学出力デバイス、オーディオ出力デバイスまたはそれらの組み合わせを含み得る。ナビゲーションデバイス１は、また、入力インターフェース５を含み、入力インターフェース５は、ユーザーが情報を入力することを可能にする。特に、入力インターフェース５は、ユーザーがテキスト情報または音声情報を入力することを可能にし得る。
【００５１】
ナビゲーションデバイスは、位置センサーおよび／またはワイヤレス受信器および／または乗り物のインターフェースのようなさらなるコンポーネントを含み得る。位置センサーは、ナビゲーションデバイス１がインストールされている乗り物の現在の位置を決定するように適合され得る。位置センサーは、ＧＰＳ（全地球測位システム）センサー、ガリレオセンサー、モバイル通信網に基づく位置センサーなどを含み得る。ワイヤレス受信器は、記憶デバイス３に記憶されたデータベースを更新するための情報を受信するように構成され得る。乗り物のインターフェースは、処理ユニット２が情報を他の乗り物システムから得ることを可能にし得るか、または乗り物状態情報を乗り物のインターフェースを介して得ることを可能にし得る。例えば、乗り物のインターフェースは、ＣＡＮ（コントローラーエリアネットワーク）またはＭＯＳＴ（メディアオリエンテッドデバイストランスポート）インターフェースを含み得る。
【００５２】
記憶デバイス３は、複数のオブジェクトを含むデータベースを記憶する。複数のオブジェクトは、テキストストリングまたは音素ストリングを含み得る。例示として、データベースは、道路名称を表すオブジェクト、ポイントオブインタレスト（ＰＯＩ）の名称を表すオブジェクトおよび／または道路またはＰＯＩに関してさらなる情報を表すオブジェクトを含み得る。そのような情報は、形態を有し得るか、またはテキストストリングまたは音素ストリングまたはマルチメディアオブジェクトを含み得る。
【００５３】
記憶デバイス３は、データベースに対して索引構造を記憶する。ナビゲーションデバイス１の使用において、プロセッサ２は、索引構造を用いて類似性サーチを行う。プロセッサ２は、入力インターフェース５において受信された入力をクエリーオブジェクトとして用い得るか、または入力に関するさらなる動作を行い得ることによってクエリーオブジェクトを生成する。次いで、プロセッサ２は、クエリーオブジェクトに対して索引構造を用いて類似性サーチを行う。類似性サーチは、クエリーオブジェクトと、データベースに記憶されたオブジェクトとの間の距離を計算することを含む。本明細書において用いられた場合、「計算する」は、さまざまな方法によって実装され得、ルックアップ動作を含む。距離は、クエリーオブジェクトと索引構造におけるオブジェクトとの相違に対する量的測定値を提供する。サーチにおいて見つかったいくつかの非常に類似したオブジェクトがユーザーに出力インターフェース４を介して出力される。例示として、プロセッサ２は、光学出力インターフェース４上にリストを生成し得る。光学出力インターフェース４において、クエリーオブジェクトから最も小さい距離を有する索引構造のオブジェクトが、クエリーオブジェクトからの距離によって決定された順番に羅列される。
【００５４】
索引構造は、論理的にデータベースから分離している。あるいは、データベースは、索引構造と結合し得る。
【００５５】
索引構造は、いずれか適切な技術を用いて実装され得る。限定としてよりも、むしろ例示として、索引構造は、ＳＱ Ｌｉｔｅを用いて実装され得る。索引構造は、ユーザー定義の索引構造としてデータベースシステム、特にリレーショナルデータベースシステムに実装され得る。リレーショナルデータベースは、テキストストリングまたは音素ストリングのためのテーブルもしくは対のテキストストリングと対の音素ストリングとの間の距離のための別のテーブルを含み得る。
【００５６】
データベースのための索引構造は、索引ツリーとして組織化され得る。索引構造は、複数のノードを含み得、ノードの少なくとも一部は、他のノードへのポインターを含むディレクトリノードであり、少なくとも一部の他のノードは、他のノードへのポインターを含まないリーフノードである。ノードの各々は、少なくとも１つおよび一般的な複数のオブジェクトに関連付けられ得る。ディレクトリノードは、ディレクトリノードに含まれるオブジェクトに対して、それらのオブジェクトの各々に関連付けられたそれぞれのサブツリーのルートへのポインターを記憶し得る。
【００５７】
記憶デバイス３に記憶された索引構造は、メトリック索引構造であり、メトリック索引構造は、距離メトリックを用いてサーチされ得る。さらに、索引構造は、また、距離メトリックに従って組織化される。つまり、索引構造は、距離メトリックに従って、決定されたデータベースのオブジェクトの間の相対的な距離に基づいてサブツリーに区分される。
【００５８】
一般的な用語に従って、本明細書における「距離メトリック」または「メトリック」は、以下の条件を満たす空でないセットＭのオブジェクトに対して規定された距離測定値を指す：
反射性（不可識別者同一とも呼ばれる）：
∀ｘ，ｙ∈Ｍ： ｘ＝ｙの場合かつｘ＝ｙの場合のみｄ（ｘ，ｙ）＝０； （１）
対称性：
∀ｘ，ｙ∈Ｍ： ｄ（ｘ，ｙ）＝ｄ（ｙ，ｘ） （２）
三角不等式：
∀ｘ，ｙ，ｚ∈Ｍ： ｄ（ｘ，ｙ）≦ｄ（ｘ，ｙ）＋ｄ（ｙ，ｚ） （３）
上の公準（１）〜（３）が満たされた場合、距離も正値性公準を満たすことになる：
∀ｘ，ｙ∈Ｍ： ｄ（ｘ，ｙ）≧０ （４）
セットＭおよびメトリックｄのタプル（Ｍ，ｄ）は、メトリック空間とも呼ばれる。
【００５９】
メトリック（このメトリックに従って、索引構造が組織化される）（また、索引構造におけるサーチを行うために用いられる）は、とりわけデータベースにおけるオブジェクトに応じて、さまざまな定義から選択され得る。例示として、テキストストリングまたは音素ストリングであるオブジェクトに対して、Ｌｅｖｅｎｓｈｔｅｉｎ距離がメトリックを規定する。Ｌｅｖｅｎｓｈｔｅｉｎ距離は、索引構造を作成するときと、索引構造において類似性サーチを行うときとの両方で用いられ得る。Ｌｅｖｅｎｓｈｔｅｉｎ距離は、編集距離とも呼ばれる。２つのストリングの間のＬｅｖｅｎｓｈｔｅｉｎ距離は、１つのストリングを他のストリングに変形させるために必要な編集の最小数として規定され、許容可能な編集動作は、単一の文字の挿入、削除または交換である。他のメトリックも索引構造を組織化することと、索引構造において類似性サーチが行われた場合に距離を計算することとのために用いられ得る。
【００６０】
他のメトリックが用いられ得る。例示として、距離機能がＤａｍｅｒａｕ−Ｌｅｖｅｎｓｈｔｅｉｎ距離、Ｊａｒｏ−Ｗｉｎｋｌｅｒ距離、Ｈａｍｍｉｎｇ距離、Ｓｏｕｎｄｅｘ距離メトリックに従って決定された距離、Ｎｅｅｄｌｅｍａｎ−Ｗｕｎｓｃｈ距離、Ｇｏｔｏｈ距離、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ−Ｇｏｔｏｈ距離、ｐ≧１を有するＬｐ距離または反射性、対称性、三角不等式の公準を用いてコンパイルする任意の他のストリングメトリックからのいずれか１つとなるように選択され得る。
【００６１】
記憶媒体３に記憶された索引構造は、オブジェクトおよびサーチツリーを規定する他のノードへのポインターを含み得るだけでなく、さらに索引構造におけるオブジェクト間の距離を示す距離情報も含み得る。そのような距離情報は、サーチを行う場合、索引構造から検索され得る。そのような距離情報は、下でさらに詳細に説明されるように、特に、オブジェクトまたはノードを類似性サーチから取り除くために用いられ得る。
【００６２】
図２は、索引構造１０の概略的表示である。図２においてツリーのような構造として示されるが、索引構造は、一般的にいずれか適切なフォーマットで記憶され得、例えば、リレーショナルデータベースにおけるユーザー定義の索引構造として記憶され得る。
【００６３】
索引構造は、ディレクトリノード１１〜１３およびリーフノード１４〜１７を含む。ディレクトリノード１１〜１３の各々は、他のノードへのポインターを含む。各ポインターは、それぞれのノードに含まれるオブジェクトにそれぞれ関連付けられ得る。例示として、ルートノード１１は、第１のオブジェクトに関連付けられたデータエントリ２１および第２のオブジェクトに関連付けられたデータエントリ２２を含み得る。データエントリ２１は、ディレクトリノード１２へのポインターを含み得る。ディレクトリノード１２は、第１のオブジェクトのサブツリーのルートである。データエントリ２２は、ディレクトリノード１３へのポインターを含み得、ディレクトリノード１３は、第２のオブジェクトのサブツリーのルートである。
【００６４】
ディレクトリノード１２は、データベースの他のオブジェクトに関連付けられたデータエントリ２３、２４を含み得る。データエントリ２３、２４は、それぞれ、別のノードへのポインターを含み得る。図２において例示される構造において、データエントリ２３、２４は、それぞれ、リーフノード１４、１５へのポインターを含む。ディレクトリノードのより大きい階層が実装され得る。同様に、ディレクトリノード１３は、データベースの他のオブジェクトに関連付けられたデータエントリ２５、２６を含み得る。データエントリ２５、２６は、それぞれ、リーフノード１６、１７のような別のノードへのポインターをそれぞれ含み得る。
【００６５】
リーフノード１４〜１７は、データベースの１つまたは複数のオブジェクトに関連付けられたデータエントリをそれぞれ含み得る。例示として、リーフノード１４は、データベースの３つのオブジェクトに関連付けられたデータエントリ２７〜２９を含んで示される。
【００６６】
索引構造において、サーチツリーは、距離メトリックに従って区分される。この目的のために、データ２１によって表される第１のオブジェクトおよびデータ２２によって表される第２のオブジェクトは、ルートノード１２を有する第１のサブツリーに含まれる全てのオブジェクトが第１のオブジェクトの周りに第１のカバレッジ半径を有するカバレッジエリア内に配置され、ルートノード１３を有する第２のサブツリーに含まれる全てのオブジェクトが第２のオブジェクトの周りに第２のカバレッジ半径を有するカバレッジエリア内に配置されるように、選択され得る。換言すると、第１のカバレッジ半径は、データエントリ２１によって表されるオブジェクトからのノード１２、１４および１５のうちのいずれか１つによって表される任意のオブジェクト間の距離の最大であり得る。データエントリ２１は、このサブツリーの親である。第２のカバレッジ半径は、データエントリ２２によって表されるオブジェクトからのノード１３、１６および１７のうちのいずれか１つによって表される任意のオブジェクト間の距離の最大であり得る。データエントリ２２は、このサブツリーの親である。
【００６７】
ルートノード１１における第１のオブジェクトおよび第２のオブジェクトならびに関連付けられたサブツリーにおけるオブジェクトは、第１および第２のカバレッジエリアが好ましくは可能な限り小さい重複を有するように選択される。さらに、ルートノード１１における第１のオブジェクトおよび第２のオブジェクトならびに関連付けられたサブツリーにおけるオブジェクトは、第１のオブジェクトとルート１２を有するサブツリーに含まれるいずれかのオブジェクトとの間の第１の最大距離および第２のオブジェクトとルート１３を有するサブツリーに含まれるいずれかのオブジェクトとの第２の最大距離が可能な限り小さいままであるように選択され得る。したがって、索引構造は、距離メトリックに従って決定されたオブジェクト間の近接に従って区分される。
【００６８】
上の索引構造を組織化するために概説された基準は、ルートノード１１に当てはまるだけでなく、いずれかのディレクトリノード１２、１３にも当てはまる。つまり、オブジェクトは、ディレクトリノードにおける異なるオブジェクトのカバレッジエリアの重複を減少させるため、さらに、カバレッジエリアのサイズを減少させるためにディレクトリおよびリーフノードに組織化される。そのような索引構造を生成するための体系的なアプローチは、図１０〜１２を参照して下で説明される。
【００６９】
いくつかの実施形態において、索引構造のディレクトリノードは、索引構造に含まれるオブジェクト間の距離に関する情報を含み得る。ディレクトリノードにおけるデータエントリ２１〜２６は、それぞれ、オブジェクトと、このオブジェクトが指すサブツリーに含まれるいずれかのオブジェクトとの間の距離の上限を含み得る。上限は、これらの距離の最大であり得る。例示として、データエントリ２１は、データエントリ２１によって表される第１のオブジェクトと、ノード１２、１４および１５におけるいずれかのオブジェクトとの間の距離の上限を含み得る。データエントリ２２は、データエントリ２２によって表される第２のオブジェクトと、ノード１３、１６および１７におけるいずれかのオブジェクトとの間の距離の上限を含み得る。データエントリ２３は、データ２３によって表されるオブジェクトと、ノード１４などにおけるオブジェクトのうちのいずれか１つとの間の距離の上限を含み得る。この上限に基づいて、除外が類似性サーチにおいて行われ得る。
【００７０】
親オブジェクトを有する全てのノードにおけるデータは、それぞれのノードにおけるいずれかのオブジェクトに対して、オブジェクトと、その親オブジェクトとの間の距離に関する情報をさらに含み得る。この情報も類似性サーチにおける距離を推定するために用いられ得る。
【００７１】
索引構造は、Ｐ．Ｃｉａｃｃｉａ、Ｍ．ＰａｔｅｌｌａおよびＰ．Ｚｅｚｕｌａによって発展されたＭツリーとして特に組織化され得る。距離メトリックに従って組織化される他の索引構造も用いられ得る。例示として、索引構造は、ｖａｎｔａｇｅポイントツリーであり得る。
【００７２】
図３は、ディレクトリノードに含まれるオブジェクトに関連付けられたデータエントリ３１に対する例示的データ構造を示す。Ｍツリーにおいて用いられる例示的データエントリが例示される。データエントリ３１は、オブジェクトＯｒを含む。あるいは、オブジェクトの特徴量がデータ３１に含まれ得る。あるいは、オブジェクトの識別子が、データ３１に含まれ得る。
【００７３】
データエントリ３１は、オブジェクトＯｒに対するサブツリーのルートノードへのポインターｐｔｒ（Ｔ（Ｏｒ））をさらに含む。
【００７４】
ディレクトリノードが索引構造のルートノードでない場合、データエントリ３１は、オブジェクトＯｒとその親オブジェクトＰ（Ｏｒ）との間の距離ｄ（Ｏｒ；Ｐ（Ｏｒ））をさらに含み得る。そのような索引構造への距離を含むことによって、値ｄ（Ｏｒ；Ｐ（Ｏｒ））は、距離を推定するためか、および／またはサーチを取り除くために用いられ得る。類似性サーチの効率は、ランタイムにおいて向上され得る。
【００７５】
データエントリ３１は、オブジェクトＯｒと、ルートノードＴ（Ｏｒ）を有するサブツリーにおけるいずれかのオブジェクトとの間の距離の上限である半径ｒ（Ｏｒ）をさらに含み得る。半径ｒ（Ｏｒ）は、そのような距離の最大であることが規定され得る：
ｒ（Ｏｒ）＝ｍａｘｊ ｄ（Ｏｊ；Ｏｒ） （５）
ここで、最大は、ポインターｐｔｒ（Ｔ（Ｏｒ））が指すサブツリーにおける全てのオブジェクトＯｊに対して決定される。
【００７６】
図４は、索引構造のリーフノードに含まれるオブジェクトに関連付けられたデータエントリ３２に対する例示的データ構造を示す。Ｍツリーにおいて用いられる例示的データエントリが例示される。データエントリ３２は、オブジェクトＯｊを含む。あるいは、オブジェクトの特徴量がデータ３２に含まれ得る。あるいは、オブジェクトの識別子がデータ３２に含まれ得る。
【００７７】
データエントリ３２は、それぞれのオブジェクトＯｊとその親オブジェクトＰ（Ｏｊ）との間の距離ｄ（Ｏｊ；Ｐ（Ｏｊ））をさらに含み得る。そのような索引構造への距離を含むことによって、値ｄ（Ｏｊ；Ｐ（Ｏｊ））は、サーチ中に距離が計算されることを要求せずに、距離を推定するためか、および／またはサーチを取り除くために用いられ得る。
【００７８】
他のデータ構造が用いられ得る。例示として、データエントリ３１またはデータエントリ３２において示されるさまざまなフィールドエントリは、互いに近接して記憶される必要はない。リレーショナルデータベースにおけるユーザー定義の索引構造は、索引構造の記憶のために用いられ得る。
【００７９】
図５は、プロセッサ２によって索引構造を用いて行われ得る方法３３のフローチャートである。
【００８０】
３４において、入力が受信される。入力は、入力インターフェース４を介して受信されたユーザー入力であり得る。あるいは、入力は、プロセッサ２へ乗り物の他のシステムまたはデバイスによって提供され得るか、または乗り物の外側から受信され得る。入力はテキストストリングであり得る。
【００８１】
３５において、テキスト−音素変換が行われる。結果の音素ストリングは、クエリーオブジェクトとして機能する。
【００８２】
３６において、類似性サーチが索引構造を用いて行われる。索引構造は、距離メトリックに従って組織化されたメトリック索引構造である。索引構造は、図２〜４を参照して上で説明されたように構成され得る。類似性サーチを行うために、クエリーオブジェクトと、索引構造におけるオブジェクトとの間の距離が距離メトリックに従って決定される。
【００８３】
３７において、サーチにおいて見つかる最も関連するオブジェクトが出力される。最も関連するオブジェクトは、クエリーオブジェクトのｋ＞１個の最も近い近傍点であり得る。つまり、索引付けされたオブジェクトの中で、クエリーオブジェクトから最も小さい距離を有するｋ個のオブジェクトであり、距離は、距離メトリックに従って決定される。あるいは、最も関連するオブジェクトは、所定の閾値より小さいクエリーオブジェクトからある距離を有する索引構造における全てのオブジェクトであり得る。
【００８４】
３７における出力は、複数のオブジェクトが出力されるように行われ得る。オブジェクトは、クエリーオブジェクトからのそれぞれの距離によって決定された順序で出力され得る。
【００８５】
図５は、類似性サーチを行う方法４０のフローチャートである。方法４０は、プロセッサ２によって行われ得る。類似性サーチは、距離メトリックｄ（・；・）に従って組織化された索引構造を用いて行われる。オブジェクトのタイプに応じて、さまざまな距離メトリックのうちのいずれか１つが上で説明されたように選択され得る。索引構造は、図２〜４を参照して説明されたように構成され得る。
【００８６】
４１において、クエリーオブジェクトが受信される。クエリーオブジェクトを受信することは、テキスト−音素変換を行うような入力の処理をすることを含み得る。
【００８７】
４２において、索引構造のノードＮがアクセスされる。方法４０のステップは、ツリーを通るパスに沿って反復的に繰り返され得る。第１の反復において、ノードＮは、索引構造のルートノードであり得る。続く反復において、ノードＮは、索引構造のディレクトリノードであり得る。
【００８８】
４３において、ノードＮにおけるオブジェクトＯｒが選択される。異なるオブジェクトＯｒは、異なるオブジェクトＯｒがノードＮに含まれる順序で選択され得る。
【００８９】
４４において、クエリーオブジェクトＱと、ノードＮにおいて選択されたオブジェクトＯｒとの間の距離ｄ（Ｏｒ；Ｑ）が決定される。テキストまたは音素ストリングに対して、距離を決定することは、Ｌｅｖｅｎｓｈｔｅｉｎ距離またはいずれか他のストリングメトリックに従う距離を計算することを含み得る。４４における距離は、距離メトリックを用いて決定され、距離メトリックに従って、索引構造が区分される。
【００９０】
４５において、距離ｄ（Ｏｒ；Ｑ）がオブジェクトＯｒのカバレッジ半径ｒ（Ｏｒ）とサーチ半径Ｒとの総計より大きいか否かが決定される。サーチ半径Ｒは、固定された半径であり得る。あるいは、サーチ半径Ｒは、また、類似性サーチが継続するとダイナミックに調節され得る。例示として、サーチ半径Ｒは、Ｒがクエリーオブジェクトと、それまでに検索されたｋ番目の最も近い近傍点との間の距離に対応するように、ｋ個の最も近い近傍点サーチにおいて調節され得る。
【００９１】
距離ｄ（Ｏｒ；Ｑ）がカバレッジ半径ｒ（Ｏｒ）とサーチ半径Ｒとの総計より大きいことが決定された場合、方法は４５から４６へ進む。
【００９２】
４６において、オブジェクトＯｒに対するサブツリーにおける全てのオブジェクトがサーチから取り除かれる。サブツリーにおけるいずれかのオブジェクトと、オブジェクトＯｒとの間の距離の上限であるカバレッジ半径ｒ（Ｏｒ）の定義によって、オブジェクトＯｒに対するサブツリーにおけるオブジェクトは、距離ｄ（Ｏｒ；Ｑ）がｒ（Ｏｒ）とＲとの総計より大きい場合、クエリーオブジェクトＱからのサーチ半径Ｒより小さいか、または等しい距離を有し得ない。サーチを取り除くことによって、不要なサーチステップが避けられ得る。
【００９３】
距離ｄ（Ｏｒ；Ｑ）がカバレッジ半径ｒ（Ｏｒ）とＲとの総計より大きくないことが決定された場合、方法は４５から４７に進む。
【００９４】
４７において、サーチは、オブジェクトＯｒに対するサブツリーにおいて継続される。この目的のために、オブジェクトＯｒに対するサブツリーのルートノードＴ（Ｏｒ）がアクセスされる。ルートノードは、４５においてテストされた条件に基づいて選択的にアクセスされる。このサブツリーにおけるサーチを継続するために、ステップ４２〜４８がサブツリー内でリーフノードに達するまで繰り返され得る。索引構造のルートからリーフノードまでのパスに沿って、４５において試験された条件がこのパスに沿って横切ったいずれかのオブジェクトＯｒに対して満たされていない場合のみ、リーフノードに達する。
【００９５】
４７においてリーフノードに達した場合、リーフノードにおけるオブジェクトＯｊと、クエリーオブジェクトＱとの間の距離ｄ（Ｏｊ；Ｑ）が決定され得る。
ｄ（Ｏｊ；Ｑ）＜Ｒ （６）
の場合、オブジェクトＯｊは、続く出力に対して関連する索引付けられたオブジェクトのリストに含まれ得る。ｋ個の最も近い近傍点サーチが行われた場合、サーチ半径Ｒが更新され得る。つまり、式（６）が満たされ、オブジェクトＯｊが索引構造において識別された関連するオブジェクトのリストに含まれた場合、サーチ半径Ｒは、減少され得る。リーフノード（リーフノードに対して式（６）が満たされる）において、オブジェクトが見つからなかった場合、方法は４８に進む。
【００９６】
４８において、別のオブジェクトＯｒがノードＮにあるか否かが決定される。別のオブジェクトがある場合、オブジェクトＯｒのうちの別の１つが選択される４３に方法は戻る。
【００９７】
他のオブジェクトがノードＮにないことが決定された場合、方法は４９に進む。４９において、識別されたオブジェクトが出力される。出力は、複数のオブジェクトが出力されるように行われ得る。類似性サーチにおいて見つかったオブジェクトは、クエリーオブジェクトＱからのそれぞれの距離によって決定された順序で出力され得る。この距離は、ステップ４４またはステップ４７において先に決定されているので、距離は、識別されたオブジェクトを続く出力に対して順序付けられたリストにおいて組織化するために用いられ得る。あるいは、サーチ中に決定された距離は、クエリーオブジェクトＱからの距離に従うオブジェクトの続く選別のために登録され得る。
【００９８】
方法４０において、類似性サーチがクエリーオブジェクトと索引付けられたオブジェクトとの間の距離に基づいて行われる。このことは、クエリーオブジェクトおよび索引付けられたオブジェクトがユークリッド空間において規定されない場合ですら、サーチが行われることを可能にする。類似性サーチ４０は、多次元ベクトル空間において規定されたオブジェクトに対しても行われ得る。フォルトトレラントなサーチは、メトリック索引構造において、類似性サーチを用いて実装される。
【００９９】
方法において、サーチは、クエリーオブジェクトと、索引構造のオブジェクトとの間の距離に基づいて選択的に取り除かれ得る。取り除くことは、方法４０のステップ４５において確認された条件に基づくか、もしくは下で説明される代替の条件またはさらなる条件に基づいて行われ得る。
【０１００】
さらなる例示として、図７および図８への参照がなされる。図７は、オブジェクトの概略的表示５０であり、図８は、索引構造７０の概略的表示である。
【０１０１】
図７において示されるオブジェクトは、索引構造のルートノードに含まれるオブジェクト５２および５５を含む。オブジェクト５２に対するサブツリーに配置されるオブジェクトは、オブジェクト５２からのカバレッジ半径５３より小さいか、または等しい距離に配置される。オブジェクト５３に対するサブツリーに配置されるオブジェクトは、オブジェクト５５からのカバレッジ半径５６より小さいか、または等しい距離に配置される。概略的に例示されるように、オブジェクト５２に対するサブツリーにおけるオブジェクトは、第１のカバレッジエリア５４に配置される。オブジェクト５５に対するサブツリーにおけるオブジェクトは、第２のカバレッジエリア５７に配置される。索引構造は、カバレッジエリア５４および５７が小さい重複を有するように組織化される。オブジェクト５２に関連付けられたサブツリーにおけるオブジェクトは、オブジェクト５２の周りに集められ、オブジェクト５５に関連付けられたサブツリーにおけるオブジェクトは、オブジェクト５５の周りに集められる。
【０１０２】
オブジェクト５２に対するサブツリーのルートノードは、オブジェクト５９および６０を含む。オブジェクト５９および６０を含むノードは、ディレクトリノードである。オブジェクト５９に関連付けられたポインターは、オブジェクト６１のようなオブジェクト５９の近接にオブジェクトを含むリーフノードを指す。オブジェクト６０に関連付けられたポインターは、オブジェクト６２のようなオブジェクト６０の近接にオブジェクトを含むリーフノードを指す。
【０１０３】
オブジェクト６３、６４は、オブジェクト５５に関連付けられたサブツリーに含まれる。
【０１０４】
図８は、図７の表示に対応する索引構造７０を例示する。図８において、オブジェクトは、Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ、Ｈ、Ｉ、Ｊとラベル付けされる。
【０１０５】
索引構造は、オブジェクトＡおよびＢを有するルートノード７１を含む。ルートノード７１におけるオブジェクトＡは、例えば、図７の５２において示されたオブジェクトに対応する。ルートノード７１におけるオブジェクトＢは、例えば、図７の５５において示されたオブジェクトに対応する。
【０１０６】
索引構造は、オブジェクトＡに関連付けられたサブツリーに対するルートノードであるディレクトリノード７２を含む。ノード７２は、オブジェクトＣおよびＤを含む。ノード７２におけるオブジェクトＣは、例えば、図７の５９において示されたオブジェクトに対応する。ノード７２におけるオブジェクトＤは、例えば、図７の６０において示されたオブジェクトに対応する。
【０１０７】
索引構造は、オブジェクトＣを親ノードとして有するリーフノード７４を含む。ノード７４は、オブジェクトＧおよびＨを含む。ノード７４におけるオブジェクトＧは、例えば、図７の６１において示されたオブジェクトに対応する。索引構造は、オブジェクトＤを親ノードとして有するリーフノード７５を含む。ノード７５は、オブジェクトＩおよびＪを含む。ノード７５におけるオブジェクトＩは、例えば、図７の６２において示されたオブジェクトに対応する。
【０１０８】
索引構造は、オブジェクトＢに関連付けられたサブツリーにさらなるノード７３を含む。
【０１０９】
近接サーチがクエリーオブジェクト５１に対して行われると想定すると、サーチは、クエリーオブジェクトと索引におけるそれぞれのオブジェクトＡ〜Ｊとの間の距離を索引構造に含まれる距離情報と組み合わせて用いて、取り除かれ得る。サーチ半径Ｒは、図７の５８において概略的に示される。
【０１１０】
サーチ方法４０が開始された場合、索引構造のルートノード７１がアクセスされる。６６において示されるクエリーオブジェクトＱとオブジェクトＢとの間の距離ｄ（Ｑ；Ｂ）は、サーチ半径５８とカバレッジ半径５６との総計よりも大きい。そのため、オブジェクトＢに対するサブツリーにおいてサーチは行われない。
【０１１１】
クエリーオブジェクトＱと、６５において示されたオブジェクトＡとの間の距離ｄ（Ｑ；Ａ）は、５８において示されたサーチ半径と、５３において示されたオブジェクトＡに対するカバレッジ半径との総計より小さい。そのため、サーチは、オブジェクトＡに対するサブツリーにおいて継続される。方法４０のステップ４２〜４９をルートノード７２を有するサブツリーに対して繰り返すことによって、クエリーオブジェクト５１からのサーチ半径より小さいか、または等しい距離に配置されるオブジェクトＧ（図７においてシンボル６１によって表される）およびＩ（図７においてシンボル６２によって表される）が識別される。
【０１１２】
これらのオブジェクトを識別することによって、距離メトリックに従って測定して、クエリーオブジェクトとの相違が最も小さいオブジェクトを戻すフォルトトレラントなサーチが実装される。
【０１１３】
類似性サーチは、サーチをカバレッジ半径に基づいて取り除くことによって効率的に行われ得る。索引構造に含まれるさらなるデータは、サーチ効率をさらに向上させるために用いられ得る。例示として、オブジェクトと、それぞれの親オブジェクトとの間の距離が索引構造に記憶される場合、この情報は、ランタイムにおいて行われる必要がある距離計算の数を減少させるために用いられ得る。
【０１１４】
例示として、方法４０のステップ４２においてアクセスされたノードＮは、索引構造のルートノードではないディレクトリノードである場合、Ｐ（Ｏｒ）がノードオブジェクトＯｒの親を意味する
｜ｄ（Ｑ；Ｐ（Ｏｒ））―ｄ（Ｏｒ；Ｐ（Ｑｒ））｜≦ｒ（Ｏｒ）＋Ｒ （７）
である場合のみ、ステップ４４〜４７は、選択的に行われ得る。距離ｄ（，）はメトリックであり、三角不等式は、オブジェクトＯｒに対するサブツリーにおけるオブジェクトがＲの距離を有さないか、または式（７）が満たされない場合、クエリーオブジェクトＱからより短い距離を有さないことを確実にする。式（７）が満たされない場合、オブジェクトＯｒに対するサブツリーは、取り除かれ得る。
【０１１５】
式（７）は、いずれかのさらなる距離計算を要求せずに、確認され得る。量ｄ（Ｑ；Ｐ（Ｏｒ））は、親ノードに対する方法４０の先行する反復において決定された。量ｄ（Ｏｒ；Ｐ（Ｏｒ））は、索引構造から読まれ得る。式（７）の条件が満たされたか否かに応じて、方法４０のステップ４４における計算を選択的に行うことによって、計算コストがかかるランタイムにおける距離決定の数が減少され得る。
【０１１６】
さらなる例示として、リーフノードが方法４０のステップ４７においてアクセスされた場合、リーフノードにおけるオブジェクトＯｊとクエリーオブジェクトＱとの間の距離は、Ｏｊが含まれるリーフノードの親をＰ（Ｏｊ）が意味する
｜ｄ（Ｑ；Ｐ（Ｏｊ）−ｄ（Ｏｊ；Ｐ（Ｏｊ））｜≦Ｒ （８）
である場合のみ、選択的に決定され得る。ｄ（，）はメトリックなので、三角不等式は、ＯｊおよびクエリーオブジェクトＱは、Ｒの距離を有することができないか、または式（８）が満たされない場合、より短い距離を有することができないことを確実にする。式（８）が満たされない場合、ｄ（Ｑ；Ｏｊ）を決定することは要求されない。
【０１１７】
式（８）は、いずれかのさらなる距離計算を要求せずに確認され得る。量ｄ（Ｑ；Ｐ（Ｏｊ））は、親ノードに対する方法４０の先行するステップにおいて決定された。量（Ｏｊ；Ｐ（Ｏｊ））は、索引構造から読まれ得る。式（８）の条件が満たされた場合のみｄ（Ｑ；Ｐ（Ｏｊ））を選択的に計算することによって、計算コストがかかるランタイムにおける距離決定の数が減少され得る。
【０１１８】
図１〜８を参照して上で説明された実施形態に従う類似性サーチを行うデバイスおよび方法は、オブジェクトがテキストストリング、音素ストリングまたはマルチメディアオブジェクトである場合、特に用いられ得る。デバイスおよび方法は、音素ストリングとの最も小さい相違を有する索引構造におけるオブジェクトを識別するために用いられ得る。索引構造は、音素ストリングに対するフィルターとして用いられ得る。
【０１１９】
図９は、類似性サーチが用いられ得る方法８０のフローチャート表示である。
【０１２０】
８１において、認識器が入力に基づいて音素ストリングを決定する。入力は、テキストストリングであり得る。音素ストリングへの変換は、クラスターにおける音素間の距離（距離メトリックを用いて決定される）が閾値より下という意味で、互いに類似する音素に対応する異なる音素クラスターに基づき得る。
【０１２１】
８２において、音素ストリングは、索引構造を用いてフィルタリングされる。音素ストリングは、図１〜８のうちのいずれか１つを参照して上で説明された索引構造において、類似性サーチを行うことによってフィルタリングされ得る。いくつかの実装において、閾値より小さいか、または等しいクエリーオブジェクトからの距離を有するオブジェクトが決定され得る。代替の実装において、クエリーオブジェクトのｋ個の最も近い近傍点オブジェクトが決定され得る。
【０１２２】
８３において、音素フィルタリングの結果がスペルマッチャーに提供される。
【０１２３】
類似性サーチを行う方法のうちのいずれか１つおよび上で説明されたナビゲーションデバイスのうちのいずれか１つにおいて、索引構造はメトリック索引構造であり得る。類似性サーチを行う方法のうちのいずれか１つおよび上で説明されたナビゲーションデバイスのうちのいずれか１つにおいて、索引構造は、平衡サーチツリーに対応し得る。類似性サーチを行う方法のうちのいずれか１つ、および上で説明されたナビゲーションデバイスのうちのいずれか１つにおいて、索引構造は、ディレクトリノード毎およびリーフノード毎のエントリの数が固定されるように構成され得る。
【０１２４】
図１０〜１２を参照して、これらのプロパティーを有する索引構造を生成する方法が説明される。
【０１２５】
図１０は、索引構造を生成する方法９０のフローチャートである。方法９０は、類似性サーチとは別個に行われ得る。特に、方法９０は、ナビゲーションデバイスのためにデータを前処理する場合、行われ得る。索引構造は、サーバーコンピュータによってセントラルサイトにおいて構築され得、次いで、複数のナビゲーションデバイスに配備され得る。
【０１２６】
方法９０は、索引構造をボトムアップ態様で構築し得、さらなるオブジェクトが続いて索引構造に加えられる。索引構造は、類似性サーチを行う場合にも続いて用いられる距離メトリックを用いて構築される。
【０１２７】
挿入されたオブジェクトは、ストリングであり得、特に音素ストリングまたはテキストストリングであり得る。
【０１２８】
方法９０において、索引構造は、オブジェクトを挿入することと、オーバーフロー状態がノードにおいて生じた場合、ノードを分割することとによって構築される。ノードが分割された場合、新たなディレクトリノードが生成される。
【０１２９】
９１において、索引構造に挿入されるオブジェクトＯｉが検索される。オブジェクトは、音素ストリングまたはテキストストリングであり得る。
【０１３０】
９２において、索引構造のノードＮがアクセスされる。１つしかノードがない場合、このノードがアクセスされる。索引構造が既にディレクトリノードを含んでいる場合、最も高いディレクトリノード（つまり、構造のルートノード）がアクセスされる。
【０１３１】
９３において、ノードＮがリーフノードか否かが決定される。ノードがリーフノードである場合、方法は９８において継続する。そうでない場合、方法は、９４において継続する。
【０１３２】
９４において、距離ｄ（Ｏｋ；Ｏｉ）は、挿入されるオブジェクトＯｉと、ノードに含まれる全てのオブジェクトＯｋとの間で決定される。距離は、それぞれ、距離メトリックに従って決定される。
【０１３３】
９５において、ノードＮに含まれるオブジェクトＯｋが決定され、オブジェクトＯｋに対してｄ（Ｏｋ；Ｏｉ）は、最小となる。
【０１３４】
９６において、新たなノードＮが選択され、ノードＮは、オブジェクトＯｋに対するサブツリーのルートノードである。ノードＮがアクセスされる。
【０１３５】
９７において、ノードＮはリーフノードであるか否かが決定される。ノードＮがリーフノードでない場合、方法は９４に戻る。そうでない場合、方法は、９８において継続する。
【０１３６】
９８において、オブジェクトの挿入後のノードＮのサイズが、許容されたノードのエントリの最大数に対応する閾値を超えるか否かが決定される。エントリの許容された最大数が超えられないことが決定された場合、オブジェクトＯｉが９９においてノードに挿入される。次いで、方法は９１に戻る。
【０１３７】
ノードＮが既に許容されたエントリの最大数を有していることが９８において決定された場合、方法は、９９において継続する。９９において、ノードＮは、１対のノードに分割される。ノードＮを分割することによって、２つの新たなリーフノードが生成される。同時に、ディレクトリノードが生成され、２つの新たなリーフノードへのポインターを有する２つのオブジェクトを含む。オブジェクトＯｉは、２つの新たなリーフノードのうちの１つか、または新たなディレクトリノードに挿入され得る。次いで、方法は９１に戻る。
【０１３８】
図１１および図１２は、ノードにおける許容されたエントリの最大数に達した場合のリーフノードの分割を例示する。
【０１３９】
図１１は、オブジェクトＡおよびＢを有するディレクトリノード１１１と、オブジェクトＣ、Ｄ、Ｇを有するリーフノード１１２と、オブジェクトＥおよびＦを有する別のリーフノード１１３とを有する索引構造１１０を示す。
【０１４０】
新たなオブジェクトＩ（新たなオブジェクトＩに対して、ｄ（Ａ；Ｉ）＜ｄ（Ｂ；Ｉ））が挿入されることを想定して、方法９０は、オブジェクトがリーフノード（ノードＡから到達することが可能である）に挿入されることを決定する。ノードに対して許容されたエントリの最大数が３つのオブジェクトに対応する場合、オブジェクトは、単にノード１１２に挿入することができない。この場合、ノード１１２は分割される。
【０１４１】
図１２は、ノード１１２が分割された後の索引構造１１０を示す。２つの新たなリーフノード１１５および１１６が生成される。さらに、新たなディレクトリノード１１４が生成される。リーフノード１１２に含まれるオブジェクトＣおよびＤは、ディレクトリノードにおけるオブジェクトにレベルが上げられる。Ｍツリーの専門用語において、オブジェクトＣおよびＤは、ルーティングオブジェクトにレベル上げされる。オブジェクトＧは、オブジェクトＣを親として有するリーフノード１１５に加えられる。オブジェクトＩは、オブジェクトＤを親として有するリーフノード１１６に加えられる。
【０１４２】
ノードが方法９０でステップ１００において分割された場合、さまざまな技術が用いられ得、ディレクトリノードへレベル上げされるオブジェクトを選択する。例えば、Ｍツリーに対して、以下の実装が用いられ得る：
一実装において、ディレクトリノードにレベル上げされるオブジェクトが無作為に選択され得る。
【０１４３】
別の実装において、サンプリングがディレクトリノードにレベル上げされた複数対のオブジェクトに対して行われる。複数対のうちのいずれか１つに対して、ノードに含まれる他のノードが２つの新たなリーフノードに区分される。オブジェクトは、新たなリーフノードのうちの１つに割り当てられる。新たなリーフノードのうちの１つに対して、オブジェクトとリーフノードの親との間の距離は、より小さい。区分が完了したとき、結果の包含半径が決定される。包含半径が式（５）に従って決定される。ディレクトリノードにレベル上げされた異なる対のオブジェクトに対して、異なる包含半径が生じる。次いで、ノードは、サンプリングされた対のオブジェクトのうちの１つがディレクトリノードに加えられるように分割され得る。ディレクトリノードに対して、２つの包含範囲の最大は、サンプリングされた対のレベル上げされたオブジェクトの中の最小値を有する。
【０１４４】
別の実装において、サンプリングは、全ての可能な対のオブジェクトＯ１およびＯ２に対して行われる。オブジェクトＯ１およびＯ２は、ノードに含まれ、原則的にはディレクトリノードに加えられ得る。分割の前にノードに含まれる他のオブジェクトは、上で説明されたように区分される。つまり、オブジェクトは、新たなリーフノードのうちの１つに割り当てられ得る。新たなリーフノードに対して、オブジェクトとリーフノードの親との間の距離は、より小さい。可能な対のオブジェクトのうちのいずれか１つに対して、包含半径ｒ（Ｏ１）＋ｒ（Ｏ２）の総計が決定される。次いで、包含半径の最小総計になる対のオブジェクトがディレクトリノードに加えられ得る。他のオブジェクトは、新たなリーフノードのうちの１つにそれぞれ割り当てられ得る。新たなリーフノードに対して、オブジェクトとリーフノードの親との間の距離は、より小さい。
【０１４５】
別の実装において、サンプリングは、全ての可能な対のオブジェクトＯ１およびＯ２に対して行われる。オブジェクトＯ１およびＯ２は、ノードに含まれ、原則的にはディレクトリノードに加えられ得る。分割の前にノードに含まれる他のオブジェクトは、上で説明されたように区分される。つまり、オブジェクトは、新たなリーフノードのうちの１つに割り当てられ得る。新たなリーフノードに対して、オブジェクトとリーフノードの親との間の距離は、より小さい。レベル上げされる可能な対のオブジェクトのうちのいずれか１つに対して、２つの包含半径ｍａｘ（ｒ（Ｏ１），ｒ（Ｏ２））の最大が決定される。次いで、包含半径の最大に対して最小値になる対のオブジェクトがディレクトリノードに加えられ得る。他のオブジェクトは、それぞれ、新たなリーフノードのうちの１つに割り当てられ得る。新たなリーフノードに対して、オブジェクトとリーフノードの親との間の距離は、それぞれ、より小さい。
【０１４６】
別の実装において、挿入されるオブジェクトから最も大きい距離ｄ（Ｏｋ；Ｏｉ）を有するリーフノードにおけるオブジェクトＯｋが決定される。次いで、このオブジェクトＯｋおよび新たなオブジェクトＯｉがディレクトノードにレベル上げされ得る。他のオブジェクトは、それぞれ、新たなリーフノードのうちの１つに割り当てられ得る。新たなリーフノードに対して、オブジェクトとリーフノードの親との間の距離は、より小さい。
【０１４７】
Ｍツリーとして構成される索引構造を生成する方法が図１０〜図１２を参照して、上で説明されたが、同じものを構築する他のメトリック索引構造および方法が他の実施形態において用いられ得る。例えば、ｖａｎｔａｇｅポイントツリーが用いられ得る。
【０１４８】
実施形態に従うデバイスおよび方法が詳細に説明されたが、改変が他の実施形態において実装され得る。例示として、包含半径、または親オブジェクトと子オブジェクトとの間の距離のような距離情報が索引データに記憶され得るが、そのようなデータは、また、ランタイムにおいて計算され得る。
【０１４９】
さらなる例示として、索引ツリーおよびそのノードの例示的構造が説明されたが、いずれか適切なデータ構造が索引ツリーを実装するために用いられ得る。例示として、索引ツリーは、リレーショナルデータベースにおけるユーザー定義の構造として記憶され得る。この場合、１つのテーブルが提供され得、テキストストリングまたは音素ストリングを含む。別のテーブルが提供され得、対のテキストストリングまたは音素ストリングの間の距離を含む。
【０１５０】
さらなる例示として、索引構造が「索引構造におけるオブジェクト」のような表現を用いて説明されたが、そのようなオブジェクトは、索引構造に組み込まれる必要はない。むしろ、索引構造は、オブジェクト自体よりも、オブジェクトへの識別子またはポインターを含み得る。
【０１５１】
さらなる例示として、類似性サーチが、クエリーオブジェクトからの固定されたサーチ半径内に配置されたオブジェクトに対するサーチに関連して説明されたか、またはｋ個の最も近い近傍点に対するサーチに関連して説明されたが、他の類似性サーチもメトリック索引構造を用いて実装され得る。いくつかのサーチが音素またはテキストストリングに対するサーチのような特定の距離メトリックまたは特定の適用に関連して説明されたが、実施形態は、それらに限定されない。
【０１５２】
発明の実施形態は、乗り物のナビゲーションデバイスに対して用いられ得る。
【符号の説明】
【０１５３】
１０、７０ 索引構造
５１ クエリーオブジェクト
１１〜１７、７１〜７５ ノード
【特許請求の範囲】
【請求項１】
索引構造（１０；７０）を用いてナビゲーションデバイスデータベースにおいて類似性サーチを行う方法であって、該データベースは、複数のオブジェクトを含み、該索引構造（１０；７０）は、複数のノード（１１−１７；７１−７５）を含み、
該方法は、
クエリーオブジェクト（５１）を受信することと、
該複数のオブジェクトのうちの少なくとも１つのオブジェクト（５２，５５，５９，６０）に関連付けられる該索引構造（１０；７０）のノード（１１−１３；７１−７３）にアクセスすることと、
該ノード（１１−１３；７１−７３）に関連付けられた該少なくとも１つのオブジェクト（５２，５５，５９，６０）の各々のオブジェクトに対して、それぞれ、該クエリーオブジェクト（５１）と該オブジェクトとの間の距離（６５，６６）を決定することであって、該距離（６５，６６）は、それぞれ、距離メトリックに従って決定される、ことと、
該決定された距離（６５，６６）に基づいて、該索引構造（１０；７０）の別のノード（１２−１７；７２−７５）に選択的にアクセスすることと
を含む、方法。
【請求項２】
前記クエリーオブジェクト（５１）は、音素ストリングまたはテキストストリングである、請求項１に記載の方法。
【請求項３】
前記クエリーオブジェクト（５１）を受信することは、テキスト入力を受信することと、テキスト−音素変換を行うこととを含む、請求項２に記載の方法。
【請求項４】
前記索引構造（１０；７０）は、前記少なくとも１つのオブジェクト（５２，５５，５９，６０）と該索引構造（１０；７０）の他のオブジェクトとの間の距離についての距離情報をさらに含み、
該他のノード（１２−１７；７２−７５）は、該距離情報と、前記決定された距離（６５，６６）とに基づいて選択的にアクセスされる、請求項１に記載の方法。
【請求項５】
前記ノード（１１−１３；７１−７３）は、いくつかのオブジェクト（５２，５５）に関連付けられ、
前記距離情報は、該いくつかのオブジェクト（５２，５５）の各々に対して、該それぞれのオブジェクト（５２，５５）と、該それぞれのオブジェクト（５２，５５）に関連付けられた前記索引構造（１０；７０）のサブツリーに含まれる任意のオブジェクト（５９−６４）との間の距離の上限（５３，５６）を含む、請求項４に記載の方法。
【請求項６】
前記クエリーオブジェクト（５１）は、音素ストリングまたはテキストストリングであり、
該クエリーオブジェクト（５１）を受信することは、テキスト入力を受信することと、テキスト−音素変換を行うこととを含む、請求項４に記載の方法。
【請求項７】
オブジェクトは、前記決定された距離（６５，６６）に基づいて、前記類似性サーチから選択的に取り除かれる、請求項１〜６のうちのいずれか一項に記載の方法。
【請求項８】
前記他のノード（１２−１７；７２−７５）が前記索引構造（１０；７０）のリーフノード（１４−１７；７４，７５）である場合に、前記距離（６５，６６）を決定することと、前記別のノード（１２−１７；７２−７５）に選択的にアクセスすることとが終了される、請求項１〜６のうちのいずれか一項に記載の方法。
【請求項９】
前記距離メトリックに従って決定された、前記クエリーオブジェクト（５１）からの所定の距離（５８）内に配置された全てのオブジェクトが識別される、請求項１〜６のうちのいずれか一項に記載の方法。
【請求項１０】
１より大きい整数ｋ個のオブジェクトが識別され、該ｋ個のオブジェクトは、前記距離メトリックに従って決定された、前記クエリーオブジェクト（５１）のｋ個の最も近い近傍点を表す、請求項１〜６のうちのいずれか一項に記載の方法。
【請求項１１】
前記識別されたオブジェクトは、前記クエリーオブジェクト（５１）と、それぞれの識別されたオブジェクトとの間の距離に基づいて決定された順序で出力される、請求項１０に記載の方法。
【請求項１２】
ナビゲーションデバイスであって、該ナビゲーションデバイスは、
複数のオブジェクトを含むデータベースに対する索引構造（１０；７０）を格納する記憶デバイス（３）であって、該索引構造（１０；７０）は、複数のノード（１１−１７；７１−７５）を含む、記憶デバイス（３）と、
該記憶デバイス（３）に結合された処理デバイス（２）と
を含み、該処理デバイス（２）は、クエリーオブジェクト（５１）に対して類似性サーチを行うために、
該複数のオブジェクトのうちの少なくとも１つのオブジェクト（５２，５５，５９，６０）に関連付けられた該索引構造（１０；７０）のノード（１１−１３；７１−７３）にアクセスすることと、
距離メトリックに従って、該クエリーオブジェクト（５１）と該少なくとも１つのオブジェクト（５２，５５，５９，６０）との間の距離（６５，６６）を決定することと、
該決定された距離（６５，６６）に基づいて、該索引構造（１０；７０）の別のノード（１２−１７；７２−７５）に選択的にアクセスすることと
を行うように構成される、ナビゲーションデバイス。
【請求項１３】
前記処理デバイス（２）は、請求項１〜６のうちのいずれか一項に記載の方法を行うように構成される、請求項１２に記載のナビゲーションデバイス。
【請求項１４】
複数のオブジェクトを含むナビゲーションデバイスデータベースのためのメトリック索引構造（１０；７０；１１０）を生成する方法であって、該方法は、該索引構造（１０；７０；１１０）の他のノードへのポインターを含む該索引構造のディレクトリノード（１１−１３；７１−７３；１１１，１１４）を生成することと、該索引構造のリーフノード（１４−１７；７４；７５；１１３，１１５，１１６）を生成することとを含み、
該ディレクトリノード（１１−１３；７１−７３；１１１，１１４）と該リーフノード（１４−１７；７４；７５；１１３，１１５，１１６）とを生成することは、
該オブジェクトの複数の組に対して、それぞれ、該オブジェクトの組のオブジェクト間の距離を決定することによって複数の距離を決定することであって、該距離は、それぞれ、距離メトリックに従って決定される、ことと、
該複数の距離に基づいて、ディレクトリノード（１１−１３；７１−７３；１１１，１１４）に含まれるべきであるオブジェクトと、リーフノード（１４−１７；７４；７５；１１３，１１５，１１６）に含まれるべきであるオブジェクトとを識別することと
を含む、方法。
【請求項１５】
前記オブジェクトは、音素ストリングまたはテキストストリングである、請求項１４に記載の方法。
【請求項１６】
前記ディレクトリノードおよび／または前記リーフノードにおいて、前記複数の距離から導かれた距離情報を格納することを含む、請求項１４または１５に記載の方法。
【請求項１】
索引構造（１０；７０）を用いてナビゲーションデバイスデータベースにおいて類似性サーチを行う方法であって、該データベースは、複数のオブジェクトを含み、該索引構造（１０；７０）は、複数のノード（１１−１７；７１−７５）を含み、
該方法は、
クエリーオブジェクト（５１）を受信することと、
該複数のオブジェクトのうちの少なくとも１つのオブジェクト（５２，５５，５９，６０）に関連付けられる該索引構造（１０；７０）のノード（１１−１３；７１−７３）にアクセスすることと、
該ノード（１１−１３；７１−７３）に関連付けられた該少なくとも１つのオブジェクト（５２，５５，５９，６０）の各々のオブジェクトに対して、それぞれ、該クエリーオブジェクト（５１）と該オブジェクトとの間の距離（６５，６６）を決定することであって、該距離（６５，６６）は、それぞれ、距離メトリックに従って決定される、ことと、
該決定された距離（６５，６６）に基づいて、該索引構造（１０；７０）の別のノード（１２−１７；７２−７５）に選択的にアクセスすることと
を含む、方法。
【請求項２】
前記クエリーオブジェクト（５１）は、音素ストリングまたはテキストストリングである、請求項１に記載の方法。
【請求項３】
前記クエリーオブジェクト（５１）を受信することは、テキスト入力を受信することと、テキスト−音素変換を行うこととを含む、請求項２に記載の方法。
【請求項４】
前記索引構造（１０；７０）は、前記少なくとも１つのオブジェクト（５２，５５，５９，６０）と該索引構造（１０；７０）の他のオブジェクトとの間の距離についての距離情報をさらに含み、
該他のノード（１２−１７；７２−７５）は、該距離情報と、前記決定された距離（６５，６６）とに基づいて選択的にアクセスされる、請求項１に記載の方法。
【請求項５】
前記ノード（１１−１３；７１−７３）は、いくつかのオブジェクト（５２，５５）に関連付けられ、
前記距離情報は、該いくつかのオブジェクト（５２，５５）の各々に対して、該それぞれのオブジェクト（５２，５５）と、該それぞれのオブジェクト（５２，５５）に関連付けられた前記索引構造（１０；７０）のサブツリーに含まれる任意のオブジェクト（５９−６４）との間の距離の上限（５３，５６）を含む、請求項４に記載の方法。
【請求項６】
前記クエリーオブジェクト（５１）は、音素ストリングまたはテキストストリングであり、
該クエリーオブジェクト（５１）を受信することは、テキスト入力を受信することと、テキスト−音素変換を行うこととを含む、請求項４に記載の方法。
【請求項７】
オブジェクトは、前記決定された距離（６５，６６）に基づいて、前記類似性サーチから選択的に取り除かれる、請求項１〜６のうちのいずれか一項に記載の方法。
【請求項８】
前記他のノード（１２−１７；７２−７５）が前記索引構造（１０；７０）のリーフノード（１４−１７；７４，７５）である場合に、前記距離（６５，６６）を決定することと、前記別のノード（１２−１７；７２−７５）に選択的にアクセスすることとが終了される、請求項１〜６のうちのいずれか一項に記載の方法。
【請求項９】
前記距離メトリックに従って決定された、前記クエリーオブジェクト（５１）からの所定の距離（５８）内に配置された全てのオブジェクトが識別される、請求項１〜６のうちのいずれか一項に記載の方法。
【請求項１０】
１より大きい整数ｋ個のオブジェクトが識別され、該ｋ個のオブジェクトは、前記距離メトリックに従って決定された、前記クエリーオブジェクト（５１）のｋ個の最も近い近傍点を表す、請求項１〜６のうちのいずれか一項に記載の方法。
【請求項１１】
前記識別されたオブジェクトは、前記クエリーオブジェクト（５１）と、それぞれの識別されたオブジェクトとの間の距離に基づいて決定された順序で出力される、請求項１０に記載の方法。
【請求項１２】
ナビゲーションデバイスであって、該ナビゲーションデバイスは、
複数のオブジェクトを含むデータベースに対する索引構造（１０；７０）を格納する記憶デバイス（３）であって、該索引構造（１０；７０）は、複数のノード（１１−１７；７１−７５）を含む、記憶デバイス（３）と、
該記憶デバイス（３）に結合された処理デバイス（２）と
を含み、該処理デバイス（２）は、クエリーオブジェクト（５１）に対して類似性サーチを行うために、
該複数のオブジェクトのうちの少なくとも１つのオブジェクト（５２，５５，５９，６０）に関連付けられた該索引構造（１０；７０）のノード（１１−１３；７１−７３）にアクセスすることと、
距離メトリックに従って、該クエリーオブジェクト（５１）と該少なくとも１つのオブジェクト（５２，５５，５９，６０）との間の距離（６５，６６）を決定することと、
該決定された距離（６５，６６）に基づいて、該索引構造（１０；７０）の別のノード（１２−１７；７２−７５）に選択的にアクセスすることと
を行うように構成される、ナビゲーションデバイス。
【請求項１３】
前記処理デバイス（２）は、請求項１〜６のうちのいずれか一項に記載の方法を行うように構成される、請求項１２に記載のナビゲーションデバイス。
【請求項１４】
複数のオブジェクトを含むナビゲーションデバイスデータベースのためのメトリック索引構造（１０；７０；１１０）を生成する方法であって、該方法は、該索引構造（１０；７０；１１０）の他のノードへのポインターを含む該索引構造のディレクトリノード（１１−１３；７１−７３；１１１，１１４）を生成することと、該索引構造のリーフノード（１４−１７；７４；７５；１１３，１１５，１１６）を生成することとを含み、
該ディレクトリノード（１１−１３；７１−７３；１１１，１１４）と該リーフノード（１４−１７；７４；７５；１１３，１１５，１１６）とを生成することは、
該オブジェクトの複数の組に対して、それぞれ、該オブジェクトの組のオブジェクト間の距離を決定することによって複数の距離を決定することであって、該距離は、それぞれ、距離メトリックに従って決定される、ことと、
該複数の距離に基づいて、ディレクトリノード（１１−１３；７１−７３；１１１，１１４）に含まれるべきであるオブジェクトと、リーフノード（１４−１７；７４；７５；１１３，１１５，１１６）に含まれるべきであるオブジェクトとを識別することと
を含む、方法。
【請求項１５】
前記オブジェクトは、音素ストリングまたはテキストストリングである、請求項１４に記載の方法。
【請求項１６】
前記ディレクトリノードおよび／または前記リーフノードにおいて、前記複数の距離から導かれた距離情報を格納することを含む、請求項１４または１５に記載の方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１２−１７４２７２（Ｐ２０１２−１７４２７２Ａ）
【公開日】平成２４年９月１０日（２０１２．９．１０）
【国際特許分類】
【出願番号】特願２０１２−３２６９８（Ｐ２０１２−３２６９８）
【出願日】平成２４年２月１７日（２０１２．２．１７）
【出願人】（５０４１４７９３３）ハーマン ベッカー オートモーティブ システムズ ゲーエムベーハー (165)
【公開日】平成２４年９月１０日（２０１２．９．１０）
【国際特許分類】
【出願日】平成２４年２月１７日（２０１２．２．１７）
【出願人】（５０４１４７９３３）ハーマン ベッカー オートモーティブ システムズ ゲーエムベーハー (165)
[ Back to top ]