目的地を決定するためのアドレスポイントを持つ地図データべース
１つまたは複数のストリート名をそれぞれが持つ複数のストリートセグメント、ストリートセグメントに沿って特定の位置を表すゼロ以上の形状点、および家屋番号またはアドレスレンジに関連するゼロ以上のアドレスポイントのインデックスを有する地図データベースを提供することで、所望の場所の位置情報を利用者に与える。利用者は、所望の場所のストリートアドレスをデバイス・アプリケーション・ソフトウェアに入力し、それにより、所望の場所がアドレスポイントであれば、その位置が利用者に戻される。所望の場所がアドレスポイントでなければ、取り囲む２つのもっとも近い住所など、小さい数字の住所と大きい数字の住所を、複数のアドレスポイントから、あるいは、１つのアドレスポイントとストリートセグメントの端点から見出すことにより、その位置を補間する。この補間される位置は、このストリートセグメントの形状点にしたがって区分的線形補間により、小さい数字の住所と大きい数字の住所との間に決められることになり、次に、その位置が、利用者に戻される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特定の住所の位置を決定する情報を持つ地図データベースに関し、さらに具体的に言えば、利用者が要望する場所の所在地または位置を正確に決定するのに用いられるデータ構造を持つ地図データベースに関する。
【０００２】
（優先権の主張）
２００６年２月８日に出願されたＭｉｃｈｅｌ Ｇｅｉｌｉｃｈ氏による「Ａ ＭＡＰ ＤＡＴＡＢＡＳＥ ＨＡＶＩＮＧ ＡＤＤＲＥＳＳ ＰＯＩＮＴＳ ＦＯＲ ＤＥＴＥＲＭＩＮＩＮＧ ＤＥＳＴＩＮＡＴＩＯＮＳ（目的地を決定するアドレスポイントを持つ地図データべース）」と称する米国特許出願第１１／３５１，１５６号（Ａｔｔｏｒｎｅｙ Ｄｏｃｋｅｔ Ｎｏ．ＴＥＬＡ−０７７７５ＵＳ０）。
【背景技術】
【０００３】
近年、消費者は、デジタル地図上で場所を捜し出すことができるように、様々な装置およびシステムを持っている。「ｐｌａｃｅ（場所）」という語は、本発明の説明の全体を通して使用されている一般的な用語である。「ｐｌａｃｅ（場所）」という語は、ストリートアドレス（street address）、店舗やランドマークなど、ストリートアドレスに位置づけられるビル、および、ショッピングモールやビジネスパークなど、いくつかのストリートアドレスに位置づけられる施設を含む。消費者に使用される様々な装置およびシステムは、運転者がストリートや道路にナビゲートできるようにする車載ナビゲーション・システム、携帯情報端末（「ＰＤＡ」）、パーソナル・ナビゲーション装置、同一機能を果たせる携帯電話などのハンドヘルド装置(hand-held device)、および、所望の場所を示す地図を利用者に作成させるインターネット・アプリケーションの形式を取っている。上記および他のタイプの装置およびシステムのすべてに共通する点は、地理的フィーチャー（geographic features）の地図データベースと、利用者入力に応答して、この地図データベースにアクセスし、処理するソフトウェアである。要するに、これらの装置およびシステムのすべてにおいて、利用者は所望の場所を入力できる。また、戻される結果は、その場所の位置となろう。一般に、利用者は、レストランなどの業務の名称、あるいは、Ｇｏｌｄｅｎ Ｇａｔｅ Ｂｒｉｄｇｅなどの目的地ランドマーク、あるいはストリートアドレスを入力し、次に、この要求された場所の位置が戻されることになる。この位置を地図ディスプレイ上に示すか、または、この位置を使用して、この位置に向かう運転方向を計算し、表示するか、あるいは、他のやり方でこの位置を使用することがある。
【０００４】
地図データベースは、ストリート上の家屋およびビルの位置に関する情報を提供する。地図データベース・ディベロッパー（map database developer）は、地図データベース中の所与のストリートまたはストリートセグメント（ストリート区分、street segment）に関して、所与のアドレスレンジ（住所範囲、住所の連なり、address range）にわたるアドレスデータ（address data）を含む。このアドレスレンジは、開始する家屋番号と位置、終了する家屋番号と位置、および、随意にいくつかの中間の家屋番号と位置とともに、このストリートセグメントの所与の側に対応する一群のビル番号または家屋番号を含むことになる。
【０００５】
利用者の入力に応答して所望の場所を捜し出すために、この装置またはシステムのソフトウェアは、まず最初に、その場所のストリートアドレスを決定し、次に、所望の住所を含むアドレスレンジを持つストリートセグメントを捜し出し、次に、そのアドレスレンジ内で補間を実行して、その場所の位置を推定することになる。しかしながら、補間アルゴリズムは、所与のストリート・ブロック（street block）に沿って、実世界におけるビル番号または家屋番号の割当ての変更をまったく考慮に入れてないこともある。例えば、このストリート・ブロックの始まりまたは中央に公園があるかもしれないか、ブロックに沿って、ばらばらに家屋が割り当てられるかもしれないか、あるいは、アドレスレンジの端にあるビルが、正確にストリート交差点に位置づけられていないかもしれない。
【０００６】
理想的には、アドレスレンジの終わりにあるビル番号または家屋番号は、現実のビル住所を表しており、中間の家屋番号を補間する際の誤差を最小限に抑えている。しかしながら、このことは、常に事実であるとは限らない。地図データベースのなかには、端点（end point）にある潜在的なビル番号または家屋番号を用いて、アドレスレンジがモデル化されるものもあり、これは、中間のビル番号または家屋番号を正確に補間するという問題を悪化させる。例えば、地図データベースは、米国郵政公社で割り当てられる潜在的なビル番号または家屋番号を用いて、アドレスレンジをモデル化することがある。一例として、ストリートが１００の住所番号（address number）から成るブロックに分けられているＮｅｗ Ｙｏｒｋ Ｃｉｔｙの商業地区では、ブロック側に沿ったビル番号または家屋番号は、全アドレスレンジをめったに表さず、また、この全アドレスレンジをいずれか一方の端にて完結するとまではいかないことが多い。
【０００７】
上記の方法を使用する補間は、このストリートセグメントの長さの５０パーセント以上の誤差を持つことがある。これらの補間誤差は、何十メートルもしくは何百メートルの誤差になることもあり、それは、たぶん、その補間された位置にナビゲートしている利用者には、所望の場所を利用者の視野範囲外におくであろう。
【０００８】
補間は、上記の方法でサポートされるもっとも正確な位置を与えるとはいえ、高いサブブロック（sub-block）精度は保証しない。それでも、利用者を、ストリート・ブロック内の適正な位置に正確に導くためには、高いサブブロック精度が必要となる。
【発明の開示】
【課題を解決するための手段】
【０００９】
一面では、本発明は、少なくとも１つのストリートセグメントを含む、記憶媒体上に格納できる地図データベースである。ストリートセグメントは、そのストリートセグメント上で家屋番号またはビル番号に対応するゼロ以上のアドレスレンジを持つことがある。ストリートセグメントはまた、そのストリートセグメントのアドレスレンジ内のビル番号、家屋番号、またはアドレスレンジの位置にそれぞれが対応するゼロ以上のアドレスポイントも持つことがある。
【００１０】
他の面では、本発明は、実際のストリートに対応するストリートセグメントをそれぞれが識別する少なくとも１つの第１のデータエントリ(data entry)を持つ地図データベースから、住所情報および対応する位置のインデックス（index)を含む記憶媒体上に格納できる地図データベースを含み、また、第１のデータエントリごとに、このインデックスは、上記ストリートセグメントのどちら側にも、そのストリートセグメント内のビル番号、家屋番号、またはアドレスレンジの位置に対応するゼロ又はそれ以上のアドレスポイント・エントリ（address point entries)を持っている。
【００１１】
さらに他の面では、本発明は、ゼロ又はそれ以上のアドレスレンジと、そのアドレスレンジ内にあるゼロ又はそれ以上のアドレスポイントとをそれぞれが持つ少なくとも１つのストリートセグメントを有する地図データベース、および、利用者による所望の場所の入力に応答して、そのアドレスレンジ（得られる場合）にあるアドレスポイント（得られる場合）を取得するアプリケーション・プログラムを含む、所望の場所に対応する情報を利用者に提供するシステムを含む。所望の場所に対応するアドレスポイントが得られない場合には、上記アプリケーション・プログラムは、得られるアドレスポイント間、あるいは、そのアドレスレンジ（得られる場合）のアドレスポイントと端点との間を補間して、所望のビル番号の近似位置を決定することになる。アドレスポイントがまったく得られない場合には、上記アプリケーション・プログラムは、そのアドレスレンジ（得られる場合）の端点間を補間して、所望のビル番号の近似位置を決定することになる。
【００１２】
さらに他の面では、本発明は、利用者によるストリート名の入力に応答して、このストリート名に関連するストリートセグメントのすべてのアドレスポイントを取得することで、所望の場所の位置情報を利用者に提供する方法である。次に、この方法は、利用者が入力したビル住所番号に応答して、ビル住所番号用に取得されたアドレスポイントを調べる。これらの取得されたアドレスポイントのどれかが、上記の入力されたビル住所番号に対応する場合には、その対応する取得されたアドレスポイントを使用して、上記の入力されたビル住所番号の位置を利用者に戻す。取得されたアドレスポイントが、上記の入力されたビル住所番号にまったく対応しない場合には、取り囲む（bracketing）２つのもっとも近いアドレスポイント、あるいは、１つのアドレスポイントとストリートセグメントの端点を使用して補間し、その近似位置を利用者に戻す。
【発明を実施するための最良の形態】
【００１３】
図１は、所与の都市の仮想Ｍａｉｎ Ｓｔｒｅｅｔ（ＭＳ）の１ブロックの一側のストリートセグメントの略図と、そのストリートセグメントに沿って、形状点（shape point）ＳＰと称される特定の地点間に直線を引いて形成されるこのストリートセグメントの区分的線形表現である。この例では、Ｍａｉｎ Ｓｔｒｅｅｔ（ＭＳ）のこのストリートセグメントは、２〜９８というアドレスレンジ内の家屋番号を持つ住宅街である。この住宅街の曲線は、Ｍａｉｎ Ｓｔｒｅｅｔ（ＭＳ）が実際のストリートであるとすると、何がＭａｉｎ Ｓｔｒｅｅｔ（ＭＳ）の実世界の曲線となるのか表している。このストリートセグメントの両端には、家屋番号２の端点ＥＰと家屋番号９８の端点ＥＰがある。これらの端点ＥＰに関連づけられるものは、経度と緯度の座標である。さらに、このストリートセグメントの彎曲（curvature）を定めるのに用いられる中間点である形状点ＳＰが、このストリートセグメントに沿って示されている。このストリートセグメントの両端にて、端点ＥＰを、もっとも近い形状点ＳＰに結ぶだけでなく、ストリートセグメントに沿って連続する形状点ＳＰも結ぶことで、このストリートセグメントの実世界の曲線の区分的線形表現を形成するために、直線が用いられている。形状点ＳＰは、経度と緯度の地点であるが、ただし、それらの地点に関連づけられる家屋番号は持たない。図１はまた、１２ Ｍａｉｎ Ｓｔｒｅｅｔ、２６ Ｍａｉｎ Ｓｔｒｅｅｔ、３４ Ｍａｉｎ Ｓｔｒｅｅｔに対応する経度と緯度の地点である３つのアドレスポイント（１２、２６、３４）も示している。アメリカ合衆国では、名称と住所の付けられたストリート・ブロック側が一億程度ある。平均的なストリート・ブロック側に、それぞれ住所を持つ現実の家屋番号が２つ含まれると仮定すると、アメリカ合衆国単独では、可能性として、アドレスポイントが２億あることになる。
【００１４】
本発明の実施形態では、アドレスポイント、端点、形状点の経度と緯度は、航空映像、衛星写真、全地球測位システム（ＧＰＳ）装置、アドレス・ジオコーディング、実地調査、地方自治体地図からの編集、または他の手段の利用により、正確に決定される。他の実施形態では、アドレスポイント、端点、形状点は、経度と緯度を除き、他の数値地理システム（numeric geographic system）により決定されることもある。
【００１５】
図１では、アドレスポイントは家屋番号を表すが、他の実施形態では、アドレスポイントは、一区画（parcel）、アパートメントビルディングなど家屋番号を２つ以上持つビル、商業ビルなど番号を２つ以上持つビル、勤務先住所（business address）、ランドマークも表すことがある。他の実施形態では、アドレスポイントはまた、２つ以上の名称で知られている場所であることもある。一例として、１ Ｍｅｄｉｃａｌ Ｃｅｎｔｅｒなどのバニティ・アドレス（vanity address）、すなわち、その場所のストリートアドレスを参照しない住所がある。
【００１６】
利用者が３４ Ｍａｉｎ Ｓｔｒｅｅｔの位置を求める場合に、２ Ｍａｉｎ Ｓｔｒｅｅｔと９８ Ｍａｉｎ Ｓｔｒｅｅｔの端点ＥＰしか持たない従来技術は、３４ Ｍａｉｎ Ｓｔｒｅｅｔを、それが端点ＥＰ間の直線（図示されてない）に沿って距離の約３分の１の所にあるように補間する。しかしながら、図１に示されるように、家屋番号３４に対するアドレスポイント３４により、実際の家屋番号３４は、このブロック側を半分以上下った所にあって、かつ、そのストリート・センターラインから、このストリートの一側にずらされている。
【００１７】
本発明では、以下でさらに詳しく述べられるように、特定の家屋番号およびアドレスレンジの位置を利用して、所与のブロックの両端にて、あるいは所与のブロックの任意の側の内部で、どんな住所に対しても正確な位置決めを実現し、表示する。上述のアドレスポイントを持つ地図データベースを提供すれば、地図データベース中にアドレスポイントがある家屋番号またはアドレスレンジの位置を見出すことができる。これは、図２に示されるような住所情報のインデックスの直接のルックアップにより達成できる。地図データベース中にアドレスポイントがないビルの位置を見出すために、このアプリケーション・ソフトウェアは、補間を実行できる。例えば、図１を参照すると、家屋番号３０ Ｍａｉｎ Ｓｔｒｅｅｔは、２６ Ｍａｉｎ Ｓｔｒｅｅｔに対するアドレスポイント番号２６と、３４ Ｍａｉｎ Ｓｔｒｅｅｔに対するアドレスポイント番号３４との間を補間して、それを補間点ＩＰとすることで見出され、それにより、端点番号２と端点番号９８との間を補間して得られるものよりも正確な位置が与えられる。補間だけでなく、直接のルックアップも示す模範的なアルゴリズムが、図４に示されている。
【００１８】
図２は、ストリートセグメント、アドレスポイント、形状点、および、それらの位置に関する表を含む住所情報のインデックスの一実施形態を示している。図２のインデックスは、地図データベースから得られることになり、これは、地図データベース・アプリケーション・ディベロッパーに伝えることができる。このインデックスは、「Ｓｔｒｅｅｔ Ｓｅｇｍｅｎｔｓ（ストリートセグメント）」と称される表１、「Ａｄｄｒｅｓｓ Ｐｏｉｎｔｓ（アドレスポイント）」と称される表２、および、「Ｓｈａｐｅ Ｐｏｉｎｔｓ（形状点）」と称される表３を含む。図２の表１に示されるエントリは、図１に示される模範的なストリートセグメントなどの所与のストリートセグメントに関するものである。
【００１９】
図２の表１は、ストリートセグメントに関するエントリを示しており、「ｗｈａｔ（何）」の欄、「ｔｙｐｅ（タイプ）」の欄、「ｃｏｍｍｅｎｔ（コメント）」の欄を含む。この実施形態では、表１に関して、「何」の欄と「タイプ」の欄のエントリだけを必要とする。「コメント」の欄は、この表１の実施形態では必要でなく、省略可能な欄である。タイプがポインタである第１のテーブル・エントリＳｅｇｓｉｄｅ＿ＩＤは、ストリートセグメントの一意の識別子（unique identifier)、すなわち、それぞれのストリート・ブロック側につき１つの識別子である。タイプが英数字である次のテーブル・エントリＨＮＲ＿ｆｒｏｍは、このストリートセグメントの「ｆｒｏｍ」端上の家屋番号である。これは、そのアドレスレンジの一部である。図１から、このストリートセグメントの「ｆｒｏｍ」端上の家屋番号は、「２ Ｍａｉｎ Ｓｔｒｅｅｔ」である。タイプが数字である次のテーブル・エントリＦｒｏｍ＿ｌａｔｌｏｎは、「ｆｒｏｍ」ノードの経度と緯度である。図１では、Ｆｒｏｍ＿ｌａｔｌｏｎは、「２ Ｍａｉｎ Ｓｔｒｅｅｔ」の経度と緯度である。タイプが英数字である次のテーブル・エントリＨＮＲ＿ｔｏは、このストリートセグメントの「ｔｏ」端上の家屋番号である。図１から、このストリートセグメントの「ｔｏ」端は、「９８ Ｍａｉｎ Ｓｔｒｅｅｔ」である。タイプが数字である次のテーブル・エントリＴｏ＿ｌａｔｌｏｎは、「ｔｏ」ノードの経度と緯度である。図１では、Ｔｏ＿ｌａｔｌｏｎは、「９８ Ｍａｉｎ Ｓｔｒｅｅｔ」の経度と緯度である。タイプがポインタである次のテーブル・エントリＳｔｒｅｅｔｎａｍｅ＿ＩＤは、このストリート名の表のインデックスである。このストリートのそれぞれの側が、複数のストリート名で知られていることがあるので、タイプがポインタである残りのテーブル・エントリ（Ａｌｉａｓ１＿ｓｔｒｎｍ＿ＩＤ〜ＡｌｉａｓＮ＿ｓｔｒｎｍ＿ＩＤ）は、それぞれの側に対する代替ストリート名に使用される。例えば、Ｓａｎ Ｆｒａｎｃｉｓｃｏでは、Ｃａｅｓａｒ Ｃｈａｖｅｚ Ｓｔｒｅｅｔは、Ａｒｍｙ Ｓｔｒｅｅｔとしても知られている。
【００２０】
アドレスポイントを示す図２の表２は、「何」の欄、「タイプ」の欄、「コメント」の欄を含む。この実施形態では、表２に関して、「何」の欄と「タイプ」の欄のエントリだけを必要とする。「コメント」の欄は、この表２の実施形態では必要でなく、省略可能な欄である。第１のテーブル・エントリＳｅｇｓｉｄｅ＿ＩＤは、ストリートセグメントの一意の識別子、すなわち、それぞれのストリート・ブロック側につき１つの識別子であって、ポインタのタイプを持っている。表１もテーブル・エントリＳｅｇｓｉｄｅ＿ＩＤを持っているので、Ｓｅｇｓｉｄｅ＿ＩＤはまた、表１のストリートセグメントからのリンクでもある。タイプがポインタである次のテーブル・エントリＡｄｄｒｐｔ＿ＩＤは、一意のアドレスポイント識別子である。図１から、一意のアドレスポイント識別子の例として、「１２ Ｍａｉｎ Ｓｔｒｅｅｔ」、「２６ Ｍａｉｎ Ｓｔｒｅｅｔ」、「３４ Ｍａｉｎ Ｓｔｒｅｅｔ」がある。タイプがポインタである次のテーブル・エントリ（ＨＮＲ＿ｓｔａｒｔ、ＨＮＲ＿ｅｎｄ）は、アドレスポイントに関して開始する家屋番号と終了する家屋番号である。アドレスポイントは、家屋番号レンジ（家屋番号の連なり、house number range）、例えばアパートメントビルディングを持つこともある。しかしながら、アドレスポイント「１２ Ｍａｉｎ Ｓｔｒｅｅｔ」に対する開始する家屋番号と、終了する家屋番号は、単に１２と１２だけである。タイプがポインタである次のテーブル・エントリＳｔｒｅｅｔｎａｍｅ＿ＩＤは、このストリート名の表のインデックスである。このストリートのそれぞれの側が、複数のストリート名で知られていることがあるので、タイプがポインタであるテーブル・エントリ（Ａｌｉａｓ１＿ｓｔｒｎｍ＿ＩＤ〜ＡｌｉａｓＮ＿ｓｔｒｎｍ＿ＩＤ）は、それぞれの側に対する代替ストリート名に使用される。これらの名称は、基礎になるセグメント上の名称、基礎になるセグメント上の名称のサブセット、あるいは他のバニティ名（vanity name）と同一であることもある。例えば、アドレスポイントは、そのアドレスポイントが沿って位置づけられているストリートセグメント名（例えば、仮想Ｆｒｏｎｔ Ｓｔｒｅｅｔ）とは異なるバニティ名（例えば、１ Ｍｅｄｉｃａｌ Ｃｅｎｔｅｒ）で知られていることがある。最後に、タイプがポインタである最後のテーブル・エントリＬａｔ／ｌｏｎは、このアドレスポイントの経度と緯度である。図１では、アドレスポイント「１２ Ｍａｉｎ Ｓｔｒｅｅｔ」のＬａｔ／ｌｏｎは、このアドレスポイントの経度と緯度である。
【００２１】
形状点を示す図２の表３は、「何」の欄、「タイプ」の欄、「コメント」の欄を含む。この実施形態では、表３に関して、「何」の欄と「タイプ」の欄のエントリだけを必要とする。「コメント」の欄は、この表３の実施形態では必要でなく、省略可能な欄である。第１のテーブル・エントリＳｅｇｓｉｄｅ＿ＩＤは、ストリートセグメントの一意の識別子、すなわち、それぞれのストリート・ブロック側につき１つの識別子であって、ポインタのタイプを持っている。表１もテーブル・エントリＳｅｇｓｉｄｅ＿ＩＤを持っているので、Ｓｅｇｓｉｄｅ＿ＩＤはまた、表１のストリートセグメントからのリンクでもある。タイプが数字である最後のテーブル・エントリ（Ｌａｔ／ｌｏｎ１〜Ｌａｔ／ｌｏｎ Ｎ）は、このストリートセグメントに沿った各形状点の経度と緯度である。
【００２２】
本発明の住所情報に関するデータベースまたはインデックスは、多くのエントリを含むであろう。本発明の実施形態では、すべてのストリートセグメントと、それらの対応するエントリが、必ずしも、関連するアドレスレンジを持つとは限らない。本発明の実施形態では、すべてのストリートセグメントと、それらの対応するデータベースまたはインデックスのエントリが、必ずしも、関連する１つまたは複数の形状点を持つとは限らない。さらに、ソフトウェア分野における当業者に明らかとなるように、住所情報に関するインデックスを除き、他の表現が、熟練のプログラマにより生み出されることもある。
【００２３】
図３は、図２のインデックスを編集して、アプリケーション・データ構造にする一実施形態を示している。図３は、地図データベース・アプリケーション・ディベロッパーが、どのように図２のインデックスを編集して、ソフトウェア・アプリケーションにすることになるのか一例を示している。図示されるように、この編集は、バイナリツリー（binary tree)の形式を取っている。それぞれのストリート名では、このデータ構造は、セグメント側（Ｓｅｇｓｉｄｅ１＿ＩＤ）ごとに、このセグメント側の最小の潜在的家屋番号（Ｐｏｔ＿ｌｏ）、このセグメント側の最小の潜在的家屋番号の経度と緯度（Ｌａｔｌｏｎ＿ｌｏ）、このセグメント側の最大の潜在的家屋番号（Ｐｏｔ＿ｈｉ）、および、このセグメント側の最大の潜在的家屋番号の経度と緯度（Ｌａｔｌｏｎ＿ｈｉ）を含む。このセグメント側のそれぞれのアドレスポイント（Ａｄｄｒｐｔ１＿ＩＤ〜ＡｄｄｒｐｔＮ＿ＩＤ）では、このデータ構造は、それぞれのアドレスポイントにて最小の実際の家屋番号（ＨＮＲ＿ｌｏ）、それぞれのアドレスポイントにて最大の実際の家屋番号（ＨＮＲ＿ｈｉ）、および、それぞれのアドレスポイントの経度と緯度（Ｌａｔｌｏｎ）を含む。
【００２４】
図４は、アドレスポイント用として、擬似コードの一実施形態を示している。利用者によりローカリティ（locality）が定められると、擬似コードが始まって、特定のストリート名を持つストリートセグメントの探索範囲を限定する。まず最初に、この擬似コードは、利用者が要望する上記ローカリティ内の正確なストリート名を用いて、データベース中に、アドレスポイントがあるかどうか判定する。入力された所望のストリート名を持つすべてのセグメント側を、図２のインデックスから取得し、次に、セグメント側ごとに、このソフトウェアは、ＨＮＲ＿ｌｏ＜＝ａｄｄｒｅｓｓ＜＝ＨＮＲ＿ｈｉとなるように、セグメント側上のそれぞれのアドレスポイントから所望の家屋番号を探索することで、適切なアドレスポイントを捜す。ここで、ＨＮＲ＿ｌｏとＨＮＲ＿ｈｉは、図３から、このセグメント側に対するアドレスポイントのそれぞれ最小と最大の実際の家屋番号であり、また、「ａｄｄｒｅｓｓ」は、所望の住所である。アドレスポイントが見出される場合には、この位置は、このアドレスポイントに対する緯度／経度であり、また、その位置が「ｆｏｕｎｄ（見出されている）」ことを示す返答がある。例えば、所望の住所が、アドレスポイントである２６ Ｍａｉｎ Ｓｔｒｅｅｔである場合には、このアドレスポイントの緯度と経度が知られているために、地図上の位置が見出されている。
【００２５】
アドレスポイントが見出されなかった場合には、所望の家屋番号が、このセグメント側の２つのアドレスポイント間にあるか、あるいは、このセグメントに対する全アドレスレンジ内にあるかどうか判定する。これは、Ｐｏｔ＿ｌｏ＜＝ａｄｄｒｅｓｓ＜＝Ｐｏｔ＿ｈｉとなるように、それぞれのセグメント側から、所望の住所を探索することで、達成される。ここで、Ｐｏｔ＿ｌｏとＰｏｔ＿ｈｉは、図３から、このセグメント側に対して、それぞれ最小と最大の潜在的家屋番号であり、また、「ａｄｄｒｅｓｓ」は、所望の住所である。図１のＭａｉｎ Ｓｔｒｅｅｔの例では、Ｐｏｔ＿ｌｏとＰｏｔ＿ｈｉが、このセグメント側の端点（それぞれ、２と９８）にセットされることになる。所望の住所を含む潜在的なレンジが見出されない場合には、「ｎｏｔ＿ｆｏｕｎｄ」を戻す。
【００２６】
しかしながら、この潜在的なアドレスレンジが所望の住所を実際に含む場合には、補間に使用するための取り囲む２つのもっとも近い実際または潜在的なアドレスポイントを取得する。これは、図３から、変数「ｌｏｗ（小さい数字）」をＰｏｔ＿ｌｏにセットすることで達成される。ここで、Ｐｏｔ＿ｌｏは、このセグメント側に対して最小の潜在的家屋番号である。このセグメント側上のそれぞれのアドレスポイント（小さい数字から大きい数字へ）では、ａｄｄｒｅｓｓ＞＝ＨＮＲ＿ｌｏの場合に、変数「ｌｏｗ」に対する新たな値はＨＮＲ＿ｌｏである。ここで、ＨＮＲ＿ｌｏは、図３から、このアドレスポイントでの最小の実際の家屋番号であり、また、「ａｄｄｒｅｓｓ」は、所望の家屋番号である。次に、このセグメント側上のそれぞれのアドレスポイント（大きい数字から小さい数字へ）では、ａｄｄｒｅｓｓ＜＝ＨＮＲ＿ｈｉの場合に、変数「ｈｉｇｈ（大きい数字）」に対する新たな値はＨＮＲ＿ｈｉである。ここで、ＨＮＲ＿ｈｉは、図３から、このアドレスポイントでの最大の実際の家屋番号であり、また、「ａｄｄｒｅｓｓ」は、所望の住所である。図４中の擬似コードのこの時点において、補間に使用するための最適な２つの実際または潜在的なアドレスポイントを計算して、「ｌｏｗ」と「ｈｉｇｈ」とし、それらを、このセグメント側の取り囲む２つのもっとも近いアドレスポイント、１つのアドレスポイントと１つのセグメント側の端点、または２つのセグメント側の端点に、好みの降順でセットした。
【００２７】
例えば、図１から、３０ Ｍａｉｎ Ｓｔｒｅｅｔの所望の住所では、図４の擬似コードは、「ｌｏｗ」と「ｈｉｇｈ」を計算して、それぞれ２６と３４とすることになる。ここで、２６と３４は２つのアドレスポイントである。図１からの他の例では、また、６６ Ｍａｉｎ Ｓｔｒｅｅｔの所望の住所では、この擬似コードは、「ｌｏｗ」と「ｈｉｇｈ」を計算して、それぞれ、３４と９８とすることになる。ここで、３４はアドレスポイントであり、また、９８は、セグメント側のアドレスレンジの端点である。
【００２８】
最後に、図４では、この擬似コードは、図１に示されるように、このストリートセグメントの両端にて、端点ＥＰを、もっとも近い形状点ＳＰに結ぶだけでなく、形状点ＳＰも結ぶ直線で定められる通り、このストリートセグメント側の彎曲の区分的線形近似を考慮に入れて、これらの所望の住所を、それが「ｌｏｗ」と「ｈｉｇｈ」の間にあるように補間する。次に、この擬似コードは、補間される所望の住所が「ｆｏｕｎｄ（見出された）」と返答する。例えば、図１の例を使用すると、３０ Ｍａｉｎ Ｓｔｒｅｅｔの所望の住所は、補間により見出されて、補間点ＩＰとなる。補間点ＩＰは、このストリートセグメント側に沿って、アドレスポイント２６とアドレスポイント３４の近くにある２つの形状点ＳＰを結ぶ直線に沿って、アドレスポイント２６とアドレスポイント３４との間で見出されることになる。次に、所望の住所の位置は、地図データベース・アプリケーション・コンバータ（map database-to-application converter）とデバイス・アプリケーション・ソフトウェア（device application software）により、地図上で利用者に表示されることになる。
【００２９】
この補間の一実施形態では、上記ストリートセグメントの両端にて、端点ＥＰを、もっとも近い形状点ＳＰに結ぶだけでなく、連続する形状点ＳＰも結ぶ直線で示される通り、図４において区分的線形表現を利用して、このストリートセグメント側の彎曲に近づける。形状点ＳＰがまったく与えられない場合には、端点ＥＰを結ぶ直線を利用して、このセグメント形状を表現する。
【００３０】
補間の他の実施形態では、所与のストリート上の所望の家屋番号にもアドレスレンジにも、アドレスポイントがまったくない場合には、アプリケーション・ソフトウェアは、デフォルトにおいて、その基礎になるストリートセグメント上のアドレスレンジから、この位置を補間することがある。あるいは、このストリートセグメント上にアドレスポイントがいくつか存在する場合には、アドレスポイントとストリートセグメントの端点との組合せが、補間に利用されることもある。図１では、例えば、家屋番号６６ Ｍａｉｎ Ｓｔｒｅｅｔの位置は、それが、アドレスポイント３４と、ストリートセグメントの端点の家屋番号９８との中間地点にあるように、線形補間されることもある。
【００３１】
最適な位置決めに用いられる探索順序は、（１）地図データベース・セグメント上で得られる場合には、実際のアドレスポイントを取得する、（２）得られない場合には、この地図データベース・セグメント上で数値的にもっとも近く、かつ取り囲む２つのアドレスポイント間を補間する、（３）取り囲むアドレスポイントが１つしか得られない場合には、そのアドレスポイントと、実際または潜在的なアドレスレンジからのセグメント端点の住所との間を補間する、（４）アドレスポイントがまったく得られない場合には、この実際または潜在的なアドレスレンジからの２つのセグメント端点に対する取り囲むアドレスレンジ間を補間する。
【００３２】
補間に関する本発明の実施形態は、他の線形表現とともに用いられることがある。図４の補間例、並びに、補間の他の実施形態に使用されるこれらの線形表現は、家屋番号を、このストリートセグメントに沿って均等に割り当てるときに使用される。しかしながら、他の実施形態では、他のタイプの補間が行われることもある。例えば、ストリートセグメントの一端に家屋を集める場合には、対数補間アルゴリズム（logarithmic interpolation algorithm）が用いられることもある。
【００３３】
本発明は、地図データベースの変更をともなうが、しかるに、他のベンダーは、地図データベース、またはそのデータの派生編集（derived compilation）を利用する地図データベース・アプリケーション・コンバータとデバイス・アプリケーション・ソフトウェアを提供する。デバイス・アプリケーション・ソフトウェアは、利用者の入力に応答して、その派生地図データにアクセスして、それを処理する。利用者へのデバイス・アプリケーション・ソフトウェアの出力は、リスト、文章、地図または画像などのグラフィカル表示、発話などの音声、あるいは他のタイプの出力で表されることもある。多くのＧＩＳ、インターネット、ナビゲーションのアプリケーションは、本発明を使用する場合もある。これらのアプリケーションは、ジオコーディング・アプリケーション（文章／リストを基本とする）、ルーティング／方向アプリケーション（グラフィカル／リスト／発話を基本とする）、および、グラフィカル・ベースの表示アプリケーションを含む。これらのアプリケーションは、とりわけ、ナビゲーションのアプリケーション、インターネット・ベースのアプリケーション、地理情報システム（ＧＩＳ）を含むこともある。このアプリケーションは、マッピング・プログラム、ナビゲーション・プログラム、または何か他のタイプのプログラムであることもある。上に説明されているように、地図アプリケーションの消費者は、所望の場所を捜し出すことができるように、様々な装置およびシステムを持っている。これらの装置およびシステムは、運転者がストリートや道路にナビゲートでき、また所望の場所を入力できるようにする車載ナビゲーション・システム、携帯情報端末（「ＰＤＡ」）や、同一機能を果たせる携帯電話などのハンドヘルド装置、および、所望の結果を利用するか、または描写して利用者が地図にアクセスできるようにするインターネット・アプリケーションの形式を取っている。この開示の目的では、このような結果はすべて、単に「ｐｌａｃｅｓ（場所）」として定義されるだけである。
【００３４】
図５は、仮想インターネット・ベース・システム(hypothetical Internet-based system)に使用される模範的な実施形態を示している。仮想インターネット・ベース・システムは、ＰＤＡや携帯電話などのハンドヘルド装置上で、あるいは、コンピュータまたはラップトップ上で用いられることもある。模範的な探索は、「Ｓｅａｒｃｈ（探索）」ボタンの隣りに示される通り、３５０ ５ｔｈ Ａｖｅ．，Ｎｅｗ Ｙｏｒｋ、すなわちＥｍｐｉｒｅ Ｓｔａｔｅ Ｂｕｉｌｄｉｎｇの住所に対して、仮想インターネット・マッピング・アプリケーションを用いて、利用者により行われる。仮想インターネット・マッピング・アプリケーションは、この時点では、Ｗｅｓｔ ３４ｔｈ Ｓｔｒｅｅｔで、かつ５ｔｈ Ａｖｅｎｕｅの付近で、点を含む泡で、この地図上の住所の位置を表示している。その一方、本発明は、アドレスポイントと、おそらく補間を利用して、ビルまたはビルが位置づけられている画地のより正確な位置（この位置は、明らかに地図上の上記泡の所ではない）を見出すことになる。本発明は、所与のブロックの両端にて、あるいは所与のブロックの任意の側の内部で、どんな住所に対しても、より正確なサブブロック位置決め情報を提供できる。
【００３５】
図６は、携帯情報端末（ＰＤＡ）などの携帯用ハンドヘルド装置上で使用される模範的な実施形態を示している。この装置はまた、例えば携帯電話であることもある。ＰＤＡ地図ソフトウェアでは、１５０ Ｃｅｎｔｒａｌ Ｐａｒｋ Ｗｅｓｔに向かう運転方向を求める利用者により、模範的な探索が行われる。このＰＤＡ地図ソフトウェアは、本発明を利用して、１５０ Ｃｅｎｔｒａｌ Ｐａｒｋ Ｗｅｓｔの位置を、このＰＤＡ地図ソフトウェアを用いて正確に表示する。
【００３６】
図７は、全地球測位システム（ＧＰＳ）などの車載ナビゲーション・システム上で使用される模範的な実施形態を示している。ＧＰＳ地図ソフトウェアでは、ＧＰＳ地図ソフトウェアの下端に示される３５ Ｗｅｓｔ Ｈｉｌｌ Ｒｏａｄに向かう運転方向を求める運転者により、模範的な探索が行われる。運転者が、ＧＰＳ地図ソフトウェアを用いて自分の目的地に達すると、このＧＰＳ地図ソフトウェアは、本発明を利用して、３５ Ｗｅｓｔ Ｈｉｌｌ Ｒｏａｄの位置を正確に表示する。
【００３７】
図８は、航空写真上に重ねられたアドレスポイントの一例を示す模範的な実施形態を示している。この例では、このブロック内のすべてのビルは、アドレスポイントに指定されており、したがって、家屋番号またはビル番号のどれについても、その位置に近づけるのに、補間はまったく行わない。Ｆｏｒｍｏｓａ Ａｖｅｎｕｅ、Ｌｅｘｉｎｇｔｏｎ Ａｖｅｎｕｅ、Ｄｅｔｒｏｉｔ Ｓｔｒｅｅｔに関するストリートセグメントの名称も、この航空写真上に重ねられている。図示されるＦｏｒｍｏｓａ Ａｖｅｎｕｅに関するストリートセグメントの一側では、そのアドレスレンジは１１２２〜１１５４である。Ｌｅｘｉｎｇｔｏｎ Ａｖｅｎｕｅに関するストリートセグメントの一側では、そのアドレスレンジは７１６８〜７１５４である。このＬｅｘｉｎｇｔｏｎ Ａｖｅｎｕｅのストリートセグメントの例は、ブロック全体にわたっていないビルの位置があるアドレスレンジの好例である。Ｄｅｔｒｏｉｔ Ａｖｅｎｕｅに関するストリートセグメントの一側では、そのアドレスレンジは、１１０７〜１１５５である。航空写真では、このアドレスレンジは、ブロック全体にわたっているビルがある唯一のものである。
【００３８】
図９は、本発明の実施形態に使用できる模範的なシステム９００のブロック図を示している。この図は、構成要素を論理的に別々なものとして描いているが、そのような描写は、単に例示目的にすぎない。この図に描かれた構成要素を組み合わせるか、あるいは、別々のソフトウェア、ファームウェア、および／またはハードウェア・コンポーネントに分けられることが当業者には明らかになろう。さらに、このような構成要素をどのように組み合わせるか、あるいは分けるかに関係なく、それらの構成要素が、同一のコンピューティング装置／システム上で実行できるか、あるいは、１つまたは複数のネットワークもしくは他の適切な通信手段により接続された異なるコンピューティング装置／システムに、それらの構成要素を割り当てられることも当業者には明らかになろう。
【００３９】
図９に示されるように、システム９００は、一般に、１つまたは複数のメモリ９１２、１つまたは複数のプロセッサ９１４、および、１つまたは複数のある種の記憶装置またはリポジトリ９１６を含むことのあるコンピューティング装置９１０を含んでいる。システム９００はさらに、ディスプレイ装置９１８も含むことがあり、ディスプレイ装置９１８上ではグラフィカル・ユーザー・インターフェースすなわちＧＵＩ９２０が動作して、このシステムが、地図および他の情報を利用者に表示できるようにしている。利用者は、このコンピューティング装置を利用して、例えば、ローカリティを地図上に表示するか、あるいは、運転方向を、地図上のルートとして、および／またはテキスト方向として表示するように求める。
【００４０】
地図データベース９３０は、コンピューティング装置またはシステム９１０の外部記憶装置として示されているが、ただし、地図データベース９３０は、ときには、記憶装置９１６と同じ記憶装置であることもある。本発明の実施形態により、地図データベース９３０は、地図セグメント（map segment）の表とインデックス９３２、アドレスポイントの表とインデックス９３４、および、形状点の表とインデックス９３６を含む。
【００４１】
プロプライエタリ（メーカー独自仕様）地図データベース作成ソフトウェア９４０は、実世界のローカリティ情報源と緯度／経度情報源９６０を利用して、地図データベース９３０において、地図セグメントの表とインデックス９３２、アドレスポイントの表とインデックス９３４、および、形状点の表とインデックス９３６をそれぞれ作成する。地図データベース９３０からの情報は、最後にコンピューティング装置９１０の利用者が利用する地図データベース・アプリケーション・コンバータとデバイス・アプリケーション・ソフトウェア９５０で使用される。地図データベース・アプリケーション・コンバータとデバイス・アプリケーション・ソフトウェア９５０は、利用者のコンピューティング装置９１０にはリモートとして図示されているが、ただし、利用者のコンピューティング装置９１０上にあることもある。
【００４２】
ソフトウェア分野における当業者に明らかとなるように、熟練プログラマであれば、本開示内容の教示に基づいて、適切なソフトウェア・プログラムを容易に作成することができる。本発明の実施形態はまた、当業者には容易に明らかとなるように、特定用途向け集積回路を用意することにより、あるいは、従来の構成回路から成る適切な回路網を相互接続することにより、実施されることがある。
【００４３】
本発明の実施形態は、本発明の実施形態のプロセスをどれでも実行するようにコンピュータをプログラムするのに用いられる命令が格納されている記憶媒体（１つまたは複数）であるコンピュータ・プログラム製品を含む。この記憶媒体は、フロッピー（登録商標）ディスク、光ディスク、ＤＶＤ、ＣＤ−ＲＯＭ、超小型ハードディスク、および光磁気ディスクを含む任意タイプのディスク、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、ＤＲＡＭ、ＶＲＡＭ、フラッシュメモリ・デバイス、磁気式または光学式のカード、ナノシステム（分子メモリＩＣを含む）、あるいは、命令および／またはデータの格納に適した任意タイプのシステムまたはデバイスを含む（ただし、それらには限定されない）こともある。
【００４４】
本発明の実施形態は、上記のコンピュータ読取り可能媒体（１つまたは複数）のどれか１つに格納されるものとして、汎用型／専用型のコンピュータまたはマイクロプロセッサのハードウェアを制御するソフトウェアと、このコンピュータまたはマイクロプロセッサが、本発明の実施形態の結果を利用して、人間の利用者または他の機構と対話できるようにするソフトウェアを両方とも含む。このようなソフトウェアは、デバイス・ドライバ、オペレーティングシステム、ユーザー・アプリケーションを含む（ただし、それらには限定されない）ことがある。最後に、このようなコンピュータ読取り可能媒体はさらに、上述の通り、本発明の実施形態を実行するソフトウェアも含む。
【００４５】
上記の汎用型／専用型のコンピュータまたはマイクロプロセッサのプログラムすなわちソフトウェアに含まれているものは、本発明の教示を実施するソフトウェア・モジュールである。本発明の実施形態は、コンピュータ分野における当業者に明らかとなるように、本開示内容の教示によりプログラムされた従来の汎用型または専用型のデジタル・コンピュータまたはマイクロプロセッサを利用して、都合よく実施されることがある。
【００４６】
本発明の上の説明は、図示と説明の目的で与えられてきた。この説明は、すべてを尽くすつもりはないし、また、本発明の実施形態を、開示されている通りの形態に限定するつもりもない。多くの変更例や変形例が、当事者には明らかになろう。これらの実施形態は、本発明の原理、および本発明の実地応用をもっともよく説明するために、選択され、述べられ、それにより、他の当業者が、本発明を様々な実施形態に関して理解することができ、また、特定の用途に適した様々な変更が考えられた。本発明の範囲は、併記の特許請求の範囲、および、それらと同等なものにより定義されることが意図される。
【図面の簡単な説明】
【００４７】
【図１】所与の都市の仮想メインストリートの１ブロックの一側のストリートセグメントの略図と、そのストリートセグメントに沿って、形状点と称される特定の地点間に直線を引いて形成されるこのストリートセグメントの区分的線形表現である。
【図２】ストリートセグメント、アドレスポイント、形状点、および、それらの位置に関する表を含む住所情報のインデックスの一実施形態を示す。
【図３】図２のインデックスを編集して、アプリケーション・データ構造にする一実施形態を示す。
【図４】アドレスポイント用として、擬似コードの一実施形態を示す。
【図５】仮想インターネット・ベース・システムに使用される模範的な実施形態を示す。
【図６】携帯情報端末（ＰＤＡ）などのハンドヘルド装置上で使用される模範的な実施形態を示す。
【図７】全地球測位システム（ＧＰＳ）などの車載ナビゲーション・システム上で使用される模範的な実施形態を示す。
【図８】航空写真上に重ねられたアドレスポイントの模範的な実施形態を示す。
【図９】地図データベース５０４の実施形態が、地図データベース・アプリケーション５０２とは別々であることを示す。
【技術分野】
【０００１】
本発明は、特定の住所の位置を決定する情報を持つ地図データベースに関し、さらに具体的に言えば、利用者が要望する場所の所在地または位置を正確に決定するのに用いられるデータ構造を持つ地図データベースに関する。
【０００２】
（優先権の主張）
２００６年２月８日に出願されたＭｉｃｈｅｌ Ｇｅｉｌｉｃｈ氏による「Ａ ＭＡＰ ＤＡＴＡＢＡＳＥ ＨＡＶＩＮＧ ＡＤＤＲＥＳＳ ＰＯＩＮＴＳ ＦＯＲ ＤＥＴＥＲＭＩＮＩＮＧ ＤＥＳＴＩＮＡＴＩＯＮＳ（目的地を決定するアドレスポイントを持つ地図データべース）」と称する米国特許出願第１１／３５１，１５６号（Ａｔｔｏｒｎｅｙ Ｄｏｃｋｅｔ Ｎｏ．ＴＥＬＡ−０７７７５ＵＳ０）。
【背景技術】
【０００３】
近年、消費者は、デジタル地図上で場所を捜し出すことができるように、様々な装置およびシステムを持っている。「ｐｌａｃｅ（場所）」という語は、本発明の説明の全体を通して使用されている一般的な用語である。「ｐｌａｃｅ（場所）」という語は、ストリートアドレス（street address）、店舗やランドマークなど、ストリートアドレスに位置づけられるビル、および、ショッピングモールやビジネスパークなど、いくつかのストリートアドレスに位置づけられる施設を含む。消費者に使用される様々な装置およびシステムは、運転者がストリートや道路にナビゲートできるようにする車載ナビゲーション・システム、携帯情報端末（「ＰＤＡ」）、パーソナル・ナビゲーション装置、同一機能を果たせる携帯電話などのハンドヘルド装置(hand-held device)、および、所望の場所を示す地図を利用者に作成させるインターネット・アプリケーションの形式を取っている。上記および他のタイプの装置およびシステムのすべてに共通する点は、地理的フィーチャー（geographic features）の地図データベースと、利用者入力に応答して、この地図データベースにアクセスし、処理するソフトウェアである。要するに、これらの装置およびシステムのすべてにおいて、利用者は所望の場所を入力できる。また、戻される結果は、その場所の位置となろう。一般に、利用者は、レストランなどの業務の名称、あるいは、Ｇｏｌｄｅｎ Ｇａｔｅ Ｂｒｉｄｇｅなどの目的地ランドマーク、あるいはストリートアドレスを入力し、次に、この要求された場所の位置が戻されることになる。この位置を地図ディスプレイ上に示すか、または、この位置を使用して、この位置に向かう運転方向を計算し、表示するか、あるいは、他のやり方でこの位置を使用することがある。
【０００４】
地図データベースは、ストリート上の家屋およびビルの位置に関する情報を提供する。地図データベース・ディベロッパー（map database developer）は、地図データベース中の所与のストリートまたはストリートセグメント（ストリート区分、street segment）に関して、所与のアドレスレンジ（住所範囲、住所の連なり、address range）にわたるアドレスデータ（address data）を含む。このアドレスレンジは、開始する家屋番号と位置、終了する家屋番号と位置、および、随意にいくつかの中間の家屋番号と位置とともに、このストリートセグメントの所与の側に対応する一群のビル番号または家屋番号を含むことになる。
【０００５】
利用者の入力に応答して所望の場所を捜し出すために、この装置またはシステムのソフトウェアは、まず最初に、その場所のストリートアドレスを決定し、次に、所望の住所を含むアドレスレンジを持つストリートセグメントを捜し出し、次に、そのアドレスレンジ内で補間を実行して、その場所の位置を推定することになる。しかしながら、補間アルゴリズムは、所与のストリート・ブロック（street block）に沿って、実世界におけるビル番号または家屋番号の割当ての変更をまったく考慮に入れてないこともある。例えば、このストリート・ブロックの始まりまたは中央に公園があるかもしれないか、ブロックに沿って、ばらばらに家屋が割り当てられるかもしれないか、あるいは、アドレスレンジの端にあるビルが、正確にストリート交差点に位置づけられていないかもしれない。
【０００６】
理想的には、アドレスレンジの終わりにあるビル番号または家屋番号は、現実のビル住所を表しており、中間の家屋番号を補間する際の誤差を最小限に抑えている。しかしながら、このことは、常に事実であるとは限らない。地図データベースのなかには、端点（end point）にある潜在的なビル番号または家屋番号を用いて、アドレスレンジがモデル化されるものもあり、これは、中間のビル番号または家屋番号を正確に補間するという問題を悪化させる。例えば、地図データベースは、米国郵政公社で割り当てられる潜在的なビル番号または家屋番号を用いて、アドレスレンジをモデル化することがある。一例として、ストリートが１００の住所番号（address number）から成るブロックに分けられているＮｅｗ Ｙｏｒｋ Ｃｉｔｙの商業地区では、ブロック側に沿ったビル番号または家屋番号は、全アドレスレンジをめったに表さず、また、この全アドレスレンジをいずれか一方の端にて完結するとまではいかないことが多い。
【０００７】
上記の方法を使用する補間は、このストリートセグメントの長さの５０パーセント以上の誤差を持つことがある。これらの補間誤差は、何十メートルもしくは何百メートルの誤差になることもあり、それは、たぶん、その補間された位置にナビゲートしている利用者には、所望の場所を利用者の視野範囲外におくであろう。
【０００８】
補間は、上記の方法でサポートされるもっとも正確な位置を与えるとはいえ、高いサブブロック（sub-block）精度は保証しない。それでも、利用者を、ストリート・ブロック内の適正な位置に正確に導くためには、高いサブブロック精度が必要となる。
【発明の開示】
【課題を解決するための手段】
【０００９】
一面では、本発明は、少なくとも１つのストリートセグメントを含む、記憶媒体上に格納できる地図データベースである。ストリートセグメントは、そのストリートセグメント上で家屋番号またはビル番号に対応するゼロ以上のアドレスレンジを持つことがある。ストリートセグメントはまた、そのストリートセグメントのアドレスレンジ内のビル番号、家屋番号、またはアドレスレンジの位置にそれぞれが対応するゼロ以上のアドレスポイントも持つことがある。
【００１０】
他の面では、本発明は、実際のストリートに対応するストリートセグメントをそれぞれが識別する少なくとも１つの第１のデータエントリ(data entry)を持つ地図データベースから、住所情報および対応する位置のインデックス（index)を含む記憶媒体上に格納できる地図データベースを含み、また、第１のデータエントリごとに、このインデックスは、上記ストリートセグメントのどちら側にも、そのストリートセグメント内のビル番号、家屋番号、またはアドレスレンジの位置に対応するゼロ又はそれ以上のアドレスポイント・エントリ（address point entries)を持っている。
【００１１】
さらに他の面では、本発明は、ゼロ又はそれ以上のアドレスレンジと、そのアドレスレンジ内にあるゼロ又はそれ以上のアドレスポイントとをそれぞれが持つ少なくとも１つのストリートセグメントを有する地図データベース、および、利用者による所望の場所の入力に応答して、そのアドレスレンジ（得られる場合）にあるアドレスポイント（得られる場合）を取得するアプリケーション・プログラムを含む、所望の場所に対応する情報を利用者に提供するシステムを含む。所望の場所に対応するアドレスポイントが得られない場合には、上記アプリケーション・プログラムは、得られるアドレスポイント間、あるいは、そのアドレスレンジ（得られる場合）のアドレスポイントと端点との間を補間して、所望のビル番号の近似位置を決定することになる。アドレスポイントがまったく得られない場合には、上記アプリケーション・プログラムは、そのアドレスレンジ（得られる場合）の端点間を補間して、所望のビル番号の近似位置を決定することになる。
【００１２】
さらに他の面では、本発明は、利用者によるストリート名の入力に応答して、このストリート名に関連するストリートセグメントのすべてのアドレスポイントを取得することで、所望の場所の位置情報を利用者に提供する方法である。次に、この方法は、利用者が入力したビル住所番号に応答して、ビル住所番号用に取得されたアドレスポイントを調べる。これらの取得されたアドレスポイントのどれかが、上記の入力されたビル住所番号に対応する場合には、その対応する取得されたアドレスポイントを使用して、上記の入力されたビル住所番号の位置を利用者に戻す。取得されたアドレスポイントが、上記の入力されたビル住所番号にまったく対応しない場合には、取り囲む（bracketing）２つのもっとも近いアドレスポイント、あるいは、１つのアドレスポイントとストリートセグメントの端点を使用して補間し、その近似位置を利用者に戻す。
【発明を実施するための最良の形態】
【００１３】
図１は、所与の都市の仮想Ｍａｉｎ Ｓｔｒｅｅｔ（ＭＳ）の１ブロックの一側のストリートセグメントの略図と、そのストリートセグメントに沿って、形状点（shape point）ＳＰと称される特定の地点間に直線を引いて形成されるこのストリートセグメントの区分的線形表現である。この例では、Ｍａｉｎ Ｓｔｒｅｅｔ（ＭＳ）のこのストリートセグメントは、２〜９８というアドレスレンジ内の家屋番号を持つ住宅街である。この住宅街の曲線は、Ｍａｉｎ Ｓｔｒｅｅｔ（ＭＳ）が実際のストリートであるとすると、何がＭａｉｎ Ｓｔｒｅｅｔ（ＭＳ）の実世界の曲線となるのか表している。このストリートセグメントの両端には、家屋番号２の端点ＥＰと家屋番号９８の端点ＥＰがある。これらの端点ＥＰに関連づけられるものは、経度と緯度の座標である。さらに、このストリートセグメントの彎曲（curvature）を定めるのに用いられる中間点である形状点ＳＰが、このストリートセグメントに沿って示されている。このストリートセグメントの両端にて、端点ＥＰを、もっとも近い形状点ＳＰに結ぶだけでなく、ストリートセグメントに沿って連続する形状点ＳＰも結ぶことで、このストリートセグメントの実世界の曲線の区分的線形表現を形成するために、直線が用いられている。形状点ＳＰは、経度と緯度の地点であるが、ただし、それらの地点に関連づけられる家屋番号は持たない。図１はまた、１２ Ｍａｉｎ Ｓｔｒｅｅｔ、２６ Ｍａｉｎ Ｓｔｒｅｅｔ、３４ Ｍａｉｎ Ｓｔｒｅｅｔに対応する経度と緯度の地点である３つのアドレスポイント（１２、２６、３４）も示している。アメリカ合衆国では、名称と住所の付けられたストリート・ブロック側が一億程度ある。平均的なストリート・ブロック側に、それぞれ住所を持つ現実の家屋番号が２つ含まれると仮定すると、アメリカ合衆国単独では、可能性として、アドレスポイントが２億あることになる。
【００１４】
本発明の実施形態では、アドレスポイント、端点、形状点の経度と緯度は、航空映像、衛星写真、全地球測位システム（ＧＰＳ）装置、アドレス・ジオコーディング、実地調査、地方自治体地図からの編集、または他の手段の利用により、正確に決定される。他の実施形態では、アドレスポイント、端点、形状点は、経度と緯度を除き、他の数値地理システム（numeric geographic system）により決定されることもある。
【００１５】
図１では、アドレスポイントは家屋番号を表すが、他の実施形態では、アドレスポイントは、一区画（parcel）、アパートメントビルディングなど家屋番号を２つ以上持つビル、商業ビルなど番号を２つ以上持つビル、勤務先住所（business address）、ランドマークも表すことがある。他の実施形態では、アドレスポイントはまた、２つ以上の名称で知られている場所であることもある。一例として、１ Ｍｅｄｉｃａｌ Ｃｅｎｔｅｒなどのバニティ・アドレス（vanity address）、すなわち、その場所のストリートアドレスを参照しない住所がある。
【００１６】
利用者が３４ Ｍａｉｎ Ｓｔｒｅｅｔの位置を求める場合に、２ Ｍａｉｎ Ｓｔｒｅｅｔと９８ Ｍａｉｎ Ｓｔｒｅｅｔの端点ＥＰしか持たない従来技術は、３４ Ｍａｉｎ Ｓｔｒｅｅｔを、それが端点ＥＰ間の直線（図示されてない）に沿って距離の約３分の１の所にあるように補間する。しかしながら、図１に示されるように、家屋番号３４に対するアドレスポイント３４により、実際の家屋番号３４は、このブロック側を半分以上下った所にあって、かつ、そのストリート・センターラインから、このストリートの一側にずらされている。
【００１７】
本発明では、以下でさらに詳しく述べられるように、特定の家屋番号およびアドレスレンジの位置を利用して、所与のブロックの両端にて、あるいは所与のブロックの任意の側の内部で、どんな住所に対しても正確な位置決めを実現し、表示する。上述のアドレスポイントを持つ地図データベースを提供すれば、地図データベース中にアドレスポイントがある家屋番号またはアドレスレンジの位置を見出すことができる。これは、図２に示されるような住所情報のインデックスの直接のルックアップにより達成できる。地図データベース中にアドレスポイントがないビルの位置を見出すために、このアプリケーション・ソフトウェアは、補間を実行できる。例えば、図１を参照すると、家屋番号３０ Ｍａｉｎ Ｓｔｒｅｅｔは、２６ Ｍａｉｎ Ｓｔｒｅｅｔに対するアドレスポイント番号２６と、３４ Ｍａｉｎ Ｓｔｒｅｅｔに対するアドレスポイント番号３４との間を補間して、それを補間点ＩＰとすることで見出され、それにより、端点番号２と端点番号９８との間を補間して得られるものよりも正確な位置が与えられる。補間だけでなく、直接のルックアップも示す模範的なアルゴリズムが、図４に示されている。
【００１８】
図２は、ストリートセグメント、アドレスポイント、形状点、および、それらの位置に関する表を含む住所情報のインデックスの一実施形態を示している。図２のインデックスは、地図データベースから得られることになり、これは、地図データベース・アプリケーション・ディベロッパーに伝えることができる。このインデックスは、「Ｓｔｒｅｅｔ Ｓｅｇｍｅｎｔｓ（ストリートセグメント）」と称される表１、「Ａｄｄｒｅｓｓ Ｐｏｉｎｔｓ（アドレスポイント）」と称される表２、および、「Ｓｈａｐｅ Ｐｏｉｎｔｓ（形状点）」と称される表３を含む。図２の表１に示されるエントリは、図１に示される模範的なストリートセグメントなどの所与のストリートセグメントに関するものである。
【００１９】
図２の表１は、ストリートセグメントに関するエントリを示しており、「ｗｈａｔ（何）」の欄、「ｔｙｐｅ（タイプ）」の欄、「ｃｏｍｍｅｎｔ（コメント）」の欄を含む。この実施形態では、表１に関して、「何」の欄と「タイプ」の欄のエントリだけを必要とする。「コメント」の欄は、この表１の実施形態では必要でなく、省略可能な欄である。タイプがポインタである第１のテーブル・エントリＳｅｇｓｉｄｅ＿ＩＤは、ストリートセグメントの一意の識別子（unique identifier)、すなわち、それぞれのストリート・ブロック側につき１つの識別子である。タイプが英数字である次のテーブル・エントリＨＮＲ＿ｆｒｏｍは、このストリートセグメントの「ｆｒｏｍ」端上の家屋番号である。これは、そのアドレスレンジの一部である。図１から、このストリートセグメントの「ｆｒｏｍ」端上の家屋番号は、「２ Ｍａｉｎ Ｓｔｒｅｅｔ」である。タイプが数字である次のテーブル・エントリＦｒｏｍ＿ｌａｔｌｏｎは、「ｆｒｏｍ」ノードの経度と緯度である。図１では、Ｆｒｏｍ＿ｌａｔｌｏｎは、「２ Ｍａｉｎ Ｓｔｒｅｅｔ」の経度と緯度である。タイプが英数字である次のテーブル・エントリＨＮＲ＿ｔｏは、このストリートセグメントの「ｔｏ」端上の家屋番号である。図１から、このストリートセグメントの「ｔｏ」端は、「９８ Ｍａｉｎ Ｓｔｒｅｅｔ」である。タイプが数字である次のテーブル・エントリＴｏ＿ｌａｔｌｏｎは、「ｔｏ」ノードの経度と緯度である。図１では、Ｔｏ＿ｌａｔｌｏｎは、「９８ Ｍａｉｎ Ｓｔｒｅｅｔ」の経度と緯度である。タイプがポインタである次のテーブル・エントリＳｔｒｅｅｔｎａｍｅ＿ＩＤは、このストリート名の表のインデックスである。このストリートのそれぞれの側が、複数のストリート名で知られていることがあるので、タイプがポインタである残りのテーブル・エントリ（Ａｌｉａｓ１＿ｓｔｒｎｍ＿ＩＤ〜ＡｌｉａｓＮ＿ｓｔｒｎｍ＿ＩＤ）は、それぞれの側に対する代替ストリート名に使用される。例えば、Ｓａｎ Ｆｒａｎｃｉｓｃｏでは、Ｃａｅｓａｒ Ｃｈａｖｅｚ Ｓｔｒｅｅｔは、Ａｒｍｙ Ｓｔｒｅｅｔとしても知られている。
【００２０】
アドレスポイントを示す図２の表２は、「何」の欄、「タイプ」の欄、「コメント」の欄を含む。この実施形態では、表２に関して、「何」の欄と「タイプ」の欄のエントリだけを必要とする。「コメント」の欄は、この表２の実施形態では必要でなく、省略可能な欄である。第１のテーブル・エントリＳｅｇｓｉｄｅ＿ＩＤは、ストリートセグメントの一意の識別子、すなわち、それぞれのストリート・ブロック側につき１つの識別子であって、ポインタのタイプを持っている。表１もテーブル・エントリＳｅｇｓｉｄｅ＿ＩＤを持っているので、Ｓｅｇｓｉｄｅ＿ＩＤはまた、表１のストリートセグメントからのリンクでもある。タイプがポインタである次のテーブル・エントリＡｄｄｒｐｔ＿ＩＤは、一意のアドレスポイント識別子である。図１から、一意のアドレスポイント識別子の例として、「１２ Ｍａｉｎ Ｓｔｒｅｅｔ」、「２６ Ｍａｉｎ Ｓｔｒｅｅｔ」、「３４ Ｍａｉｎ Ｓｔｒｅｅｔ」がある。タイプがポインタである次のテーブル・エントリ（ＨＮＲ＿ｓｔａｒｔ、ＨＮＲ＿ｅｎｄ）は、アドレスポイントに関して開始する家屋番号と終了する家屋番号である。アドレスポイントは、家屋番号レンジ（家屋番号の連なり、house number range）、例えばアパートメントビルディングを持つこともある。しかしながら、アドレスポイント「１２ Ｍａｉｎ Ｓｔｒｅｅｔ」に対する開始する家屋番号と、終了する家屋番号は、単に１２と１２だけである。タイプがポインタである次のテーブル・エントリＳｔｒｅｅｔｎａｍｅ＿ＩＤは、このストリート名の表のインデックスである。このストリートのそれぞれの側が、複数のストリート名で知られていることがあるので、タイプがポインタであるテーブル・エントリ（Ａｌｉａｓ１＿ｓｔｒｎｍ＿ＩＤ〜ＡｌｉａｓＮ＿ｓｔｒｎｍ＿ＩＤ）は、それぞれの側に対する代替ストリート名に使用される。これらの名称は、基礎になるセグメント上の名称、基礎になるセグメント上の名称のサブセット、あるいは他のバニティ名（vanity name）と同一であることもある。例えば、アドレスポイントは、そのアドレスポイントが沿って位置づけられているストリートセグメント名（例えば、仮想Ｆｒｏｎｔ Ｓｔｒｅｅｔ）とは異なるバニティ名（例えば、１ Ｍｅｄｉｃａｌ Ｃｅｎｔｅｒ）で知られていることがある。最後に、タイプがポインタである最後のテーブル・エントリＬａｔ／ｌｏｎは、このアドレスポイントの経度と緯度である。図１では、アドレスポイント「１２ Ｍａｉｎ Ｓｔｒｅｅｔ」のＬａｔ／ｌｏｎは、このアドレスポイントの経度と緯度である。
【００２１】
形状点を示す図２の表３は、「何」の欄、「タイプ」の欄、「コメント」の欄を含む。この実施形態では、表３に関して、「何」の欄と「タイプ」の欄のエントリだけを必要とする。「コメント」の欄は、この表３の実施形態では必要でなく、省略可能な欄である。第１のテーブル・エントリＳｅｇｓｉｄｅ＿ＩＤは、ストリートセグメントの一意の識別子、すなわち、それぞれのストリート・ブロック側につき１つの識別子であって、ポインタのタイプを持っている。表１もテーブル・エントリＳｅｇｓｉｄｅ＿ＩＤを持っているので、Ｓｅｇｓｉｄｅ＿ＩＤはまた、表１のストリートセグメントからのリンクでもある。タイプが数字である最後のテーブル・エントリ（Ｌａｔ／ｌｏｎ１〜Ｌａｔ／ｌｏｎ Ｎ）は、このストリートセグメントに沿った各形状点の経度と緯度である。
【００２２】
本発明の住所情報に関するデータベースまたはインデックスは、多くのエントリを含むであろう。本発明の実施形態では、すべてのストリートセグメントと、それらの対応するエントリが、必ずしも、関連するアドレスレンジを持つとは限らない。本発明の実施形態では、すべてのストリートセグメントと、それらの対応するデータベースまたはインデックスのエントリが、必ずしも、関連する１つまたは複数の形状点を持つとは限らない。さらに、ソフトウェア分野における当業者に明らかとなるように、住所情報に関するインデックスを除き、他の表現が、熟練のプログラマにより生み出されることもある。
【００２３】
図３は、図２のインデックスを編集して、アプリケーション・データ構造にする一実施形態を示している。図３は、地図データベース・アプリケーション・ディベロッパーが、どのように図２のインデックスを編集して、ソフトウェア・アプリケーションにすることになるのか一例を示している。図示されるように、この編集は、バイナリツリー（binary tree)の形式を取っている。それぞれのストリート名では、このデータ構造は、セグメント側（Ｓｅｇｓｉｄｅ１＿ＩＤ）ごとに、このセグメント側の最小の潜在的家屋番号（Ｐｏｔ＿ｌｏ）、このセグメント側の最小の潜在的家屋番号の経度と緯度（Ｌａｔｌｏｎ＿ｌｏ）、このセグメント側の最大の潜在的家屋番号（Ｐｏｔ＿ｈｉ）、および、このセグメント側の最大の潜在的家屋番号の経度と緯度（Ｌａｔｌｏｎ＿ｈｉ）を含む。このセグメント側のそれぞれのアドレスポイント（Ａｄｄｒｐｔ１＿ＩＤ〜ＡｄｄｒｐｔＮ＿ＩＤ）では、このデータ構造は、それぞれのアドレスポイントにて最小の実際の家屋番号（ＨＮＲ＿ｌｏ）、それぞれのアドレスポイントにて最大の実際の家屋番号（ＨＮＲ＿ｈｉ）、および、それぞれのアドレスポイントの経度と緯度（Ｌａｔｌｏｎ）を含む。
【００２４】
図４は、アドレスポイント用として、擬似コードの一実施形態を示している。利用者によりローカリティ（locality）が定められると、擬似コードが始まって、特定のストリート名を持つストリートセグメントの探索範囲を限定する。まず最初に、この擬似コードは、利用者が要望する上記ローカリティ内の正確なストリート名を用いて、データベース中に、アドレスポイントがあるかどうか判定する。入力された所望のストリート名を持つすべてのセグメント側を、図２のインデックスから取得し、次に、セグメント側ごとに、このソフトウェアは、ＨＮＲ＿ｌｏ＜＝ａｄｄｒｅｓｓ＜＝ＨＮＲ＿ｈｉとなるように、セグメント側上のそれぞれのアドレスポイントから所望の家屋番号を探索することで、適切なアドレスポイントを捜す。ここで、ＨＮＲ＿ｌｏとＨＮＲ＿ｈｉは、図３から、このセグメント側に対するアドレスポイントのそれぞれ最小と最大の実際の家屋番号であり、また、「ａｄｄｒｅｓｓ」は、所望の住所である。アドレスポイントが見出される場合には、この位置は、このアドレスポイントに対する緯度／経度であり、また、その位置が「ｆｏｕｎｄ（見出されている）」ことを示す返答がある。例えば、所望の住所が、アドレスポイントである２６ Ｍａｉｎ Ｓｔｒｅｅｔである場合には、このアドレスポイントの緯度と経度が知られているために、地図上の位置が見出されている。
【００２５】
アドレスポイントが見出されなかった場合には、所望の家屋番号が、このセグメント側の２つのアドレスポイント間にあるか、あるいは、このセグメントに対する全アドレスレンジ内にあるかどうか判定する。これは、Ｐｏｔ＿ｌｏ＜＝ａｄｄｒｅｓｓ＜＝Ｐｏｔ＿ｈｉとなるように、それぞれのセグメント側から、所望の住所を探索することで、達成される。ここで、Ｐｏｔ＿ｌｏとＰｏｔ＿ｈｉは、図３から、このセグメント側に対して、それぞれ最小と最大の潜在的家屋番号であり、また、「ａｄｄｒｅｓｓ」は、所望の住所である。図１のＭａｉｎ Ｓｔｒｅｅｔの例では、Ｐｏｔ＿ｌｏとＰｏｔ＿ｈｉが、このセグメント側の端点（それぞれ、２と９８）にセットされることになる。所望の住所を含む潜在的なレンジが見出されない場合には、「ｎｏｔ＿ｆｏｕｎｄ」を戻す。
【００２６】
しかしながら、この潜在的なアドレスレンジが所望の住所を実際に含む場合には、補間に使用するための取り囲む２つのもっとも近い実際または潜在的なアドレスポイントを取得する。これは、図３から、変数「ｌｏｗ（小さい数字）」をＰｏｔ＿ｌｏにセットすることで達成される。ここで、Ｐｏｔ＿ｌｏは、このセグメント側に対して最小の潜在的家屋番号である。このセグメント側上のそれぞれのアドレスポイント（小さい数字から大きい数字へ）では、ａｄｄｒｅｓｓ＞＝ＨＮＲ＿ｌｏの場合に、変数「ｌｏｗ」に対する新たな値はＨＮＲ＿ｌｏである。ここで、ＨＮＲ＿ｌｏは、図３から、このアドレスポイントでの最小の実際の家屋番号であり、また、「ａｄｄｒｅｓｓ」は、所望の家屋番号である。次に、このセグメント側上のそれぞれのアドレスポイント（大きい数字から小さい数字へ）では、ａｄｄｒｅｓｓ＜＝ＨＮＲ＿ｈｉの場合に、変数「ｈｉｇｈ（大きい数字）」に対する新たな値はＨＮＲ＿ｈｉである。ここで、ＨＮＲ＿ｈｉは、図３から、このアドレスポイントでの最大の実際の家屋番号であり、また、「ａｄｄｒｅｓｓ」は、所望の住所である。図４中の擬似コードのこの時点において、補間に使用するための最適な２つの実際または潜在的なアドレスポイントを計算して、「ｌｏｗ」と「ｈｉｇｈ」とし、それらを、このセグメント側の取り囲む２つのもっとも近いアドレスポイント、１つのアドレスポイントと１つのセグメント側の端点、または２つのセグメント側の端点に、好みの降順でセットした。
【００２７】
例えば、図１から、３０ Ｍａｉｎ Ｓｔｒｅｅｔの所望の住所では、図４の擬似コードは、「ｌｏｗ」と「ｈｉｇｈ」を計算して、それぞれ２６と３４とすることになる。ここで、２６と３４は２つのアドレスポイントである。図１からの他の例では、また、６６ Ｍａｉｎ Ｓｔｒｅｅｔの所望の住所では、この擬似コードは、「ｌｏｗ」と「ｈｉｇｈ」を計算して、それぞれ、３４と９８とすることになる。ここで、３４はアドレスポイントであり、また、９８は、セグメント側のアドレスレンジの端点である。
【００２８】
最後に、図４では、この擬似コードは、図１に示されるように、このストリートセグメントの両端にて、端点ＥＰを、もっとも近い形状点ＳＰに結ぶだけでなく、形状点ＳＰも結ぶ直線で定められる通り、このストリートセグメント側の彎曲の区分的線形近似を考慮に入れて、これらの所望の住所を、それが「ｌｏｗ」と「ｈｉｇｈ」の間にあるように補間する。次に、この擬似コードは、補間される所望の住所が「ｆｏｕｎｄ（見出された）」と返答する。例えば、図１の例を使用すると、３０ Ｍａｉｎ Ｓｔｒｅｅｔの所望の住所は、補間により見出されて、補間点ＩＰとなる。補間点ＩＰは、このストリートセグメント側に沿って、アドレスポイント２６とアドレスポイント３４の近くにある２つの形状点ＳＰを結ぶ直線に沿って、アドレスポイント２６とアドレスポイント３４との間で見出されることになる。次に、所望の住所の位置は、地図データベース・アプリケーション・コンバータ（map database-to-application converter）とデバイス・アプリケーション・ソフトウェア（device application software）により、地図上で利用者に表示されることになる。
【００２９】
この補間の一実施形態では、上記ストリートセグメントの両端にて、端点ＥＰを、もっとも近い形状点ＳＰに結ぶだけでなく、連続する形状点ＳＰも結ぶ直線で示される通り、図４において区分的線形表現を利用して、このストリートセグメント側の彎曲に近づける。形状点ＳＰがまったく与えられない場合には、端点ＥＰを結ぶ直線を利用して、このセグメント形状を表現する。
【００３０】
補間の他の実施形態では、所与のストリート上の所望の家屋番号にもアドレスレンジにも、アドレスポイントがまったくない場合には、アプリケーション・ソフトウェアは、デフォルトにおいて、その基礎になるストリートセグメント上のアドレスレンジから、この位置を補間することがある。あるいは、このストリートセグメント上にアドレスポイントがいくつか存在する場合には、アドレスポイントとストリートセグメントの端点との組合せが、補間に利用されることもある。図１では、例えば、家屋番号６６ Ｍａｉｎ Ｓｔｒｅｅｔの位置は、それが、アドレスポイント３４と、ストリートセグメントの端点の家屋番号９８との中間地点にあるように、線形補間されることもある。
【００３１】
最適な位置決めに用いられる探索順序は、（１）地図データベース・セグメント上で得られる場合には、実際のアドレスポイントを取得する、（２）得られない場合には、この地図データベース・セグメント上で数値的にもっとも近く、かつ取り囲む２つのアドレスポイント間を補間する、（３）取り囲むアドレスポイントが１つしか得られない場合には、そのアドレスポイントと、実際または潜在的なアドレスレンジからのセグメント端点の住所との間を補間する、（４）アドレスポイントがまったく得られない場合には、この実際または潜在的なアドレスレンジからの２つのセグメント端点に対する取り囲むアドレスレンジ間を補間する。
【００３２】
補間に関する本発明の実施形態は、他の線形表現とともに用いられることがある。図４の補間例、並びに、補間の他の実施形態に使用されるこれらの線形表現は、家屋番号を、このストリートセグメントに沿って均等に割り当てるときに使用される。しかしながら、他の実施形態では、他のタイプの補間が行われることもある。例えば、ストリートセグメントの一端に家屋を集める場合には、対数補間アルゴリズム（logarithmic interpolation algorithm）が用いられることもある。
【００３３】
本発明は、地図データベースの変更をともなうが、しかるに、他のベンダーは、地図データベース、またはそのデータの派生編集（derived compilation）を利用する地図データベース・アプリケーション・コンバータとデバイス・アプリケーション・ソフトウェアを提供する。デバイス・アプリケーション・ソフトウェアは、利用者の入力に応答して、その派生地図データにアクセスして、それを処理する。利用者へのデバイス・アプリケーション・ソフトウェアの出力は、リスト、文章、地図または画像などのグラフィカル表示、発話などの音声、あるいは他のタイプの出力で表されることもある。多くのＧＩＳ、インターネット、ナビゲーションのアプリケーションは、本発明を使用する場合もある。これらのアプリケーションは、ジオコーディング・アプリケーション（文章／リストを基本とする）、ルーティング／方向アプリケーション（グラフィカル／リスト／発話を基本とする）、および、グラフィカル・ベースの表示アプリケーションを含む。これらのアプリケーションは、とりわけ、ナビゲーションのアプリケーション、インターネット・ベースのアプリケーション、地理情報システム（ＧＩＳ）を含むこともある。このアプリケーションは、マッピング・プログラム、ナビゲーション・プログラム、または何か他のタイプのプログラムであることもある。上に説明されているように、地図アプリケーションの消費者は、所望の場所を捜し出すことができるように、様々な装置およびシステムを持っている。これらの装置およびシステムは、運転者がストリートや道路にナビゲートでき、また所望の場所を入力できるようにする車載ナビゲーション・システム、携帯情報端末（「ＰＤＡ」）や、同一機能を果たせる携帯電話などのハンドヘルド装置、および、所望の結果を利用するか、または描写して利用者が地図にアクセスできるようにするインターネット・アプリケーションの形式を取っている。この開示の目的では、このような結果はすべて、単に「ｐｌａｃｅｓ（場所）」として定義されるだけである。
【００３４】
図５は、仮想インターネット・ベース・システム(hypothetical Internet-based system)に使用される模範的な実施形態を示している。仮想インターネット・ベース・システムは、ＰＤＡや携帯電話などのハンドヘルド装置上で、あるいは、コンピュータまたはラップトップ上で用いられることもある。模範的な探索は、「Ｓｅａｒｃｈ（探索）」ボタンの隣りに示される通り、３５０ ５ｔｈ Ａｖｅ．，Ｎｅｗ Ｙｏｒｋ、すなわちＥｍｐｉｒｅ Ｓｔａｔｅ Ｂｕｉｌｄｉｎｇの住所に対して、仮想インターネット・マッピング・アプリケーションを用いて、利用者により行われる。仮想インターネット・マッピング・アプリケーションは、この時点では、Ｗｅｓｔ ３４ｔｈ Ｓｔｒｅｅｔで、かつ５ｔｈ Ａｖｅｎｕｅの付近で、点を含む泡で、この地図上の住所の位置を表示している。その一方、本発明は、アドレスポイントと、おそらく補間を利用して、ビルまたはビルが位置づけられている画地のより正確な位置（この位置は、明らかに地図上の上記泡の所ではない）を見出すことになる。本発明は、所与のブロックの両端にて、あるいは所与のブロックの任意の側の内部で、どんな住所に対しても、より正確なサブブロック位置決め情報を提供できる。
【００３５】
図６は、携帯情報端末（ＰＤＡ）などの携帯用ハンドヘルド装置上で使用される模範的な実施形態を示している。この装置はまた、例えば携帯電話であることもある。ＰＤＡ地図ソフトウェアでは、１５０ Ｃｅｎｔｒａｌ Ｐａｒｋ Ｗｅｓｔに向かう運転方向を求める利用者により、模範的な探索が行われる。このＰＤＡ地図ソフトウェアは、本発明を利用して、１５０ Ｃｅｎｔｒａｌ Ｐａｒｋ Ｗｅｓｔの位置を、このＰＤＡ地図ソフトウェアを用いて正確に表示する。
【００３６】
図７は、全地球測位システム（ＧＰＳ）などの車載ナビゲーション・システム上で使用される模範的な実施形態を示している。ＧＰＳ地図ソフトウェアでは、ＧＰＳ地図ソフトウェアの下端に示される３５ Ｗｅｓｔ Ｈｉｌｌ Ｒｏａｄに向かう運転方向を求める運転者により、模範的な探索が行われる。運転者が、ＧＰＳ地図ソフトウェアを用いて自分の目的地に達すると、このＧＰＳ地図ソフトウェアは、本発明を利用して、３５ Ｗｅｓｔ Ｈｉｌｌ Ｒｏａｄの位置を正確に表示する。
【００３７】
図８は、航空写真上に重ねられたアドレスポイントの一例を示す模範的な実施形態を示している。この例では、このブロック内のすべてのビルは、アドレスポイントに指定されており、したがって、家屋番号またはビル番号のどれについても、その位置に近づけるのに、補間はまったく行わない。Ｆｏｒｍｏｓａ Ａｖｅｎｕｅ、Ｌｅｘｉｎｇｔｏｎ Ａｖｅｎｕｅ、Ｄｅｔｒｏｉｔ Ｓｔｒｅｅｔに関するストリートセグメントの名称も、この航空写真上に重ねられている。図示されるＦｏｒｍｏｓａ Ａｖｅｎｕｅに関するストリートセグメントの一側では、そのアドレスレンジは１１２２〜１１５４である。Ｌｅｘｉｎｇｔｏｎ Ａｖｅｎｕｅに関するストリートセグメントの一側では、そのアドレスレンジは７１６８〜７１５４である。このＬｅｘｉｎｇｔｏｎ Ａｖｅｎｕｅのストリートセグメントの例は、ブロック全体にわたっていないビルの位置があるアドレスレンジの好例である。Ｄｅｔｒｏｉｔ Ａｖｅｎｕｅに関するストリートセグメントの一側では、そのアドレスレンジは、１１０７〜１１５５である。航空写真では、このアドレスレンジは、ブロック全体にわたっているビルがある唯一のものである。
【００３８】
図９は、本発明の実施形態に使用できる模範的なシステム９００のブロック図を示している。この図は、構成要素を論理的に別々なものとして描いているが、そのような描写は、単に例示目的にすぎない。この図に描かれた構成要素を組み合わせるか、あるいは、別々のソフトウェア、ファームウェア、および／またはハードウェア・コンポーネントに分けられることが当業者には明らかになろう。さらに、このような構成要素をどのように組み合わせるか、あるいは分けるかに関係なく、それらの構成要素が、同一のコンピューティング装置／システム上で実行できるか、あるいは、１つまたは複数のネットワークもしくは他の適切な通信手段により接続された異なるコンピューティング装置／システムに、それらの構成要素を割り当てられることも当業者には明らかになろう。
【００３９】
図９に示されるように、システム９００は、一般に、１つまたは複数のメモリ９１２、１つまたは複数のプロセッサ９１４、および、１つまたは複数のある種の記憶装置またはリポジトリ９１６を含むことのあるコンピューティング装置９１０を含んでいる。システム９００はさらに、ディスプレイ装置９１８も含むことがあり、ディスプレイ装置９１８上ではグラフィカル・ユーザー・インターフェースすなわちＧＵＩ９２０が動作して、このシステムが、地図および他の情報を利用者に表示できるようにしている。利用者は、このコンピューティング装置を利用して、例えば、ローカリティを地図上に表示するか、あるいは、運転方向を、地図上のルートとして、および／またはテキスト方向として表示するように求める。
【００４０】
地図データベース９３０は、コンピューティング装置またはシステム９１０の外部記憶装置として示されているが、ただし、地図データベース９３０は、ときには、記憶装置９１６と同じ記憶装置であることもある。本発明の実施形態により、地図データベース９３０は、地図セグメント（map segment）の表とインデックス９３２、アドレスポイントの表とインデックス９３４、および、形状点の表とインデックス９３６を含む。
【００４１】
プロプライエタリ（メーカー独自仕様）地図データベース作成ソフトウェア９４０は、実世界のローカリティ情報源と緯度／経度情報源９６０を利用して、地図データベース９３０において、地図セグメントの表とインデックス９３２、アドレスポイントの表とインデックス９３４、および、形状点の表とインデックス９３６をそれぞれ作成する。地図データベース９３０からの情報は、最後にコンピューティング装置９１０の利用者が利用する地図データベース・アプリケーション・コンバータとデバイス・アプリケーション・ソフトウェア９５０で使用される。地図データベース・アプリケーション・コンバータとデバイス・アプリケーション・ソフトウェア９５０は、利用者のコンピューティング装置９１０にはリモートとして図示されているが、ただし、利用者のコンピューティング装置９１０上にあることもある。
【００４２】
ソフトウェア分野における当業者に明らかとなるように、熟練プログラマであれば、本開示内容の教示に基づいて、適切なソフトウェア・プログラムを容易に作成することができる。本発明の実施形態はまた、当業者には容易に明らかとなるように、特定用途向け集積回路を用意することにより、あるいは、従来の構成回路から成る適切な回路網を相互接続することにより、実施されることがある。
【００４３】
本発明の実施形態は、本発明の実施形態のプロセスをどれでも実行するようにコンピュータをプログラムするのに用いられる命令が格納されている記憶媒体（１つまたは複数）であるコンピュータ・プログラム製品を含む。この記憶媒体は、フロッピー（登録商標）ディスク、光ディスク、ＤＶＤ、ＣＤ−ＲＯＭ、超小型ハードディスク、および光磁気ディスクを含む任意タイプのディスク、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、ＤＲＡＭ、ＶＲＡＭ、フラッシュメモリ・デバイス、磁気式または光学式のカード、ナノシステム（分子メモリＩＣを含む）、あるいは、命令および／またはデータの格納に適した任意タイプのシステムまたはデバイスを含む（ただし、それらには限定されない）こともある。
【００４４】
本発明の実施形態は、上記のコンピュータ読取り可能媒体（１つまたは複数）のどれか１つに格納されるものとして、汎用型／専用型のコンピュータまたはマイクロプロセッサのハードウェアを制御するソフトウェアと、このコンピュータまたはマイクロプロセッサが、本発明の実施形態の結果を利用して、人間の利用者または他の機構と対話できるようにするソフトウェアを両方とも含む。このようなソフトウェアは、デバイス・ドライバ、オペレーティングシステム、ユーザー・アプリケーションを含む（ただし、それらには限定されない）ことがある。最後に、このようなコンピュータ読取り可能媒体はさらに、上述の通り、本発明の実施形態を実行するソフトウェアも含む。
【００４５】
上記の汎用型／専用型のコンピュータまたはマイクロプロセッサのプログラムすなわちソフトウェアに含まれているものは、本発明の教示を実施するソフトウェア・モジュールである。本発明の実施形態は、コンピュータ分野における当業者に明らかとなるように、本開示内容の教示によりプログラムされた従来の汎用型または専用型のデジタル・コンピュータまたはマイクロプロセッサを利用して、都合よく実施されることがある。
【００４６】
本発明の上の説明は、図示と説明の目的で与えられてきた。この説明は、すべてを尽くすつもりはないし、また、本発明の実施形態を、開示されている通りの形態に限定するつもりもない。多くの変更例や変形例が、当事者には明らかになろう。これらの実施形態は、本発明の原理、および本発明の実地応用をもっともよく説明するために、選択され、述べられ、それにより、他の当業者が、本発明を様々な実施形態に関して理解することができ、また、特定の用途に適した様々な変更が考えられた。本発明の範囲は、併記の特許請求の範囲、および、それらと同等なものにより定義されることが意図される。
【図面の簡単な説明】
【００４７】
【図１】所与の都市の仮想メインストリートの１ブロックの一側のストリートセグメントの略図と、そのストリートセグメントに沿って、形状点と称される特定の地点間に直線を引いて形成されるこのストリートセグメントの区分的線形表現である。
【図２】ストリートセグメント、アドレスポイント、形状点、および、それらの位置に関する表を含む住所情報のインデックスの一実施形態を示す。
【図３】図２のインデックスを編集して、アプリケーション・データ構造にする一実施形態を示す。
【図４】アドレスポイント用として、擬似コードの一実施形態を示す。
【図５】仮想インターネット・ベース・システムに使用される模範的な実施形態を示す。
【図６】携帯情報端末（ＰＤＡ）などのハンドヘルド装置上で使用される模範的な実施形態を示す。
【図７】全地球測位システム（ＧＰＳ）などの車載ナビゲーション・システム上で使用される模範的な実施形態を示す。
【図８】航空写真上に重ねられたアドレスポイントの模範的な実施形態を示す。
【図９】地図データベース５０４の実施形態が、地図データベース・アプリケーション５０２とは別々であることを示す。
【特許請求の範囲】
【請求項１】
アドレスレンジを持つ少なくとも１つのストリートセグメントと、
前記ストリートセグメントの前記アドレスレンジ内の家屋番号、ビル番号、またはアドレスレンジの位置に対応する少なくとも１つのアドレスポイントと、
を含む、記憶媒体上に格納できる地図データベース。
【請求項２】
アドレスレンジを持たない少なくとも１つのストリートセグメントをさらに含む請求項１に記載の地図データベース。
【請求項３】
一部がアドレスレンジを持ち、また一部がアドレスレンジを持たない１つまたはそれ以上のストリートセグメントをさらに含む請求項１に記載の地図データベース。
【請求項４】
関連する少なくとも１つのアドレスポイントを持たない少なくとも１つのストリートセグメントをさらに含む請求項１に記載の地図データベース。
【請求項５】
一部が、関連する少なくとも１つのアドレスポイントを持ち、また一部が、関連する少なくとも１つのアドレスポイントを持たない１つまたはそれ以上のストリートセグメントをさらに含む請求項１に記載の地図データベース。
【請求項６】
前記少なくとも１つのストリートセグメントの前記アドレスレンジが、第１の端点と第２の端点により表される請求項１に記載の地図データベース。
【請求項７】
前記第１の端点、前記第２の端点、および前記アドレスポイントのそれぞれが、数値地理参照システムにそれぞれ関連づけられる請求項６に記載の地図データベース。
【請求項８】
前記数値地理参照システムが緯度と経度を含む請求項７に記載の地図データベース。
【請求項９】
前記第１の端点と前記第２の端点がそれぞれ、実際のアドレスレンジを確立する実際の家屋番号に対応する請求項６に記載の地図データベース。
【請求項１０】
前記第１の端点と前記第２の端点がそれぞれ、潜在的なアドレスレンジとなるアドレスレンジを確立する潜在的な家屋番号に対応する請求項６に記載の地図データベース。
【請求項１１】
前記少なくとも１つのストリートセグメントの曲線に沿った１つまたはそれ以上の形状点が前記少なくとも１つのストリートセグメントに関連づけられる請求項１に記載の地図データベース。
【請求項１２】
前記１つまたはそれ以上の形状点がそれぞれ、数値地理参照システムに関連づけられる請求項１１に記載の地図データベース。
【請求項１３】
前記数値地理参照システムが緯度と経度を含む請求項１２に記載の地図データベース。
【請求項１４】
実際のストリートのストリートセグメントを識別する少なくとも１つのストリートセグメント・データエントリと、前記ストリートセグメント上にある特定の家屋番号、ビル番号、またはアドレスレンジの位置に対応する少なくとも１つのアドレスポイント・データエントリとを持つインデックスを含む、記憶媒体上に格納できる地図データベース。
【請求項１５】
前記インデックスが、関連する少なくとも１つのアドレスポイント・データエントリを持たない少なくとも１つのストリートセグメント・データエントリをさらに含む請求項１４に記載の地図データベース。
【請求項１６】
一部が、関連する少なくとも１つのアドレスポイント・データエントリを持ち、また一部が、関連する少なくとも１つのアドレスポイント・データエントリを持たない１つまたはそれ以上のストリートセグメント・データエントリを、前記インデックスがさらに含む請求項１４に記載の地図データベース。
【請求項１７】
前記第１のデータエントリのそれぞれが、前記ストリートセグメントの両端の経度と緯度に対応する前記ストリートセグメントの第１の端点と第２の端点を含み、また、前記アドレスデータポイントエントリが、前記ストリートセグメント上にある家屋番号またはアドレスレンジの経度と緯度に対応する請求項１４に記載の地図データベース。
【請求項１８】
前記インデックスが、前記アドレスデータポイントエントリごとに、前記特定の家屋番号またはアドレスレンジが位置づけられるストリート名、および、前記名称を持つストリート上の住所の家屋番号またはアドレスレンジのリストに対応するエントリをさらに含む請求項１４に記載の地図データベース。
【請求項１９】
所望の場所に対応する情報を利用者に提供するシステムであって、
アドレスレンジと、前記アドレスレンジ内にある少なくとも１つのアドレスポイントとを持つ少なくとも１つのストリートセグメントを有する地図データベースと、
利用者からの所望の場所に関する問合せに応答して、前記アドレスレンジ内の前記少なくとも１つのアドレスポイントを取得するためのアプリケーション・プログラムと、
を含むシステム。
【請求項２０】
前記地図データベースが、アドレスレンジを持たない少なくとも１つのストリートセグメントをさらに含む請求項１９に記載のシステム。
【請求項２１】
一部がアドレスレンジを持ち、また一部がアドレスレンジを持たない１つまたはそれ以上のストリートセグメントを、前記地図データベースがさらに含む請求項１９に記載のシステム。
【請求項２２】
前記地図データベースが、関連する少なくとも１つのアドレスポイントを持たない少なくとも１つのストリートセグメントをさらに含む請求項１９に記載のシステム。
【請求項２３】
一部が、関連する少なくとも１つのアドレスポイントを持ち、また一部が、関連する少なくとも１つのアドレスポイントを持たない１つまたはそれ以上のストリートセグメントを、前記地図データベースがさらに含む請求項１９に記載のシステム。
【請求項２４】
前記利用者の所望の場所に対応するアドレスポイントが得られない場合には、前記アプリケーション・プログラムが、数値的にもっとも近く、かつ前記所望の場所を取り巻く２つのアドレスポイント間、あるいは、前記ストリートセグメントのアドレスポイントと端点との間を補間して、前記所望の場所の近似位置を決定することになる請求項１９に記載のシステム。
【請求項２５】
前記少なくとも１つのストリートセグメントの曲線に沿った１つまたはそれ以上の形状点が、前記補間において使用される請求項２４に記載のシステム。
【請求項２６】
形状点間に直線を引いて、前記少なくとも１つのストリートセグメントの曲線に近づける請求項２５に記載のシステム。
【請求項２７】
アドレスポイント、端点、形状点が、経度と緯度に関連づけられる請求項２５に記載のシステム。
【請求項２８】
前記システムがインターネット・ベース・システムを含む請求項１９に記載のシステム。
【請求項２９】
前記システムが車載ナビゲーション・システムを含む請求項１９に記載のシステム。
【請求項３０】
所望の場所に対応する情報を利用者に提供する携帯用ハンドヘルド装置であって、
アドレスレンジと、前記アドレスレンジ内にある少なくとも１つのアドレスポイントとを持つ少なくとも１つのストリートセグメントを有する地図データベースと、
利用者からの所望の場所に関する問合せに応答して、前記アドレスレンジ内の前記少なくとも１つのアドレスポイントを得られる場合、取得するアプリケーション・プログラムと、
を含む携帯用ハンドヘルド装置。
【請求項３１】
所望の場所に対応する情報を利用者に提供する地理情報システム（ＧＩＳ）ベースのアプリケーション・プログラムであって、
アドレスレンジと、前記アドレスレンジ内に位置する少なくとも１つのアドレスポイントとを持つ少なくとも１つのストリートセグメントを有する地図データベースを含み、利用者からの所望の場所に関する問合せに応答して、前記アドレスレンジ内の少なくとも１つのアドレスポイントが取得される地理情報システム（ＧＩＳ）ベースのアプリケーション・プログラム。
【請求項３２】
所望の場所の位置情報を利用者に提供する方法であって、
利用者によるストリート名の入力に応答して、前記ストリート名に関連する前記ストリートセグメントのすべてのアドレスポイントを、地図データベースから取得することと、
利用者が入力したビル住所番号に応答して、ビル住所番号に対して取得されたアドレスポイントを調べることと、
前記取得されたアドレスポイントのどれかが、前記入力されたビル住所番号に対応する場合には、前記対応する取得されたアドレスポイントを使用して、前記入力されたビル住所番号の位置を利用者に戻し、また、取得されたアドレスポイントが、前記入力されたビル住所番号にまったく対応しない場合には、前記取得されたアドレスポイントの少なくとも１つを使用して、前記入力されたビル住所番号の位置に近いポイントまで補間して、その近似位置を利用者に戻すことと、
を含む方法。
【請求項３３】
前記ストリートセグメントが、アドレスレンジを持たない請求項３２に記載の方法。
【請求項３４】
前記ストリートセグメントが、関連するアドレスポイントをまったく持たない請求項３２に記載の方法。
【請求項３５】
数値的にもっとも近く、かつ前記所望の場所を取り巻く２つの取得されたアドレスポイントに対して、前記補間を行う請求項３２に記載の方法。
【請求項３６】
アドレスポイントを１つしか取得できない場合には、前記１つの取得されたアドレスポイントと前記所望の場所を取り巻く前記ストリートセグメントの端点に対して、前記補間を行う請求項３２に記載の方法。
【請求項３７】
補間することが、前記少なくとも１つのストリートセグメントの曲線に沿って１つまたはそれ以上の形状点を使用することをさらに含む請求項３２に記載の方法。
【請求項３８】
形状点間に直線を引いて、前記少なくとも１つのストリートセグメントの曲線に近づけることをさらに含む請求項３７に記載の方法。
【請求項３９】
それぞれのアドレスポイントを、経度と緯度に関連づけることをさらに含む請求項３２に記載の方法。
【請求項４０】
それぞれの端点を、経度と緯度に関連づけることをさらに含む請求項３６に記載の方法。
【請求項４１】
それぞれの形状点を、経度と緯度に関連づけることをさらに含む請求項３７に記載の方法。
【請求項４２】
前記地図データベースが少なくとも１つのストリートセグメントのインデックスを含み、それぞれのストリートセグメントがアドレスレンジ、名称、少なくとも１つのアドレスポイントで定義され、また、それぞれのアドレスポイントが、前記少なくとも１つのストリートセグメントに沿った家屋番号またはアドレスレンジの位置を表し、さらに、前記インデックスが、それぞれのアドレスポイントに関連する家屋番号またはアドレスレンジをさらに含む請求項２８に記載の方法。
【請求項４３】
操作が格納されている機械可読媒体であって、
１つまたはそれ以上のプロセッサで処理されると、
利用者によるストリート名の入力に応答して、前記ストリート名に関連する前記ストリートセグメントのすべてのアドレスポイントを、地図データベースから取得するステップと、
利用者が入力したビル住所番号に応答して、ビル住所番号に対して取得されたアドレスポイントを調べるステップと、
前記取得されたアドレスポイントのどれかが、前記入力されたビル住所番号に対応する場合には、前記対応する取得されたアドレスポイントを使用して、前記入力されたビル住所番号の位置を利用者に戻し、また、取得されたアドレスポイントが、前記入力されたビル住所番号にまったく対応しない場合には、前記取得されたアドレスポイントの少なくとも１つを使用して、前記入力されたビル住所番号の位置に近いポイントまで補間して、その近似位置を利用者に戻すステップと、
をシステムに実行させる機械可読媒体。
【請求項１】
アドレスレンジを持つ少なくとも１つのストリートセグメントと、
前記ストリートセグメントの前記アドレスレンジ内の家屋番号、ビル番号、またはアドレスレンジの位置に対応する少なくとも１つのアドレスポイントと、
を含む、記憶媒体上に格納できる地図データベース。
【請求項２】
アドレスレンジを持たない少なくとも１つのストリートセグメントをさらに含む請求項１に記載の地図データベース。
【請求項３】
一部がアドレスレンジを持ち、また一部がアドレスレンジを持たない１つまたはそれ以上のストリートセグメントをさらに含む請求項１に記載の地図データベース。
【請求項４】
関連する少なくとも１つのアドレスポイントを持たない少なくとも１つのストリートセグメントをさらに含む請求項１に記載の地図データベース。
【請求項５】
一部が、関連する少なくとも１つのアドレスポイントを持ち、また一部が、関連する少なくとも１つのアドレスポイントを持たない１つまたはそれ以上のストリートセグメントをさらに含む請求項１に記載の地図データベース。
【請求項６】
前記少なくとも１つのストリートセグメントの前記アドレスレンジが、第１の端点と第２の端点により表される請求項１に記載の地図データベース。
【請求項７】
前記第１の端点、前記第２の端点、および前記アドレスポイントのそれぞれが、数値地理参照システムにそれぞれ関連づけられる請求項６に記載の地図データベース。
【請求項８】
前記数値地理参照システムが緯度と経度を含む請求項７に記載の地図データベース。
【請求項９】
前記第１の端点と前記第２の端点がそれぞれ、実際のアドレスレンジを確立する実際の家屋番号に対応する請求項６に記載の地図データベース。
【請求項１０】
前記第１の端点と前記第２の端点がそれぞれ、潜在的なアドレスレンジとなるアドレスレンジを確立する潜在的な家屋番号に対応する請求項６に記載の地図データベース。
【請求項１１】
前記少なくとも１つのストリートセグメントの曲線に沿った１つまたはそれ以上の形状点が前記少なくとも１つのストリートセグメントに関連づけられる請求項１に記載の地図データベース。
【請求項１２】
前記１つまたはそれ以上の形状点がそれぞれ、数値地理参照システムに関連づけられる請求項１１に記載の地図データベース。
【請求項１３】
前記数値地理参照システムが緯度と経度を含む請求項１２に記載の地図データベース。
【請求項１４】
実際のストリートのストリートセグメントを識別する少なくとも１つのストリートセグメント・データエントリと、前記ストリートセグメント上にある特定の家屋番号、ビル番号、またはアドレスレンジの位置に対応する少なくとも１つのアドレスポイント・データエントリとを持つインデックスを含む、記憶媒体上に格納できる地図データベース。
【請求項１５】
前記インデックスが、関連する少なくとも１つのアドレスポイント・データエントリを持たない少なくとも１つのストリートセグメント・データエントリをさらに含む請求項１４に記載の地図データベース。
【請求項１６】
一部が、関連する少なくとも１つのアドレスポイント・データエントリを持ち、また一部が、関連する少なくとも１つのアドレスポイント・データエントリを持たない１つまたはそれ以上のストリートセグメント・データエントリを、前記インデックスがさらに含む請求項１４に記載の地図データベース。
【請求項１７】
前記第１のデータエントリのそれぞれが、前記ストリートセグメントの両端の経度と緯度に対応する前記ストリートセグメントの第１の端点と第２の端点を含み、また、前記アドレスデータポイントエントリが、前記ストリートセグメント上にある家屋番号またはアドレスレンジの経度と緯度に対応する請求項１４に記載の地図データベース。
【請求項１８】
前記インデックスが、前記アドレスデータポイントエントリごとに、前記特定の家屋番号またはアドレスレンジが位置づけられるストリート名、および、前記名称を持つストリート上の住所の家屋番号またはアドレスレンジのリストに対応するエントリをさらに含む請求項１４に記載の地図データベース。
【請求項１９】
所望の場所に対応する情報を利用者に提供するシステムであって、
アドレスレンジと、前記アドレスレンジ内にある少なくとも１つのアドレスポイントとを持つ少なくとも１つのストリートセグメントを有する地図データベースと、
利用者からの所望の場所に関する問合せに応答して、前記アドレスレンジ内の前記少なくとも１つのアドレスポイントを取得するためのアプリケーション・プログラムと、
を含むシステム。
【請求項２０】
前記地図データベースが、アドレスレンジを持たない少なくとも１つのストリートセグメントをさらに含む請求項１９に記載のシステム。
【請求項２１】
一部がアドレスレンジを持ち、また一部がアドレスレンジを持たない１つまたはそれ以上のストリートセグメントを、前記地図データベースがさらに含む請求項１９に記載のシステム。
【請求項２２】
前記地図データベースが、関連する少なくとも１つのアドレスポイントを持たない少なくとも１つのストリートセグメントをさらに含む請求項１９に記載のシステム。
【請求項２３】
一部が、関連する少なくとも１つのアドレスポイントを持ち、また一部が、関連する少なくとも１つのアドレスポイントを持たない１つまたはそれ以上のストリートセグメントを、前記地図データベースがさらに含む請求項１９に記載のシステム。
【請求項２４】
前記利用者の所望の場所に対応するアドレスポイントが得られない場合には、前記アプリケーション・プログラムが、数値的にもっとも近く、かつ前記所望の場所を取り巻く２つのアドレスポイント間、あるいは、前記ストリートセグメントのアドレスポイントと端点との間を補間して、前記所望の場所の近似位置を決定することになる請求項１９に記載のシステム。
【請求項２５】
前記少なくとも１つのストリートセグメントの曲線に沿った１つまたはそれ以上の形状点が、前記補間において使用される請求項２４に記載のシステム。
【請求項２６】
形状点間に直線を引いて、前記少なくとも１つのストリートセグメントの曲線に近づける請求項２５に記載のシステム。
【請求項２７】
アドレスポイント、端点、形状点が、経度と緯度に関連づけられる請求項２５に記載のシステム。
【請求項２８】
前記システムがインターネット・ベース・システムを含む請求項１９に記載のシステム。
【請求項２９】
前記システムが車載ナビゲーション・システムを含む請求項１９に記載のシステム。
【請求項３０】
所望の場所に対応する情報を利用者に提供する携帯用ハンドヘルド装置であって、
アドレスレンジと、前記アドレスレンジ内にある少なくとも１つのアドレスポイントとを持つ少なくとも１つのストリートセグメントを有する地図データベースと、
利用者からの所望の場所に関する問合せに応答して、前記アドレスレンジ内の前記少なくとも１つのアドレスポイントを得られる場合、取得するアプリケーション・プログラムと、
を含む携帯用ハンドヘルド装置。
【請求項３１】
所望の場所に対応する情報を利用者に提供する地理情報システム（ＧＩＳ）ベースのアプリケーション・プログラムであって、
アドレスレンジと、前記アドレスレンジ内に位置する少なくとも１つのアドレスポイントとを持つ少なくとも１つのストリートセグメントを有する地図データベースを含み、利用者からの所望の場所に関する問合せに応答して、前記アドレスレンジ内の少なくとも１つのアドレスポイントが取得される地理情報システム（ＧＩＳ）ベースのアプリケーション・プログラム。
【請求項３２】
所望の場所の位置情報を利用者に提供する方法であって、
利用者によるストリート名の入力に応答して、前記ストリート名に関連する前記ストリートセグメントのすべてのアドレスポイントを、地図データベースから取得することと、
利用者が入力したビル住所番号に応答して、ビル住所番号に対して取得されたアドレスポイントを調べることと、
前記取得されたアドレスポイントのどれかが、前記入力されたビル住所番号に対応する場合には、前記対応する取得されたアドレスポイントを使用して、前記入力されたビル住所番号の位置を利用者に戻し、また、取得されたアドレスポイントが、前記入力されたビル住所番号にまったく対応しない場合には、前記取得されたアドレスポイントの少なくとも１つを使用して、前記入力されたビル住所番号の位置に近いポイントまで補間して、その近似位置を利用者に戻すことと、
を含む方法。
【請求項３３】
前記ストリートセグメントが、アドレスレンジを持たない請求項３２に記載の方法。
【請求項３４】
前記ストリートセグメントが、関連するアドレスポイントをまったく持たない請求項３２に記載の方法。
【請求項３５】
数値的にもっとも近く、かつ前記所望の場所を取り巻く２つの取得されたアドレスポイントに対して、前記補間を行う請求項３２に記載の方法。
【請求項３６】
アドレスポイントを１つしか取得できない場合には、前記１つの取得されたアドレスポイントと前記所望の場所を取り巻く前記ストリートセグメントの端点に対して、前記補間を行う請求項３２に記載の方法。
【請求項３７】
補間することが、前記少なくとも１つのストリートセグメントの曲線に沿って１つまたはそれ以上の形状点を使用することをさらに含む請求項３２に記載の方法。
【請求項３８】
形状点間に直線を引いて、前記少なくとも１つのストリートセグメントの曲線に近づけることをさらに含む請求項３７に記載の方法。
【請求項３９】
それぞれのアドレスポイントを、経度と緯度に関連づけることをさらに含む請求項３２に記載の方法。
【請求項４０】
それぞれの端点を、経度と緯度に関連づけることをさらに含む請求項３６に記載の方法。
【請求項４１】
それぞれの形状点を、経度と緯度に関連づけることをさらに含む請求項３７に記載の方法。
【請求項４２】
前記地図データベースが少なくとも１つのストリートセグメントのインデックスを含み、それぞれのストリートセグメントがアドレスレンジ、名称、少なくとも１つのアドレスポイントで定義され、また、それぞれのアドレスポイントが、前記少なくとも１つのストリートセグメントに沿った家屋番号またはアドレスレンジの位置を表し、さらに、前記インデックスが、それぞれのアドレスポイントに関連する家屋番号またはアドレスレンジをさらに含む請求項２８に記載の方法。
【請求項４３】
操作が格納されている機械可読媒体であって、
１つまたはそれ以上のプロセッサで処理されると、
利用者によるストリート名の入力に応答して、前記ストリート名に関連する前記ストリートセグメントのすべてのアドレスポイントを、地図データベースから取得するステップと、
利用者が入力したビル住所番号に応答して、ビル住所番号に対して取得されたアドレスポイントを調べるステップと、
前記取得されたアドレスポイントのどれかが、前記入力されたビル住所番号に対応する場合には、前記対応する取得されたアドレスポイントを使用して、前記入力されたビル住所番号の位置を利用者に戻し、また、取得されたアドレスポイントが、前記入力されたビル住所番号にまったく対応しない場合には、前記取得されたアドレスポイントの少なくとも１つを使用して、前記入力されたビル住所番号の位置に近いポイントまで補間して、その近似位置を利用者に戻すステップと、
をシステムに実行させる機械可読媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公表番号】特表２００９−５２６２７３（Ｐ２００９−５２６２７３Ａ）
【公表日】平成２１年７月１６日（２００９．７．１６）
【国際特許分類】
【出願番号】特願２００８−５５４４７１（Ｐ２００８−５５４４７１）
【出願日】平成１９年２月５日（２００７．２．５）
【国際出願番号】ＰＣＴ／ＵＳ２００７／０６１６２６
【国際公開番号】ＷＯ２００７／０９２８１７
【国際公開日】平成１９年８月１６日（２００７．８．１６）
【出願人】（５０７３８８８８９）テレ アトラス ノース アメリカ インコーポレイテッド (23)
【Ｆターム（参考）】
【公表日】平成２１年７月１６日（２００９．７．１６）
【国際特許分類】
【出願日】平成１９年２月５日（２００７．２．５）
【国際出願番号】ＰＣＴ／ＵＳ２００７／０６１６２６
【国際公開番号】ＷＯ２００７／０９２８１７
【国際公開日】平成１９年８月１６日（２００７．８．１６）
【出願人】（５０７３８８８８９）テレ アトラス ノース アメリカ インコーポレイテッド (23)
【Ｆターム（参考）】
[ Back to top ]