(57)【要約】  文書内の複数の地理空間リファレンスの1つまたは複数を識別すること、および複数の地理空間リファレンスのそれぞれの識別された地理空間リファレンスに関して、(1)選択された座標系の座標セットによって表される地理的場所を、識別された地理空間リファレンスに関連付けること、(2)座標をインタリーブして、階層表現を形成することが含まれることが可能な、地理的場所を符号化する地理的テキストストリングを生成すること、および(3)地理的テキストストリングを、識別された地理空間リファレンスに関連付けることを含む文書を処理する方法。
2007538343.tif 000002
【特許請求の範囲】
【請求項１】
文書を処理する方法であって、
前記文書内の複数の地理空間リファレンスの1つまたは複数を識別すること、および
前記複数の地理空間リファレンスのそれぞれの識別された地理空間リファレンスに関して、選択された座標系の座標セットによって表される地理的場所を、前記識別された地理空間リファレンスに関連付けること、
前記座標セットの階層座標表現を生成すること、
前記階層座標表現に基づき、汎用のクエリスタイルにおいて与えられたクエリによって取得されることが可能な地理的テキストストリングを生成すること、および
前記地理的テキストストリングを前記識別された地理空間リファレンスに関連付けることを含む方法。
【請求項２】
前記汎用のクエリスタイルは、末尾ワイルドカードクエリである請求項1に記載の方法。
【請求項３】
前記汎用のクエリスタイルは、句検索クエリである請求項1に記載の方法。
【請求項４】
前記汎用のクエリスタイルは、ストリングマッチクエリである請求項1に記載の方法。
【請求項５】
前記選択された座標系は、非階層型であり、階層座標表現を生成することは、前記座標セットの座標をインタリーブすることを含む請求項1に記載の方法。
【請求項６】
前記選択された座標系は、緯度座標と経度座標を含む請求項5に記載の方法。
【請求項７】
前記選択された座標系は、四元三角形メッシュ座標系である請求項1に記載の方法。
【請求項８】
前記地理的テキストストリングを前記識別された地理空間リファレンスに関連付けることは、対応する地理空間リファレンスの位置において前記文書の中にその地理的テキストストリングを挿入することを含む請求項1に記載の方法。
【請求項９】
前記地理的テキストストリングを前記識別された地理空間リファレンスに関連付けることは、前記文書内でその地理的テキストストリングが関連付けられている前記地理空間リファレンスを識別するスタンドオフメタデータのデータ構造の中に、その地理的テキストストリングを入れることを含む請求項1に記載の方法。
【請求項１０】
前記複数の地理空間リファレンスのそれぞれの識別された地理空間リファレンスに関して、前記関連付けられた地理的場所に関する信頼レベルを算出することも行い、前記地理的場所を地理的テキストストリングとして符号化することは、前記地理的場所と前記信頼レベルをともに前記地理的テキストストリングに符号化することを含む請求項1に記載の方法。
【請求項１１】
前記地理的テキストストリングを生成することは、前記テキストストリング内の前記信頼レベルを、異なる信頼レベル範囲をそれぞれが表す複数のビンの対応するビンとして表現することを含む請求項10に記載の方法。
【請求項１２】
前記地理的テキストストリングを生成することは、前記地理空間リファレンスの付近のテキストの一部分を識別する文字シーケンスを追加することを含む請求項1に記載の方法。
【請求項１３】
文書を処理する方法であって、
前記文書内の複数の地理空間リファレンスの1つまたは複数を識別すること、および
前記複数の地理空間リファレンスのそれぞれの識別された地理空間リファレンスに関して、選択された座標系の座標セットによって表される地理的場所を、その識別された地理空間リファレンスに関連付けること、
その関連付けられた地理的場所に関する信頼レベルを算出すること、
前記地理的場所と、その識別された地理空間リファレンスに関する前記信頼レベルをともに地理的テキストストリングとして符号化すること、および
前記地理的テキストストリングを前記識別された地理空間リファレンスに関連付けることを含む方法。
【請求項１４】
符号化することは、その関連付けられた地理的場所に関する前記座標セットの座標をインタリーブして、前記地理的テキストストリングを生成することを含む請求項13に記載の方法。
【請求項１５】
前記地理的場所と、その識別された地理空間リファレンスに関する前記信頼レベルをともに地理的テキストストリングとして符号化することは、前記テキストストリング内の前記信頼レベルを、異なる信頼レベル範囲をそれぞれが表す複数のビンの対応するビンとして表現することを含む請求項13に記載の方法。
【請求項１６】
前記地理的場所と、その識別された地理空間リファレンスに関する前記信頼レベルをともに地理的テキストストリングとして符号化することは、前記信頼レベルを数字ストリングとして表現し、前記数字ストリングを、その関連付けられた地理的場所に関する前記座標セットの座標と一緒にインタリーブして、前記地理的テキストストリングを生成することを含む請求項13に記載の方法。
【請求項１７】
前記選択された座標系は、階層座標系である請求項13に記載の方法。
【請求項１８】
前記選択された座標系は、緯度座標と経度座標を含む請求項13に記載の方法。
【請求項１９】
前記選択された座標系は、四元三角形メッシュ座標系である請求項13に記載の方法。
【請求項２０】
前記地理的テキストストリングを前記識別された地理空間リファレンスに関連付けることは、対応する地理空間リファレンスの位置において前記文書の中にその地理的テキストストリングを挿入することを含む請求項13に記載の方法。
【請求項２１】
前記地理的テキストストリングを前記識別された地理空間リファレンスに関連付けることは、前記文書内でその地理的テキストストリングが関連付けられている前記地理空間リファレンスを識別するスタンドオフメタデータのデータ構造の中に、その地理的テキストストリングを入れることを含む請求項13に記載の方法。
【請求項２２】
文書セットを処理する方法であって、
前記文書セットの中の各文書に関して、その文書内の複数の地理空間リファレンスの1つまたは複数を識別すること、
その文書内の前記複数の地理空間リファレンスのそれぞれの識別された地理空間リファレンスに関して、選択された座標系の座標セットによって表される地理的場所を、前記識別された地理空間リファレンスに関連付けること、
前記関連付けられた地理的場所に関する信頼レベルを算出すること、
前記地理的場所と、前記地理的場所の信頼レベルを地理的テキストストリングに符号化すること、および
前記地理的テキストストリングを前記識別された地理空間リファレンスに関連付けることを含む方法。
【請求項２３】
前記文書セットに関する汎用の検索エンジンテキスト索引を作成することをさらに含み、前記テキスト索引は、前記文書セットの中の語とともに、前記文書セットの中の文書に関連付けられた前記地理的テキストストリングにも索引を付ける請求項22に記載の方法。
【請求項２４】
前記文書セットに関する拡張された検索エンジン索引を作成することをさらに含み、前記拡張された検索エンジン索引は、前記文書セットの中の語とともに、前記文書セットの中の文書に関連付けられた前記地理的テキストストリングにも索引を付け、前記拡張された検索エンジン索引は、前記地理的テキストストリングの特別な扱いをもたらす請求項22に記載の方法。
【請求項２５】
前記拡張された検索エンジン索引によってもたらされる前記特別な扱いは、前記地理的テキストストリングに関連付けられた信頼度値が、適合度スコア付けに影響を与えることを可能にすることを含む請求項24に記載の方法。
【請求項２６】
複数の文書のなかで、地理的場所に関連付けられた地理空間リファレンスを含有する文書を識別するためのテキスト検索クエリを構築する方法であって、
前記地理的場所のIDを受け取ること、
前記指定を受け取ったことに応答して、前記地理的場所を座標セットとして表現すること、および
前記地理的場所に関する前記座標セットの座標をインタリーブすることにより、前記地理的座標セットから地理的テキストストリングを生成することを含む方法。
【請求項２７】
前記地理的テキストストリングをテキスト検索エンジンにサブミットすることをさらに含み、前記テキスト検索エンジンは、前記地理的場所に関連付けられた地理空間リファレンスを含有する文書を識別するように前記複数の文書に関するテキスト索引を検索する請求項26に記載の方法。
【請求項２８】
信頼度の指定を受け取ることをさらに含み、前記地理的テキストストリングを生成することは、前記信頼レベルの表現を前記地理的座標セットと組み合わせて、前記地理的テキストストリングを生成することをさらに含む請求項26に記載の方法。
【請求項２９】
複数の異なる検索エンジンを利用して、地理的に制約された検索を構築する方法であって、
複数の特別にフォーマットされた階層ストリングを生成すること、
少なくとも1つの特別にフォーマットされた階層ストリングで補足された索引付き文書をそれぞれが有する複数の検索エンジンに、前記複数の特別にフォーマットされたストリングを送ること、および
前記複数の検索エンジンから応答を受け取ると、1つまたは複数の結果レイヤを生成することを含む方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書データベース、地理的情報取得、および検索エンジンに関する。
【背景技術】
【０００２】
検索者が、文書を徹底的に探し、明示的に指定されたテキストを探し出すことができるようにする多くのテキスト検索ツールが存在する。テキスト検索エンジンは、ユーザが、キーワードと呼ばれる特定の語、およびキーフレーズを求めて文書を検索することができるようにする、広く使用される部類のツールに数えられる。また、テキスト検索エンジンは、範囲制約、句クエリ(phrase queries)、ワイルドカードクエリ、および任意の許容されるクエリのブール結合(Boolean combinations)を含むクエリも、通常、サポートする。
【０００３】
ときとして、地理空間クエリで文書を検索することが望ましい。地理空間クエリでは、検索者は、空間的な地理的場所の範囲に対応する情報を探す。そのような範囲は、緯度と経度の範囲などの、地理的座標の範囲として指定される。地理空間クエリを実行するのに、検索者は、レコードの中の地理的フィールドに従ってデータレコードに索引付けをする、Rツリーまたはクワッドツリーなどの、特別に構築された空間的索引を使用する特別な検索エンジンを使用しなければならない。ユーザがキーワード制約と地理的制約の両方を使用して文書を検索することを可能にするシステムを構築するのに、2つの別個の索引、すなわち、テキスト索引および空間的索引を使用することができる。そのようなシステムは、2つの索引からの別々の結果リストを交差させた後、結果を再ソートしなければならない。そのようなソートされる結合(sorted join)は、文書の大量の集まりに関して多数回のディスクシークを要して、通常、極めて非効率であり、文書の大量の集まりに対する単純なクエリに回答するのに数分かかる、または数時間さえかかる可能性がある。2つの別々の索引を組み合わせることは、地理空間クエリをテキスト検索と組み合わせるクエリを効率的に扱うことができない。
【特許文献１】米国特許出願公開第２００２／００７８０３５号明細書
【特許文献２】米国特許出願公開第２００４／００７８７５０号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本明細書で説明される諸実施形態は、別個の地理的索引を作成することなしに、従来のテキスト検索索引を使用する地理的テキスト検索のための様々な方法を使用する。それらの技術は、汎用のキーワード検索システムが、地理的座標に関する特別な索引付け、および自然言語信頼度スコアメタデータなしに、特定の地理的ドメインに結果を限定することを可能にする。さらに、それらの技術は、変更されていない汎用のキーワード検索システムが、そのような複数制約クエリの結果を、複数制約の少なくともいくらかの知識を有して、適合率に応じてソートすることを可能にする。本明細書で説明される他の諸実施形態は、システムの適合度ソートファンクションが、文書における地理的情報に対してより高い意識を有することを可能にするように、汎用のキーワード検索システムに行われることが可能な変更を説明する。そのような変更された検索システムは、本明細書では、「拡張された検索エンジン」と呼ばれる。
【０００５】
このため、本明細書で説明される諸実施形態は、地理的検索システムを構築する際の次の2つの特定の課題に対処する。すなわち、1)地理的検索制約と非地理的検索制約をともに含む検索に合致する文書のリストを効率的に生成すること、および2)指定された検索に対する各文書の関連性の地理的評価と非地理的評価の両方を組み込む適合度ファンクションに基づき、そのようなリストを効率的にソートすることである。これは、地理的座標、信頼度スコア、重点スコア(emphasis score)、およびその他の情報を、特別にフォーマットされたストリングに符号化することによって達せられる。説明される実施形態は、それらのストリングに汎用のテキスト検索コマンドを使用してアクセスすることが可能なように、それらのストリングをフォーマットするいくつかの方法を教示する。
【０００６】
以上により、地理的マップベースのユーザインタフェースが、適切にソートされた結果でユーザクエリに回答するのに高いコストがかかる、ソートされる結合を要する別個の地理的範囲クエリ索引を要さずに、汎用のキーワード検索システムから、非構造化文書にアクセスすることが可能になる。地理的クエリおよび非地理的クエリが、別個の索引によって回答される場合、2つの索引からの結果のリストは、一緒に交差させられなくてはならないだけではなく、地理的要因と非地理的要因をともに組み込む新たなソートファンクションに従って再ソートも行われなければならない。地理的要因と非地理的要因をともに組み込む適合度ファンクションの例が、検索クエリと合致する地理的リファレンスが、その検索クエリによって指定される非地理的項にテキストとして近い場合を検出する、テキスト近接適合度ファンクションである。例えば、地理的クエリ制約と非地理的クエリ制約にともに合致する文を有する文書は、文書の両端における段落を介して制約と合致する文書よりも明らかに適合度が高い。以上、およびその他の組み合わせられた適合度ファンクションは、文書全体の分析を要求し、この分析は、別々の索引からの結果を結合する時点で実行するのに極めて高いコストがかかる。ソートされる結合としても知られる、この再ソートされる交差は、結合される2つのリストのサイズに比例した時間を要し、このサイズは、通常、文書の集まりのサイズである。数百万の文書の集まりの場合、このことは、検索結果を計算するのに数分、数時間、または数日さえかかることを意味する可能性がある。
【課題を解決するための手段】
【０００７】
本明細書で説明されるのは、あたかも通常のキーワードであるかのように索引付けされることが可能であり、末尾ワイルドカードクエリ、句クエリ、およびブール演算子クエリを含む、様々な汎用のキーワード検索技術を使用して検索されることが可能なテキストストリングで、文書についての地理的場所メタデータを表す様々な方法である。一部の実施形態は、その地理的情報を利用するためにグラフィカルユーザインタフェース技術を使用する。一般に、地理的マッピングユーザインタフェースのシステムは、そのような特別に符号化された地理的メタデータを含む1つまたは複数のテキスト検索索引と対話する。本明細書で説明されるそれらの技術は、場合により、既存のテキスト検索索引付けソフトウェアを全く変更せずに、地理的メタデータが、既存のテキスト検索インフラストラクチャに追加されることを可能にする。また、パフォーマンスをさらに向上させるのに役立つ特定の変更も開示される。
【０００８】
他の先行技術のシステムでは、座標メタデータが、通常、索引の中に格納される。例えば、本出願の譲受人によってやはり所有され、参照により本明細書に組み込まれている米国特許出願第０９／７９１，５３３号（米国特許出願公開第２００２／００７８０３５号）明細書および米国特許出願第１０／６３３，９１５号（米国特許出願公開第２００４／００７８７５０号）明細書において説明されるシステムのようなシステムは、地理的範囲検索がテキスト検索と組み合わせられることを許す非常に独特な構造の中に文書からのテキスト情報を保持するための特別な索引を使用する。それらの先行技術のシステムは、テキストデータと地理的データをともに、普通でないデータ構造の中に保持することにより、ソートされる結合を効率的に計算する目標を達する。CartaTreeとして知られる、この特殊化された索引データ構造は、文書からのすべての語を、従来の地理的クワッドツリーに似た空間ツリーに構成する。VerityのK2、AutonomyのIDOL、およびApacheのLuceneなどの汎用の検索エンジンツールは、そのような混成空間テキスト索引を含まないので、2つの別々の索引からの結果をマージさせ、再ソートすることなしに、地理的検索に回答することができない。本明細書で説明される概念は、特殊化されたクライアントアプリケーション(「拡張されたマップユーザインタフェース」と呼ばれる)が、地理的検索のために汎用の検索索引を利用することを可能にする。本明細書で説明される諸概念は、地理的検索の複雑さを索引から、汎用の索引の中に一般的な技術を使用して格納された特殊化されたメタデータを利用するクライアントソフトウェアに移す。
【０００９】
従来のテキスト索引付けソフトウェア、テキスト索引、およびテキスト検索エンジンソフトウェアは、地理的範囲クエリとしても知られる空間ドメインクエリを扱うための機構を全く有さない。多くのテキスト索引は、リポジトリからの文書と一緒に索引付けされたメタデータに、<>≦≧で表される比較演算子を適用する機構を有するが、このメタデータは、データ値を比較するためにユークリッドメトリックを適用することができる別個の索引の中に別個に読み込まれなければならない。通常、テキスト索引は、抽象的な2つの語の間の「距離」の概念を全く有さずに、語を別々のデータ要素として扱う。通常のテキスト検索索引は、それぞれの特定の文書内の語と語の間の、いわゆる「文字距離」をキャプチャするが、これは、語自体の空間に対する根拠のある距離メトリックではない。地球上の地理的距離は、正にそのような根拠のある距離メトリックを提供する。すなわち、任意の2つの地点間の距離は、それらの地点について述べるいずれの文書とも無関係に、キロメートル単位で測定されることが可能である。このため、汎用のテキスト検索システムが、地理的情報を保持するには、システムは、システムのテキスト索引とは別個である、Rツリーもしくはクワッドツリー、または他の特別な空間データ索引などの、多次元範囲クエリ索引を使用しなければならない。この分離は、そのようなシステムが、それらの演算子を他のテキスト検索コマンドと組み合わせるクエリに回答するのに、通常、長い時間を要することを余儀なくする。地理的範囲に基づく、適合度ソートされた結果リストを生成することは、従来のテキスト検索エンジンでは、不可能であるか、または極めて遅い。
【００１０】
本明細書で説明される様々な諸実施形態は、従来のテキスト検索索引を使用して、座標を格納し、オプションとして、ジオパーサ(geoparser)によって生成される信頼度メタデータ、および他の適合率も格納して、それらにアクセスする。ジオパーサは、電子ファイルについての情報に基づいて地理的座標を作成するソフトウェアシステムである。ジオパーサは、人的入力を使用して、いずれの座標をファイルに関連付けるかを判定することができ、あるいは、完全に自動的に動作して地理的座標を作成して、ファイルに関係のある点、線、多角形、および他の地理的エンティティを記述することもできる。人間の操作者の助けを借りて、または完全に自動的に、そのようなメタデータを作成する際、ジオパーサは、特定の座標、または特定の地理的エンティティが、ファイルに実際に正しく関連付けられている尤度を示す数値である、信頼度スコアを通常、生成する。例えば、完全に自動的なジオパーサは、文書の自然言語文脈を解釈して、いずれの場所を作成者が意図していたかを推測することができる。それらの推測の品質は、地理的エンティティを記述する座標と一緒に、ジオパーサによって出力される信頼度スコア(ジオコンフィデンス)によって見積もられる。ジオコンフィデンスは、通常、地理的制約を含むクエリに応答して、ファイルの適合度スコア付けに算入される。このため、ジオコンフィデンスが地理的座標とともに、汎用のテキスト検索エンジンの中に格納されることを可能にする形で、ジオコンフィデンスを符号化することにより、それらの方法は、従来のテキスト検索エンジンが、比較演算子を使用することなく、特別なメタデータテーブルを全く使用することなく、文書の中の他のすべての語を処理するのに使用される技術とは別個の特別な読み込み技術を必然的に要求することなしに、何らかの形態の適合度ソートされた地理的範囲クエリに回答することを可能にする。
【００１１】
本明細書で説明される符号化は、テキスト検索エンジンに対する特別な変更なしに、また、別個の地理的データ構造の必要性なしに、ほとんどあらゆるテキスト検索エンジンにおいて使用されることが可能である。汎用の検索システムに対する有用な変更は、可能である。本発明は、汎用の検索システムが、特別にフォーマットされた地理的ストリングを含む文書に対して良好な適合度ファンクションを計算することがよりよくできるようにする、汎用の検索システムに対する様々な特定の拡張を企図している。例えば、汎用の検索エンジンは、通常、文書内のすべての語に、語位置を割り当て、文書に追加されたすべての地理的ストリングに語位置を通常、割り当てる。スタンドオフメタデータ(以下に説明する)を受け入れるように汎用の検索エンジンを変更することにより、地理的ストリングをより適切に扱う拡張された検索エンジンを作成することができる。別の実施例として、汎用の検索エンジンは、通常、信頼度スコアの概念を全く有さない。本発明は、これに対処する2つの方法を教示する。前述したとおり、第1は、ジオコンフィデンスを、特別にフォーマットされた地理的ストリングに符号化することである。第2の方法は、信頼度を、文書におけるすべての語の特性として扱うように検索エンジンを拡張することである。
【００１２】
地理的項をキーワード検索可能なフォーマットでアクセス可能にすることにより、本発明は、スタンドオフ表記や信頼度スコアなどの、さらなる変更が、他のすべての語を保持するのと同一の汎用のテキスト索引構造に対して作用することを可能にする。このため、本発明は、汎用のテキスト検索システムの多種多様なさらなる地理的検索拡張を実現可能にする鍵(key enabler)である。
【００１３】
重要な概念は、階層座標系の概念である。階層座標系は、多様体、つまり、アフィン空間の領域のグラフ表現である。数学において従来、定義されるアフィン空間は、任意の2つの点がベクトルによって接続されることが可能な空間である。アフィン空間内の座標に関して、好ましい原点は、必ずしも存在せず、座標は、平坦(すなわち、ユークリッド)でなくてもよい。例えば、地球の表面上の投影されていない緯度座標/経度座標が、非ユークリッドアフィン空間内の座標の例である。アフィン空間内の各点は、nタプル(n-tuple)の数によって定義されることが可能である。一般に、そのような数は、実数または複素数であることが可能であり、地球上の緯度/経度は、実数を使用する。特に、地理的情報システム(GIS)において、そのような座標nタプルは、無限精度であるものと、しばしば、想定され、これは、nタプルの中の各数の終わりに、0の無限ストリングが存在するものと暗黙に想定されていることを意味する。つまり、以下の座標、
(48.23, 23.39)
は、実際には、
(48.2300000000..., 22.39000000...)
であり、これらの0は、永遠に繰り返す。これは、座標タプルが、点オブジェクトを定義することを意味する。
【００１４】
これとは対照的に、階層座標系は、広がりを有するオブジェクトを定義する。階層座標系は、長いストリングを使用して、非常に小さい面積を指すことが可能である。しかし、実際の点を記述するのに、階層ストリングは、無限長でなければならない。階層ストリングのこの面積特性は、本明細書で開示される方法の一部を成す。例えば、地球の表面上の多角形は、面積を有し、その多角形に内接する多角形の集合も、面積の広がりを有する。例えば、ドイツ国が、面積の広がりを有する多角形によって記述されることが可能である。ドイツ内の様々な州は、やはり面積の広がりを有する多角形によって記述されることが可能である。階層座標系は、それらの多角形のそれぞれに名前を割り当て、各名前の中に、含有される多角形のすべての名前を含めることによって構築される。含有する多角形は、ツリー構造において、子の多角形の親である。階層座標系は、そのようなツリー構造、つまり、有向非循環グラフに対する単なる命名規則である。階層座標系は、各多角形の名前が、ツリーにおけるその多角形より上位の親ノードのすべてをあいまいさなしに明らかにすることを可能にする。MGRS(Military  Grid  Reference  System)およびQTM(Quaternary  Triangular  Mesh(四元三角形メッシュ))が、階層座標系の例である。QTMでは、地表が、三角形のメッシュで覆われ、各三角形は、4つの新たな「子」三角形に細分される。QTMツリー構造を初期設定するのに、8つの大きい三角形が、八面体の形状で地球上に配置される(QTMの背景に関しては、http://www.spatial-effects.com/SE-papers1.htmlを参照されたい)。それらの初期の8つの三角形には、0から7までの番号が付けられることが可能である。それらの三角形が、次に、より小さい三角形に細分される。各三角形に番号(0,1,2,または3)を付けることにより、任意の三角形が、最も大きい含有する三角形を最初にリストアップし、次のより小さい含有する三角形を次にリストアップし、次のより小さい三角形を次にリストアップし、以下同様に、最も小さい三角形の番号がリストアップされるまで続けることによって識別されることが可能である。
【００１５】
例えば、ドイツの一部を覆う三角形は、ツリー構造を初期設定するのに使用された第5の大きい三角形の第3の三角形内の第2の三角形であることが可能である。ドイツ上のこの三角形は、ストリング532によって識別される。この三角形は、階層の1つ下のレベルにおいて4つの三角形を含み、それらの三角形は、5320、5321、5322、および5323という名前を有する。また、それらのそれぞれも、4つの三角形を含み、任意の深度レベルまで、以下同様である。より深いレベルは、より高い空間精度に対応する。
【００１６】
階層座標ストリングの特徴を定義する別の特徴は、ストリングの両端の記号が、大きいスケールと小さいスケールを指すことである。ストリングにおけるそれぞれのさらなる記号は、漸進的に小さくなるスケールに対応する。あらゆる10進法のような表記法の場合と同様に、記号は、右から左にも、左から右にも書かれることが、当然、適切な変更が汎用のクエリスタイルに加えられて、可能である。アフィン空間の漸進的により小さい面積(つまり、ハイパーボリューム)を指定する記号の任意のストリングが、階層座標として使用されることが可能である。
【００１７】
そのような階層座標系は、任意のアフィンベクトルから構築されることが可能である。アフィン空間内の点を定義するnタプルの数が、以下に説明される方法を使用して、階層座標系の趣旨で再フォーマットされることが可能である。本発明は、任意のアフィン空間ベクトルnタプルを有用な階層表現に変換する方法を教示する。
【００１８】
本発明は、アフィン空間のそのような階層ツリー表現を利用して、例えば、地理的意味などの、1次元より高次の意味を含む、語のようなストリングを構築する。それらの語のようなストリングは、空間座標を有する任意のデータオブジェクトに関して構築されることが可能である。最初の空間座標が、変換される必要があったアフィンベクトルとしてフォーマットされていたか、または階層ツリー座標として既にフォーマット済みであったかにかかわらず、本発明は、汎用のテキスト検索エンジンにおいて使用するために、階層ストリングをフォーマットするためのいくつかの方法を教示する。それらのフォーマット技術は、汎用のテキスト検索エンジンが地理の概念を有することを全く要求することなしに、汎用のテキスト検索コマンドが、ストリングの地理的意味を検出することができるように、特別に符号化されたストリングに対して作用することを可能にする。説明される実施形態は、次の2つの形で、すなわち、第1に、語だけを保持するために設計されたテキスト索引において使用される汎用のテキスト検索コマンドを介して、階層ストリング符号化にアクセスする形、および第2に、特別にフォーマットされた階層ストリングが、クエリに応答して生成された結果をソートする適合度スコア付けに影響を与えることを可能にする形で、階層座標系を使用する。
【００１９】
本明細書で述べる、「クエリスタイル」とは、検索エンジンに発行されることが可能な任意のタイプの検索コマンドである。例えば、ワイルドカードクエリスタイルは、ユーザが、ワイルドカードクエリによって指定されたサブストリングを含む語を含有する文書を探し出すことを可能にする。この場合、通常の表現に関する一般的に知られているシンタックスが、適用される。例えば、
te?t
を検索することは、「te」で始まり、「t」で終わり、中間に1文字を有するすべてのストリングを探し出す。また、
te*t
を検索することは、「te」で始まり、「t」で終わり、中間に任意の数の文字を有するすべてのストリングを探し出す。一部の実施形態において使用される特定のクエリスタイルは、以下のとおり、クエリストリングの終わりにアスタリスクを付ける末尾ワイルドカードクエリスタイルであり、
te*
これは、文字「te」で始まり、文字なしを含め、任意の数の文字をその後に有する語を含有するすべての文書を取得する。
別のタイプのクエリスタイルは、句クエリスタイルである。句検索は、以下のとおり、クエリ語のまわりに引用符を付けることによって通常、指定され、
“elephant  food”
これは、互いに隣り合う「elephant」という語と「food」という語を含有する文書だけを探し出す。引用符なしでは、通常の検索エンジンは、任意の位置で両方の語を含むすべての文書を戻す。一部の検索エンジンは、以下のような句検索に対して作用することが可能な近さ演算子をサポートする。すなわち、
“elephant  food”〜30
これは、互いから30語の範囲内で、これらの語を含有するすべての文書を探し出す。これは、エンジンが、文書の句読法を分析して、語の境界を識別することに通常、基づき、文書を語に分けることを要求する。
【００２０】
別のクエリスタイルは、ユーザが、一般的に知られているAND演算子、OR演算子、およびNOT演算子を使用して、様々な他のクエリスタイルを単一の表現に組み合わせることを可能にするブールクエリスタイルである。
【００２１】
多くのクエリスタイルが存在する。本明細書で使用する「汎用のクエリスタイル」とは、ストリングの中のいずれの意味も解釈することなしに、ストリングに対して作用するクエリスタイルを指す。一般的ではないクエリスタイルの例は、関係上の意味を、クエリが作用するフィールドの中のデータの属性と考える、標準の範囲クエリである。一般的に知られている大なり演算子および小なり演算子は、意味のある形態にキャストされているデータオブジェクトだけに適用されることが可能である。通常、この意味生成は、データオブジェクトを型付けされたフィールドの中に入れることによって達せられ、型は、整数と同形である。大なり演算子および小なり演算子は、整数に対して定義されることが可能であるので、型付けされたフィールドと整数の間の同形性を利用して、範囲演算子を適用することができる。この意味生成ステップは、型付けされていない記号ストリングに対してだけ作用することが可能な、汎用のクエリスタイルには要求されない。そのような型付けされていないストリングは、しばしば、非構造化データと呼ばれる。汎用のクエリスタイルは、非構造化データに対して作用する。
【００２２】
説明される実施形態は、汎用のクエリスタイルだけを使用する地理的検索システムを構築する。つまり、実施形態は、非構造化データを扱うようにだけ設計された索引を利用する地理的検索システムを構築する。エンジンが、様々な一般的でないクエリスタイルをサポートする場合でも、それらのクエリスタイルは、文書の大量の集まりに対する語検索と組み合わせられた場合、実行が遅い可能性が高い(前述したとおり)。
【００２３】
それらの汎用のクエリスタイルを使用して、それらの特別にフォーマットされた階層ストリング符号化にアクセスすることに加えて、説明される実施形態は、結果をソートするために、何らかの形態の地理を意識した適合度を効率的に計算することができる、拡張された検索エンジンをさらに開示する。そのような地理を意識したテキスト検索適合度ファンクションに盛り込まれることが可能な多くの要因のなかで、高い重要性の3つの要因を説明する。説明される実施形態は、汎用の検索エンジン上と拡張された検索エンジン上の両方で、汎用のクエリスタイルを介して、特別にフォーマットされた階層ストリング符号化を使用する際に、それら3つの要因をどのようにキャプチャするかを教示する。
【００２４】
さらに、説明される実施形態は、それらの特別にフォーマットされた階層ストリング符号化を使用して、拡張されたマップ検索インタフェースが、異なるタイプの汎用のクエリスタイルをサポートするテキスト検索エンジンを介して、複数の文書リポジトリにアクセスすることを可能にする。そのような拡張されたマップ検索インタフェースは、複数のリポジトリにわたる、いわゆるフェデレーション検索を実行して、その結果を、1つまたは複数の結果セットに効率的にマージすることができる。
【００２５】
一般に、一態様では、本発明は、文書を処理する方法を特徴とする。方法は、文書内の複数の地理空間リファレンスの1つまたは複数を識別すること、および複数の地理空間リファレンスのそれぞれの識別された地理空間リファレンスに関して、(1)選択された座標系の座標セットによって表される地理的場所を、識別された地理空間リファレンスに関連付けること、(2)座標セットの座標をインタリーブする、または別の形で、座標の階層表現を獲得することが含まれる、地理的座標を符号化する地理的テキストストリングを生成すること、(3)地理的テキストストリングを、選択されたクエリスタイルで使用するためにフォーマットすること、および(4)地理的テキストストリングを、識別された地理空間リファレンスに関連付けることを含む。
【００２６】
他の諸実施形態は、以下の特徴の1つまたは複数を含む。選択された座標系は、地球上、または地球の一部分(例えば、緯度の座標と経度の座標を含む、または、例えば、マサチューセッツ州平面図座標を含む)上の非階層座標系である。代替的に、選択された座標系は、階層座標系(例えば、三角形メッシュなどの、入れ子形状のメッシュを含む)である。階層座標系の特定の例が、四元三角形メッシュ座標系である。地理的テキストストリングを、識別された地理空間リファレンスに関連付けることには、その地理的テキストストリングを、対応する地理空間リファレンスの位置で文書の中に挿入することが含まれる。代替的に、地理的テキストストリングを識別された地理空間リファレンスに関連付けることには、その地理的テキストストリングを別個のファイルの中に入れることが含まれ、これによっても、文書の中でその地理的テキストストリングが関連付けられている地理空間リファレンスが識別される。複数の地理空間リファレンスのそれぞれの識別された地理空間リファレンスに関して、関連する地理的位置に関する信頼レベルを算出することも、地理的場所を地理的テキストストリングとして符号化することには、地理的場所と信頼レベルをともに地理的テキストストリングに符号化することが含まれる。地理的テキストストリングを生成することには、テキストストリング内で信頼レベルを、複数のビンの対応するビンとして表現することが含まれ、前記複数のビンのそれぞれが、異なる範囲の信頼レベルを表す。地理的テキストストリングを生成することには、地理空間リファレンスの付近に、テキストの一部分を識別する文字シーケンスを追加することが含まれる。
【００２７】
一般に、別の態様では、本発明は、文書を処理する別の方法を特徴とする。方法には、文書内の複数の地理空間リファレンスの1つまたは複数を識別すること、および複数の地理空間リファレンスのそれぞれの識別された地理空間リファレンスに関して、(1)選択された座標系の座標セットによって表される地理的場所を、その識別された地理空間リファレンスに関連付けること、(2)その関連付けられた地理的場所に関する信頼レベルを算出すること、(3)地理的場所と、その識別された地理空間リファレンスに関する信頼レベルをともに、地理的テキストストリングとして符号化すること、および(4)地理的テキストストリングを、識別された地理空間リファレンスに関連付けることが含まれる。
【００２８】
他の諸実施形態は、以下の特徴の1つまたは複数を含む。符号化することには、その関連付けられた地理的場所に関する座標セットの座標をインタリーブして、地理的テキストストリングを生成することが含まれる。地理的場所と、その識別された地理空間リファレンスに関する信頼レベルをともに、地理的テキストストリングとして符号化することには、テキストストリング内で信頼レベルを、複数のビンの対応するビンとして表現することが含まれ、複数のビンのそれぞれが、異なる範囲の信頼レベルを表す。代替的に、地理的場所と、その識別された地理空間リファレンスに関する信頼レベルをともに、地理的テキストストリングとして符号化することには、信頼レベルを数字ストリングとして表現すること、およびその数字ストリングを、その関連付けられた地理的場所に関する座標セットの座標とともにインタリーブして、地理的テキストストリングを生成することが含まれる。選択された座標系は、アフィン座標系(例えば、緯度の座標と経度の座標を使用する)である。代替的に、選択された座標系は、階層座標系である。地理的テキストストリングを、識別された地理空間リファレンスに関連付けることには、その地理的テキストストリングを、対応する地理空間リファレンスの位置で文書の中に挿入することが含まれる。地理的テキストストリングを、識別された地理空間リファレンスに関連付けることには、その地理的テキストストリングを別個のファイルの中に入れることが含まれ、これによっても、文書の中でその地理的テキストストリングが関連付けられている地理空間リファレンスが識別される。
【００２９】
一般に、さらに別の態様では、本発明は、文書セットを処理する方法を特徴とする。方法には、文書セットの中の各文書に関して、その文書内の複数の地理空間リファレンスの1つまたは複数を識別すること、およびその文書内の複数の地理空間リファレンスのそれぞれの識別された地理空間リファレンスに関して、(1)選択された座標系の座標セットによって表される地理的場所を、識別された地理空間リファレンスに関連付けること、(2)関連付けられた地理的場所に関する信頼レベルを算出すること、地理的場所、およびその地理的場所の信頼レベルを地理的テキストストリングに符号化すること、および地理的テキストストリングを、識別された地理空間リファレンスに関連付けることが含まれる。
【００３０】
さらに別の態様では、本発明は、複数の文書のなかで、地理的場所に関連する地理空間リファレンスを含有する文書を識別するためのテキスト検索クエリを構築する方法を特徴とする。方法には、地理的場所のIDを受け取ること、その指定を受け取ったことに応答して、前記地理的場所を座標セットとして表すこと、およびその地理的場所に関する座標セットの座標をインタリーブすることにより、地理的座標セットから地理的テキストストリングを生成することが含まれる。
【００３１】
他の諸実施形態は、以下の特徴の1つまたは複数を含む。方法は、テキスト検索エンジンに地理的テキストストリングをサブミットすることも含み、これにより、複数の文書に対するテキスト索引が検索されて、前記地理的場所に関連する地理空間リファレンスを含有する文書が識別される。方法は、信頼度の指定を受け取ることをさらに含み、地理的テキストストリングを生成することには、信頼レベルの表現を地理的座標セットと組み合わせて、地理的テキストストリングを生成することがさらにかかわる。
【００３２】
別の実施形態は、本明細書で説明される特別なテキストストリングを使用して、複数のテキスト検索エンジンのためのテキスト検索クエリを構築するクライアントアプリケーションを含む。異なるテキスト検索エンジンに関するテキスト符号化およびクエリフォーマットは、異なることが可能である。クライアントアプリケーションは、それらの様々なエンジンからの結果を1つまたは複数の結果セットにまとめて、それらの結果セットを、テキスト読み出しで、または地理的マップ上でユーザに表示することができる。
【００３３】
本発明の1つまたは複数の実施形態の詳細を、添付の図面、および以下の説明で提示する。本発明の他の特徴、目的、および利点は、説明および図面、ならびに特許請求の範囲から明白となろう。
【発明を実施するための最良の形態】
【００３４】
テキスト検索エンジンを使用することによって文書の地理空間適合度が検索されることが可能なように、文書を処理するテキスト索引付け-検索システム100が、図1に示されている。システム100は、システムに関する検索空間内の文書のすべてを含有する文書リポジトリ101と、リポジトリ101の中に格納された文書内の地理空間リファレンスを識別し、それらのリファレンスに、特別なテキストストリングをタグ付けして、タグ付けされた文書を一時文書リポジトリ102の中に入れるジオパーサ104と、一時文書リポジトリ102の中に格納されたすべての文書に関するテキスト索引108を生成するテキスト索引付けソフトウェア106と、ユーザによって指定された検索クエリ112に応える文書リポジトリ101の中のすべての文書を探し出すように、テキスト索引108に対して作用するテキスト検索ソフトウェア110とを含む。また、システム100は、キーワード検索ユーザインタフェース114およびマップユーザインタフェース116も含む。キーワード検索ユーザインタフェース114は、検索クエリ内に含められるべきいずれのキーワードでも、ユーザが指定することができるようにし、マップユーザインタフェース116は、検索クエリの中で使用されるべきいずれの地理空間範囲でも、ユーザが指定することができるようにし、また、対応する指定された信頼度閾値を満たす地理空間リファレンスだけに結果を制限する信頼度閾値を指定することも、ユーザが行うことができるようにする。検索クエリを指定するユーザインタフェースからテキストストリングを受け取ったことに応答して、テキスト検索エンジン110は、テキスト索引108を使用して、すべての関係のある文書を探し出し、通常、ディスプレイデバイス上の視覚的出力の形態で、または印刷出力として、または保存された電子ファイルとして、結果をユーザに戻す。
【００３５】
ジオパーサ104は、文書リポジトリ101の中で探し出された各テキスト文書を処理し、各文書に関して、その文書内で探し出された対応する地理空間リファレンスに関して、(緯度,経度,高度)のような、地理的座標を生成する。ジオパーサ104によって実行されるファンクションは、ジオパース(geoparsing)と呼ばれる。一般に、ジオパースには、地理的意義または地理的意味(すなわち、地理空間リファレンス)を有する文書内のリファレンスを探すことが含まれる。例えば、ジオパーサ104は、都市の名前(例えば、パリ、ボストン、ニューヨーク)、ウォールデン池またはチャールズ川のような場所の名前、および「カンダハールの北20マイル」のような、他の既知のストリングを探すことが可能である。ジオパーサ104は、それらのリファレンスを、地理空間的意義を有するものとして解釈し、次に、それらのリファレンスに、それらのリファレンスが関連付けられることが可能な1つまたは複数の地理的場所の座標を補う。
【００３６】
説明される実施形態では、ジオパーサ104は、米国特許出願第09/791,533号および米国特許出願第10/633,915号において説明されるとおり、ジオパース機能を自動的に実行するコードで実施される。しかし、人間が、ジオパーサの諸機能を実行して、文書についての関係する情報を手で入力することもできる。
【００３７】
また、ジオパーサ104は、識別されたテキストリファレンスが、ジオパーサ104がそのリファレンスに関連付ける場所を実際に参照している確率を示す信頼度スコアを生成することも行う。言い換えれば、信頼度スコアは、文書の作成者が、そのリファレンスに関する座標のソフトウェアによる選択に同意する確率と見なされることも可能である。それらの座標および信頼度スコアは、文書内のデータ(すなわち、文書内の地理空間リファレンス)についてのデータであり、したがって、「メタデータ」と呼ばれる。信頼度スコアは、作成者の元の言い回しを表現するようにソフトウェアによって選択された場所に人間が同意する確率を示すパーセンテージとして、通常、表現される。68%という信頼度スコアは、それらの座標が、作成者が意図したものであることに、100名の人間の読み取り者のうち68名が同意することを意味すると解釈されることが可能である。特定の地理的リファレンスに、異なる信頼度のいくつかの候補場所がタグ付けされることも可能である。例えば、世界には、Parisとして知られている少なくとも44の都市が存在し、したがって、「Paris」という語への特定のリファレンスは、いずれの特定の場所が作成者によって意図されていたかを明確に明らかにしない可能性がある。そのようなケースでは、自動ジオパーサは、そのリファレンスに、95%の信頼度で中央フランスのParisに関する座標をタグ付けし、57%の信頼度でテキサス州のParisに関する座標をタグ付けし、他の信頼度スコアで他の場所に関する座標をタグ付けすることが可能である。
【００３８】
そのような信頼度スコアの目的は、人間の読み取り者が、文書の大量の集まりからの検索結果を理解し、対応することができるように、システムが、最も正しく、最も有用な結果を最初に提示することを可能にすることである。そのような検索結果は、マップ検索ユーザインタフェース(これは、説明される実施形態では、検索エンジン110によって実施される機能である)上でプロットされる。信頼度スコアに従って結果をソートすることにより、正しくタグ付けされている可能性が高い場所が、先にユーザに提示される。
【００３９】
ジオパーサ104は、従来のテキスト検索索引付けソフトウェアを使用して検索されることが可能な形で座標-信頼度メタデータを符号化する、特別に構造化されたテキストストリングとして、場所-信頼度情報(すなわち、メタデータ)を表現する。それらの特別な符号化は、句検索、またはワイルドカードクエリ、またはブール演算子を活用して、範囲クエリを表現する。
【００４０】
一般に、ジオパーサ104によって使用される符号化方法は、特定の場所を識別する複数の空間座標を、単一の地理的テキストストリングに変換する。方法は、場所の座標を構成する数字をインタリーブすることにより、これを行う。したがって、例えば、座標が、(緯度,経度)に関して位置を指定する(48.28°,24.55°)である場合、左端の数字から始めて(すなわち最上位の数字)各座標から数字を交互にとり、数字のすべてが使用されるまで、その数字をテキストストリングに加えることにより、特別なテキストストリングを構築する。(48.28°,24.55°)という座標のケースでは、このプロセスは、以下のストリングをもたらす。すなわち、
「42842585」
である。
【００４１】
このインタリーブ技術は、各座標次元に沿った変位が、ストリング(通常、数字のストリング)によって表され、ストリングの各要素(つまり、各数字)が、その要素の右側の要素または数字より大きい空間範囲を表す、任意の多次元空間座標系に適用されることが可能である。前段で使用された緯度座標のケースでは、「4」という数字は、40.00°から49.99°までにわたる範囲を表す。これに対して、次の数字、すなわち、「8」は、10分の1の大きさの、8.00°から8.99°までにわたる範囲を表す。
【００４２】
座標系の他の例には、UMT(Universal  Traverse  Mercatur)が含まれる。前述したとおり、各座標ペアは、通常、無限精度を有するものと想定され、0の無限長のストリングが、終わりに暗黙に付けられている。それらの座標をインタリーブする際、それらの座標の左側と右側を十分な数の0でパディングして、有意な桁の実際の数にかかわらず、さらに精度にかかわらず、すべての座標次元が同一の長さであるようにすることが有用である。
【００４３】
MGRS(military  grid  reference  system)やQTM(quaternary  triangular  mesh)などの階層座標系は、既に単一ストリングフォーマットになっている。アフィン空間座標に関して前述したインタリーブ手続きは、アフィン空間に対応する階層座標を生成するための方法である。本明細書で説明される地理的ストリング符号化は、単に、階層座標のストリング表現である。説明される実施形態は、任意の階層座標系からのストリングに、または階層ストリングに変換される他の任意の座標系に適用されることが可能な、地理的テキスト取得における、それらのストリングの独特な用法を教示する。
【００４４】
一実施形態では、ジオパーサ104は、その地理的テキストストリングを、地理空間リファレンスのすぐ隣で文書の中に直接に挿入する。このアプローチは、本明細書では、「インライン」方法と呼ばれる。インライン方法によれば、ジオパーサ104は、文書を実際に変更し、これにより、特別なテキストストリングが挿入される位置の後に続く、文書内のすべての語位置が変更されることがもたらされる。つまり、インライン方法は、文書を「歪め」、これは、検索クエリにおいて近接条件が使用される場合、検索結果に影響を与える可能性が高い。
【００４５】
この問題を回避する代替のアプローチは、「スタンドオフ」方法と呼ばれる。スタンドオフ方法によれば、特別なテキストストリングを担持する別個のファイルが作成される。テキストストリングを担持することに加え、その別個のファイルは、実際の文書内で対応する地理空間リファレンスの位置を明らかにする文字位置を指定することも行う。これにより、地理的テキストストリングが、文書内の1つの文字位置、文字範囲、1つの語位置、または選択された語セットに関連付けられることが可能になる。地理的リファレンスを明らかにする語を選択することにより、スタンドオフ方法は、文書を歪めず、地理的テキストストリングが、テキスト近接性を使用する適合度ランク付け計算に参加することを許す。汎用の検索エンジンは、通常、スタンドオフメタデータをサポートしない。拡張された検索エンジンは、スタンドオフメタデータを扱うことができる。
【００４６】
ジオパーサ104は、符号化された地理的メタデータ情報を一時文書リポジトリ102の中に、インラインメタデータまたはスタンドオフメタデータとして、文書の一部として格納する。それらの特別なストリングを文書のコピーに追加することにより、従来のテキスト索引付けソフトウェアが、それらの特別なストリングを通常の語として解釈するように、基本的にごまかされ、それらのストリングが、汎用のクエリスタイルを使用する従来のテキスト検索ソフトウェアによって検索可能になる。これにより、従来のテキスト検索エンジンが、マップユーザインタフェースによって指定された地理的範囲に関係のある地理的表現を含有するすべての文書を、容易に探し出すことができるようになる。
【００４７】
通常、ただし、常にではないが、複数の文書が、文書リポジトリ101の中に格納され、バッチで一括処理されて、メタデータが追加される一時文書リポジトリ102が作成されることが可能である。代替的に、文書タグ付けパイプライン、またはジオパーサによって出力されたメタデータの正確さをユーザが確認することを可能にする文書エディタユーザインタフェースなどの、より大きい処理システムの一環として、個々の文書が、ジオパースされることも可能である。
【００４８】
リポジトリ102の中に格納された文書は、WebブラウザにURLを入力することなど、単に文書識別子をビューアに入力することにより、文書をユーザが取得することを可能にする、URLなどの文書識別子を通常、有する。テキスト索引付けエンジン106は、テキスト検索エンジン110によって操作されることが可能な「逆索引」、つまり、テキスト索引108を作成するようにリポジトリ102からの文書を処理して、文書識別子をユーザが知っていることを要求するのではなく、文書に含有されるキーワードおよび/または地理空間リファレンスに基づき、ユーザが文書を取得することを可能にする。
【００４９】
テキスト索引108は、ディスク上、またはメモリ内に格納された大きいファイルとして通常、表現される。テキスト索引108は、キーワード検索ユーザインタフェース114を介して入力された検索クエリコマンドに基づき、文書、またはURLなどの文書リファレンスをユーザが取得することを可能にする。キーワード検索ユーザインタフェース114は、リポジトリ102の中の文書を検索するために使用されるクエリを、ユーザが構築することを可能にする。検索クエリは、通常、1つまたは複数の文字ストリングを含み、場合により、スペースで分けられたストリングのセットを表す引用符、ワイルドカードマッチングを表すアスタリスク、およびブール演算を表すAND/OR/NOT演算子などの、演算子も含む。テキスト検索エンジン110は、次に、それらのコマンドを、一時文書リポジトリ102の中の文書について、テキスト索引108の中にエンジン110が格納している情報に適用する。テキスト索引108の中の情報は、それらのコマンドを適用するのに要求される時間を最適化するように、索引を作成したテキスト索引付けエンジンによって通常、編成される。例えば、「cat」という文字で始まる語の高速の取得を可能にするのに、テキスト索引エンジン110は、「catalog」および「catastrophe」という語を含有する文書を含め、「cat」で始まるあらゆる語を含有する文書に対するすべての文書識別子のリストを作成して、格納することが可能である。これにより、テキスト索引が、単に文書識別子のリストを戻すことによって、「cat*」という形態のワイルドカードクエリに回答することが可能になり、これは、そのクエリコマンドに合致する語を探して、すべての文書を再処理することよりもはるかに高速である。
【００５０】
説明される実施形態では、マップユーザインタフェース116は、ユーザが、検索条件として含まれるべき地理的区域を、グラフィカルユーザインタフェースを介して定義することができるようにする。インタフェース116は、グラフィカルユーザインタフェースを介してユーザによって入力される地理空間範囲を指定するだけでなく、それらの地理空間範囲を、以下により詳細に説明されるような地理的ストリング符号化に変換することも行うため、「拡張された」マップユーザインタフェースと呼ばれる。それらの符号化は、テキスト検索エンジン114に供給され、エンジン114は、それらの符号化を使用して、テキスト索引108を検索して、一時文書リポジトリ102の中の関係のある文書を識別する。
【００５１】
マップユーザインタフェース116は、キーワード検索ユーザインタフェース114を介してテキスト検索エンジン110と対話し、インタフェース114は、テキスト検索エンジン110と対話することができる汎用のキーワード検索ユーザインタフェースである。キーワード検索ユーザインタフェースは、テキスト検索エンジン110によって適用されるべき全体的検索クエリの一部を構成するキーワードを、ユーザがタイプ入力するインタフェースである。代替のアプローチは、テキスト検索エンジン110と直接に対話するようにマップユーザインタフェース116を設計することであり、そのケースでは、インタフェース116は、キーワード検索ユーザインタフェースの機能を組み込んで、符号化された地理的クエリとともにテキスト索引ソフトウェアに転送されるキーワードまたは検索コマンドを、ユーザが入力することができるようにすることが可能である。
【００５２】
マップユーザインタフェース116は、例えば、Windows（登録商標）オペレーティングシステムを使用するデスクトップコンピュータ上で実行されているESRI  ArcGISクライアント、または以下に説明される符号化を使用して、テキスト検索エンジンにクエリを発行する能力で拡張されたWebサーバによるサービスを受けるWebブラウザベースのアプリケーションを含め、多数のマップ表示アプリケーションのいずれか1つによって実施されることが可能である。テキスト検索エンジン110からの結果は、通常、表示アプリケーションにおけるマップ上にプロットされる。
【００５３】
マップ検索ユーザインタフェース116は、ユーザが、マップイメージをズームすることによって関心対象の空間ドメインを選択することを可能にする。イメージ内の表示可能なマップ領域が、次に、クエリ制約として使用されることが可能であり、あるいはユーザが、マップ上の関心対象の領域を強調表示することにより、空間検索条件を定義することができるようにされてもよい。例えば、2次元マップ検索ユーザインタフェースが、欧州のような区域の緯度-経度マップを示し、関心対象の領域のまわりにユーザがループを描くことができるようにすることが可能である。他方、3次元マップ検索ユーザインタフェースは、複合建造物のフライスルーを示し、関心対象の通路を囲む平行六面体をユーザが選択することができるようにすることが可能である。そのようなグラフィカルユーザインタフェースを使用して、単純な、または複雑な関心対象領域を定義するための、多数の既知の技術が存在する。いずれにしても、関心対象の多次元ドメインは、次に、キーワード検索コマンドと組み合わされて、汎用のテキスト検索エンジン110に送られ、エンジン110は、汎用のクエリスタイルだけを使用して、地理的クエリ制約と非地理的クエリ制約をともに表現する。これにより、空間ドメイン制約とキーワード制約の両方に合致する文書、または文書識別子が取得される。
【００５４】
文書の中に格納され、テキスト索引の中で索引付けされる、前述のインタリーブされた表現は、テキスト検索エンジン110が、汎用のクエリスタイルを使用して範囲検索を容易に実行することを可能にすることに留意されたい。例えば、4284*を求めるワイルドカード検索は、テキスト検索索引に適用されると、「42840000」から「42849999」までの間の座標を有するすべての文書を取得する。言い換えれば、そのワイルドカード検索は、(48.00°,24.00°)および(48.99°,24.99°)によって境界が定められた長方形の区域全体の範囲内に入る座標を有するすべての文書を取得する。これは、さらに以下に詳しく説明する。
【００５５】
図2は、システムが、地理的テキストストリングを含むテキスト索引を構築するプロセスの流れ図を示す。最初、操作者またはシステム管理者が、検索可能であるべきすべての文書のリポジトリを提供する(ステップ202)。次に、ジオパーサが、リポジトリの中の各文書を調べて、地理空間リファレンスを識別する(ステップ204)。文書内で識別された各地理空間リファレンスに関して、ジオパーサは、その地理空間リファレンスが参照する可能性がある地理的場所を特定し、それらの場所に関する信頼度スコアを計算し、その情報を含有するメタデータを構築する(ステップ206)。ジオパーサは、次に、そのメタデータを、前述したタイプの地理的テキストストリングに符号化し(ステップ208)、それらのストリングを、インラインアプローチまたはスタンドオフアプローチを使用して、文書の中に挿入する(ステップ210)。ジオパーサが、そのように文書リポジトリの中のすべての文書を処理した後、もたらされる補われた文書リポジトリは、テキスト索引付けエンジンによって索引付けされる準備ができている。
【００５６】
代替的に、システムは、文書が、リポジトリと索引付けエンジンの間の処理パイプラインを通過させられる際に、文書にジオパーサを適用してもよい。メタデータは、リポジトリの中に格納されなくてもよい。メタデータは、文書が、索引付けエンジンに送り込まれると、メモリ内で文書に関連付けられることが可能である。
【００５７】
テキスト索引付けエンジンは、そのようなエンジンによって一般的に使用される諸技術を使用して、リポジトリの中の文書に索引を付ける(ステップ210)。しかし、地理空間情報が、特別なテキストストリングとして文書に追加されているため、テキスト索引付けエンジンは、文書のコーパス内で探し出されたすべてのキーワード、およびすべてのキーワード句に索引を付けるのと同一の形で、その情報に索引を付ける。異なるキーワードまたはキーワード句にそれぞれが関する多くの索引を含むことが可能な、もたらされる逆索引は、すべてのキーワード、およびすべてのテキストストリングを、文書リポジトリの中の適切な文書にマップする。
【００５８】
図3は、どのようにシステムが、1つまたは複数のキーワードと、関心対象の地理的区域とを含むクエリに関係のあるすべての文書を、ユーザが検索することができるようにするかを示す。マップユーザインタフェースが、検索クエリの一部であるべき1つまたは複数の地理的区域をユーザが指定することができるようにする視覚的グラフィック表現を、ユーザに提示する(ステップ302)。このインタフェースを介して、ユーザは、それらの地理的区域に関係のある地理空間リファレンスを含有する文書を見ることを所望する、すべての地理的区域を明らかにする。また、ユーザは、指定された地理を参照している確率が十分には高くない地理空間リファレンスを含有する、あらゆる文書を無視するよう、検索エンジンに指示する信頼度閾値を指定することも、そのインタフェースによって許される。
【００５９】
このインタフェースの別の部分、すなわち、キーワード検索ユーザインタフェースは、ユーザが、検索クエリの一部を形成すべきキーワードのリストを指定することも可能にする。また、インタフェースは、ユーザが、従来のブール演算子およびブール条件、ならびに他の標準の演算子および条件を使用して、キーワード検索クエリを構築することも可能にする(ステップ304)。例えば、keyword2のうちのkeyword1 w/in 3は、
“keyword1  keyword2”〜3
と書かれることが可能であり、ただし、終わりの〜3は、引用符で囲まれた語の間の許容される語の隔たりを表す。
【００６０】
ユーザインタフェースは、次に、検索に適用されるべき検索基準を定義するようにテキスト検索エンジンに提示されるべき適切な検索ストリングを生成する(ステップ306)。この動作の一環として、ユーザインタフェースは、選択された地理的区域を、本明細書の他の箇所で説明されるタイプの特別なストリングに符号化する。
【００６１】
検索クエリが、いずれのフォーマットにせよ、検索エンジンによって要求されるフォーマットにフォーマットされた後、システムは、検索コマンドを検索エンジンに与え、エンジンは、次に、検索を行う(ステップ308)。検索を完了した後、検索エンジンは、何らかの有用な形態で、例えば、ビジュアルディスプレイにおいて表示される、またはハードコピーで印刷される、または電子媒体上に格納される情報として、結果をユーザに提供する(ステップ310)。
【００６２】
(アフィン空間nタプルから階層座標を構築すること)
説明される実施形態では、ジオパーサによって作成された地理的座標メタデータは、このセクションで説明したとおり、インタリーブすることにより、階層座標に変換される。このインタリーブは、地球の球体上の、またはユークリッド3次元空間内の座標タプルなどの、任意の多次元アフィン座標タプルに対して実行されることが可能である。タプルは、緯度、経度、および海抜メートル数、または特定のアンカポイントのxフィート東、およびyフィート北を含むことが可能である。インタリーブは、各座標の第1の数字をとり、それらの数字を連結し、次に、各座標の第2の数字をとり、それらの数字を、第1の数字のストリングに連結して、すべての数字を以下同様に連結する。例えば、432フィート東、および987フィート北という座標位置は、以下のとおり符号化されることが可能である。すなわち、
493827
これは、そのようなストリングの読み取り者が、次元の数(この例では、2)、および連結の順序を理解することを要求する。この例では、連結の順序は、第1に東であり、第2に北である。このストリング符号化は、正方形の階層と等価である。49という数は、400.000...フィート東から499.999...フィート東まで、および900.000...フィート北から999.999...フィート北までのすべての座標を含む正方形に対応する。この文が例示すとおり、精度についての通常の想定は、ストリングインタリーブから構築された階層座標について考える場合、変更することを余儀なくされる。精度は、ストリングの長さによって決まり、階層座標の終わりに0の無限ストリングを自動的に想定することは、もはや正しくない。階層座標は、ある領域を指す。この例では、各座標は、正方形を指す。ストリングが長いほど、正方形は小さい。
【００６３】
さらに多くの次元を使用する別の例に関して、緯度-32.21°、経度-78.19°、および海抜4349メートルという位置を考慮されたい。この位置は、以下のストリングとして符号化されることが可能である。すなわち、
-3-74283214199
である。
【００６４】
しかし、負の数の使用を回避するため、ジオパースは、負の記号が現れないように原点を最初に移すことにより、それらの座標を符号化することも可能である。小数点左の数字の数を、すべての座標の間で同一に保つため、ジオパースは、パディングの0を追加する。したがって、前述した位置の場合、ジオパースは、原点を90°南、および180°西に移し、0をパディングして、以下のインタリーブ符号化を生成することができる。すなわち、
(00057.79°,00101.81°,04349.00)=000004013504719780910
である。
このストリング符号化は、長方形の領域の階層と等価である。
【００６５】
ここで説明するnタプルインタリーブは、元の座標系の特異性を保つ。例えば、緯度-経度座標は、ほぼ同一の場所に関して多くの非常に異なる座標を有することにより、極において劣った振る舞いをする。インタリーブすることによって緯度-経度から直接に構築された階層座標系は、赤道においてとの対比で極において考慮されると、等しい「サイズ」の正方形に非常に異なる量の現実の地表を覆わせることにより、やはり、この問題を含む。
【００６６】
以下のクエリスタイルの例では、以下の例示的なストリングを使用する。
(057.79°,101.81°)=0150717891
【００６７】
QTMなどの他の階層座標系は、より巧妙な構築により、この問題を回避する。すべての階層座標ストリングは、本明細書で説明されるフォーマット技術に適している。
【００６８】
(末尾ワイルドカード汎用クエリスタイルを介して実施された範囲制約)
前述の例において使用される階層ストリングを含有する文書は、000004013504*のような末尾ワイルドカードクエリを使用して探し出されることが可能である。というのは、このクエリは、000004013504000000000から000004013504999999999までのあらゆるストリングを取得するからである。この範囲のテキストストリングは、(00050.00°,00100.00°,04340.00)から(00059.99°,00109.99°,04349.99)までにおよぶ3次元バウンディングボックス内のすべての場所に関する符号化に対応する。
【００６９】
これらのストリングにおける右端の数字が、最下位である。n次元アフィン空間座標の場合、終わりのn桁は、座標方向のそれぞれにおける最小桁に対応する。それらの座標上で無限精度を想定することが通常であり、これは、0の無限ストリングが、それらの最小桁の右に付けられることを意味する。ここで説明されるワイルドカード汎用クエリスタイル実施形態、および以下に説明される他の諸実施形態を介して実施される範囲制約に関して、範囲クエリによって取得される文書は、精度(すなわち、0でないストリングの長さ)にかかわらず、一致するプレフィックスストリング(最上位の数字)を有するすべての文書を含む。
【００７０】
末尾ワイルドカードクエリスタイルは、非地理的クエリ制約と組み合わせられることが可能である。例えば、「roadblock」という語と、50度以上、および60度未満の緯度と、100度を超え、110度未満の経度とを有するバウンディングボックス内の場所をともに指す文書を探し出すのに、以下のいずれかのようなクエリが、テキスト検索索引に送られることが可能である。すなわち、
roadblock  0150*
“roadblock  0150*”〜40
roadblock  magicstring0150*
第1の例は、文書が、roadblockという語を含み、マジックストリングの後に続く正確な句も含むことを要求する。第2の例は、文書が、magicstring句から40語の範囲内にroadblockを含むことを要求する。第3の例は、ワイルドカード検索が、ジオパーサによって挿入された数字に対してだけ作用し、文書内で出現する他の無関係の数字に対しては作用しないことを確実にするために、「magicstring」という文字のような、特別な識別ストリングが、特別に符号化された地理的ストリングの先頭にどのように付けられることが可能であるかを示す。
【００７１】
(ストリングマッチング汎用クエリスタイルによって実施される範囲制約)
一部の検索エンジンは、ワイルドカードクエリでの実行が遅い。前述の設計の代替には、可能なすべてのプレフィックスストリングをエンジンに挿入することが含まれる。(057.79°,101.81°)=0150717891という前述した例示的なストリングの場合、システムは、このストリングに含まれるすべてのプレフィックスを挿入することができる。すなわち、
0
01
015
0150
01507
015071
0150717
01507178
015071789
0150717891
である。これにより、テキスト索引付けエンジンが、すべてのプレフィックスを文書内の語として格納するようにさせられる。次に、プレフィックスのうちのいずれかに関するクエリが、文書を受け取る。前述の例の場合と同様に、各プレフィックスの先頭にmagicstringが付加されて、そのプレフィックスが、クエリを介して一意に識別可能であることが確実にされることも可能である。索引付けエンジンが、スタンドオフ方法をサポートする場合、すべてのプレフィックスは、地理的リファレンスの文字位置、または語位置だけに関連付けられることが可能である。この設計は、テキスト索引が、はるかに多くの語を保持することを要求する可能性があるが、語は、ワイルドカードクエリをサポートする必要がない単純な索引の中に格納されることが可能である。ワイルドカードクエリスタイルの場合と同様に、このストリングマッチングクエリスタイルは、非地理的クエリ制約と組み合わせられることが可能である。例えば、特定の領域内でroadblockを探し出すのに、以下を求めるクエリを発行するだけでよい。すなわち、
roadblock  0150
である。
前述の場合と同様に、近接性演算子を使用して、空間的リファレンスから、ある語数の範囲内でroadblockが探し出されることも可能である。これは、提案される技術の抱える問題を例示する。特別にフォーマットされた階層ストリングが、インラインで挿入された場合、語近接性演算子は、それらのストリングをクエリ語の間の分離の一部としてカウントする可能性がある。これは、最も正しい振る舞いではない。スタンドオフメタデータを受け入れることにより、拡張された検索エンジンは、この問題を回避する。スタンドオフメタデータは、複数の特別に符号化された地理的ストリングが、文書内の既存の語と同一の語位置を占めることを可能にする。
【００７２】
(句検索汎用クエリスタイルを介して実施される範囲制約)
通常の汎用のテキスト検索エンジンは、句を検索する能力を備えている。エンジンの設計に依存して、句検索は、末尾ワイルドカード検索よりも効率的である可能性がある。というのは、システムが、ワイルドカードに先行する検索ストリングで始まる、すべての部分的な語のリストを生成しなくてもよいからである。ワイルドカード検索における非効率の別の原因は、別々の索引の使用に由来する。すなわち、プレフィックス索引が、文字位置を含まない場合、プレフィックス索引に対する検索は、テキスト近接性ベースの語適合度ファンクションを計算するために、語位置の索引と結合されなければならない。本方法では、システムは、句検索汎用クエリスタイルを使用して、語の組合せを検索するだけでよい。
【００７３】
句検索クエリを可能にするのに、階層ストリングが、空白スペースによって別々のストリング(つまり、句)に分けられる。例えば、前述の例は、以下のとおり書き換えられることが可能である。すなわち、
000004013504719780910→000  004  013  504  719  780  910
0150717891→01  50  71  78  91
である。
句検索は、テキストストリングの検索される要素を、別々の語として扱い、要求される語の組合せだけを検索することができる。
【００７４】
クエリが、意図されるストリングだけに一致することを確実にするのに、特別なストリングが、符号化の先頭に追加される。例えば、説明される実施形態では、以下のストリングが、文書に追加される。すなわち、
magicstring01  50  71  78  91
である。
このケースでは、
“magicstring01  50  71  78  91”
を求める句検索は、前述の例と同一のバウンディングボックス内の文書を取得する。この句クエリは、非地理的クエリ制約と組み合わせられることが可能である。例えば、「roadblock」という語と、前述の例で使用されたバウンディングボックス内の場所とをともに指す文書を探し出すのに、以下のクエリのいずれかが、テキスト検索索引に送られることが可能である。すなわち、
roadblock  “magicstring01  50  71  78  91”
“roadblock  “magicstring01  50  71  78  91””〜40
である。
第1の例は、文書が、roadblockという語を含み、マジックストリングの後に続く正確な句も含むことを要求する。第2の例は、文書が、magicstring句から40語の範囲内にroadblockを含むことを要求する。
【００７５】
句は、任意のサイズであることが可能である。しかし、座標空間の次元の数に対応するサイズを選択することに利点がある可能性がある。前述の例では、座標空間は、2つの次元、すなわち、緯度と経度を有し、選択された句は、2つの数字を有していた。このため、3つの文字の別のセットを、前段で指定された句検索の末尾の端に追加することにより、各次元に沿ってクエリボックスのサイズが、10分の1に縮小される。
【００７６】
また、他の汎用のクエリスタイルも、汎用の検索エンジンによって索引付けされた文書に挿入される前に正しくフォーマットされると、階層ストリングに対して効果的に作用することが可能である。本発明は、非構造化文書に追加された特別にフォーマットされた階層ストリングにアクセスする、汎用のクエリスタイルの任意の使用を含む。
【００７７】
(信頼レベルを符号化すること)
ジオパーサは、地理的メタデータについての自然言語信頼度スコアを、単に信頼度を別の座標次元として扱うことにより、特別にフォーマットされた階層ストリングに追加することもできる。
【００７８】
前述の例を拡張して、この場合、その例が、以下のとおり信頼度スコアを含むものと想定されたい。すなわち、
【００７９】
【表１】
2007538343.tif 000003
【００８０】
ジオパーサは、あたかも信頼度が、第4のアフィン座標次元であるかのように信頼度を符号化することができる。末尾ワイルドカードクエリの場合、これは、以下のような外見である。すなわち、
magicstring0000004001305048719878009100
である。
あるいは、句検索クエリの場合、信頼度を新たな座標として扱うことは、以下のような外見である。すなわち、
magicstring0000  0040  0130  5048  7198  7800  9100
magicstring0000004001305048*というワイルドカードクエリは、80.00%から89.99%までの信頼レベルで、(50.00°,100.00°,4340m)から(59.99°,109.99°,4349m)までにおよぶ緯度、経度、高度のバウンディングボックスを指す文書を取得する。句検索のケースでは、“magicstring0000  0040  0130  5048”という句検索ストリングが、同一の文書セットを取得する。
【００８１】
このアプローチの代替を以下に説明する。信頼度を第4のアフィン座標として扱う代わりに、信頼度をビン化することができる。
【００８２】
(座標をインタリーブの前に正規化すること)
以上に提示した符号化スキームでは、クエリは、すべての座標方向で同一の精度を使用することを余儀なくされる。座標が、異なる有効桁数を有する場合、クエリは、1つの次元で比較的小さい範囲を指定し、別の次元で比較的大きい範囲を指定する可能性がある。すべての座標次元を0から1までの範囲に正規化することにより、この問題が緩和される。前述の例を使用すると、以下の正規化が適用される。緯度が、緯度に生じる可能性がある最大の偏りである、180で割られる。経度が、経度に生じる可能性がある最大の偏りである、360で割られる。高度が、恣意的な最大高度である、海抜50,000メートルに正規化される。信頼度スコアは、1に既に正規化されているので、通常、変更されなくてもよい。もたらされる正規化された座標は、以下のとおりである。すなわち、
【００８３】
【表２】
2007538343.tif 000004
【００８４】
前述したインタリーブ手続きを使用して、正規化された座標は、以下のとおり符号化される。すなわち、
末尾ワイルドカード検索の場合、320828881260089050806600であり、
句検索の場合、3208  2888  1260  0890  5080  6600である。
【００８５】
(座標スコアをビン化すること)
異なる座標で非常に異なる精度を使用するクエリを可能にするのに、ジオパーサは、符号化スキームが、座標の1つまたは複数をビン化して、ビン化された座標を、インタリーブ座標符号化からそれらの座標を除外する形で表現する、混合符号化戦略を使用することができる。例えば、ビン化された信頼度スコアの場合、以下のビンが定義されることが可能である。すなわち、
【００８６】
【表３】
2007538343.tif 000005
【００８７】
ビン化を使用する符号化は、以下のとおりである。すなわち、
magicstring[ビン番号][座標符号化]
このスキームの下で、前述の例は、以下のとおりとなる。すなわち、
【００８８】
【表４】
2007538343.tif 000006
【００８９】
であり、符号化は、以下のテキストストリングをもたらす。すなわち、
magicstringA000004013504719780910
であり、これは、末尾ワイルドカードクエリを使用して検索することができる、または、符号化は、以下の句スリングをもたらす。すなわち
magicstringA000004013504719780910,
であり、これは、句検索クエリに適している。あるいは、符号化は、ワイルドカードも句検索も要することなしに検索されることが可能な、以下のプレフィックスをもたらす。
magicstringA0
magicstringA00
magicstringA000
magicstringA0000
magicstringA00000
magicstringA000004
magicstringA0000040
magicstringA00000401
(...すべての中間プレフィックス...)
magicstringA000004013504719780
magicstringA0000040135047197809
magicstringA00000401350471978091
magicstringA000004013504719780910
【００９０】
この符号化スキーム、およびこのスキームの均等形態は、拡張されたマップ検索ユーザインタフェースと対話しているユーザが、以下を求めるキーワードクエリを単に生成することにより、特定の範囲内で80%を超える信頼度スコアを有する文書を取得することを可能にする。すなわち、末尾ワイルドカードクエリ対応のテキスト検索エンジンの場合、
magicstringA000004013504*
であり、あるいは、句検索クエリ対応のテキスト検索エンジンの場合、または句検索とワイルドカード検索のいずれも必ずしもサポートしないエンジンに関するリストアップされるプレフィックスのいずれのプレフィックスの場合も、
“magicstringA000  004  013  504”
である。
【００９１】
(様々なグリッド座標系に関する符号化)
前述したインタリーブスキームは、任意のアフィン空間からの座標に適用することができる。地理的マッピング投影が、アフィン空間座標の例である。地理的マッピング投影は、地球上の球体様の座標を使用することが多い。一般的な例には、「投影されない」緯度-経度およびUTM(Universal  Transverse  Mercator)が含まれる。
【００９２】
MGRS(military  grid  reference  system)やQTM(quaternary  triangular  mesh)などの「階層」座標系としても知られるグリッド座標系は、既に階層表現になっている。そのようなグリッド座標系は、インタリーブされなくてもよい。様々な汎用のクエリスタイルのそれぞれに関して、前述した特別なストリングフォーマッティングを直接に適用することができる。
【００９３】
例えば、QTMは、地表に正八面体をはめ込み、次に、その正八面体の三角形の面を4つの三角形に細分し、それらの三角形が、4つの三角形にさらに細分されることが無限に続けられる。正八面体の各面には、0から7まで番号が付けられ、それぞれの三角形の区画には、0から3まで番号が付けられる。多面体の頂点が、次に、球体の放射線に沿って表面に投影される。すると、表面上の任意のポイントが、最初の数字が0から7までにおよび、後続のそれぞれの記号が、0から3までにおよぶ、数字のより長い、またはより短いストリングを使用して、任意の精度レベルまで指定されることが可能である。末尾ワイルドカードクエリは、クエリにおいて指定された最後の三角形番号内のすべての場所を取得する。
【００９４】
グリッドストリングは、様々なタイプの汎用のクエリスタイル向けにフォーマットされることが可能である。例えば、
【００９５】
【表５】
2007538343.tif 000007
【００９６】
前述した信頼度ビン化符号化スキームが使用される場合、以下のタイプのストリングが、地理的メタデータとして文書に追加されて、末尾ワイルドカード検索および句検索を使用する、対応するクエリがサポートされる。
【００９７】
【表６】
2007538343.tif 000008
【００９８】
(クエリ後処理のために追加情報を符号化すること)
ほとんどのテキスト検索エンジンは、元の文書からの検索語のインスタンスを含有するテキストの断片を有する結果をもたらす。より有用な結果をユーザにもたらすのに、ジオパーサは、1つまたは複数の文字/数字ペアを符号化されたストリングに付加することにより、既存の符号化に追加の情報を追加する。検索エンジンは、検索結果を提示する際、その情報を取得して、ユーザが、文書のテキスト内で関心対象のジオタグを探し出すのを助ける。例えば、特定のジオタグを作成するのに使用された語が、そのジオタグにおける最初の文字に12文字先行して開始したことを示すため、「c12」という文字/数字ペアが、以下のとおり追加される。すなわち、
magicstringA2012  0302  1023  0203  012c12
解釈されるストリングの正規化された表現が、そのジオタグの15文字後に提示されることを示すのに、スキームは、第2の文字/数字ペアを以下のとおり追加する。すなわち、
magicstringA2012  0302  1023  0203  012c12b15
【００９９】
地理的メタデータ情報にそのような情報を追加することにより、検索結果をユーザに提示するアプリケーションが、ユーザによりわかりやすい形で提示を行うことが可能になる。例えば、システムは、ジオタグを1つの色で強調表示し、ジオタグの正規化された表現を別の色で強調表示することができる。
【０１００】
(マッピングアプリケーションからの複数のクエリ)
選択された座標系内の通常の境界に沿わない境界を有する地理的範囲を有するクエリに関して、マップユーザインタフェースは、所望されるクエリを、複数のサブクエリから構築する。1つのアプローチによれば、マッピングアプリケーションは、ユーザの入力によって指定されたドメインを取り上げ、そのドメインを、末尾ワイルドカードまたは句などの、汎用のクエリスタイルを使用する複数のクエリのセットに変換する。マッピングアプリケーションは、次に、それらの複数のクエリをブールOR演算子で組み合わせて、単一のクエリ表現を形成する。代替的に、マッピングアプリケーションは、複数のクエリをテキスト検索エンジンに送る。複数のクエリをテキスト検索エンジンに送る場合、マッピングアプリケーションは、検索エンジンによって戻されるいくつかの結果リストを組み合わせなければならない可能性があり、ユーザの入力によって意図される範囲を外れる結果を切り捨てなければならない可能性がある。切り捨てることは、戻された文書を調べて、地理空間リファレンスが、ユーザによって指定された範囲を外れる文書を識別することによって行われる。しかし、戻される文書のセットは、リポジトリの中に格納されている数と比べて、通常、少数であるので、切り捨てる動作は、通常、それほど時間がかからない。
【０１０１】
複数クエリの例が、図4Aに示されており、図4Aでは、太線のボックス302が、ユーザによってクエリが行われる長方形範囲を示している。図4Aに示される方法によれば、マッピングアプリケーションは、ボックス304、306、308、および310によって示される4つのサブクエリをマージして、次に、太線のボックスの範囲を外れる結果を切り捨てる。代替的に、マッピングアプリケーションは、ボックス304、306、308、または310に入る結果を求める単一の4部分ORクエリを生成して、次に、結果を切り捨てる。
【０１０２】
図4Bに示される方法によれば、マッピングアプリケーションは、ボックス312、314、316、318、320、および322によって示される6つのサブクエリをマージし、あるいは代替的に、単一の6部分ブールORクエリを生成する。この方法は、切り捨てを全く要求しないが、ボックスの境界が、太線のボックスの境界と重なるようにボックスが定義されることを要求する。第2の条件を満たすことは、あまりにも小さいボックスサイズを使用することを要求して、検索エンジンによって実行される必要がある検索の回数が、手続きの効率を深刻に低下させる可能性がある。
【０１０３】
拡張されたマップ検索ユーザインタフェースは、複数の検索エンジンにクエリを行う可能性がある。異なる検索エンジンは、異なる汎用のクエリスタイルを多少、効率的に扱う可能性があるので、本発明の異なる諸実施形態において「ラップされる」ことが可能である。1つの検索エンジンが、末尾ワイルドカード汎用クエリスタイルを使用して、範囲クエリを実施するようにセットアップされることが可能であり、別の検索エンジンが、句検索汎用クエリスタイルを使用するようにセットアップされることが可能である。クライアントは、様々な検索エンジンから結果を受け取ると、それらの結果をマージして、ユーザに提示される1つまたは複数の結果セットにすることができる。
【０１０４】
(拡張された検索エンジン)
前述したスタンドオフメタデータ拡張に加えて、他の3つの拡張が開示される。それらの拡張は、検索エンジンが、最も関係のある結果を先に提示することを可能にする適合度ソートファンクションを向上させる。それら3つの拡張は、以下を扱う。すなわち、
1.座標の正しさの信頼度
2.地理的項と非地理的項の両方の相対的な項の位置
3.語の使用頻度
である。
【０１０５】
本明細書の他の箇所で説明されるとおり、特定の座標が、文書の作成者によって意図されていた尤度を示す信頼度スコアが、通常、ジオパーサによって生成される。信頼度スコアを検索エンジンに組み込む最も強力なやり方は、各語に一般的な信頼度値が付いているように索引を拡張することである。そのような一般的な信頼度値は、地理的または非地理的な、任意のタイプの語に割り当てられることが可能であり、その語が文書に入っていることを作成者が意図していた尤度を示すのに使用されることが可能である。明らかに、ほとんどの語は、作成者によって書かれており、したがって、語のほとんどは、100%の信頼度を有する。しかし、メタデータが、様々な自動化されたプロセスによって文書に追加されると、テキストの一部は、100%未満の信頼度を有する可能性がある。検索エンジンが、この信頼度概念をサポートする場合、結果リストに対して作用するスコア付けファンクションは、その項ごとの信頼度情報を、検索エンジンにおける一般的な機能として直接に利用することができる。検索エンジンが、この信頼度概念をサポートしない場合、信頼度は、信頼度ビン化方法を使用して、または信頼度を、前述したとおり、追加のアフィン座標として扱うことにより、特別にフォーマットされた階層ストリングに組み込むことができる。これらの方法のいずれも、拡張されたマップ検索インタフェースが、信頼度の範囲またはビンに関するクエリを構築して、検索エンジンの外部から、適合度に対する信頼度の影響を実現することを要求する。クエリを発行するクライアントは、汎用のクエリスタイルを使用して、まず、高い、例えば、80%の信頼度を超える、信頼度範囲または信頼度ビンの範囲内の文書を要求することにより、これを行うことができ、次いで、十分な結果が戻されなかった場合、クライアントは、より低い範囲またはビンの中のさらなる文書を要求することができる。拡張された検索エンジンは、制約に合致する最高の信頼度を文書適合度に単に掛けることを含め、様々な形で、信頼度値をエンジンによる適合度計算に直接に組み込むことができる。
【０１０６】
地理的項と非地理的項の両方の相対的な項の位置は、ほとんどの非構造化情報取得適合度ファンクションに極めて重要である。説明される実施形態によって教示される特別にフォーマットされた地理的ストリング符号化の有用性の一環には、それらの符号化が、汎用の検索エンジンにおける既存の項近接性インフラストラクチャを直接活用することがある。前述したとおり、検索エンジンによって索引付けされた文書に、特別にフォーマットされたストリングを追加する2つの方法、すなわち、インライン方法およびスタンドオフ方法が存在する。インライン方法の方が、文書の構造を複雑にすることなしに、文書を変更するため、実施するのが最も容易である。スタンドオフ方法は、文書内で同一の語位置を占める複数の語を有するという概念を検索エンジンがサポートすることを要求する。これは、多くの文書作成システムにおいて標準の概念である。例えば、Microsoft  Wordは、コメントおよび編集マークが、文書内の様々な語位置を指すのを許す。それらの追加の情報は、文書の本文の一部ではないが、本文の特定の部分に関連付けられている。スタンドオフメタデータをサポートする検索エンジンに関して、特別にフォーマットされた地理的ストリングは、文書の全長を歪めることなしに、文書の一部となるため、特に効果的である。いずれの方法が使用されるかにかかわらず、両方の方法は、特別にフォーマットされた地理的ストリングを文書内のテキストの特定の区域に関連付ける。地理的ストリングには、テキスト内の所与の語位置が与えられる。これは、地理的ストリングが、検索エンジンの一般的な適合度計算によって実行されるあらゆる語近接性計算に自動的に、シームレスに組み込まれることを意味する。インライン挿入方法の歪みを伴っても、これは、2つの別々の索引からの結果をマージしようと試みることよりも劇的に良好な結果をもたらす。
【０１０７】
企図される第3の拡張は、項の頻度に関する。通常、適合度ファンクションは、項の頻度を使用して、項の重要度を算出する。直観的に、まれな語は、ユーザによる検索の中に含まれる普通の語よりも重要度が高いことが期待される。出現頻度は、語の出現回数を語の総数で割ることによって計算される。このため、所与の語の項-文書頻度(TDF)および項-コーパス頻度(TCF)は、以下のとおりである。すなわち、
【０１０８】
【数１】
2007538343.tif 000009
【０１０９】
【数２】
2007538343.tif 000010
【０１１０】
適合度計算は、通常、以上2つの頻度の比に適用される対数曲線およびその他の数学的曲線が含まれる様々なファンクションを含む。集まりにおける、または文書内の語の総数に、すべての特別にフォーマットされた階層ストリングが含まれる場合、適合度ファンクションは、それらの存在によって歪められる可能性がある。これは、語の出現回数をカウントする際にmagicstring語を無視する適合度ファンクションを構築することにより、回避することができる。
【０１１１】
検索エンジンの他の拡張が、それらの特別にフォーマットされた階層ストリングの使用を円滑にする可能性がある。例えば、語の重点、およびその他の統計が、ストリング、またはストリングの扱いに加えられることが可能である。諸実施形態には、汎用のクエリスタイルを使用して、特別にフォーマットされた階層ストリングにアクセスする、すべてのそのような拡張された検索エンジンが含まれる。
【０１１２】
他の諸実施形態も、添付の特許請求の範囲に含まれる。例えば、空間座標系のテキストストリング符号化は、経度の数字を、緯度の対応する数字よりも前に取り上げること、または高度の数字を先に取り上げることなどにより、異なる順序でインタリーブされることが可能である。さらに、信頼度情報は、キーワードクエリが、所望される検索のために構築されることが可能である限り、他の符号化スキームによる空間座標に派生するテキストストリングと組み合わせられることが可能である。地理空間範囲は、規則的な、または恣意的に定義された境界をそれぞれが有して、2次元、3次元、またはn次元であることが可能である。範囲は、緯度と経度のような、ありふれた「絶対」座標において測定されることも、任意の点に関する座標などの、相対座標において測定されることも可能である。関心対象の地理空間範囲を指定する能力をユーザに提供する、任意の所望の座標正規化スキームが、使用されることが可能である。そのような範囲は、いくつかの次元のそれぞれにおいて同様の絶対範囲を含むことも、次元の1つまたは複数において異なる範囲を含むことも可能である。地理的ストリングフォーマットは、任意の階層座標系、または任意のアフィン空間の階層表現に適用されることが可能である。
【図面の簡単な説明】
【０１１３】
【図１】地理的場所テキスト索引付け-検索のシステムの主要な要素を示す高レベルブロック図である。
【図２】地理空間クエリを文書リポジトリにサブミットするのに使用されることが可能なテキスト索引を生成するためのプロセスを示す流れ図である。
【図３】文書リポジトリの地理空間クエリを行うためのプロセスを示す流れ図である。
【図４Ａ】マッピングアプリケーションからのクエリを複数のクエリに分解することを示す図である。
【図４Ｂ】マッピングアプリケーションからのクエリを複数のクエリに分解することを示す図である。
【符号の説明】
【０１１４】
100  検索システム
101  文書リポジトリ
102  一時文書リポジトリ
104  ジオパーサ
106  テキスト索引付けエンジン
108  テキスト索引
110  テキスト検索エンジン
112  検索クエリ
114  キーワード検索ユーザインタフェース
116  マップユーザインタフェース
【図１】
2007538343.tif 000011
【図２】
2007538343.tif 000012
【図３】
2007538343.tif 000013
【図４Ａ】
2007538343.tif 000014
【図４Ｂ】
2007538343.tif 000015
【国際調査報告】
2007538343.tif 000016
2007538343.tif 000017
2007538343.tif 000018