(57)【要約】【課題】  どんなにデータベースが大規模であったとしても、検索性能がある特定のスケール及び細かさで位置ベースの照会を行うために最適化されるように、位置タグが付されたデータのデータベースを生成する。【解決手段】  グリッドのサイズと座標値の精度とが関連付けられた階層的インデックスを構築することによって、精度情報が１次元インデックスの一部に含まれるように、データベースのエントリー座標値を正確に推定する。【選択図】  図２
2004334888.tif 000002
【特許請求の範囲】
【請求項１】
データベースのエントリー座標値の精度推定と前記座標値を結び付けてシングルインデックスにするコンピュータにより実行される方法において、
１又はより多くの位置エンティティを入力する動作と、
各位置エンティティが各位置エンティティの位置を組み入れたグリッドの列として表されたグリッドインデックス列を計算する動作と
を備えたことを特徴とするコンピュータにより実行される方法。
【請求項２】
前記グリッドインデックス列をデータベースに出力する動作を更に備えることを特徴とする請求項１記載のコンピュータにより実行される方法。
【請求項３】
位置エンティティは、点であることを特徴とする請求項１記載のコンピュータにより実行される方法。
【請求項４】
位置エンティティは、エリアであることを特徴とする請求項１記載のコンピュータにより実行される方法。
【請求項５】
前記エリアは、中心緯度、経度、広さ、高さにより定義され、各々が中心の緯度と経度から測定され、緯度及び経度の線に沿って測定されることを特徴とする請求項４記載のコンピュータにより実行される方法。
【請求項６】
正距円筒図法を用いて、前記１又はより多くの位置エンティティの緯度、経度の値をユーグリッド座標系上のx-y対として入力することを特徴とする請求項１記載のコンピュータにより実行される方法。
【請求項７】
前記グリッドインデックス列を計算する動作は、所定の分解能で地球を格子化すること、
ラスタースキャンの順で各グリッドをインデックス化すること、
各位置エンティティの緯度と経度の座標をインデックスにマッピングすること
を備えることを特徴とする請求項１記載のコンピュータにより実行される方法。
【請求項８】
前記所定の分解能は、２０であることを特徴とする請求項７記載のコンピュータにより実行される方法。
【請求項９】
前記ラスタースキャンの順で各グリッドをインデックス化することは、
各グリッドに対して、
標準偏差σが、与えられた緯度・経度座標の測定誤差であって、３標準偏差に対応する、ディグリーでの経度間隔Ｄを決定すること、
精度のディグリースケールＲを決定してＤよりちょうど大きい分解能の離散要素とすること
を備えることを特徴とする請求項７記載のコンピュータにより実行される方法。
【請求項１０】
３σメータに相当するディグリーでの経線間隔、すなわちd=[180(3σ)cos(latitude)]/kπを決定し、ｋがメートルでの地球の円周であることを特徴とする請求項９記載のコンピュータにより実行される方法。
【請求項１１】
精度のディグリースケールＲを決定し、Ｄよりちょうど大きい分解能の離散要素とする動作は、r=|-log2d/20|を設定することを備えることを特徴とする請求項９記載のコンピュータにより実行される方法。
【請求項１２】
正確さを増加させるために、地球を各スケールにおいてオーバーラッピンググリッドで格子化することを特徴とする請求項７記載のコンピュータにより実行される方法。
【請求項１３】
位置エンティティの座標を、中心が近接したスクウェアにマップすることを特徴とする請求項１２記載のコンピュータにより実行される方法。
【請求項１４】
前記位置エンティティは、地理上の位置データであることを特徴とする請求項１記載のコンピュータにより実行される方法。
【請求項１５】
前記位置エンティティは、位置と経度で記述されることを特徴とする請求項１記載のコンピュータにより実行される方法。
【請求項１６】
前記緯度と経度の値は、ユーグリッド座標系上の直線ｘ−ｙ対として取り出されることを特徴とする請求項１５記載のコンピュータにより実行される方法。
【請求項１７】
前記位置エンティティは、緯度、経度及び高度で記述されることを特徴とする請求項１記載のコンピュータにより実行される方法。
【請求項１８】
前記緯度、経度及び高さの値は、ユーグリッド座標系上の（ｘ、ｙ、ｚ）対として取り出されることを特徴とする請求項１７記載のコンピュータにより実行される方法。
【請求項１９】
前記緯度(lat)及び経度(long)での位置エントリー座標は、
l=(360/r)((lat+90)/r)+((long+180)/r)によって前記インデックスにマップされ、ｒは、精度のディグリースケールであり、ｌは、前記座標を前記位置エンティティにマップすることであることを特徴とする請求項７記載のコンピュータにより実行される方法。
【請求項２０】
前記緯度及び経度の値を回復するために、前記緯度(lat)及び経度(long)は、
lat=lr2/360-90+r/2            
long=l%(r2/360)-180+r/2
として計算され、ｒは、精度のディグリースケールであり、ｌは、前記座標を前記位置エンティティにマップし、％は係数オペレータであることを特徴とする請求項１９記載のコンピュータにより実行される方法。
【請求項２１】
前記データベースは、位置エンティティ識別子と、
異なるグリッドに対応する１又はより多くのスケールの各々のスケールインデックスと
を備えることを特徴とする請求項２記載のコンピュータにより実現される方法。
【請求項２２】
データベースへの照会は、どの位置エンティティが、所定のグリッドスケールでの所定のグリッドセルにあるかを照会する動作と、
前記所定のグリッドセルの値に対して前記所定のグリッドスケールのデータ内を検索する動作と、
前記所定のグリッドスケールでの前記所定のグリッドセルの前記値を返す動作と
を備えることを特徴とする請求項２記載のコンピュータにより実現される方法。
【請求項２３】
１次元の数値を用いて多次元空間をインデックス化するシステムにおいて、
汎用コンピューティング装置と、
コンピュータ装置によって実行可能なプログラムモジュールを備えたコンピュータプログラムであって、該コンピュータプログラムの前記プログラムモジュールにより前記コンピュータ装置が、各グリッドのサイズがデータベースエントリーの座標値の精度と関連付けられ異なるサイズのグリッド単位を備えた同じ空間上に重畳される多数のグリッドインデックスから階層的グリッドインデックスを構築するコンピュータプログラムと
を備えたことを特徴とするシステム。
【請求項２４】
前記データベースエントリーが地理上の位置であることを特徴とする請求項２３記載のシステム。
【請求項２５】
前記データベースエントリーが時刻であることを特徴とする請求項２３記載のシステム。
【請求項２６】
データベースのエントリー座標値の精度推定と座標値を結合してシングルインデックスにするコンピュータ実行可能な命令を格納するコンピュータ読み取り可能媒体において、
１又はより多くの位置エンティティを入力する命令と、
各位置エンティティが、各位置エンティティの位置を組み入れたグリッド列として表されたグリッドインデックス列を計算する命令と
を備えたことを特徴とするコンピュータ読み取り可能媒体。
【請求項２７】
グリッドインデックスを計算する命令が、正距円筒図法を用いることを特徴とする請求項２６記載のコンピュータ読み取り可能媒体。
【請求項２８】
前記グリッド列が、サイズが２０Ｘ（１／２）ｒ  ディグリー（ｒ＜＝ｒ＜２０）であるスクウェア要素を用いて、地球を２０の異なる分解能に格子化することを特徴とする請求項２６記載のコンピュータ読み取り可能媒体。
【請求項２９】
前記グリッド列が、プラトニックソリッド内にはめ込まれた等辺の多角形であることを特徴とする請求項２６記載のコンピュータ読み取り可能媒体。
【請求項３０】
前記グリッド列が、地球を格子化する階層的多角形列であることを特徴とする請求項２６記載のコンピュータ読み取り可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、位置と精度の符号化のためのシステム及び方法に関する。より詳細には、本発明は、データベースのエントリー座標値(database entry’s coordinate value)の精度推定を兼ね備え精度情報が１次元インデックスの一部に含まれるようにするシステム及び方法に関する。
【背景技術】
【０００２】
地理情報システム（Geographic Information System; GIS）は、一部において、地理的関係を用いて分類された情報を十分に体系付けたデータベースである。しばしば、これらのデータベースには、百万又は１０億（或いはより多く）程度のデータエレメントを含み、各データエレメントは各自の地理的位置と関連付けられている。例として、各写真がその写真が取られた位置と関連付けられているワールドワイド・フォト・データベースを考えてみるとよい。
【０００３】
最新のリレーショナルデータベースは、各種のアルゴリズム的効率化を図り、データベースに含まれるデータの検索スピードを上げるが、特別なタスクにおいては、非効率のままである。例えば、データベースは、１次元を超えるレンジ範囲（range queries）を実行することは比較的不得手である。これらは、「数値Xがx1とx2の間にあり、数値Yがy1とy2の間にあり、数値Zがz1とz2の間にあるような全てのデータを検索しなさい。」という形式の照会である。（また、最新のデータベースは、もしデータエレメントの数が比較的小さければ、これら種類の照会であってもうまく処理することができる。しかし、データベースはデータ形式を予め知ることができないため、データベースは、効率性を犠牲にして一般性のために設計される必要があり、大量のデータに対しては非効率のままである。）
【０００４】
さらに、いくつかのGISアプリケーションにおいては、エレメントは異なるスケール（scale）で地理的な地域と関連づけられており、また、照会をある範囲のスケールにわたって実行してもよい。例えば、写真データベースの場合、アイテム（item）を全体としてニューヨークの市と関連付けてもよいし、或いは、より具体的にエンパイアステートビルディングを示す市内のブロックと関連付けてもよい。ある程度の種類の照会の場合、ニューヨークシティで撮られた写真を照会するときには、エンパイアステートビルディングで撮られた全てのアイテムを検索するのが有用であるかもしれない。しかし、その逆は望ましくないかもしれない。ニューヨークシティで撮られた写真の全てがエンパイアステートビルディングに関する照会と関連性があるとは限らないからである。
【０００５】
【非特許文献１】Diomidis, D.S, Position-annotated photographs: a geotemporal web.  IEEE Pervasive Computing. 2(2):72-79,2003
【非特許文献２】Sahr, K. and White, D, Discrete Global Grid Systems. In Proc. 13 th Symp. Interface, Comp. Sci. & Stat. 269-278, 1998
【発明の開示】
【発明が解決しようとする課題】
【０００６】
したがって、位置タグが付されたデータ(location-tagged data)のデータベースを生成し、どんなにデータベースが大規模であったとしても、検索性能を最適化して特定のスケール及び細かさで位置ベースの照会(location-based queries)を行うことができるシステム及び方法が必要である。
【課題を解決するための手段】
【０００７】
本発明は、データベースのエントリー座標値の精度推定を兼ね備え、グリッドのサイズが座標値の精度と関連付けられた階層的インデックス(hierarchical index)を構築することによって、精度情報が１次元インデックス(one-dimensional index)の一部に含まれるようにするシステム及び方法を対象とする。
【０００８】
グリッドインデックス(grid index)とは、グリッド単位を形成するグリッド空間(grid space)の規則正しい仕切り(partition)の中にn次元空間(n-dimensional space)を格子化(gridding)したものである。そのために、空間内の点ｘに対して、関数インデックス（ｘ）があり、それが点ｘを含むグリッドの唯一(unique)の整数値を引き出す。階層化されたグリッドインデックスは、実際には、同じ空間上に重畳される多数のグリッドインデックスのことであり、異なるサイズのグリッド単位を備える。この場合、各々の関数は、使用するグリッド単位の大きさを明示する追加引数(additional argument)を必要とする。従って、仮に、グリッドサイズｓがグリッドサイズＳのセットから引き出されると、インデックス（x、s）は、点ｘを含みサイズがｓのグリッドの唯一の整数値を返す。階層的インデックスは、データベース照会の性能を高めるために使用される。小さなグリッドサイズであるｓsmall  から結果を求める照会は、大きなグリッドサイズs largeでは一致を探索しない。
【０００９】
同様な演算を限定されたエリアAのために実行することができる。すなわち、グリッドインデックスを空間内の限定されたエリアAに関して使用することができ、エリアAを完全に含むグリッドの唯一の整数値を検索する関数インデックス（A）が存在する。
【００１０】
一般的に、情報が１次元インデックスの一部に含まれるように、データベースエントリー座標値の精度推定を兼ね備えたデータベースを得るために、１又はより多くの位置エンティティ(location entities)を、本発明によるシステム及び方法に入力する。各グリッドが各位置エンティティの位置を組み込んだグリッド列として表されるグリッドインデックス列が計算される。このグリッドインデックス列をデータベースに出力することができる。
【００１１】
より具体的には、本発明によるシステム及び方法の１実施形態は、正距円筒図法（equirecangular projection:”unprojected lat/long”  としても知られている）を用い、そこでは、位置エンティティの緯度／経度（lat/long）値がユークリッド座標系上の直線ｘ−ｙ対として取得され、システムに入力される。地球は、サイズが２０Ｘ（１／２）r ディグリー(degrees)（０＜＝ｒ＜２０）に相当する“正方（square）”要素で２０の異なる分解能で格子化される。赤道では、これらの値は〜２４０kmから〜０．５ｍの範囲で変動するスケール(scales)に相当する。各グリッドは、ラスタースキャンの順（raster-scan order）でインデックス化される。したがって、測定誤差が、通常、標準偏差σメータで分散すると思われる与えられた緯度／経度座標（long, lat）は、以下のようにインデックス化されるであろう。最初に、３σメータに対応する、ディグリーによる経度間隔(longitudinal span)、すなわちd=[180(3σ)cos(lat)]/kπが決定され、そこでは、ｋは  地球の円周をメートルであらわしたもの（４Ｘ１０８ｍ）である。次に、精度のディグリースケール（degree-scale）ｒがｄよりちょうど大きい分解能の離散要素(discrete unit))、すなわち、r=|-log2d/20|になるよう決定される。最後に、座標（long,lat）がインデックスにマップされる。
l=(360/r)((lat+90)/r)+((long+180)/r)         
そして、インデックスにマップされた座標をデータベースに出力されうる。そのlat/long値を元にもどすためには、この操作を逆にする。
lat=lr2/360-90+r/2            
long=l%(r2/360)-180+r/2                    
【００１２】
ここで、’%’は係数オペレータ(modulus operator)であり、また、r/2タームは、それらのグリッドの中心にその返却値(returned values)を置く。
【００１３】
上述の表現(representation)は都合よく２Ｄ lat／long座標を精度(precision)と一緒にパッケージ化し、また、それを用いて、シングル８バイトインデックスによりデータベースの中のアイテムをインデックス化することができる。照会が特別のグリッドの中の全てのアイテムに発行されたならば、その与えられたグリッドよりも精度が高い位置タグを備えたアイテムを検索するために、複数の照会をつくることが必要となろう。大きなエリアから引き継がれた全てのアイテムのための照会は、計算コストが高く、時間を浪費する(time-consuming)。これを避けるために、２０フィールド（グリッド分解能毎に１つ）が用いられ、各フィールドは特定の精度でアイテムの位置を表す。(long、lat)と精度ｒ*で与えられたアイテムのために、lrが計算され(for all r>=r*)、そして、(for r<r*)で, ヌルの値が割り当てられる。この仕組みにより、精度ｒで位置を表すフィールド上でのシングル完全一致照会(single, exact-match query)を用いて、精度ｒで特定のグリッド内で起こったと知られる全てのアイテムのために照会することができる。たとえ、グリッドが交差(intersect)しても（これは階層的グリッドインデックスの標準的な使用法を逆転させる。）、位置タグ精度(location-tag precisions)が照会されたものより粗いアイテムは、返されないであろう。
【発明の効果】
【００１４】
本発明によるシステム及び方法は、従来のデータベース方式においては典型的であるように、多次元照会(multidimensional query)を生成するのに要するほんの少しの時間で非常に大きなデータベースを照会できるという利点がある。
【００１５】
前述した利点に加えて、本発明の他の利点は、詳細な記載に付随する図面に関連して以下に続く説明から明白であろう。
【発明を実施するための最良の形態】
【００１６】
本発明の特別の特徴、様相及び利点は、以下の説明、付属の特許請求の範囲及び添付の図面に関してよりよく理解されるであろう。
本発明の好ましい実施例に関する以下の説明において、これの一部をなす添付の図面が参照され、それは、発明が実施されるかもしれない具体的な実施例を図解することによって示される。その他の実施例を利用してもよく、また、本発明の範囲から逸脱しないで構造上の変更がされ得ることが理解される。
【００１７】
（１．０  例示的オペレーション環境）
図１は、本発明を実行することができる好適なコンピューティングシステム環境１００の一例を示す。コンピューティングシステム環境１００は、好適なコンピューティング環境の一例に過ぎず、本発明の使用又は機能の範囲に関して如何なる限定を示唆するつもりはない。コンピューティングシステム環境１００は、代表的なコンピューティングシステム環境１００の中に図示されているコンポーネントのいずれか１つ或いはコンポーネントの組み合わせに関係する如何なる依存も必要条件をも有するものとして解釈すべきではない。
【００１８】
本発明は多数の他の汎用又は特定用途コンピューティングシステム環境又は構成を使って操作可能である。本発明を用いた使用に適切かもしれない周知のコンピューティングシステム、環境、及び／又は構成の例には、これらに限定されないパーソナルコンピュータ、サーバーコンピュータ、ハンドヘルド又はラップトップ装置、マルティプロセッサシステム、マイクロプロセッサに基づいたシステム、セットトップボックス(set top boxes)、プログラムマブルコンシューマーエレクトロニクス(programmable consumer electronics)、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記のシステム又は装置を含んだ分散コンピューティング環境及び同種のものが含まれる。
【００１９】
本発明は、コンピュータにより実行可能なプログラムモジュール等のコンピュータ実行可能な命令の一般的な文脈により記述することができる。一般的に、プログラムモジュールは、特有なタスクを実行するか又は特有な抽象データ型を実装するルーティン、プログラム、オブジェクト、コンポーネント、データ構造等を含んでいる。本発明は、タスクが通信ネットワークを介して連結されるリモートプロセッシングユニットにより実行される分散コンピューティング環境においても実行されることがある。分散コンピューティング環境においては、プログラムモジュールは、メモリ記憶装置を含んだローカルとリモートの両コンピュータ記憶媒体の中に置かれることがある。
【００２０】
図１を参照すると、本発明を実装する代表的なシステムは、コンピュータ１１０の形式の汎用コンピューティング装置を含む。コンピュータ１１０の構成要素は、プロセッシングユニット１２０、システムメモリ１３０、システムメモリを含んだ様々なシステムコンポーネントをプロセッシングユニット１２０につなぐシステムバス１２１を含むが、これらに限定されない。システムバス１２１は、様々なバスアーキテクチュアのいずれかを使用しているメモリバス又はメモリコントローラ、周辺バス、および、ローカルバスが含まれるバス構造の幾つかのタイプのいずれであってもよい。例として、そのようなアーキテクチュアには、インダストリー・スタンダード・アーキテクチャ（ISA）バス、マイクロチャネル・アーキテクチャ（MCA）バス、エンハンスドISA(EISA)バス、ビデオ・エレクトロニクス・スタンダード・アソシエーション（VESA）ローカルバス、及び、メザニンバス（Mezzanine Bus）としても知られるペリフェラル・コンポーネント・インターコネクト（PCI）バスが含まれるが、これらに限定されるわけではない。
【００２１】
コンピュータ１１０は一般的にコンピュータにより読み取り可能な多種類の媒体を含んでいる。コンピュータにより読み取り可能な媒体は、コンピュータ１１０によってアクセス可能であり、揮発性と不揮発性の両媒体と、取り外し可能と取り外し不可能な媒体とを含んだ有用な媒体であればよい。例として、コンピュータにより読み出し可能な媒体は、コンピュータ記憶媒体と通信媒体とから構成されることがあるが、これらに限定されない。コンピュータ記憶媒体には、コンピュータ読み出し可能な命令、データ構造、プログラムモジュール又はその他のデータのような情報の記憶装置に関するいかなる方法又は技術で実装される揮発性と不揮発性の両媒体、取り外し可能・取り外し不可能な媒体が含まれる。コンピュータ記憶メディアには、RAM,ROM,EEPROM、フラッシュメモリ、又は、その他のメモリ技術、CD-ROM、DVD 、又は、その他の光ディスク記憶、磁気カセット、磁気テープ、磁気ディスク記憶装置又はその他の磁気記憶装置、又は所望のデータを蓄えるために用いることができ、コンピュータ１１０によりアクセス可能なその他の媒体が含まれるが、これらに限定されない。通信メディアは、典型的に、コンピュータ読み出し可能な命令、データ構造、プログラムモジュール、又は、搬送波又は他の伝達メカニズム等の変調データ信号の中の他のデータを具現化し、そして、いかなる情報伝達媒体を含む。“変調されたデータ信号”という用語は、１つ又はより多くのその特徴的なセットをもつ信号、又は、信号上で符号化情報に関する方式などにより変換された信号を意味する。例としては、通信媒体には、有線のネットワーク又は直接有線接続等の有線媒体(wired media)と、音響、RF、赤外線や他の無線媒体等の無線媒体(wireless media)とが含まれる。上述したことのいかなる組み合わせもコンピュータ読み取り可能媒体の範囲内に含まれるはずである。
【００２２】
システムメモリ１３０には、リードオンリーメモリ（ROM）１３１及びランダムアクセスメモリ(RAM)１３２等の揮発性及び／又は不揮発性メモリの形式のコンピュータ記憶媒体が含まれる。起動中のように、コンピュータ１１０内の要素間で情報を転送するのを助ける基本ルーティンを含む基本入出力システム（BIOS）１３３は、一般的に、ROM１３１に記憶されている。RAM１３２は、一般的に  直ちにプロセッシングユニット１２０にアクセスされ、及び／又はやがてプロセッシングユニット１２０により操作されるデータ及び／又はプログラムモジュールを含む。例として、図１は、オペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６、とプログラムデータ１３７を示すが、これらに限定されない。
【００２３】
コンピュータ１１０は、他の取り外し式／取り外し不能式、揮発性／不揮発性コンピュータ記憶媒体もまた含んでもよい。唯一の例として、図１は、取り外し不可で不揮発性の磁気媒体との間で読み取り又は書き込みを行うハードディスクドライブ１４１と、取り外し式で不揮発の磁気ディスク１５２との間で読み取り又は書き込みを行う磁気ディスクドライブ１５１と、例えばＣＤ−ROM又は他の光メディア等の取り外し式で不揮発性の光ディスク１５６との間で読み取り又は書き込みを行う光ディスクドライブ１５５を示す。代表的なオペレーティング環境で使用することができる他の取り外し式／不揮発性、揮発性／不揮発性のコンピュータ記憶メディアには、磁気テープカセット、フラッシュメモリカード、ＤＶＤ、ディジタルビデオテープ、ソリッドステートRAM(solid state RAM)、ソリッドステートROM(solid state ROM)等が含まれるが、これらに限定されない。ハードディスクドライブ１４１は、一般的に、インタフェース１４０等の取り外し不能式メモリインタフェースを通してシステムバスに接続され、また、磁気ディスクドライブ１５１と光ディスクドライブ１５５は、一般的に、インタフェース１５０等の取り外し式メモリインタフェースによってシステムバス１２１に接続される。
【００２４】
上述し、かつ、図1に示されたドライブとそれらと関連するコンピュータ記憶媒体は、コンピュータ１１０のためのコンピュータ読み取り可能な命令、データ構造、プログラムモジュールおよびその他のデータの記憶を提供する。図１において、例えば、ハードディスクドライブ１４１は、オペレーティングシステム１４４、アプリケーションプログラム１４５、その他のプログラムモジュール１４６およびプログラムデータ１４７を記憶するものとして示される。尚、これらのコンポーネントは、オペレーティングシステム１３４、アプリケーションプログラム１３５、その他のプログラムモジュール１３６及びプログラムデータ１３７と同じであっても、異なっていてもよい。オペレーティングシステム１４４、アプリケーションプログラム１４５、その他のプログラムモジュール１４６及びプログラムデータ１４７には、最小限、それらが異なるコピーであることを示すために、ここでは異なる番号が付与される。ユーザは、キーボード１６２や、一般にはマウス、トラックボール又はタッチパッド(touch pad)と呼ばれるポインティングデバイス１６１等の入力装置を使ってコンピュータ１１０にコマンドや情報を入力してもよい。他の入力装置（図示せず）には、ジョイスティック、ゲームパッド、サテライトディシュ(satellite dish)、スキャナ等が含まれてもよい。これら又は他の入力装置は、システムバス１２１につながれるユーザ入力インンターフェース１６０を介してプロセッシングユニット１２０と接続されることが多いが、パラレルポート、ゲームポート又はユニバーサルシリアルバス（USB）等の他のインタフェースやバス構造によって接続されてもよい。モニター１９１或いは他のタイプのディスプレイ装置は、ビデオインタフェース１９０等のインタフェースを介してシステムバス１２１にも接続される。加えて、モニター、コンピュータは、スピーカ１９７やプリンタ１９６等の、出力周辺インタフェース１９５を通して接続されるかもしれない他の周辺出力装置をまた含んでもよい。本発明にとって、一連のイメージ１６４を撮ることができるカメラ１６３（デジタル／エレクトロニックスチール(still)又はビデオカメラ、又はフィルム／写真スキャナ）もパーソナルコンピュータ１１０に対する入力装置として含めることができることが特に重要である。さらに、たった一つのカメラが描かれたとしても、多数のカメラがパーソナルコンピュータ１１０に対する入力装置として含まれる可能性がある。１つ又はより多くのカメラからの画像１６４は、適当なカメラインタフェース１６５を介してコンピュータ１１０に入力される。マイクロホーン１６８は、カメラと連携してもよく、１又はより多くのカメラと連携するインタフェース１６５を備えたコンピュータ１１０に入力してもよい。このインタフェース１６５はシステムバス１２１に接続され、これにより、画像は引き出され、RAM132の中に又はコンピュータ１１０と連携する他のデータ記憶装置の一つの中に記憶することができる。しかしながら、画像データは、カメラ１６３の使用を必要とせずに、前述のコンピュータ読み取り可能な媒体のいずれかからコンピュータ１１０に入力できることを付記する。
【００２５】
コンピュータ１１０は、リモートコンピュータ１８０等の１つ又はより多くのリモートコンピュータへの論理コネクションを用いて、ネットワーク環境の中で機能してもよい。リモートコンピュータ１８０はパーソナルコンピュータ、サーバー、ルーター、ネットワークＰＣ、ピアデバイス(peer device)、又は他の一般的なネットワークノードでよく、メモリ記憶装置１８１だけが図１に示されているが、一般的には、コンピュータ１１０に関連する上述したエレメントの多く又は全てを含む。図１に示されたロジカルコネクションはローカルエリアネットワーク（LAN）１７１と広域エリアネットワーク（WAN）１７３を含むが、他のネットワークをまた含んでもよい。そのようなネットワーキング環境は、オフィス、企業規模のコンピュータネットワーク、イントラネット、インターネットにおいてはごく普通である。
【００２６】
LANネットワーキング環境において使用する場合には、コンピュータ１１０は、ネットワークインタフェース又はアダプター１７０を介してLAN１７１に接続される。WANネットワーキング環境において使用する場合には、コンピュータ１１０は一般的にモデム１７２或いはインターネットのようなWAN１７３上で通信を確立する他の手段を含む。モデム１７２は、内部或いは外部にあっても良いが、ユーザ入力インタフェース１６０を介して、又は、他の適当なメカニズムを介してシステムバス１２１に接続されてもよい。ネットワーク化された環境においては、コンピュータ１１０に関連して描かれるプログラムモジュール又はそれの一部分をリモートメモリ記憶装置の中に格納しても良い。例として、図１は、メモリ装置１８１に存するリモートアプリケーションプログラム１８５を示すが、これに限定されない。示されたネットワークコネクションが代表的であり、コンピュータ間の通信リンクを確立する他の手段が有用であることが認識されるであろう。
【００２７】
（２．０  位置と精度の符号化のためにグリッドインデックスを使用するシステム及び方法）
（２．１  概要）
本発明は、データベースのエントリー座標の精度推定を兼ね備え、グリッドのサイズが座標値の精度と関連付けられている階層的インデックスを構築することによって精度情報が１次元インデックスの一部に含まれるシステム及び方法に関する。階層的グリッドインデックスは  同じ空間上に重畳された多数のグリッドインデックスから形成される。グリッドインデックスとは、グリッド空間の規則正しい仕切りの中にn次元空間をグリッド単位に格子化したものであり、空間内の点ｘに対して、関数インデックス（ｘ）があり、それが点ｘを含むグリッドの唯一の整数値を引き出す。階層化されたグリッドインデックスは、実際には、同じ空間上に重畳される多数のグリッドインデックスのことであり、異なるサイズのグリッド単位を備える。この場合、各々の関数は、使用するグリッド単位の大きさを明示する追加引数を必要とする。従って、仮に、グリッドサイズｓがグリッドサイズＳのセットから引き出されると、インデックス（x、s）は、点ｘを含みサイズがｓのグリッドの唯一の整数値を返す。階層的インデックスはデータベース照会の性能を高めるために使用される。小さなグリッドサイズであるｓsmall  から結果を求める照会は、大きなグリッドサイズs largeでは一致を探索しない。
【００２８】
同様な演算を限定されたエリアAのために実行することができる。すなわち、グリッドインデックスを空間内の限定されたエリアAに関して使用することができ、エリアAを完全に含むグリッドの唯一の整数値を検索する関数インデックス（A）が存在する。
【００２９】
図２は、情報が１次元インデックスの一部として含まれるようにデータベースのエントリー座標の精度推定を兼ね備えるデータベースを生成する処理動作の単純化されたフローダイアグラムを示す。これは、グリッドのサイズが座標値の精度と関連づけられている階層インデックスを構築することによりなされる。最も一般的な用語として、位置エンティティ(location entities)は、処理動作２０２に示されるように入力される。位置エンティティは一つの点又は一つの限定されたエリアでありうる。次に、各グリッドが各位置エンティティの位置を組み入れたグリッドの列(series)として表されているグリッドインデックス列が計算される（処理動作２０４）。次に、インデックス列はデータベースに出力されうる（処理動作２０６）。
【００３０】
以下の章でより具体的に本発明によるシステム及び方法を説明する。
（２．２  位置表示）
２次元位置（及び時刻）以外のパラメータがリアルワールドオブジェクトをユニークに配置するために必要である。これらのパラメータには、高度や方位仕様(orientation specification)の３つのディグリー（degree）と、あるいは、その他のパラメータが含まれるが、それは、オブジェクトが何であるかに依存する。この議論においては、検討(examination)を２Ｄ位置に制限する。その理由は、それは、残りのパラメータを組み入れたより広い理解に向かう処理しやすい最初の動作だからである。しかしながら、本発明によるシステムと方法は、多重次元位置情報(multi-dimensional location)を処理できる点に注意すべきである。
【００３１】
ジオリファーシング（Georeferencing）、或いは、位置をどのように表すかはGISにおいて根本的な問題である。位置を多くの方法で表現(representation)することができ、例えば、確立した地名（“サンフランシスコ”）、ユーザに依存の地名（“祖母の家”）、道路アドレス、郵便コード、緯度／経度座標、幾つかの原点に関するユークリッド座標、等がある。
【００３２】
GISプロジェクトの大多数は、地理上のポイント座標を明示するために、WGS８４で定義された座標とともに緯度／経度座標（以後、lat/longという。）を用いる。この仕組みは、地球上のポイントを明示する方法として理解される。その理由は、それは簡潔でポイント位置を表す確立した方法であるからである。
閲覧と相互作用(interaction)の目的のために、２つの追加の位置データ構造の型が必要となる：（１）地図や照会のために、表示されたマップに対応する物理位置の観念(notion)（２）メタデータタギング(metadata-tagging)のために、lat/long座標と、精度又は分解能の測度を含むデータ型。
【００３３】
地図は大抵２次元ディスプレイ上に長方形(rectangles)として表示される。したがって、地図を表示するために、エリアタイプと呼ばれる構造を用いるが、その構造は、中心（center）lat/longと、キロメータでの幅及び高さとで定義され、各々は中心点から測定され、緯度と経度のラインに沿って測定される。
【００３４】
これは地球上のユニークな地域、すなわち、“長方形”(”rectangular”)を定義し、それは、３D地球(3D globe)上の４つの大きな円の円弧(four great-circle arcs)により囲まれる。２Ｄの中に投影されるとき、エリアは、投影種別、スケールおよび地球上の位置に依存して、概略的に、直線から若干それる(deviate)かもしれない縦の辺をもった長方形にみえる。
【００３５】
データ項目の位置タグのために、エンパイアステートビルディングと関連付けられたアイテムと、粗いラベル(coarser label)であるニューヨークシティとだけ関連付けられたアイテムとを区別するために、lat/longと何らかの精度の指示を表したい。優先度は、潜在的に大量の数のそのようなアイテム上のデータベースからの素早い検索である。オフザシェルフ（off-the shelf）リレーショナルデータベースにおいては、データベースエントリーがシングルナンバーによってインデックス化できる場合に、照会を最適化することができる。したがって、本発明によるシステム及び方法は  lat／longと精度の３連続変数(three continuous variables)をシングル離散インデックス(single discretized index)に減らす仕組みを用いる。この基準(criterion)を満たす空間的データ構造(spatial data structure)はディスクリートグローバルグリッドシステムズ（discrete global grid systems）(DGGSs)と呼ばれ、その幾つかの例を表１に示す。
【００３６】
【表１】
2004334888.tif 000003
【００３７】
さて、図３、４、５を参照すると、本発明によるシステムと方法の一実施例は、正距円筒図法（”unprojected lat/long”としても知られている）を用い、そこでは、lat/longがユークリッド座標系上の直線ｘ−ｙ対として取得され（図５（ｂ）参照）、システムに入力される（図３の処理動作３０２）。処理動作３０４では、地球は、サイズが２０Ｘ（１／２）r ディグリー(degrees)（０＜＝ｒ＜２０）に相当する“正方（square）”要素で２０の異なる分解能で格子化される。図５（b）は、図５（a）に略図された地域の２０−、１０−、５ディグリー格子化(degree gridding)を示す。赤道上では、これらの値は〜２４０kmから〜０．５ｍの範囲で変動するスケールに相当する。もし、より大きい又はより小さい精度が必要であれば、格子化は、より大きな又はより小さな分解能で起こり得る。
【００３８】
次に、処理動作３０６では、各グリッドはラスタースキャンの順でインデックス化される。したがって、測定誤差が、通常、標準偏差σメータで分散すると思われる与えられた緯度／経度座標（long, lat）は、以下のようにインデックス化されるであろう。最初に、図４の処理動作３０６Aでは、３σメータに対応する、ディグリーによる経度間隔、すなわちd=[180(3σ)cos(lat)]/kπが決定され、そこでは、ｋは地球の円周をメートルであらわしたもの（４Ｘ１０８ｍ）である。次に、処理動作３０６Ｂでは、精度のディグリースケール（degree-scale）ｒがｄよりちょうど大きい分解能の離散要素(discrete unit))、すなわち、r=|-log2d/20|になるよう決定される。最後に、処理動作３０８で示すように、座標（long,lat）がインデックスにマップされる。
l=(360/r)((lat+90)/r)+((long+180)/r)     （１）      
【００３９】
次に、インデックスにマップされた座標をデータベースに出力されうる（処理動作３１０）。そのlat/long値を元にもどすためには、このオペレーションを逆にする。
lat=lr2/360-90+r/2            
long=l%(r2/360)-180+r/2                      （２）
【００４０】
ここで、’%’は係数オペレータであり、また、r/2タームは、それらのグリッドの中心にその戻り値(returned values)を置く。言うまでもなく、式１のフロアーオペレーション（floor operation）のため、数値、プラスマイナスr/2、すなわち、都合よくアイテムの位置推定(location estimate)の精度である数値をただ単に回復できる。ｒが減少するにつれて、望まれるように、精度は、漸近的(asymptotically)にゼロに近づく。なお、これらのグリッドは、一般的に、物理的な地域のオブジェクトに対応はしない。しかし、特別のエリアで生じるグリッド要素は、エリアとオーバーラップする単位を列挙することによって容易に判断されうる。もし、より高い精度が必要であれば、各スケールでオーバーラップしているグリッドが、中心が最も密集した四角にマップされた座標を使って用いられる。（図５（ｃ）参照）
【００４１】
（２．３  グリッドタイプ）
正距円筒図法を使って正方グリッドを用いることは、直感的であり、データベース照会を効率的にし続ける。しかし、同一のインデックススケールでのグリッド要素の物理サイズと形が、特に極の近辺で歪んでいる点で洗練されていない。しかしながら、他のグリッディングの仕組みを用いることができる。本発明の１実施形態においては、グリッディング方式は、最小の領域変動と形の歪(shape distortion)を有しプラトンの立体(Platonic solid)内に埋め込まれた等辺のポリゴン(equilateral polygons)の階層列(hierarchical)を用いる。このグリッディングの仕組みの大きな利点は、固定化されたスケールにおいて、要素が類似するサイズと形となることである。本来、座標に付与されるグリッドインデックスとグリッドインデックスに付与される座標を決定するための等式(equations)は、これらの交互(alternate)の仕組みのために採用されなければならない。
【００４２】
（２．４  位置データベーススキーマデザイン）（Location Database Schema Design）
上述の表現(representation)は都合よく２Ｄ lat／long座標を精度(precision)と一緒にパッケージ化し、また、それを用いて、シングル８バイトインデックスによりデータベースの中のアイテムをインデックス化することができる。
【００４３】
照会が特別のグリッドの中の全てのアイテムに発行されたならば、その与えられたグリッドよりも精度が高い位置タグを備えたアイテムを検索するために、複数の照会をつくることが必要となろう。大きなエリアから引き継がれた全てのアイテムのための照会は、計算コストが高く、時間を浪費する。これを避けるために、２０フィールド（グリッド分解能毎に１つ）が用いられ、一実施例における各フィールドは特定の精度でアイテムの位置（例えば、位置エンティティ）を表す。(long、lat)と精度ｒ*で与えられたアイテムのために、lrが式１にて計算され(for all r>=r*)、そして、(for r<r*)で, ヌルの値が割り当てられる。この仕組みにより、精度ｒで位置を表すフィールド上でのシングル完全一致照会を用いて、精度ｒで特定のグリッド内で起こったと知られる全てのアイテムのために照会することができる。たとえ、グリッドが交差しても（これは階層的グリッドインデックスの標準的な使用法を逆転させる。）、位置タグ精度が照会されたものより粗いアイテムは、返されないであろう。すなわち、もし、あるマンハッタンブロック内で撮られた全てのアイテムに対してサーチがなされたならば、そのグリッド要素のための照会は、ニューヨークシティのどこかと関連するということだけが知られているアイテムを返さないであろう。
【００４４】
本発明のシステム及び方法によって構成されるデータベースから所望のデータを検索する処理動作のフローダイアグラムを図６に示す。ユーザは、処理動作５０２に示されたように、与えられたスケールＳで与えられたセルｙ内の全てのロケーションエンティティを返すようにデータベースに照会する。それから、所望のスケールに対応するデータベースのカラム(column)Ｓがセルｙの値のために検索され（プロセス動作５０４）、これらの値が返される（プロセス動作５０６）。尚、たとえ、セルｙ自身よりも細かいスケールで生じたとしても、セルｙによって表されるグリッド内で生じるデータベーステーブル内の全てのエンティティは検索結果の中に含まれるであろう。
【００４５】
本発明の一実施形態のための代表的なデータベースフォーマットを図７に示す。データベースは、データベース内の各エントリーのために位置エンティティID６０２を含む。選択的には、緯度・経度座標６０４もまた、グリッドスケール６０６を表すインディケーターと同様に、記憶されうる。スケール１のスケールインデックスは、１桁の整数、すなわち、完全に位置表示を含むスケール１のグリッド又はもし含まれないのであれば（位置表示が有限エリア又は有限ポイントの代わりの地域であれば、そのケースになるであろう）ヌルがセットされたものを提供する。スケール２でのスケールインデックスは、スケール１よりも細かい分解能でグリッドセルを表す１つの整数を提供する。そして、スケールNまで等。もし、有限エリアが、与えられたグリッドセル内に完全に含まれていないならば、スケールインデックスには、この位置表示のためにゼロ値がセットされる。
【００４６】
この表示はデータベース内に付加的なフィールドを必要とするけれど、これは、性能上ゲイン(gain)によってより重大である（ほぼ１０倍 for >百万列(rows)）
【００４７】
本発明の前述した説明は、図示及び説明の目的のために提供される。余すことなく、又は、開示された正確な形式に本発明を限定することを意図しない。多くの変更とバリエーションが上記の教示に照らして可能である。本発明の範囲は、この詳細な説明によって限定されず、むしろ、これに添えられている特許請求の範囲によって限定される。
【図面の簡単な説明】
【００４８】
【図１】本発明を実行する代表的なシステムを構成する汎用コンピューティング装置を示す図である。
【図２】グリッドインデックス列を計算するデータベースを生成する全体のプロセスを単純化した流れ図であり、各ポイントが本発明によるグリッド列として表されている。
【図３】本発明の一実施形態の単純化された流れ図であり、緯度と経度がユーグリッド座標系上のX-Y対として表され、また、地球は２０の異なる分解能で格子化される。
【図４】図３の各グリッドをラスタースキャンの順でインデックスする処理動作の単純化された流れ図である。
【図５】本発明の一実施例で用いられる座標と精度インデックシング(precision indexing)のためのグリッディングを示す図である。図５（a）で太線で輪郭が描かれたキュアシレクタンギュラー(quasi-rectangular)地域は、地球上の２０−ディグリー（20-degree）“正方”(”square”)によって２０−ディグリーを示す。図５（ｂ）において、同じグリッドは、正距円筒図法を用いて投影され、黒い線はさらに１０−ディグリー正方グリッドに細分化され、灰色の線は５−ディグリーグリッドに細分化される。図５（ｃ）は、与えられた精度でより大きなポイント正確(point accuracy)のために用いられる重複されたグリッドを示す。大きめの正方の各々は同じ精度でシングルグリッドを表すが、重複されたグリッド単位から引き出される。もし、ドットが、表された精度でアイテムのlat/long座標を表すならば、太く示された点だけが、トップレフト（top left）のグリッドに属するであろう。
【図６】本発明によるシステム及び方法で用いられるデータベース照会の流れ図である。
【図７】本発明によるシステム及び方法の一実施例で用いられる例示的なデータベース構造を示す図である。
【符号の説明】
【００４９】
１００  コンピューティングシステム環境
１１０  コンピュータ
１２０  プロセッシングユニット
１２１  システムバス
１３０  システムメモリ
１３１  リードオンリーメモリ（ROM）
１３２  ランダムアクセスメモリ(RAM)
１３３  基本入出力システム（BIOS）
１３４  オペレーティングシステム
１３５  アプリケーションプログラム
１３６  他のプログラムモジュール
１３７  プログラムデータ
１４０  インタフェース
１４１  ハードディスクドライブ
１４４  オペレーティングシステム
１４５  アプリケーションプログラム
１４６  その他のプログラムモジュール
１４７  プログラムデータ
１５１  磁気ディスクドライブ
１５２  取り外し式で不揮発の磁気ディスク
１５５  光ディスクドライブ
１５６  取り外し式で不揮発性の光ディスク
１６０  ユーザ入力インンターフェース
１６１  ポインティングデバイス
１６２  キーボード
１６３  カメラ
１６４  イメージ
１６５  カメラインタフェース
１６８  マイクロホーン
１７１  ローカルエリアネットワーク（LAN）
１７３  広域エリアネットワーク（WAN）
１８０  リモートコンピュータ
１８１  メモリ記憶装置
１８５  リモートアプリケーションプログラム
１９０  ビデオインタフェース
１９１  モニター
１９５  出力周辺インタフェース
１９６  プリンタ
１９７  スピーカ
【図１】
2004334888.tif 000004
【図２】
2004334888.tif 000005
【図３】
2004334888.tif 000006
【図４】
2004334888.tif 000007
【図６】
2004334888.tif 000008
【図７】
2004334888.tif 000009
【図５】
2004334888.tif 000010