可変圧縮による適応索引に対する最近接探索
【課題】
【解決手段】
探索システムは、ユーザにより入力される位置に最近接する木に格納されたオブジェクトを見つけるために木のノードを探索できる。木は、木のノードがオブジェクトの部分集合を囲んでいるバウンディングボックスに対応するようにインタレースされた座標を有するオブジェクトキーを用いて構成される。探索アルゴリズムは、ある位置に対する最近接オブジェクトを見つけられる。
【解決手段】
探索システムは、ユーザにより入力される位置に最近接する木に格納されたオブジェクトを見つけるために木のノードを探索できる。木は、木のノードがオブジェクトの部分集合を囲んでいるバウンディングボックスに対応するようにインタレースされた座標を有するオブジェクトキーを用いて構成される。探索アルゴリズムは、ある位置に対する最近接オブジェクトを見つけられる。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、以下の同時継続の出願：２００６年６月３０日出願の、Tsia Kuznetsov等による「可変圧縮による適応索引」という名称の米国仮出願番号６０／８０６，３６６（Attorney Docket No. TELA-07780US0）；２００６年６月３０日出願の、Tsia Kuznetsov等による「可変圧縮による適応索引における最近傍検索」という名称の米国仮出願番号６０／８０６，３６７（Attorney Docket No. TELA-07781US0）；２００７年６月２８日出願の、Tsia Kuznetsov等による「可変圧縮による適応索引」という名称の米国特許出願番号１１／７７０，０５８（Attorney Docket No. TELA-07780US1）；及び、２００７年６月２８日出願の、Tsia Kuznetsov等による「可変圧縮による適応索引における最近傍検索」という名称の米国特許出願番号１１／７７０，４２６（Attorney Docket No. TELA-07781US1）、の優先権を主張するものであり、それらの内容は、本願に合体されるものである。
【背景技術】
【０００２】
多くのアプリケーションは、ユーザに対して空間探索サービスを提供するために、格納された空間データを使用できる。アプリケーションは、移動マッピングシステム又は固定マッピングシステムを含むことができる。移動マッピングシステム又は固定マッピングシステムは、マップレンダリング、空間オブジェクト探索、経路探索、方向及び位置決めを含むことができる。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
多くの場合、ユーザは、所定の座標系においてオブジェクトの場所を特定し、そのオブジェクトに関するより多くの情報の取得を要求する。多くのオブジェクトを含む複雑なデータベースにおいて、入力位置に最近接するオブジェクトを迅速に見つけることが問題となる場合がある。特に、システムがモバイルナビゲーション装置のようにメモリを制約される場合に問題となる。
【図面の簡単な説明】
【０００４】
【図１】本発明の探索を使用するマップに基づくシステムを示す図である。
【図２Ａ】本発明の一実施形態の木の構成を示す図である。
【図２Ｂ】本発明の一実施形態の木の構成を示す図である。
【図２Ｃ】本発明の一実施形態の木の構成を示す図である。
【図２Ｄ】本発明の一実施形態の木の構成を示す図である。
【図２Ｅ】本発明の一実施形態の木の構成を示す図である。
【図３】本発明の一実施形態の探索方法を示すフローチャートである。
【図４Ａ】ノードに対するバウンディングボックスの一例を示す。
【図４Ｂ】ノードに対するバウンディングボックスの一例を示す。
【図５Ａ】一実施形態の好適な探索を示す図である。
【図５Ｂ】一実施形態の好適な探索を示す図である。
【図５Ｃ】一実施形態の好適な探索を示す図である。
【図５Ｄ】一実施形態の好適な探索を示す図である。
【図５Ｅ】一実施形態の好適な探索を示す図である。
【図５Ｆ】一実施形態の好適な探索を示す図である。
【図６】ノードが除外情報等の他の探索基準の指示を含む一例を示す図である。
【発明を実施するための形態】
【０００５】
本発明の一実施形態は、最近接オブジェクトに関する木１０２のノードを探索する探索システムを含むコンピュータにより実現される方法である。木のノード各々が空間座標キーを有するオブジェクトの部分集合を囲んでいるバウンディングボックス（bounding box）に対応するように、木は、それらオブジェクトの集合に対して構成される。探索により、ある位置に対する最近接オブジェクトが見つけられる。
【０００６】
一実施形態において、根の下の木ノードのバウンディングボックスは、オブジェクトが存在する領域のみを範囲に含む。これにより、オブジェクトの格納及び潜在的な最近接オブジェクトの検索が最適化される。同様に、一実施形態において、子ノードのバウンディングボックスは、オブジェクトが存在する領域のみを範囲に含む。根ノードのバウンディングボックスは、関連するオブジェクトを有さないいくつかの領域を含まないようなバウンディングボックスである。
【０００７】
一実施形態において、緯度及び経度の座標が使用される。例えば、緯度及び経度の座標の数字は、以下に説明するように文字列キーにインタレース（interlace）される。
【０００８】
符号化オブジェクトキーの精度は、根から葉までのパス上のノード毎に向上する。関連するバウンディングボックスの範囲は、根から葉に向けて減少する。範囲は、座標キーシステムに固有である。例えば、範囲は、所定の方向に対するキーの最高精度における距離の１つの単位である。以下に説明するインタレースされた座標系の一例は、子ノード毎に１／１０に減少するいずれかの座標方向のバウンディングボックスの範囲を有する。
【０００９】
別の実施形態において、格納された範囲値が使用される。
【００１０】
一実施形態において、葉ノードは、複数のオブジェクトを指し示すことができる。木は、所定の基準に基づいて葉のオブジェクト数を最大限にする傾向がある葉ノードを与えるように構成される。一実施形態において、指定される枝刈り基準は、各木ノードが少なくとも子孫のオブジェクトであり、そうでない場合には、枝は枝刈りされ、オブジェクトは葉ノードに割り当てられる。
【００１１】
最大の探索半径値は、探索を制限するように維持される。探索半径値は、バウンディングボックス情報に基づいて減少される。ある位置から各ノードまでの最短距離及び最長距離は、ノードのバウンディングボックスを用いて計算される。ノードは、最大探索半径値に基づいて考慮の対象から外される。一例において、バウンディングボックスが最大探索半径より長いある位置からの最短距離を有するノードは無視される。
【００１２】
ノードに対するオブジェクトキー情報は、バウンディングボックスの角の位置及び範囲を符号化するのに十分である。一例において、座標情報がインタレースされる場合、ノードのバウンディングボックスの左下の角等の角は、デインタレースされた座標により決められ、各座標に対するバウンディングボックスの範囲は、座標の構成から決められる。
【００１３】
コンピュータにより実現される方法は、マップシステム１００又はナビゲーションシステムの一部である。オブジェクトは、道路区間、地点情報（ＰＯＩ）又は他の空間オブジェクト等の空間オブジェクトを含むことができる。空間オブジェクトは、１つ以上の座標により示される。
【００１４】
本発明の一実施形態は、アプリケーション１０４を具備するシステム１００である。アプリケーション１０４は、位置を取得するためのインタフェースを含むことができる。アプリケーションは、最近接オブジェクトに対する木のノードを探索する空間探索を使用できる。木のノードがオブジェクトの部分集合を囲んでいるバウンディングボックスに対応するように、木１０２は、座標により符号化された空間キーに基づいてもよい。探索により、ある位置に対する最近接オブジェクトが見つけられる。
【００１５】
アプリケーション１０４は、マップディスプレイ１０２を有することができる。アプリケーションは、ユーザに対して情報を伝えるために、聴覚プレゼンテーション等の非視覚的な手段を使用できる。
【００１６】
オブジェクト座標が木を作成するのに使用される方法の一例を以下のように与える。
【００１７】
緯度及び経度からキーを作成するために以下を行なう。
１．１０進数を地球の円周を表す所定のビット数の整数座標に変換する。
２．座標を正の空間に移動する。
３．各整数を文字列に変更する。
４．長さを等しくするために各文字列の先頭に「０」を付加する。
５．緯度及び経度の１０進数字をインタレースしてキー文字列とすることにより探索キーを作成する。
緯度の文字列が「００１２３」を含むと仮定する。
経度の文字列が「０００７８」を含むと仮定する。
結果として得られるインタレースされた文字列キーは「００００１０２７３８」となる。
【００１８】
この空間キーは、座標索引ａを構築するのに用いられる。キーの精度は、根から葉までのパス上のノード毎に向上する。
【００１９】
格納及び検索の最適化のために、索引の葉ノードキーは、親のキーと等しくなるように切り捨てられ、葉はマージさせられる。これにより、探索は、オブジェクトストアに対するオブジェクト参照に従う必要がある。なお、オブジェクトストアは、最近接オブジェクトの選択時の最終ステップである。
【００２０】
最近接探索は、木１０２上で実現される。探索パス上の各ノードのバウンディングボックスは、ノードの空間キーから復元されうる。空間探索に関するノードのバウンディングボックスを検索するために以下を行なう。
各木ノードは、キーのプレフィックスを格納でき、キープレイフィックスは根において最低の精度を有し、葉において最高の精度を有する。可変圧縮による適応索引において、ノード毎の完全なキーが根からノードまでの全てのキープレフィックスの連結となるように、それらのキープレフィックスは減少されうる。この連結により、そのノードに対する完全なキーが得られ、ノードの各キーは、左下の角及びノードのバウンディングボックスの範囲を符号化できる。
【００２１】
一実施形態において、ノードの左下の角及びバウンディングボックスの空間範囲を算出するために以下を行なう。
ノードの空間キーをデインタレースし、結果として得られる緯度及び経度の文字列に欠落している「０」を付加して左下の角を表す全長（この例においては５）とする。
ａ）一例において、ノードキーが「００００１０２」であると仮定すると、緯度は「００１２０」である。ここで付加された「０」は、ノードの子の緯度が１２０〜１２９であるため、ノードの緯度の範囲は１０の１乗であることを意味する。経度は「０００００」である。ここで付加された「００」は、ノードの子の経度が０〜９９であるため、ノードの経度の範囲は１０の２乗であることを意味する。
ｂ）別の例において、ノードキーが「００００１０２７」であると仮定すると、緯度は「００１２０」であり、ノードの子の緯度は１２０〜１２９であるため、ノードの緯度の範囲は１０の１乗である。経度は「０００７０」であり、ノードの子の経度は７０〜７９であるため、ノードの経度の範囲は１０の１乗である。
【００２２】
ノードの左下の角の算出を完了するために、文字列の緯度及び経度を整数座標に変換し、整数を元の座標空間に戻す。
【００２３】
ノードのバウンディングボックスは、空間範囲及び左下の角の整数の緯度及び経度の座標から算出される。
【００２４】
図２Ａ〜図２Ｅは、木の構成の一例を示す。
【００２５】
図２Ａは、Ｘで示す道路区間点を含む好適なマップを示す。図２Ｂに示すように、参照点座標の緯度及び経度は、インタレースされてキーになる。キーは、図２Ｃに示すようにノード木を構成するために使用されうる。各ノードにおけるキーの一部は、上述のようにノードに対するバウンディングボックスを復号化するために使用されうる。図２Ｃの例において、ノード２１０（００００１０２７３８）は図２Ａのバウンディングボックス２０２に対応する。ノード２１２（００００１０２７３）は図２Ａのバウンディングボックス２０４に対応する。ノード２１４（００００１０２７）は図２Ａのバウンディングボックス２０６に対応する。
【００２６】
葉ノード２１０は、オブジェクトストア２１６のオブジェクトを指し示すことができるか、あるいはオブジェクトを直接格納できる。オブジェクトは、名前及び他の情報、並びに１つ以上の座標を含むことができる。一例において、オブジェクト座標は、道路区間の中点又は終点であってもよい。ポインタは、バウンディングボックス２０２において特定の緯度及び経度の座標を有するオブジェクトの場所を特定するために使用される。
【００２７】
２００６年６月３０日に出願され且つ本明細書に参考として取り入れられている米国特許出願第６０／８０６，３６６号公報（Attorney Docket No. TELA-07780US0に対応する）「ADAPTIVE INDEX WITH VARIABLE COMPRESSION」において説明されるように、葉ノードはオブジェクトに対する複数の参照を含むことができる。図２Ｄの例において、葉ノードはバウンディングボックス２０４の２つのオブジェクトを指し示す。図２Ｅの例において、葉ノードはバウンディングボックス２０６の２６個のオブジェクトを指し示す。
【００２８】
ノード木に対する好適な探索について以下に説明する。
【００２９】
適応圧縮された索引に対する空間探索
座標の緯度、経度を有する点Ｐを仮定する。
根ノードｒを読み出し、そのバウンディングボックスを復元する。
Ｐから根の最も遠い場所までの最大半径ｍａｘＲを算出する。
ＲｅｔｕｒｎＶａｌｕｅは組（オブジェクト（object），距離（distance））であってもよい。これは以下の手順により算出されうる。
（ｏｂｊｅｃｔ，ｄｉｓｔａｎｃｅＴｏＯｂｊｅｃｔ）＝ＦｉｎｄＮｅａｒｅｓｔＯｂｊｅｃｔ（）（木ノード（tree-node），ｍａｘＲ）
ノード（node）が葉（leaf）である場合；
最近接オブジェクト及びｄｉｓｔａｎｃｅＴｏＯｂｊｅｃｔを取得する；
ｄｉｓｔａｎｃｅＴｏＯｂｊｅｃｔ＜ｍａｘＲの場合、更新する：
ｍａｘＲ＝ｄｉｓｔａｎｃｅＴｏＯｂｊｅｃｔ
ｒｅｔｕｒｎ（ｏｂｊｅｃｔ，ｄｉｓｔａｎｃｅＴｏＯｂｊｅｃｔ）
子ノード（child nodes）を読み出す
各子ノードに対してＰまでの距離、ｍｉｎＤ及びｍａｘＤを算出する
ｍｉｎＤ＞ｍａｘＲを有する子を考慮の対象から外す
ルートｒの下、以下の子ノードが最初に考慮される
（ａ，ｍｉｎＤ，ｍａｘＤ）
（ｆ，ｍｉｎＤ，ｍａｘＤ）
（ｈ，ｍｉｎＤ，ｍａｘＤ）
ｍａｘＲを子のｍａｘＤの最小値まで減少する
ｍｉｎＤで子アレイをソートする
子アレイが空でなく且つｍｉｎ（子のｍｉｎＤ）＜ｍａｘＲの場合に以下を行なう
最小のｍｉｎＤを有する子ノード（child-node）を選択する；
（ｏｂｊｅｃｔ，ｄｉｓｔａｎｃｅＴｏＯｂｊｅｃｔ）＝ＦｉｎｄＮｅａｒｅｓｔＯｂｊｅｃｔ（子ノード，ｍａｘＲ）
Ｒｅｔｕｒｎ（ｏｂｊｅｃｔ，ｄｉｓｔａｎｃｅＴｏＯｂｊｅｃｔ）
【００３０】
図３は、好適な探索を示すフローチャートの一例を示す。
【００３１】
図４Ａは、図４Ｂの木に対するバウンディングボックスを示す。図４Ａは、子ノードに対するバウンディングボックスが親ノード内にネストされる方法を示す。バウンディングボックスの大きさは、縮尺したものではない。
【００３２】
図５Ａ〜図５Ｆは、好適な探索を示す。点Ｐは、カーソル選択、タッチスクリーン選択又は別の入力手段等のユーザ入力から決められうる。点Ｐは、全地球測位システム（ＧＰＳ）又は他の位置決めシステムから取得されうる。図５Ａ〜図５Ｆに示すステップは、点Ｐに対する最近接オブジェクトを見つけるために木構造を探索する方法を示す。
【００３３】
図５Ａ（図３のステップ３０２に対応する）において、ｍａｘＲは点Ｐから根ノードのバウンディングボックスの最も遠い角までの距離となるように決められる。根（ノードｒ）が葉ノードでないため、図３のステップ３０４において、ノードの子ノード（ノードａ、ｆ、ｈ）が取得される。
【００３４】
子ノードの各バウンディングボックスに関する最長距離及び最短距離が取得されうる（ステップ３０６）。図５Ａに示すように、最長距離は点Ｐからバウンディングボックスの最も遠い角までの線の距離に対応してもよい。最短距離は、可能であれば、点Ｐから緯度又は経度の値に沿うバウンディングボックスの辺までの直線であってもよいし、また、そのような緯度又は経度に沿う線が存在しなければ、バウンディングボックスの最近接の角までの線であってもよい。
【００３５】
ｍａｘＲは、子ノードの最短のｍａｘＤが現時点のｍａｘＲより小さければ、そのｍａｘＤに設定される（図３のステップ３０８）。ｍｉｎＤがｍａｘＲより大きい子ノードは削除される。図５Ｂにおいて、ノードｈ及びその子は無視されうる。他のノードは、最近接オブジェクトを含む可能性が最も高いノードが最初に調査されるように、ｍｉｎＤの値の昇順のリストに配置される（図３のステップ３１０）。従って、この時点におけるリストは｛ａ，ｆ｝である。
【００３６】
図５Ｃにおいて、ノードａの子ノードがチェックされる。図５Ｄにおいて、ｍａｘＲはバウンディングボックスｂのｍａｘＤに設定される。この時点におけるリストは｛ｂ，ｆ｝である。
【００３７】
図５Ｅにおいて、ノードｂの子がチェックされ、リストは｛ｅ，ｆ｝になる。
【００３８】
図５Ｆにおいて、ノードｅが葉ノードであるため、ノードｅのオブジェクトは、点Ｐに対する最近接オブジェクトを見つけるためにチェックされる。ノードｅは、オブジェクトストアのオブジェクトに対するポインタを複数有することができる。それらは、ノードｅにおいて最近接オブジェクトを見つけるためにチェックされうる。これは、図３のステップ３２０に対応する。オブジェクトまでの距離が現時点のｍａｘＲより小さいため、ｍａｘＲはオブジェクトまでの距離に設定される。この時点におけるリストは｛ｆ｝である。
【００３９】
その後、ノードｆがチェックされ、子ノードｇを有することが判明する。ノードｇはｍｉｎＤ＞ｍａｘＲを有するため、この方法は終了し、ノードｅにおいて見つけられたオブジェクトのうちの最近接オブジェクトがその位置に対する最近接オブジェクトとなるように決められる。ユーザは、マップディスプレイ、メニュー又は他の種類のユーザインタフェースを介してこのオブジェクトの指示を与えられうる。例えば、道路名がユーザに対して表示され且つ道路がマップ上で強調表示されるか、又は道路名がテキスト音声デジタイザを介して出力される。
【００４０】
一実施形態において、木ノードは他の探索基準の指示を格納できる。最近接探索は、その指示を使用してｎ次元探索を実現できる。例えば、一実施形態において、探索はカテゴリによりフィルタリングされる。指示は、ノードのバウンディングボックスに含まれるか又は含まれないカテゴリの指示を含むことができる。
【００４１】
例えば、ある位置に対して最近接するレストランに関する探索では、子にレストランが存在することを示さないノードは探索木から削除される。
【００４２】
一実施形態において、ノードはＰＯＩカテゴリ除外情報を格納できる。これは、特定のカテゴリの探索を単純化し且つ高速化するためである。除外情報は、ノードに関するバウンディングボックスのオブジェクトがカテゴリに存在しないことを示すことができる。
【００４３】
図６は一例を示す。この例において、ここで示す木セグメントにおける探索は、レストランの探索であればノード６０２で停止でき、ガソリンスタンドの探索であればノード６０４で停止できる。除外情報等の他の探索基準の指示は、ノード木の作成時に実現されうる。
【００４４】
コンピュータ技術者には明らかとなるように、一実施形態は、本開示の教示に従ってプログラムされた従来の汎用又は専用デジタルコンピュータ又はマイクロプロセッサを使用して実現されてもよい。ソフトウェア技術者には明らかとなるように、適切なソフトウェアコーディングは、本開示の教示に基づいて熟練したプログラマにより容易に準備される。本発明は、当業者には容易に明らかとなるように、集積回路を準備することにより又は従来のコンポーネント回路の適切なネットワークを相互接続することにより実現されてもよい。
【００４５】
一実施形態は、本明細書で提示される任意の機能を実行するようにコンピュータをプログラムするために使用される命令を格納した記憶媒体であるコンピュータプログラム製品を含む。記憶媒体は、フロッピー（登録商標）ディスク、光ディスク、ＤＶＤ、ＣＤ−ＲＯＭ、マイクロドライブ、並びにコンピュータ可読媒体の任意の１つに格納された命令及び／又はデータを格納するのに適した媒体又はデバイスの光磁気ディスク、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、ＤＲＡＭ、フラッシュメモリを含む任意の種類のディスクを含むことができるが、それらに限定されない。本発明は、汎用／専用コンピュータ又はマイクロプロセッサのハードウェアを制御するためのソフトウェア及びコンピュータ又はマイクロプロセッサが人間のユーザ又は本発明の結果を利用する他の機構と対話することを可能にするためのソフトウェアを含む。そのようなソフトウェアは、デバイスドライバ、オペレーティングシステム、実行環境／コンテナ及びユーザアプリケーションを含んでもよいが、それらに限定されない。
【００４６】
本発明の好適な実施形態の上記説明は、例示及び説明の目的で提供された。本発明を網羅する意図はなく、あるいは本発明を開示された厳密な形式に限定する意図はない。多くの変更及び変形が当業者には明らかとなるだろう。例えば、開示される本発明の実施形態において実行されるステップは別の順序で実行でき、特定のステップは省略でき、また追加のステップが追加できる。実施形態は、本発明の原理及びその実際的な応用例を最適に説明し、それにより他の当業者が特定の使用に適すると考えられる種々の変更を伴う種々の実施形態に対して本発明を理解できるように選択及び説明される。本発明の範囲は、請求の範囲及びそれらの等価物により規定されることが意図される。
【技術分野】
【０００１】
本願は、以下の同時継続の出願：２００６年６月３０日出願の、Tsia Kuznetsov等による「可変圧縮による適応索引」という名称の米国仮出願番号６０／８０６，３６６（Attorney Docket No. TELA-07780US0）；２００６年６月３０日出願の、Tsia Kuznetsov等による「可変圧縮による適応索引における最近傍検索」という名称の米国仮出願番号６０／８０６，３６７（Attorney Docket No. TELA-07781US0）；２００７年６月２８日出願の、Tsia Kuznetsov等による「可変圧縮による適応索引」という名称の米国特許出願番号１１／７７０，０５８（Attorney Docket No. TELA-07780US1）；及び、２００７年６月２８日出願の、Tsia Kuznetsov等による「可変圧縮による適応索引における最近傍検索」という名称の米国特許出願番号１１／７７０，４２６（Attorney Docket No. TELA-07781US1）、の優先権を主張するものであり、それらの内容は、本願に合体されるものである。
【背景技術】
【０００２】
多くのアプリケーションは、ユーザに対して空間探索サービスを提供するために、格納された空間データを使用できる。アプリケーションは、移動マッピングシステム又は固定マッピングシステムを含むことができる。移動マッピングシステム又は固定マッピングシステムは、マップレンダリング、空間オブジェクト探索、経路探索、方向及び位置決めを含むことができる。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
多くの場合、ユーザは、所定の座標系においてオブジェクトの場所を特定し、そのオブジェクトに関するより多くの情報の取得を要求する。多くのオブジェクトを含む複雑なデータベースにおいて、入力位置に最近接するオブジェクトを迅速に見つけることが問題となる場合がある。特に、システムがモバイルナビゲーション装置のようにメモリを制約される場合に問題となる。
【図面の簡単な説明】
【０００４】
【図１】本発明の探索を使用するマップに基づくシステムを示す図である。
【図２Ａ】本発明の一実施形態の木の構成を示す図である。
【図２Ｂ】本発明の一実施形態の木の構成を示す図である。
【図２Ｃ】本発明の一実施形態の木の構成を示す図である。
【図２Ｄ】本発明の一実施形態の木の構成を示す図である。
【図２Ｅ】本発明の一実施形態の木の構成を示す図である。
【図３】本発明の一実施形態の探索方法を示すフローチャートである。
【図４Ａ】ノードに対するバウンディングボックスの一例を示す。
【図４Ｂ】ノードに対するバウンディングボックスの一例を示す。
【図５Ａ】一実施形態の好適な探索を示す図である。
【図５Ｂ】一実施形態の好適な探索を示す図である。
【図５Ｃ】一実施形態の好適な探索を示す図である。
【図５Ｄ】一実施形態の好適な探索を示す図である。
【図５Ｅ】一実施形態の好適な探索を示す図である。
【図５Ｆ】一実施形態の好適な探索を示す図である。
【図６】ノードが除外情報等の他の探索基準の指示を含む一例を示す図である。
【発明を実施するための形態】
【０００５】
本発明の一実施形態は、最近接オブジェクトに関する木１０２のノードを探索する探索システムを含むコンピュータにより実現される方法である。木のノード各々が空間座標キーを有するオブジェクトの部分集合を囲んでいるバウンディングボックス（bounding box）に対応するように、木は、それらオブジェクトの集合に対して構成される。探索により、ある位置に対する最近接オブジェクトが見つけられる。
【０００６】
一実施形態において、根の下の木ノードのバウンディングボックスは、オブジェクトが存在する領域のみを範囲に含む。これにより、オブジェクトの格納及び潜在的な最近接オブジェクトの検索が最適化される。同様に、一実施形態において、子ノードのバウンディングボックスは、オブジェクトが存在する領域のみを範囲に含む。根ノードのバウンディングボックスは、関連するオブジェクトを有さないいくつかの領域を含まないようなバウンディングボックスである。
【０００７】
一実施形態において、緯度及び経度の座標が使用される。例えば、緯度及び経度の座標の数字は、以下に説明するように文字列キーにインタレース（interlace）される。
【０００８】
符号化オブジェクトキーの精度は、根から葉までのパス上のノード毎に向上する。関連するバウンディングボックスの範囲は、根から葉に向けて減少する。範囲は、座標キーシステムに固有である。例えば、範囲は、所定の方向に対するキーの最高精度における距離の１つの単位である。以下に説明するインタレースされた座標系の一例は、子ノード毎に１／１０に減少するいずれかの座標方向のバウンディングボックスの範囲を有する。
【０００９】
別の実施形態において、格納された範囲値が使用される。
【００１０】
一実施形態において、葉ノードは、複数のオブジェクトを指し示すことができる。木は、所定の基準に基づいて葉のオブジェクト数を最大限にする傾向がある葉ノードを与えるように構成される。一実施形態において、指定される枝刈り基準は、各木ノードが少なくとも子孫のオブジェクトであり、そうでない場合には、枝は枝刈りされ、オブジェクトは葉ノードに割り当てられる。
【００１１】
最大の探索半径値は、探索を制限するように維持される。探索半径値は、バウンディングボックス情報に基づいて減少される。ある位置から各ノードまでの最短距離及び最長距離は、ノードのバウンディングボックスを用いて計算される。ノードは、最大探索半径値に基づいて考慮の対象から外される。一例において、バウンディングボックスが最大探索半径より長いある位置からの最短距離を有するノードは無視される。
【００１２】
ノードに対するオブジェクトキー情報は、バウンディングボックスの角の位置及び範囲を符号化するのに十分である。一例において、座標情報がインタレースされる場合、ノードのバウンディングボックスの左下の角等の角は、デインタレースされた座標により決められ、各座標に対するバウンディングボックスの範囲は、座標の構成から決められる。
【００１３】
コンピュータにより実現される方法は、マップシステム１００又はナビゲーションシステムの一部である。オブジェクトは、道路区間、地点情報（ＰＯＩ）又は他の空間オブジェクト等の空間オブジェクトを含むことができる。空間オブジェクトは、１つ以上の座標により示される。
【００１４】
本発明の一実施形態は、アプリケーション１０４を具備するシステム１００である。アプリケーション１０４は、位置を取得するためのインタフェースを含むことができる。アプリケーションは、最近接オブジェクトに対する木のノードを探索する空間探索を使用できる。木のノードがオブジェクトの部分集合を囲んでいるバウンディングボックスに対応するように、木１０２は、座標により符号化された空間キーに基づいてもよい。探索により、ある位置に対する最近接オブジェクトが見つけられる。
【００１５】
アプリケーション１０４は、マップディスプレイ１０２を有することができる。アプリケーションは、ユーザに対して情報を伝えるために、聴覚プレゼンテーション等の非視覚的な手段を使用できる。
【００１６】
オブジェクト座標が木を作成するのに使用される方法の一例を以下のように与える。
【００１７】
緯度及び経度からキーを作成するために以下を行なう。
１．１０進数を地球の円周を表す所定のビット数の整数座標に変換する。
２．座標を正の空間に移動する。
３．各整数を文字列に変更する。
４．長さを等しくするために各文字列の先頭に「０」を付加する。
５．緯度及び経度の１０進数字をインタレースしてキー文字列とすることにより探索キーを作成する。
緯度の文字列が「００１２３」を含むと仮定する。
経度の文字列が「０００７８」を含むと仮定する。
結果として得られるインタレースされた文字列キーは「００００１０２７３８」となる。
【００１８】
この空間キーは、座標索引ａを構築するのに用いられる。キーの精度は、根から葉までのパス上のノード毎に向上する。
【００１９】
格納及び検索の最適化のために、索引の葉ノードキーは、親のキーと等しくなるように切り捨てられ、葉はマージさせられる。これにより、探索は、オブジェクトストアに対するオブジェクト参照に従う必要がある。なお、オブジェクトストアは、最近接オブジェクトの選択時の最終ステップである。
【００２０】
最近接探索は、木１０２上で実現される。探索パス上の各ノードのバウンディングボックスは、ノードの空間キーから復元されうる。空間探索に関するノードのバウンディングボックスを検索するために以下を行なう。
各木ノードは、キーのプレフィックスを格納でき、キープレイフィックスは根において最低の精度を有し、葉において最高の精度を有する。可変圧縮による適応索引において、ノード毎の完全なキーが根からノードまでの全てのキープレフィックスの連結となるように、それらのキープレフィックスは減少されうる。この連結により、そのノードに対する完全なキーが得られ、ノードの各キーは、左下の角及びノードのバウンディングボックスの範囲を符号化できる。
【００２１】
一実施形態において、ノードの左下の角及びバウンディングボックスの空間範囲を算出するために以下を行なう。
ノードの空間キーをデインタレースし、結果として得られる緯度及び経度の文字列に欠落している「０」を付加して左下の角を表す全長（この例においては５）とする。
ａ）一例において、ノードキーが「００００１０２」であると仮定すると、緯度は「００１２０」である。ここで付加された「０」は、ノードの子の緯度が１２０〜１２９であるため、ノードの緯度の範囲は１０の１乗であることを意味する。経度は「０００００」である。ここで付加された「００」は、ノードの子の経度が０〜９９であるため、ノードの経度の範囲は１０の２乗であることを意味する。
ｂ）別の例において、ノードキーが「００００１０２７」であると仮定すると、緯度は「００１２０」であり、ノードの子の緯度は１２０〜１２９であるため、ノードの緯度の範囲は１０の１乗である。経度は「０００７０」であり、ノードの子の経度は７０〜７９であるため、ノードの経度の範囲は１０の１乗である。
【００２２】
ノードの左下の角の算出を完了するために、文字列の緯度及び経度を整数座標に変換し、整数を元の座標空間に戻す。
【００２３】
ノードのバウンディングボックスは、空間範囲及び左下の角の整数の緯度及び経度の座標から算出される。
【００２４】
図２Ａ〜図２Ｅは、木の構成の一例を示す。
【００２５】
図２Ａは、Ｘで示す道路区間点を含む好適なマップを示す。図２Ｂに示すように、参照点座標の緯度及び経度は、インタレースされてキーになる。キーは、図２Ｃに示すようにノード木を構成するために使用されうる。各ノードにおけるキーの一部は、上述のようにノードに対するバウンディングボックスを復号化するために使用されうる。図２Ｃの例において、ノード２１０（００００１０２７３８）は図２Ａのバウンディングボックス２０２に対応する。ノード２１２（００００１０２７３）は図２Ａのバウンディングボックス２０４に対応する。ノード２１４（００００１０２７）は図２Ａのバウンディングボックス２０６に対応する。
【００２６】
葉ノード２１０は、オブジェクトストア２１６のオブジェクトを指し示すことができるか、あるいはオブジェクトを直接格納できる。オブジェクトは、名前及び他の情報、並びに１つ以上の座標を含むことができる。一例において、オブジェクト座標は、道路区間の中点又は終点であってもよい。ポインタは、バウンディングボックス２０２において特定の緯度及び経度の座標を有するオブジェクトの場所を特定するために使用される。
【００２７】
２００６年６月３０日に出願され且つ本明細書に参考として取り入れられている米国特許出願第６０／８０６，３６６号公報（Attorney Docket No. TELA-07780US0に対応する）「ADAPTIVE INDEX WITH VARIABLE COMPRESSION」において説明されるように、葉ノードはオブジェクトに対する複数の参照を含むことができる。図２Ｄの例において、葉ノードはバウンディングボックス２０４の２つのオブジェクトを指し示す。図２Ｅの例において、葉ノードはバウンディングボックス２０６の２６個のオブジェクトを指し示す。
【００２８】
ノード木に対する好適な探索について以下に説明する。
【００２９】
適応圧縮された索引に対する空間探索
座標の緯度、経度を有する点Ｐを仮定する。
根ノードｒを読み出し、そのバウンディングボックスを復元する。
Ｐから根の最も遠い場所までの最大半径ｍａｘＲを算出する。
ＲｅｔｕｒｎＶａｌｕｅは組（オブジェクト（object），距離（distance））であってもよい。これは以下の手順により算出されうる。
（ｏｂｊｅｃｔ，ｄｉｓｔａｎｃｅＴｏＯｂｊｅｃｔ）＝ＦｉｎｄＮｅａｒｅｓｔＯｂｊｅｃｔ（）（木ノード（tree-node），ｍａｘＲ）
ノード（node）が葉（leaf）である場合；
最近接オブジェクト及びｄｉｓｔａｎｃｅＴｏＯｂｊｅｃｔを取得する；
ｄｉｓｔａｎｃｅＴｏＯｂｊｅｃｔ＜ｍａｘＲの場合、更新する：
ｍａｘＲ＝ｄｉｓｔａｎｃｅＴｏＯｂｊｅｃｔ
ｒｅｔｕｒｎ（ｏｂｊｅｃｔ，ｄｉｓｔａｎｃｅＴｏＯｂｊｅｃｔ）
子ノード（child nodes）を読み出す
各子ノードに対してＰまでの距離、ｍｉｎＤ及びｍａｘＤを算出する
ｍｉｎＤ＞ｍａｘＲを有する子を考慮の対象から外す
ルートｒの下、以下の子ノードが最初に考慮される
（ａ，ｍｉｎＤ，ｍａｘＤ）
（ｆ，ｍｉｎＤ，ｍａｘＤ）
（ｈ，ｍｉｎＤ，ｍａｘＤ）
ｍａｘＲを子のｍａｘＤの最小値まで減少する
ｍｉｎＤで子アレイをソートする
子アレイが空でなく且つｍｉｎ（子のｍｉｎＤ）＜ｍａｘＲの場合に以下を行なう
最小のｍｉｎＤを有する子ノード（child-node）を選択する；
（ｏｂｊｅｃｔ，ｄｉｓｔａｎｃｅＴｏＯｂｊｅｃｔ）＝ＦｉｎｄＮｅａｒｅｓｔＯｂｊｅｃｔ（子ノード，ｍａｘＲ）
Ｒｅｔｕｒｎ（ｏｂｊｅｃｔ，ｄｉｓｔａｎｃｅＴｏＯｂｊｅｃｔ）
【００３０】
図３は、好適な探索を示すフローチャートの一例を示す。
【００３１】
図４Ａは、図４Ｂの木に対するバウンディングボックスを示す。図４Ａは、子ノードに対するバウンディングボックスが親ノード内にネストされる方法を示す。バウンディングボックスの大きさは、縮尺したものではない。
【００３２】
図５Ａ〜図５Ｆは、好適な探索を示す。点Ｐは、カーソル選択、タッチスクリーン選択又は別の入力手段等のユーザ入力から決められうる。点Ｐは、全地球測位システム（ＧＰＳ）又は他の位置決めシステムから取得されうる。図５Ａ〜図５Ｆに示すステップは、点Ｐに対する最近接オブジェクトを見つけるために木構造を探索する方法を示す。
【００３３】
図５Ａ（図３のステップ３０２に対応する）において、ｍａｘＲは点Ｐから根ノードのバウンディングボックスの最も遠い角までの距離となるように決められる。根（ノードｒ）が葉ノードでないため、図３のステップ３０４において、ノードの子ノード（ノードａ、ｆ、ｈ）が取得される。
【００３４】
子ノードの各バウンディングボックスに関する最長距離及び最短距離が取得されうる（ステップ３０６）。図５Ａに示すように、最長距離は点Ｐからバウンディングボックスの最も遠い角までの線の距離に対応してもよい。最短距離は、可能であれば、点Ｐから緯度又は経度の値に沿うバウンディングボックスの辺までの直線であってもよいし、また、そのような緯度又は経度に沿う線が存在しなければ、バウンディングボックスの最近接の角までの線であってもよい。
【００３５】
ｍａｘＲは、子ノードの最短のｍａｘＤが現時点のｍａｘＲより小さければ、そのｍａｘＤに設定される（図３のステップ３０８）。ｍｉｎＤがｍａｘＲより大きい子ノードは削除される。図５Ｂにおいて、ノードｈ及びその子は無視されうる。他のノードは、最近接オブジェクトを含む可能性が最も高いノードが最初に調査されるように、ｍｉｎＤの値の昇順のリストに配置される（図３のステップ３１０）。従って、この時点におけるリストは｛ａ，ｆ｝である。
【００３６】
図５Ｃにおいて、ノードａの子ノードがチェックされる。図５Ｄにおいて、ｍａｘＲはバウンディングボックスｂのｍａｘＤに設定される。この時点におけるリストは｛ｂ，ｆ｝である。
【００３７】
図５Ｅにおいて、ノードｂの子がチェックされ、リストは｛ｅ，ｆ｝になる。
【００３８】
図５Ｆにおいて、ノードｅが葉ノードであるため、ノードｅのオブジェクトは、点Ｐに対する最近接オブジェクトを見つけるためにチェックされる。ノードｅは、オブジェクトストアのオブジェクトに対するポインタを複数有することができる。それらは、ノードｅにおいて最近接オブジェクトを見つけるためにチェックされうる。これは、図３のステップ３２０に対応する。オブジェクトまでの距離が現時点のｍａｘＲより小さいため、ｍａｘＲはオブジェクトまでの距離に設定される。この時点におけるリストは｛ｆ｝である。
【００３９】
その後、ノードｆがチェックされ、子ノードｇを有することが判明する。ノードｇはｍｉｎＤ＞ｍａｘＲを有するため、この方法は終了し、ノードｅにおいて見つけられたオブジェクトのうちの最近接オブジェクトがその位置に対する最近接オブジェクトとなるように決められる。ユーザは、マップディスプレイ、メニュー又は他の種類のユーザインタフェースを介してこのオブジェクトの指示を与えられうる。例えば、道路名がユーザに対して表示され且つ道路がマップ上で強調表示されるか、又は道路名がテキスト音声デジタイザを介して出力される。
【００４０】
一実施形態において、木ノードは他の探索基準の指示を格納できる。最近接探索は、その指示を使用してｎ次元探索を実現できる。例えば、一実施形態において、探索はカテゴリによりフィルタリングされる。指示は、ノードのバウンディングボックスに含まれるか又は含まれないカテゴリの指示を含むことができる。
【００４１】
例えば、ある位置に対して最近接するレストランに関する探索では、子にレストランが存在することを示さないノードは探索木から削除される。
【００４２】
一実施形態において、ノードはＰＯＩカテゴリ除外情報を格納できる。これは、特定のカテゴリの探索を単純化し且つ高速化するためである。除外情報は、ノードに関するバウンディングボックスのオブジェクトがカテゴリに存在しないことを示すことができる。
【００４３】
図６は一例を示す。この例において、ここで示す木セグメントにおける探索は、レストランの探索であればノード６０２で停止でき、ガソリンスタンドの探索であればノード６０４で停止できる。除外情報等の他の探索基準の指示は、ノード木の作成時に実現されうる。
【００４４】
コンピュータ技術者には明らかとなるように、一実施形態は、本開示の教示に従ってプログラムされた従来の汎用又は専用デジタルコンピュータ又はマイクロプロセッサを使用して実現されてもよい。ソフトウェア技術者には明らかとなるように、適切なソフトウェアコーディングは、本開示の教示に基づいて熟練したプログラマにより容易に準備される。本発明は、当業者には容易に明らかとなるように、集積回路を準備することにより又は従来のコンポーネント回路の適切なネットワークを相互接続することにより実現されてもよい。
【００４５】
一実施形態は、本明細書で提示される任意の機能を実行するようにコンピュータをプログラムするために使用される命令を格納した記憶媒体であるコンピュータプログラム製品を含む。記憶媒体は、フロッピー（登録商標）ディスク、光ディスク、ＤＶＤ、ＣＤ−ＲＯＭ、マイクロドライブ、並びにコンピュータ可読媒体の任意の１つに格納された命令及び／又はデータを格納するのに適した媒体又はデバイスの光磁気ディスク、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、ＤＲＡＭ、フラッシュメモリを含む任意の種類のディスクを含むことができるが、それらに限定されない。本発明は、汎用／専用コンピュータ又はマイクロプロセッサのハードウェアを制御するためのソフトウェア及びコンピュータ又はマイクロプロセッサが人間のユーザ又は本発明の結果を利用する他の機構と対話することを可能にするためのソフトウェアを含む。そのようなソフトウェアは、デバイスドライバ、オペレーティングシステム、実行環境／コンテナ及びユーザアプリケーションを含んでもよいが、それらに限定されない。
【００４６】
本発明の好適な実施形態の上記説明は、例示及び説明の目的で提供された。本発明を網羅する意図はなく、あるいは本発明を開示された厳密な形式に限定する意図はない。多くの変更及び変形が当業者には明らかとなるだろう。例えば、開示される本発明の実施形態において実行されるステップは別の順序で実行でき、特定のステップは省略でき、また追加のステップが追加できる。実施形態は、本発明の原理及びその実際的な応用例を最適に説明し、それにより他の当業者が特定の使用に適すると考えられる種々の変更を伴う種々の実施形態に対して本発明を理解できるように選択及び説明される。本発明の範囲は、請求の範囲及びそれらの等価物により規定されることが意図される。
【特許請求の範囲】
【請求項１】
コンピュータにより実現される方法であって、
最近接オブジェクトに関する木のノードを探索する探索システムを含み、
前記木は、前記木のノードが前記オブジェクトの部分集合を囲んでいるバウンディングボックスに対応するように、座標を符号化するオブジェクトキーを用いて構築され、
前記探索アルゴリズムは、ある位置に対する前記再近接オブジェクトを見つけ、
根より下の前記木ノードの前記バウンディングボックスは、オブジェクトが存在する領域のみを範囲に含み、
前記探索は、特定のバウンディングボックスを有するノードを考慮の対象から除外する
ことを特徴とするコンピュータにより実現される方法。
【請求項２】
符号化オブジェクトキーの精度は、前記根から葉までのパス上のノード毎に向上する
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項３】
前記座標は、緯度及び経度を含む
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項４】
ノードに関する前記オブジェクトキー情報は、
角の位置及び範囲を用いることにより該ノードのバウンディングボックスを符号化するのに十分である
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項５】
前記座標情報は、インタレースされる
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項６】
前記ノードのバウンディングボックスの左下の角は、デインタレースされた座標により決められ、
各座標に対する前記バウンディングボックスの範囲は、前記座標の構成から決められる
ことを特徴とする請求項５記載のコンピュータにより実現される方法。
【請求項７】
ノードは、他の探索基準の指示を格納する
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項８】
前記他の探索基準の指示は、
ノードのバウンディングボックスに含まれないオブジェクトのカテゴリの指示を含む
ことを特徴とする請求項７記載のコンピュータにより実現される方法。
【請求項９】
前記他の探索基準の指示は、
ノードのバウンディングボックスに含まれるオブジェクトのカテゴリの指示を含む
ことを特徴とする請求項８記載のコンピュータにより実現される方法。
【請求項１０】
殆どの葉ノードは、複数のオブジェクトを指し示す
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項１１】
前記木の構成は、
所定の基準に基づいて前記葉ノードと関連付けられるオブジェクト数を最大限にする傾向がある
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項１２】
前記方法は、
最大探索半径値を維持し、前記最大探索半径に基づいていくつかのノードを考慮の対象から外す
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項１３】
前記方法は、
ノードに対する位置までの最短距離を維持し、前記最短距離を用いて最短距離値が前記最大探索半径より大きいノードを考慮の対象から外す
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項１４】
ある位置までの前記ノードの最短距離及び最長距離は、前記ノードのバウンディングボックスを用いて計算される
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項１５】
前記オブジェクトは、空間オブジェクトを含む
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項１６】
前記空間オブジェクトは、マップ幾何学的特徴を含む
ことを特徴とする請求項１５記載のコンピュータにより実現される方法。
【請求項１７】
前記空間オブジェクトは、地点情報を含む
ことを特徴とする請求項１５記載のコンピュータにより実現される方法。
【請求項１８】
前記コンピュータにより実現される方法は、マッピングシステムの一部である
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項１９】
システムであって、
位置を取得するためのインターフェースを含むアプリケーションを具備し、
前記アプリケーションは、前記位置に対する最近接オブジェクトの木のノードを探索する探索システムを使用し、
前記木は、前記木のノードが所定の座標のバウンディングボックスに対応するようにインタレース座標を有する探索キーに基づいており、
前記探索は、位置に対する前記最近接オブジェクトを見つけ、
根の下の前記木ノードの前記バウンディングボックスは、オブジェクトが存在する領域のみを範囲に含み、
前記探索は、特定のバウンディングボックスを有するノードを考慮の対象から外す
ことを特徴とするシステム。
【請求項２０】
前記位置は、カーソル選択に基づいて取得される
ことを特徴とする請求項１９記載のシステム。
【請求項２１】
前記位置は、
ユーザの接触、ユーザの場所、ユーザの音声入力に基づいて取得されるか又は他のユーザインタフェース手段により取得される
ことを特徴とする請求項１９記載のシステム。
【請求項２２】
前記アプリケーションは、マップディスプレイを含む
ことを特徴とする請求項１９記載のシステム。
【請求項２３】
コンピュータにより実現されるシステムであって、
最近接オブジェクトに関する木のノードを探索する探索システムであり、
前記木は、前記木のノードがオブジェクトの部分集合を囲んでいるバウンディングボックスに対応するように、座標を符号化するオブジェクトキーを用いて構築され、
前記探索は、ある位置に対する前記最近接オブジェクトを見つけ、
前記システムは、特定のノードに対して全体の最大探索半径値及び最短距離を維持し、
前記システムは、前記最短距離を用いて、最短距離が前記最大探索半径より大きいノードを考慮の対象から外す
ことを特徴とするコンピュータにより実現されるシステム。
【請求項２４】
コンピュータにより実現される方法であって、
最近接空間オブジェクトに関する木のノードを探索する探索システムを含み、
前記木は、前記木のノードが前記オブジェクトの部分集合を囲んでいるバウンディングボックスに対応するように、座標を符号化するオブジェクトキーを用いて構成され、
前記探索アルゴリズムは、ある位置に対する前記最近接空間オブジェクトを見つけ、
前記根の下の前記木ノードの前記バウンディングボックスは、空間オブジェクトが存在する領域のみを範囲に含み、
前記方法は、最大探索半径値を維持し、前記最大探索半径に基づいていくつかのノードを考慮の対象から外し、
前記探索半径値は、バウンディングボックス情報に基づいて減少される
ことを特徴とするコンピュータにより実現される方法。
【請求項１】
コンピュータにより実現される方法であって、
最近接オブジェクトに関する木のノードを探索する探索システムを含み、
前記木は、前記木のノードが前記オブジェクトの部分集合を囲んでいるバウンディングボックスに対応するように、座標を符号化するオブジェクトキーを用いて構築され、
前記探索アルゴリズムは、ある位置に対する前記再近接オブジェクトを見つけ、
根より下の前記木ノードの前記バウンディングボックスは、オブジェクトが存在する領域のみを範囲に含み、
前記探索は、特定のバウンディングボックスを有するノードを考慮の対象から除外する
ことを特徴とするコンピュータにより実現される方法。
【請求項２】
符号化オブジェクトキーの精度は、前記根から葉までのパス上のノード毎に向上する
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項３】
前記座標は、緯度及び経度を含む
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項４】
ノードに関する前記オブジェクトキー情報は、
角の位置及び範囲を用いることにより該ノードのバウンディングボックスを符号化するのに十分である
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項５】
前記座標情報は、インタレースされる
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項６】
前記ノードのバウンディングボックスの左下の角は、デインタレースされた座標により決められ、
各座標に対する前記バウンディングボックスの範囲は、前記座標の構成から決められる
ことを特徴とする請求項５記載のコンピュータにより実現される方法。
【請求項７】
ノードは、他の探索基準の指示を格納する
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項８】
前記他の探索基準の指示は、
ノードのバウンディングボックスに含まれないオブジェクトのカテゴリの指示を含む
ことを特徴とする請求項７記載のコンピュータにより実現される方法。
【請求項９】
前記他の探索基準の指示は、
ノードのバウンディングボックスに含まれるオブジェクトのカテゴリの指示を含む
ことを特徴とする請求項８記載のコンピュータにより実現される方法。
【請求項１０】
殆どの葉ノードは、複数のオブジェクトを指し示す
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項１１】
前記木の構成は、
所定の基準に基づいて前記葉ノードと関連付けられるオブジェクト数を最大限にする傾向がある
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項１２】
前記方法は、
最大探索半径値を維持し、前記最大探索半径に基づいていくつかのノードを考慮の対象から外す
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項１３】
前記方法は、
ノードに対する位置までの最短距離を維持し、前記最短距離を用いて最短距離値が前記最大探索半径より大きいノードを考慮の対象から外す
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項１４】
ある位置までの前記ノードの最短距離及び最長距離は、前記ノードのバウンディングボックスを用いて計算される
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項１５】
前記オブジェクトは、空間オブジェクトを含む
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項１６】
前記空間オブジェクトは、マップ幾何学的特徴を含む
ことを特徴とする請求項１５記載のコンピュータにより実現される方法。
【請求項１７】
前記空間オブジェクトは、地点情報を含む
ことを特徴とする請求項１５記載のコンピュータにより実現される方法。
【請求項１８】
前記コンピュータにより実現される方法は、マッピングシステムの一部である
ことを特徴とする請求項１記載のコンピュータにより実現される方法。
【請求項１９】
システムであって、
位置を取得するためのインターフェースを含むアプリケーションを具備し、
前記アプリケーションは、前記位置に対する最近接オブジェクトの木のノードを探索する探索システムを使用し、
前記木は、前記木のノードが所定の座標のバウンディングボックスに対応するようにインタレース座標を有する探索キーに基づいており、
前記探索は、位置に対する前記最近接オブジェクトを見つけ、
根の下の前記木ノードの前記バウンディングボックスは、オブジェクトが存在する領域のみを範囲に含み、
前記探索は、特定のバウンディングボックスを有するノードを考慮の対象から外す
ことを特徴とするシステム。
【請求項２０】
前記位置は、カーソル選択に基づいて取得される
ことを特徴とする請求項１９記載のシステム。
【請求項２１】
前記位置は、
ユーザの接触、ユーザの場所、ユーザの音声入力に基づいて取得されるか又は他のユーザインタフェース手段により取得される
ことを特徴とする請求項１９記載のシステム。
【請求項２２】
前記アプリケーションは、マップディスプレイを含む
ことを特徴とする請求項１９記載のシステム。
【請求項２３】
コンピュータにより実現されるシステムであって、
最近接オブジェクトに関する木のノードを探索する探索システムであり、
前記木は、前記木のノードがオブジェクトの部分集合を囲んでいるバウンディングボックスに対応するように、座標を符号化するオブジェクトキーを用いて構築され、
前記探索は、ある位置に対する前記最近接オブジェクトを見つけ、
前記システムは、特定のノードに対して全体の最大探索半径値及び最短距離を維持し、
前記システムは、前記最短距離を用いて、最短距離が前記最大探索半径より大きいノードを考慮の対象から外す
ことを特徴とするコンピュータにより実現されるシステム。
【請求項２４】
コンピュータにより実現される方法であって、
最近接空間オブジェクトに関する木のノードを探索する探索システムを含み、
前記木は、前記木のノードが前記オブジェクトの部分集合を囲んでいるバウンディングボックスに対応するように、座標を符号化するオブジェクトキーを用いて構成され、
前記探索アルゴリズムは、ある位置に対する前記最近接空間オブジェクトを見つけ、
前記根の下の前記木ノードの前記バウンディングボックスは、空間オブジェクトが存在する領域のみを範囲に含み、
前記方法は、最大探索半径値を維持し、前記最大探索半径に基づいていくつかのノードを考慮の対象から外し、
前記探索半径値は、バウンディングボックス情報に基づいて減少される
ことを特徴とするコンピュータにより実現される方法。
【図１】
【図２Ａ】
【図２Ｂ】
【図２Ｃ】
【図２Ｄ】
【図２Ｅ】
【図３】
【図４Ａ】
【図４Ｂ】
【図５Ａ】
【図５Ｂ】
【図５Ｃ】
【図５Ｄ】
【図５Ｅ】
【図５Ｆ】
【図６】
【図２Ａ】
【図２Ｂ】
【図２Ｃ】
【図２Ｄ】
【図２Ｅ】
【図３】
【図４Ａ】
【図４Ｂ】
【図５Ａ】
【図５Ｂ】
【図５Ｃ】
【図５Ｄ】
【図５Ｅ】
【図５Ｆ】
【図６】
【公表番号】特表２００９−５４３２２５（Ｐ２００９−５４３２２５Ａ）
【公表日】平成２１年１２月３日（２００９．１２．３）
【国際特許分類】
【出願番号】特願２００９−５１８５６１（Ｐ２００９−５１８５６１）
【出願日】平成１９年６月２８日（２００７．６．２８）
【国際出願番号】ＰＣＴ／ＵＳ２００７／０７２４１２
【国際公開番号】ＷＯ２００８／００５８０９
【国際公開日】平成２０年１月１０日（２００８．１．１０）
【出願人】（５０７３８８８８９）テレ アトラス ノース アメリカ インコーポレイテッド (23)
【Ｆターム（参考）】
【公表日】平成２１年１２月３日（２００９．１２．３）
【国際特許分類】
【出願日】平成１９年６月２８日（２００７．６．２８）
【国際出願番号】ＰＣＴ／ＵＳ２００７／０７２４１２
【国際公開番号】ＷＯ２００８／００５８０９
【国際公開日】平成２０年１月１０日（２００８．１．１０）
【出願人】（５０７３８８８８９）テレ アトラス ノース アメリカ インコーポレイテッド (23)
【Ｆターム（参考）】
[ Back to top ]