(57)【要約】  本技術の実施形態は、データサニタイゼーション及び正規化、並びにこれを適用したジオコーディング方法に関する。例示的な方法は、ジオデータセットをサニタイジングするステップと、正規化されたレーベンシュタイン距離アルゴリズムを用いて、サニタイジングされたジオデータを正規化するステップを含む。【選択図】図１
2016528553.tif 000002
【特許請求の範囲】
【請求項１】
プロセッサと、実行可能な命令を保存するメモリとを備えるコンピュータによって実行される方法であって、前記プロセッサが前記命令を実行することによって実現される方法において、
それぞれがフォーマットを有する複数のセグメントをそれぞれ有する２つのマルチセグメント文字セットを受信するステップと、
前記セグメントのフォーマットが標準化されたフォーマットでない場合、前記マルチセグメント文字セットの複数のセグメント内のセグメントを標準化されたフォーマットに変換し、前記変換されたセグメント及び変換されていないセグメントから連続する文字列を作成して、前記２つのマルチセグメント文字セットのそれぞれを短縮することにより、前記２つのマルチセグメント文字セットをサニタイジングするステップと、
サニタイジングされた前記マルチセグメント文字セットを用いて、サニタイジングされた前記マルチセグメント文字セットの文字間の差を表す距離スコアを算出するステップと
を有する方法。
【請求項２】
前記サニタイジングするステップは、更に、前記複数のセグメントから非英数字を削除するステップを含む請求項１記載の方法。
【請求項３】
前記サニタイジングするステップは、更に、前記複数のセグメントのそれぞれの大文字を小文字に変換するステップを含む請求項１記載の方法。
【請求項４】
前記複数のセグメントの少なくとも１つは、第１の言語で表され、前記複数のセグメントの少なくとも１つは、第２の言語で表されている請求項１記載の方法。
【請求項５】
前記距離スコアを算出するステップは、サニタイジングされた前記マルチセグメント文字セットについてのレーベンシュタイン距離（LDexp1）を算出するステップを含む請求項１記載の方法。
【請求項６】
前記距離スコアを算出するステップは、サニタイジングされた前記マルチセグメント文字セットについての正規化されたレーベンシュタイン距離（NLD）を算出するステップを含み、前記正規化されたレーベンシュタイン距離は、以下の式を用いて算出される、請求項５記載の方法。
NLD＝1−(LDexp1−abs（［LSexp1］−［LSexp2］））/min（［LDexp1］，［LSexp2］）
ここで、LSexp1は、サニタイジングされた前記マルチセグメント文字セットの第１の文字列の長さであり、LSexp2は、サニタイジングされた前記マルチセグメント文字セットの第２の文字列の長さであり、LDexp1は、サニタイジングされた前記マルチセグメント文字セットのLDである。
【請求項７】
前記NLDをパーセンテージスコアに変換するステップを更に有する請求項６記載の方法。
【請求項８】
前記２つのマルチセグメント文字セットのうちの第１のマルチセグメント文字セットの複数のセグメント内のセグメントの文字を再編成して、並べ替えられたセグメントを生成することにより、前記２つのマルチセグメント文字セットのうちの前記第１のマルチセグメント文字セットから、複数の、並べ替えられたマルチセグメント文字セットを作成するステップと、
前記複数の並べ替えられたマルチセグメント文字セットと、前記２つのマルチセグメント文字セットのうちの第２のマルチセグメント文字セットとの様々な組合せを含むマルチセグメント文字セットの対をサニタイジングするステップと、
前記マルチセグメント文字セットの対のそれぞれについて正規化されたレーベンシュタイン距離（NLD）を算出するステップとを更に有する請求項１記載の方法。
【請求項９】
実行可能な命令を保存するメモリと、
前記実行可能な命令を実行して、
それぞれがフォーマットを有する複数のセグメントをそれぞれ有する２つのマルチセグメント文字セットを受信し、
セグメントのフォーマットが標準化されたフォーマットでない場合、前記マルチセグメント文字セットの前記複数のセグメント内のセグメントを標準化されたフォーマットに変換し、変換された前記複数のセグメントから連続する文字列を作成して、前記２つのマルチセグメント文字セットのそれぞれを短縮することにより、前記２つのマルチセグメント文字セットをサニタイジングし、
サニタイジングされた前記マルチセグメント文字セットについて正規化されたレーベンシュタイン距離（NLD）を算出するプロセッサと
を備え、
前記正規化されたレーベンシュタイン距離は、
サニタイジングされた前記マルチセグメント文字セットについてのレーベンシュタイン距離（LDexp1）を算出し、
以下の式を用いて前記LDexp1を正規化することによって算出される、演算デバイス。
NLD＝1−（LDexp1−abs（［LSexp1］−［LSexp2］））/min（［LDexp1］，［LSexp2］）
ここで、LSexp1は、サニタイジングされた前記マルチセグメント文字セットの第１の文字列の長さであり、LSexp2は、サニタイジングされた前記マルチセグメント文字セットの第２の文字列の長さであり、LDexp1は、サニタイジングされた前記マルチセグメント文字セットのＬＤである。
【請求項１０】
前記プロセッサは、更に、前記複数のセグメントのそれぞれから非英数字を削除することにより、サニタイジングの命令を実行する請求項９記載の演算デバイス。
【請求項１１】
前記プロセッサは、更に、前記複数のセグメントのそれぞれの大文字を小文字に変換することにより、サニタイジングの命令を実行する請求項９記載の演算デバイス。
【請求項１２】
更に、前記NLDをパーセンテージスコアに変換するステップを有する請求項９記載の演算デバイス。
【請求項１３】
前記２つのマルチセグメント文字セットのそれぞれは、地図上の関心点を表す請求項９記載の演算デバイス。
【請求項１４】
前記２つのマルチセグメント文字セットのそれぞれを関心点として地図上にプロットし、
前記プロットの間の物理的距離を算出し、
前記物理的距離が距離閾値を下回る場合、前記２つのマルチセグメント文字セットが同じ関心点を表すと特定するステップを更に有する請求項９記載の演算デバイス。
【請求項１５】
プロセッサと、実行可能な命令を保存するメモリとを備える演算デバイスによって実行されるジオコーディング方法であって、前記プロセッサが前記命令を実行することによって実現される方法において、
それぞれがフォーマットを有する複数のセグメントをそれぞれ有し、同じ関心点を表現する可能性がある２つのジオデータ文字列を受信するステップと、
セグメントのフォーマットが標準化されたフォーマットでない場合、前記ジオデータ文字列の複数のセグメント内のセグメントを標準化されたフォーマットに変換するステップと、
変換された複数の前記セグメントから連続する文字列を作成することによって、前記２つのジオデータ文字列のそれぞれを短縮するステップと、
サニタイジングされたマルチセグメント文字セットを用いて、短縮されてサニタイジングされた前記２つのジオデータセグメント文字列の文字の差を表す距離スコアを算出するステップと、
前記距離スコアを閾値と比較するステップと、
前記距離スコアが閾値を下回る場合、データベースにおいて、前記２つの短縮され、サニタイジングされたジオデータ文字列が、同じ関心点を表していると特定するステップとを有する方法。
【請求項１６】
前記複数のセグメントは、ＰＯＩ名、都市、番地、州、国、郵便番号、電話番号、ファックス番号、ウェブサイトＵＲＬ、座標及びこれらの組合せのいずれかを含む請求項１５記載の方法。
【請求項１７】
前記ジオデータ文字列のそれぞれを関心点として地図上にプロットするステップと、
前記プロットの間の地理的距離を算出するステップと、
前記地理的距離が距離閾値を下回る場合、前記２つのジオデータ文字列が同じ関心点を表していると特定するステップとを更に有する請求項１５記載の方法。
【請求項１８】
サニタイジングするステップは、更に、前記複数のセグメントから非英数字を削除するステップを含む請求項１５記載の方法。
【請求項１９】
サニタイジングするステップは、更に、前記複数のセグメントのそれぞれの大文字を小文字に変換するステップを含む請求項１５記載の方法。
【請求項２０】
前記複数のセグメントの少なくとも１つは、第１の言語で表され、前記複数のセグメントの少なくとも１つは、第２の言語で表されている請求項１５記載の方法。
【請求項２１】
関心点を地図上にプロットするステップを更に有し、前記関心点は、サニタイジングされた前記ジオデータセグメント文字列が同じ関心点を表すと判定される場合、サニタイジングされた前記ジオデータセグメント文字列によって定義される請求項１５記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願
本出願は、２０１３年８月１４日に出願された米国仮出願番号第６１／８６５，９８４号、発明の名称「Systems and Methods for Geocoding and Correcting Geocoded Data」の優先権を主張し、この文献は、その内に記載されている全ての引用文献を含み、その全体が引用によって本明細書に援用される。
本技術の分野
本技術は、包括的には、ジオコーディング（geocoding）及び地図作成に関し、詳しくは、以下に限定されるわけではないが、各関心点が異なるデータベースとの間で一貫性を欠く複数の表現によって表されている際に、関心点を正しくジオコーディングするシステム及び方法に関する。本技術は、これらの一貫性を欠く表現を調和させて、これらのジオコーディングされた位置の一貫性を向上させる。
【発明の概要】
【課題を解決するための手段】
【０００２】
本技術の実施形態は、方法を含み、この方法は、（ａ）それぞれがフォーマットを有する複数のセグメントをそれぞれ有する２つのマルチセグメント文字セットを受信するステップと、（ｂ）（ｉ）セグメントのフォーマットが標準化されたフォーマットでない場合、マルチセグメント文字セットの複数のセグメント内のセグメントを標準化されたフォーマットに変換し、（ｉｉ）変換されたセグメント及び変換されていないセグメントから連続する文字列を作成することによって、２つのマルチセグメント文字セットのそれぞれを短縮することによって、２つのマルチセグメント文字セットのそれぞれをサニタイジングするステップと、（ｃ）サニタイジングされたマルチセグメント文字セットを用いて、サニタイジングされたマルチセグメント文字セットの文字間の差を表す距離スコアを算出するステップとを有する。
【０００３】
本技術の他の実施形態は、演算デバイスを含み、この演算デバイスは、（ａ）実行可能な命令を保存するメモリと、（ｂ）実行可能な命令を実行して、（ｉ）それぞれがフォーマットを有する複数のセグメントをそれぞれ有する２つのマルチセグメント文字セットを受信し、(ii)（１）セグメントのフォーマットが標準化されたフォーマットでない場合、マルチセグメント列の複数のセグメント内のセグメントを標準化されたフォーマットに変換し、（２）変換された複数のセグメントから連続する文字列を作成することによって、２つのマルチセグメント文字セットを短縮することによって、２つのマルチセグメント文字セットをサニタイジングし、(iii)サニタイジングされたマルチセグメント文字セットについて正規化されたレーベンシュタイン距離（NLD）を算出するプロセッサとを備え、正規化されたレーベンシュタイン距離は、（Ａ）サニタイジングされたマルチセグメント文字セットについてのレーベンシュタイン距離（LD）を算出し、（Ｂ）以下の式を用いてLDを正規化することによって算出され、
NLD＝1−（LDexp1−abs（［LSexp1］−［LSexp2］））/min（［LDexp1］，［LSexp2］）
ここで、LSexp1は、サニタイジングされたマルチセグメント文字セットの第１の文字列の長さであり、LSexp2は、サニタイジングされたマルチセグメント文字セットの第２の文字列の長さである。
【０００４】
本技術の更なる実施形態は、ジオコーディング方法を含み、この方法は、（ａ）それぞれがフォーマットを有する複数のセグメントをそれぞれが有し、同じ関心点を表現する可能性がある２つのマルチセグメント文字セットを受信するステップと、（ｂ）セグメントのフォーマットが標準化されたフォーマットでない場合、マルチセグメント列の複数のセグメント内のセグメントを標準化されたフォーマットに変換するステップと、（ｃ）変換されたセグメント及び変換されていない複数のセグメントから連続する文字列を作成することによって、２つのマルチセグメント文字セットのそれぞれを短縮するステップと、（ｄ）サニタイジングされたマルチセグメント文字セットを用いて、サニタイジングされたマルチセグメント文字セットの文字の差を表す距離スコアを算出するステップと、（ｄ）距離スコアを閾値と比較するステップと、（ｅ）距離スコアが閾値を下回る場合、データベースにおいて、サニタイジングされたマルチセグメント文字セットが、同じ関心点を表していると特定するステップとを有する。
【図面の簡単な説明】
【０００５】
【図１】本技術の側面を実現するためのコンピューティング環境の高レベル概略図である。
【図２】ジオコーディング処理を例示する概要及びフローチャートである。
【図３】同じ物理的な関心点を表す２つのジオコーディングされた点の間の物理的距離計算の処理を説明する地図を示す図である。
【図４】本技術の方法のフローチャートである。
【図５】正規化されたレーベンシュタイン距離計算及び物理的距離計算を実行する方法のフローチャートである。
【図６】ジオデータインスタンスのセグメント／フィールドの順列を作成及び使用する方法のフローチャートである。
【図７】本技術に基づく実施形態を実現するために使用されるコンピュータシステムの概略図である。
【発明を実施するための形態】
【０００６】
以下では、本発明の完全な理解のために、限定ではなく説明を目的として、例えば、特定の実施形態、手順、技術等を具体的詳細に述べる。しかしながら、本発明は、これら具体的詳細とは異なる他の実施形態において実現してもよいことは、当業者にとって明らかである。
【０００７】
本明細書における「一実施形態」又は「実施形態」という表現は、その実施形態に関連して記述される特定の特徴、構造又は特性が、本発明の少なくとも１つの実施形態に含まれることを意味する。したがって、明細書の様々な箇所で用いる「一実施形態において」又は「実施形態において」又は「実施形態によれば」といった表現（又は同様の趣旨の語句）は、全てが必ずしも同じ実施形態について言及しているというわけではない。更に、１つ以上の実施形態において、適切な何らかの手法で、特定の特徴、構造又は特性を組合せてもよい。更に、この説明の文脈に応じて、単数形の語句は、複数の意味も含み、複数形の語句は、単数の意味も含むことができる。同様に、ハイフンで接続した語句（例えば、「（on-demand）」）は、場合に応じて、ハイフンがない同じ語句（例えば、「on demand」）と交換可能に使用してもよく、先頭を大文字にした語句（例えば、「Software」）は、先頭を大文字にしていない同じ語句（例えば、「software」）と交換可能に使用でき、複数語は、アポストロフィの有無を問わず（例えば、PE's又はPEs）、そして、イタリック体の語（例えば、「「N+1」（イタリックフォント）」）は、非イタリック体のバージョン（例えば、「N+1」（標準フォント））と交換可能に使用できる。このような場合に応じた交換可能な使用は、互いに一貫性を有していないとはみなされないものとする。
【０００８】
また、幾つかの実施形態は、タスク又は一組のタスクを実行する「手段」に関して記述することがある。「手段」とは、例えば、プロセッサ、メモリ、カメラ等の入出力装置又はこれらの組合せに関する構造の表現であってもよい。これに代えて、「手段」は、機能又は方法のステップを記述するアルゴリズムを含んでもよく、更に他の実施形態においては、「手段」は、数式（formula）や記述（prose）に関連して表現してもよいし、又は、フローチャートや信号図として表現してもよい。
【０００９】
本明細書中の用語は、特定の実施形態を記述することを目的とし、本発明を制限する意図はない。ここで使用する、不定冠詞及び定冠詞が付された単数名詞は、文脈上、明確に他を示すものでない限り、複数も包含するものとする。更に、本明細書で使用する「備える」、及び／又は「有する」等の表現は、記述した特徴、値、ステップ、動作、要素及び／又は成分の存在を特定するものであり、これ以外の特徴、値、ステップ、動作、要素、成分及び／又はこれらのグループの存在又は追加を除外する意図はない。
【００１０】
なお、ここで用いる「接続（coupled, connected, connecting）」、「電気的に接続（electrically connected）」といった用語は、本明細書において交換可能に用いられ、電気的／電子的に接続される状態を包括的に意味する。同様に、信号のタイプ（アナログ又はデジタル）を問わず、第１のエンティティが第２のエンティティに情報信号（データ情報又は非データ／制御情報を含むかを問わず。）を電気的に送信及び／又は受信（有線手段を介するか又は無線手段を介するかを問わず。）している場合、第１のエンティティは、第２のエンティティ（又は複数のエンティティ）と「通信」しているとみなす。更に、本明細書で示し説明する様々な図面（ブロック図を含む。）は、例示のみを目的とし、実際の縮尺を反映していない。
【００１１】
関心点を表すソースデータ表現は、誤っていることがあり、及び／又は完全な情報が不足することがあるので、ジオコーディングは、不正確な処理になることも多い。この誤ったソースデータによって、関心点は、地図上で誤ってプロットされ、これによって、地図のエンドユーザに不都合が生じ、地図提供者が信頼を失う可能性がある。
【００１２】
特徴の位置マッピングの一貫性及び利便性を維持するために、地図上で関心点を正しくプロットすることが重要である。経験上、全ての関心点（例えば、ホテル）の２５％は、誤ってプロットされているとされている。例えば、これらのホテルは、正しい位置から１マイル以上離れてプロットされていることもある。このようなことが生じるのは、ホテルのジオロケーションデータ（以下、「ジオデータ」）が不完全であり、誤っており、又はフォーマットが不十分であるためである。更に、マッピングシステムは、複数の異種のデータベースに依存することが多く、各データベースは、それぞれ異なるフォーマットを用いて関心点を定義することがある。例えば、１つのホテルデータベースがホテルのアドレスを「20 5th Avenue West, New York」としてフォーマット化し、他のホテルデータベースが全く同じホテルのアドレスを「20 Fifth Ave., W. newyork」としてフォーマット化することがある。これらのアドレスは、同じ位置の同じホテルを指しているが、地図上でホテルをプロットする際、アドレスのフォーマットによってエラーが導入される可能性がある。
【００１３】
本技術は、ジオデータサニタイゼーション、距離及び正規化処理によって、これらの問題を解決することができるという利点を有する。なお、本技術をジオデータのコンテキストで説明するが、ここに開示するサニタイゼーション及び正規化処理は、データフォーマットの調和を必要とする任意のデータ処理方法にも適用できる。例えば、入力データが様々なフォーマットで提供されることに影響を受けやすく、このため、入力データが適用される際にエラーが生じるおそれがある場合に本技術を用いることができる。
【００１４】
本技術は、検証及び再フォーマット化が必要な関心点を特定することによってジオコーディング処理を改善する。本技術は、本明細書に記述するジオデータフォーマット方法を用いて、関係性を有さないデータベースからの関心点を一致させ、関係性を有さないデータベースから提供されたジオデータをマッピングロジックを用いて統合し、プロット精度を向上させる。また、本技術は、新しい関心点を正確にプロットする。このように、本技術の幾つかの実施形態は、ジオコーディング並びに地図作成の技術を向上させ、特に、以下に限定されるわけではないが、本技術の実施形態に基づいてサニタイジングされ、正規化されたジオデータを用いて関心点をマッピングする。図面全体（図１〜図７）を参照して、本技術のこれら及びこの他の利点を以下に説明する。
【００１５】
図１は、本技術のコンピューティング構造（以下、アーキテクチャ１００）の高レベル概略図である。アーキテクチャ１００は、データサニタイゼーション及び正規化システム（以下、「サーバ１０５」）、第１のジオデータソース１１０、第２のジオデータソース１１５、ネットワーク１２０及びフォーマット化されたジオデータデータベース１２５を備える。
【００１６】
サーバ１０５、第１のジオデータソース１１０及び第２のジオデータソース１１５は、ネットワーク１２０を介して互いに通信可能に接続されている。ネットワーク１２０は、適切な任意の私有の又は公の通信ネットワークを含んでいてもよい
サーバ１０５は、通常、例えば、第１のジオデータソース１１０及び第２のジオデータソース１１５等の複数のジオデータソースからジオデータを受信する。これより多くのジオデータソースが含まれていてもよい。これらのジオデータソースのそれぞれは、様々な関心点（points of interest：ＰＯＩ）を表すジオデータインスタンスをサーバ１０５に提供することができる。例えば、第１のジオデータソース１１０及び第２のジオデータソース１１５は、ホテルの予約を提供するウェブサイトに関連する旅行サービスデータベースであってもよい。これらのジオデータソースは、ホテルが所有する専用のホテルデータベースであってもよい。
【００１７】
ジオデータインスタンス１１０Ａ〜Ｎ等のジオデータインスタンスは、任意の数の情報フィールドを含んでいてもよい。ジオデータは、例えば、ＰＯＩ名、番地、都市、州、地方、郵便番号、電話番号、ファックス番号、ウェブサイト／領域／ＵＲＬ（ユニフォームリソースロケータ）、緯度及び経度等の座標をはじめとする情報フィールド並びにこれらの情報フィールドの組合せを含むことができる。当業者に知られている他の情報フィールドも本技術において使用することができる。幾つか実施形態では、ジオデータのフィールドは、セグメントと呼ばれる。すなわち、ジオデータのインスタンスは、複数のセグメント（例えば、複数のフィールド）を有することができる。
【００１８】
ジオデータは、ファイル、データベースエントリ、タブで区切られたファイル、コンマで分離された値のファイル、又は他の類似したデータ構造としてデータベースに保存することができる。上述したように、異なるソースからの同じ関心点についてのジオデータは、互いに一貫性を有していないことがあり得る。例えば、１つのジオデータインスタンスでは、番地（street address）が「145th St.」として特定され、他のジオデータインスタンスでは、同じ番地が「145 Street」として特定される等、幾つかのフィールドが異なるフォーマットを有していることがある。幾つか例では、ジオデータフィールドが誤っていることがあり得る。例えば、関心点の都市が、実際には「Menlo Park」であるのに、「Palo Alto」と誤記されていることもある。また、言語の不一致がジオコーディングを誤らせることもある。例えば、番地が、１つのジオデータインスタンスでは、「123 Avenida」とされ、他のジオデータインスタンスでは、「123 Avenue」とされることがある。この言語の違いによって、マッピング機能が言語差を補償することができない場合、関心点が誤ってプロットされることがある。
【００１９】
幾つかの実施形態においては、サーバ１０５が取得するジオデータは、まず、ジオデータ内の関心点（ＰＯＩ）を判定することによって処理される。サーバ１０５は、ジオデータソースから得られるジオデータから、例えば、番地、都市、州、郵便番号等のアドレスフィールドを取得する。サーバ１０５は、アドレスフィールドを使用して、地図上にＰＯＩをプロットする。
【００２０】
そして、サーバ１０５は、ＰＯＩアドレスの潜在的正確度（potential accuracy）を判定し、更に、互いに一致する任意のＰＯＩアドレスを選択する。幾つかの実施形態においては、サーバ１０５は、地図上にプロットされるＰＯＩアドレスの間の距離を計算することによってＰＯＩアドレスの正確度を判定する。また、サーバ１０５は、第１のジオデータソース１１０及び第２のジオデータソース１１５の初期正確度評価（initial accuracy rating）も考慮する。すなわち、幾つかの具体例では、第１のジオデータソース１１０及び第２のジオデータソース１１５のそれぞれは、そのジオデータソースが提供しているジオデータがどれほど正確かを表す正確度値をサーバ１０５に提供する。幾つかの具体例では、サーバ１０５は、第１のジオデータソース１１０及び第２のジオデータソース１１５によって提供される正確度値が正しくないと判定した場合、これらの正確度値を参考にしなくてもよい。
【００２１】
ＰＯＩアドレスは、緯度及び経度情報を含む座標データベースと比較することによって検証することができる。幾つかの具体例では、ＰＯＩアドレスが、座標を含んでいてもよく、これらのジオデータ座標を座標データベース内の座標と比較して、ＰＯＩアドレスの正確度を判定することができる。例えば、ＰＯＩアドレスが「1234 Main Street」であり、緯度３７、経度−１３２である場合、サーバ１０５は、この座標を座標データベースで調べ、ＰＯＩ番地を座標と比較して、ＰＯＩ番地が座標に実質的に対応するかを確認することができる。ＰＯＩ番地及び座標は、これらの２点が地図上にプロットでき、これらの間の距離が無視できる程度であるとき、実質的に対応する。例えば、地図のユーザが地図を使用して、誤った位置に案内されない場合、この距離は無視できる程度であるとみなされる。幾つかの具体例では、この距離の精度（granularity）及び近さ（closeness）は、位置によって判定できる。例えば、ＰＯＩが多くの一方通行を有する人口密度が高い都市部にある場合、ユーザが間違った通りを進み、間違った位置に案内される可能性を低減するために、この距離は、より短い必要がある。一方、ＰＯＩが人口過疎地域にあり、エンドユーザを混乱させる可能性がある隣接位置がない場合、この距離は、より長くてもよい。
【００２２】
何れの場合も、地図システム管理者は、この距離に閾値を設定することができる。距離が閾値より長い場合、ＰＯＩには、不正確を示すフラグを付してもよく、サーバ１０５による再コーディングが必要であるというフラグを付してもよい。これにより、サーバ１０５は、ジオデータソースにジオデータを再コーディングするよう要求することができる。これに代えて又はこれに加えて、幾つかの実施形態においては、サーバ１０５がＰＯＩのためのジオデータを無視してもよく、削除してもよい。
【００２３】
また、図１及び図２に示すように、サーバ１０５は、同じＰＯＩに関するジオデータの複数のインスタンスを管理するように構成されている。ＰＯＩの重複は、複数のデータソースが同じＰＯＩに関するジオデータを提供した場合に生じる。上述のように、複数のホテル予約システムが、これらのホテルＰＯＩジオデータをサーバ１０５に提供できる。地図上でこれらのホテルＰＯＩジオデータインスタンスを表示するために、サーバ１０５は、比較及び／又は調和化（harmonization）を行う。
【００２４】
幾つかの実施形態では、サーバ１０５は、少なくともプロセッサ１５０及びメモリ１５５を備える。メモリ１５５は、サニタイゼーションモジュール１６０、距離モジュール１６５及びプロッティングモジュール１７５を包括的に含む。
【００２５】
プロセッサ１５０は、メモリに保存されているサニタイゼーションモジュール１６０を実行して、様々な動作を実行する。１つの実施形態においては、サニタイゼーションモジュール１６０は、ジオデータのインスタンスをフィールドに分けるように構成される。なおジオデータのインスタンスは、包括的に、マルチセグメント文字セット（multi-segment set of characters）と呼ばれる場合もある。例えば、ジオデータのインスタンスは、「Hotel Mainstreet, 1234 Main St., Anytown, State, USA, 99991, (34, -123)」を含むことがある。上述のように、ジオデータは、任意のフォーマットを有していてもよい。例えば、ジオデータは、列又は行スタイルのリスト、コンマで分離された一組の値、タブで区切られた一組のフィールド又は他の適切な任意のフォーマットに配列されたフィールドを含むことができる。サーバ１０５は、ジオデータのインスタンスを別々のフィールド、例えば、「Name=Hotel Mainstreet; StreetAddress=1234 Main St.; City=Anytown; State=State; Country=USA; Zipcode=99991; Latitude=34; Longitude=-123」に分けてもよい。
【００２６】
幾つかの実施形態において、サニタイゼーションモジュール１６０は、ジオデータのインスタンス内の全ての大文字を小文字に変換する。また、サニタイゼーションモジュール１６０は、ジオデータのインスタンスから全ての非英数字を除去する。非英数字の除去によって、フィールドを１つの文字列に連結し又は短縮することができる。
【００２７】
そして、サニタイゼーションモジュール１６０は、例えば、フィールドサニタイザ（field sanitizer）モジュール１８０Ａ〜Ｎ等の複数の特定用途サニタイザ（special purpose sanitizers）を用いて、ジオデータのインスタンスのフィールドを処理してもよい。包括的に言えば、サニタイゼーションモジュール１６０は、セグメントのフォーマットが標準化されたフォーマットでない場合、セグメント又はフィールドを標準化されたフォーマットに変換するように構成されている。フィールドサニタイザモジュール１８０Ａ〜Ｎの以下の例は、同じＰＯＩを表すジオデータの矛盾したフィールドを調和させるために、フィールドを標準的なフォーマットに変換するのに用いられる。
【００２８】
フィールドサニタイザモジュール１８０Ａ〜Ｎの数は、ジオデータのインスタンスに存在するフィールドの数に依存する。フィールドサニタイザモジュール１８０Ａ〜Ｎのそれぞれは、特定の種類のジオデータフィールドをサニタイジングするように構成されている。例えば、名称フィールドサニタイザモジュール１８０Ａは、ジオデータのインスタンスの名称フィールドをサニタイジングする。ある具体例においては、名称フィールドが単語「hotel」若しくは「inn」又は例えば、「motel」等の他の類似した語を含まない場合、名称フィールドサニタイザモジュール１８０Ａは、名称フィールドに「hotel」という語を入れる。すなわち、名称フィールドについて標準化されたフォーマットは、名称フィールドに「hotel」という語が存在することを要求する。番地フィールドサニタイザモジュール１８０Ｂは、ジオデータのインスタンスの番地フィールドを正規化するように構成されている。例えば、番地フィールドサニタイザモジュール１８０Ｂは、「Avenida」、「Avenue」及び「Av」等のフィールドデータを、「ave」に置換することができる。したがって、「ave」は標準化されたフォーマットである。他の例として、「Four」、「Fourth」、「4th」、「IV」、「quatre」及び「cuatro」は、全て「４」の標準化されたフォーマットに変更される。このように、各種の番地データに対し、標準化されたフォーマットが適用され、多くの異なるフォーマットが標準化されたフォーマットに正規化される。
【００２９】
１つの非限定的な例では、ジオデータの第１のインスタンスは、「20 5th Avenue West, New York」の番地フィールドを含み、これは、「205avewnewyork」に変換される。大文字は、小文字に変更され、非英数字、例えば、スペース及びコンマは、取り除かれる。そして、番地フィールドは、「5th」を「5」に、「avenue」を「ave」に、「west」を「w」に変更するように処理される。
【００３０】
他の例では、ジオデータの第２のインスタンスは、「20 Fifth Ave., W., newyork」の番地フィールドを含み、これは「205avewnewyork」に変換される。大文字は、小文字に変更され、スペース及びコンマのような非英数字は、取り除かれる。そして、１つの番地フィールドは、「Fifth」を「5」に変更するように処理される。
【００３１】
この例では、ジオデータの第１のインスタンスは、第１のジオデータソース１１０に由来し、ジオデータの第２のインスタンスは、第２のジオデータソース１１５に由来していてもよい。
【００３２】
都市、州及び国名も同様の手法で、それぞれのフィールド正規化モジュールを用いてサニタイジングできる。サニタイゼーション／正規化の後、サニタイジングされたアドレスフィールド及び都市フィールドは、サーバ１０５によってジオコーディングエンジン１７０に供給され、ジオコーディングエンジン１７０は、ジオデータのインスタンスの間で、可能な一致を特定する。ジオコーディングエンジン１７０は、サーバ１０５に統合してもよく、又は、幾つかの実施形態は、１つ以上のサードパーティのジオコーディングエンジンを含んでいてもよい。
【００３３】
別の例では、サニタイジングされたアドレス及び都市を、例えば、仮想個人名別電話帳又は仮想職業別電話帳等のローカルディレクトリエンジン１８５に供給して、サニタイジングされたアドレスが、ローカルディレクトリエンジン１８５内のリストに関連性を有しているかを判定してもよい。
【００３４】
１つの実施形態においては、距離モジュール１６５は、サニタイジングされたジオデータの２つのインスタンスの間のレーベンシュタイン距離（Levenshtein distance：ＬＤ）を算出する。通常、レーベンシュタイン距離は、２つの文字列の間で算出される。当業者は、サニタイジングされた一対のジオデータ文字列について、ＬＤを算出することができる。一般に、ＬＤは、第１の文字列を変形して第２の文字列に対応付けるために、第１の文字列において幾つの置換が必要かを表す数値である。レーベンシュタイン距離は、幾つか単純な上限及び下限を有する。これらは、（ａ）ＬＤは、常に少なくとも２つの文字列のサイズの差であること、（ｂ）ＬＤは、多くても長い方の文字列の長さであること、（ｃ）文字列が等しい場合に限り、ＬＤはゼロであること、（ｄ）文字列が同じサイズである場合、ハミング距離がＬＤの上限であること、（ｅ）２つの文字列の間のＬＤは、第３の文字列に対するそれぞれのＬＤの合計を超えないこと（三角不等式）を含む。
【００３５】
例えば、第１のサニタイジングされた文字列は、「100 Avenida de Republica, Madrid」からサニタイジングされた「100avedereublicamadrid」を含み、第２のサニタイジングされた文字列は、「100 Republica Avenue, Madrid」からサニタイジングされた「100republicaavemadrid」である。
【００３６】
「100 Avenida de Republica, Madrid」と「100 Republica Avenue, Madrid」の間のＬＤは、１７であり、これは、「100 Republica Avenue, Madrid」に至るまでに「100 Avenida de Republica, Madrid」に１７回の置換を行う必要があることを意味する。第１及び第２のサニタイジングされた文字列のためのＬＤｅｘｐ１も算出でき、これは、９であり、これは、「100republicaavemadrid」にいたるまでに「100avedereublicamadrid」に９回の置換を行う必要があることを意味する。
【００３７】
なお、距離モジュール１６５が、２つのジオデータインスタンスからの類似したフィールドタイプを比較又は照合することに注目すべきである。例えば、距離モジュール１６５は、第１のジオデータインスタンスの番地フィールドを第２のジオデータインスタンスの番地フィールドと比較する。フィールドタイプを考慮せずにフィールド間の比較を行うと、距離モジュール１６５による比較の結果が劣化するおそれがある。
【００３８】
距離モジュール１６５は、まず、第１のサニタイジングされた文字列の長さ（２２である）と判定し、次に第２のサニタイジングされた文字列の長さ（２１である）と判定することによって、ＬＤｅｘｐ１値を正規化する。
【００３９】
これらの長さ値を判定した後に、距離モジュール１６５は、以下の式を用いて正規化されたＬＤ（normalized LD：ＮＬＤ）値を算出する。
ＮＬＤ＝１−（ＬＤｅｘｐ１−ａｂｓ（［ＬＳｅｘｐ１］−［ＬＳｅｘｐ２］））／ｍｉｎ（［ＬＤｅｘｐ１］，［ＬＳｅｘｐ２］）      ［式１］
ここで、ＬＳｅｘｐ１は、サニタイジングされたマルチセグメント文字セットの第１の文字列の長さであり、ＬＳｅｘｐ２は、サニタイジングされたマルチセグメント文字セットの第２の文字列の長さであり、ＬＤｅｘｐ１は、サニタイジングされた対について算出されたＬＤである。距離モジュール１６５の出力は、距離モジュール１６５によって比較された一対のジオデータのインスタンスのそれぞれのＮＬＤスコアである。
【００４０】
詳しくは、距離モジュール１６５は、第１の文字列の長さから第２の文字列の長さを減算し、この値をＬＤｅｘｐ１及び第２の文字列の長さの最小値によって除算する。この結果としての値の絶対値を求め、１から減算する。この絶対値をＬＤｅｘｐ１から減算する。そして、距離モジュール１６５は、この最終的な数値に１００を乗算して、ＮＬＤを得る。上述の例では、第１及び第２のサニタイジングされた文字列のＮＬＤは、６１．９％である。
【００４１】
幾つかの実施形態においては、距離モジュール１６５は、ジオデータインスタンスのセグメント／フィールドの様々な順列についてのＮＬＤ値を算出してもよい。上述の例で説明を続けると、アドレスフィールドの順列（単語の順序の変化）は、「100 de Reublica Ave, Madrid」と「100 Republica Ave, Madrid」を含む。サニタイジングされたバージョンは、「100dereublicaavemadrid」と「100republicaavemadrid」である。式１を使用すると、このジオデータインスタンスの対について９０．１％のＮＬＤ値が算出される。ジオデータインスタンスから抽出したフィールドの再編成（rearrangement）によって、多くの異なる種類の順列を実現できる。一実施形態においては、距離モジュール１６５は、ジオデータインスタンス間の一致する単語の対毎の整列（pairwise alignment）を実行することができる。対毎の整列により、結果として生じるサニタイジングされた文字列について算出されるＬＤが小さくなる。距離モジュール１６５は、ジオデータインスタンスのフィールドの可能な全ての順列についてＮＬＤ値を算出し、最高ランクのＮＬＤ値を判定することができる。
【００４２】
この場合も、順列処理は、フィールドの下位部分が再編成されるように、フィールドの又はセグメントのレベルで行ってもよい。例えば、「100 Ave de Reublica, Madrid」は、「100 de Reublica Ave, Madrid」又は「100 Reublica de Ave, Madrid」に再編成してもよい。
【００４３】
図６を参照して、ジオデータインスタンスのセグメント／フィールドの順列を作成及び使用する処理の例示的なフローチャートのより詳細な説明を以下で行う。
【００４４】
幾つかの実施形態においては、距離モジュール１６５は、ＮＬＤ閾値を適用することができ、ＮＬＤがＮＬＤ閾値を超えた場合、第１及び第２のサニタイジングされた文字列が同じＰＯＩに対応するとみなす。例えば、ＮＬＤ閾値は、８０％であってもよい。これにより、ＮＬＤが８０％より低ければ、ジオデータインスタンスは、同じＰＯＩを表している可能性が低いと判定される。ＮＬＤが８０％未満であっても、ジオデータインスタンスが実際に同じＰＯＩを表していることもあり、ジオデータインスタンスは、最終的な判定を行うために地図プロッティング又は人間による確認を要求してもよい。第１及び第２のサニタイジングされた文字列が取得されるところの、ジオデータインスタンスは、更なる確認のためにフラグを付すことができる。また、サーバ１０５は、これらのデータのフォーマット及び／又はコンテンツに誤りがある可能性があることを各ジオデータソースに警告してもよい。ＮＬＤ閾値は、要求される任意の感度に設定してもよい。
【００４５】
上述の例では、８０％のＮＬＤ閾値の使用を想定しているが、このＮＬＤ閾値は、単なる例であり、ＮＬＤ閾値は、望ましい任意の値に設定してもよく、システムのエンドユーザは、ジオデータインスタンスを比較するために望ましい感度レベルを決定することができる。
【００４６】
他の具体例では、第１のサニタイジングされた文字列である「sheratonhotel」と、第２のサニタイジングされた文字列である「sheratonhoteldowntowntoronto」について、ＮＬＤを算出する。この具体例では、ＬＤは１５であり、文字列が全く類似していないことを示すが、ＮＬＤは、サニタイジングされた文字列が同一であって、それぞれが同じＰＯＩを表すことを示す１００％が算出される。ＬＤが第１及び第２の文字列の間の大きな距離的相違を示していても、ＮＬＤ式は、式１を用いて第１及び第２の文字列の最小値をとる際、第２の文字列内の余分な文字を基本的に無視する。
【００４７】
このように、本技術は、一般的なＬＤ計算の使用に対し、様々な目的のために使用できる正規化されたＬＤを用いることによる利点を提供し、すなわち、通常、一貫性が大きく欠ける（例えば、距離が大きい）文字列が同じコンテンツを表していることを特定することができる。ある例では、コンテンツは、ジオデータを含むが、他のコンテンツは、複数のフィールド（例えば、セグメント）によって表現される如何なるデータのタイプであってもよい。
【００４８】
幾つかの実施形態においては、距離モジュール１６５は、ＮＬＤが８０％未満である場合、２つのサニタイジングされたアドレスの間で物理的距離チェックを実行することができる。例えば、距離モジュール１６５は、プロッティングモジュール１７５と連携して、２点の間の物理的距離を判定することができる。プロッティングモジュール１７５は、地図上に第１のサニタイジングされたアドレスと第２のサニタイジングされたアドレスをプロットする。距離モジュール１６５は、第１及び第２のサニタイジングされたアドレス間の物理的距離を算出することができる。例えば、距離モジュール１６５は、地図上の２つのプロットされた点の間の地理的距離を算出することができる。
【００４９】
物理的距離が１００フィート未満である場合、距離モジュール１６５は、ＮＬＤが閾値以下であっても、第１及び第２のサニタイジングされたアドレスが同じＰＯＩを表しているとみなす。上述の例に戻って説明すると、第１のサニタイジングされた文字列である「100avedereublicamadrid」と、第２のサニタイジングされた文字列である「100republicaavemadrid」は、地図上にプロットされると、物理的距離がゼロであることが判る。したがって、ＮＬＤ（６１．９％）が８０％の閾値を僅かに下回っていても、サニタイジングされたアドレスは、実際に同じＰＯＩを表している。
【００５０】
図３を参照して説明すると、第１のサニタイジングされたアドレスは、地図３００上に点３０５としてプロットされる。第２のサニタイジングされたアドレスは、３００上に点３１０としてプロットされる。実際の関心点は、２本の街路３２０、３２５の交差点にあるホテル３１５である。第１及び第２の点３０５、３１０の間の距離３３０は、各点３０５、３１０の座標を判定することによって算出（又は推定）できる。一実施形態においては、地図３００が座標を含む場合、座標を判定できる。点を地図３００上に重ねたときに、座標を推定してもよい。
【００５１】
この場合も、距離３３０が実質的にゼロであるため、点３０５、３１０は、ホテル３１５に対応する同じＰＯＩを表していると判定される。また、サーバ１０５は、ジオデータインスタンスの名称フィールド又は他のフィールドを比較することによって、第１及び第２の点の間の対応を確認してもよい。
【００５２】
図４は、本技術の例示的な方法のフローチャートである。この方法は、２つのマルチセグメント文字セット（例えば、ジオデータのインスタンス）を受信するステップ４０５を有する。２つのマルチセグメント文字セットのそれぞれは、複数のセグメント又はフィールドから構成されている。また、各フィールドは、フォーマットを有している。これらは、例えば、ＰＯＩ名、都市、番地、州、等である。
【００５３】
方法は、２つのマルチセグメント文字セットのそれぞれをサニタイジングするステップ４１０を含み、ここでは、まず、マルチセグメント文字列の複数のセグメントのうちの何れかのセグメントのフォーマットが標準化されたフォーマットでない場合、そのセグメントを標準化されたフォーマットに変換するステップ４１５を行う。この変換は、標準化されたフォーマットではないセグメント毎に実行してもよい。例えば、「fifth」、「5th」、「V」等のフィールドを、標準化されたフォーマットである「5」に変換してもよい。各フィールドは、必要に応じてサニタイジングしてもよい。
【００５４】
次に、サニタイゼーションは、変換されたセグメント及び変換されていないセグメントから連続する文字列を作成することによって２つのマルチセグメント文字セットのそれぞれを短縮するステップ４２０を含む。すなわち、幾つかのセグメント／フィールドは、サニタイジングしなくてもよい。サーバ１０５は、変換されたセグメント及び変換されていないセグメントの両方を１つの文字列に結合する。短縮処理は、大文字を小文字に変更するステップ４２５及び非英数字を除去するステップ４３０を含んでいてもよい。
【００５５】
次に、方法は、サニタイジングされたマルチセグメント文字セットを用いて距離スコアを算出するステップ４３５を含む。なお、距離スコアは、サニタイジングされたマルチセグメント文字セットの文字間の違いを表す。距離スコアを算出する方法については、図５を用いて以下に説明する。
【００５６】
図５は、正規化されたレーベンシュタイン距離（ＮＬＤ）を算出する方法を例示的に示している。この方法は、第１及び第２のサニタイジングされた文字列（例えば、サニタイジングされた文字列）を受信するステップ５０５を含む。幾つかの実施形態においては、この方法は、第１及び第２の文字列の両方のレーベンシュタイン距離を算出するステップ５１０を含む。この方法は、更に第１及び第２の文字列のそれぞれの文字長を判定し、文字長を用いてＮＬＤを算出するステップ５１５を含む。ＮＬＤは、上に詳しく説明した式１を用いて算出してもよい。
【００５７】
上述したように、ＮＬＤは、文字コンテンツに関して、文字列の「近さ」を表現するパーセンテージで表されるスコアである。例えば、「1234mainst」と「1234mainst」のＮＬＤは、１００％であり、「100avedereublicamadrid」と「100republicaavemadrid」のＮＬＤは、６１．９％である。
【００５８】
方法は、更に、ＮＬＤを閾値と比較するステップ５２０と、ＮＬＤが閾値に達していない又は閾値を超えていない場合に、第１及び第２の文字列の間の物理的距離計算を実行するステップ５２５とを含む。例えば、６１．９％のＮＬＤは、８０％の閾値と比較される。ＮＬＤは、閾値に達していないので、サーバ１０５は、物理的距離計算を実行することができる。
【００５９】
例えば、サーバは、第１及び第２の文字列を地図上にプロットすることができ、具体的には、第１及び第２の文字列の番地をプロットすることができる。他の実施形態においては、第１及び第２の文字列が座標を含む場合、第１及び第２の文字列は、座標を用いてプロットしてもよい。プロットされた点の間の距離を判定し、距離閾値と比較してもよい。例えば、距離が１００フィート未満である場合、プロットされた点は、同じＰＯＩを表しているとみなすことができる。
【００６０】
図４及び図５のフローチャートは、フローチャートに示されているステップの幾つかを省略してもよいし、更にステップを追加してもよい。更に、フローチャートのステップは、本明細書に提供されている説明及び具体例に応じて、他のステップに置き換えることもできる。
【００６１】
図６は、ジオデータインスタンスのセグメント／フィールドの順列を作成及び使用し、ジオデータインスタンスの対についてのＮＬＤ値を算出し比較する方法のフローチャートである。上述したように、以下の例は、「マルチセグメント文字セット」としてのジオデータインスタンスを用いて説明される。
【００６２】
まず、２つのマルチセグメント文字セットのうちの第１のマルチセグメント文字セットを選択する。２つのマルチセグメント文字セットのうちの第２のマルチセグメント文字セットは、変更しなくてもよい。この方法は、２つのマルチセグメント文字セットのうちの第１のマルチセグメント文字セットを選択した後、２つのマルチセグメント文字セットのうちの第１のマルチセグメント文字セットから、複数の並べ替えられたマルチセグメント文字セットを作成するステップ６０５を有する。この処理は、２つのマルチセグメント文字セットのうちの１つのマルチセグメント文字セットの複数のセグメント内のセグメントの文字を再編成して、並べ替えられたセグメントを作成するステップを含む。再編成処理は、第１のマルチセグメント文字セットに対して、複数回実行され、複数の並べ替えられたマルチセグメント文字セットが生成される。
【００６３】
次に、この方法は、マルチセグメント文字セットの対を作成するステップを有する。これらの対は、マルチセグメント文字セットから並べ替えられた複数のマルチセグメント文字セットの１つと、第２のマルチセグメント文字セットとを含む。例えば、第１の対は、マルチセグメント文字セット「Hotel California, Los Angeles downtown」と第２のマルチセグメント文字セット「Los Angeles california hotel」を含む。第２の対では、並べ替えられたマルチセグメント文字セット「California Hotel Los Angeles downtown」が第２のマルチセグメント文字セット「Los Angeles california hotel」と対にされる。第３の対では、他の並べ替えられたマルチセグメント文字セット「Los Angeles California Hotel downtown」が第２のマルチセグメント文字セット「Los Angeles california hotel」と対にされる。
【００６４】
次に、この方法は、マルチセグメント文字セットの対をサニタイジングするステップ６１０を有する。上述のように、マルチセグメント文字セットの対は、複数の並べ替えられたマルチセグメントセットと、第２のマルチセグメント文字セットとの様々な組合せを含む。
【００６５】
ある実施形態においては、この方法は、マルチセグメント文字セットの対のそれぞれについて、正規化されたレーベンシュタイン距離（normalized Levenshtein distance：ＮＬＤ）を算出するステップ６１５を有する。
【００６６】
幾つかの実施形態においては、この方法は、マルチセグメント文字セットの全ての対のうち、最高ランクのＮＬＤを判定するステップを有する。
【００６７】
他の実施形態においては、この方法は、マルチセグメント文字セットの全ての対から最小のＮＬＤを判定するステップ６２０を含む。ＮＬＤが最小の対は、ジオコーディングされたインスタンス（例えば、マルチセグメント文字セットの対）のうち最も一致する対であると考えられる。
【００６８】
図７は、コンピュータシステム１の形式の例示的なマシンのブロック図であり、このマシン内の一組の命令が実行されることによって、マシンは、本明細書に説明した動作の１つ以上を実行する。様々な例示的実施形態において、マシンは、独立型デバイスとして動作してもよく、他のマシンに接続（例えば、ネットワーク化）してもよい。ネットワーク化された構成では、このマシンは、サーバ−クライアントネットワーク環境におけるサーバ又はクライアントマシンの能力で動作してもよく、又はピアツーピア（又は分散型）ネットワーク環境のピアマシンとして動作してもよい。このマシンは、パーソナルコンピュータ（personal computer：ＰＣ）、タブレットＰＣ、セットトップボックス（set-top box：ＳＴＢ）、個人携帯情報端末（personal digital assistant：ＰＤＡ）、携帯電話機、携帯用音楽プレーヤ（例えば、携帯用ハードドライブ音声装置、例えば、ＭＰＥＧ（Moving Picture Experts Group）オーディオレイヤ３（ＭＰ３）プレーヤ）、ウェブ機器、ネットワークルータ、スイッチ又はブリッジ、又はマシンに実行させる動作を指定する一組の命令を（連続的又は他の形式で）実行することができる任意のマシンであってもよい。更に、１つのマシンのみを例示しているが、「マシン」という用語は、個別に又は連携して、一組（又は複数組）の命令を実行して、本明細書に説明した動作の１つ以上を実行するマシンのあらゆる集合体を含む。
【００６９】
例示的に示すコンピュータシステム１は、プロセッサ又は複数のプロセッサ５（例えば、中央演算処理装置（central processing unit：ＣＰＵ）、グラフィックス処理装置（graphics processing unit：ＧＰＵ）又はこれらの両方）と、それぞれバス２０を介して互いに通信するメインメモリ１０及びスタティックメモリ１５とを含む。コンピュータシステム１は、更に、ビデオディスプレイ３５（例えば、液晶ディスプレイ（liquid crystal display：ＬＣＤ））を含んでいてもよい。コンピュータシステム１は、英数字入力デバイス３０（例えば、キーボード）、カーソル制御装置（例えば、マウス）、音声認識又は生体認証ユニット（図示せず）、ドライブユニット３７（ディスクドライブユニットとも呼ばれる）、信号生成デバイス４０（例えば、スピーカ）、及びネットワークインターフェースデバイス４５を含んでいてもよい。コンピュータシステム１は、更に、データを暗号化するデータ暗号化モジュール（図示せず）を含んでいてもよい。
【００７０】
ディスクドライブユニット３７は、本明細書に説明した動作又は機能の何れか１つ以上を実現又は利用する命令（例えば、命令５５）及びデータ構造の１つ以上の組が保存されるコンピュータ又はマシン可読媒体５０を含む。命令５５は、コンピュータシステム１による実行の間、メインメモリ１０及び／又はプロセッサ５内に完全に又は部分的に常駐してもよい。また、メインメモリ１０及びプロセッサ５もマシン可読媒体を構成してもよい。
【００７１】
更に、命令５５は、幾つか周知の転送プロトコルの１つ（例えば、ハイパテキスト転送プロトコル（Hyper Text Transfer Protocol：ＨＴＴＰ））を利用するネットワークインターフェースデバイス４５によって、ネットワーク１４０（図２参照）を介して送信又は受信してもよい。例示的な実施形態においては、マシン可読媒体５０を１つの媒体として示しているが、「コンピュータ可読媒体」という用語は、一組以上の命令を保存する単一の媒体及び複数の媒体（例えば、集中型又は分散型データベース及び／又は関連するキャッシュ及びサーバ）を含む。また、「コンピュータ可読媒体」という用語は、マシンによって実行され、マシンがここに説明する方法の１つ以上を実現する一組の命令を保存し、符号化し、搬送することができるあらゆる媒体、又はこのような一組の命令に利用され若しくはこれに関係するデータ構造を保存し、符号化し、搬送することができるあらゆる媒体を含む。したがって、「コンピュータ可読媒体」という用語は、以下に限定されるわけではないが、ソリッドステートメモリ、光磁気媒体及び搬送波信号を含む。このような媒体は、以下に限定されるわけではないが、ハードディスク、フロッピー(登録商標)ディスク、フラッシュメモリカード、デジタルビデオディスク、ランダムアクセスメモリ（random access memory：ＲＡＭ）、読出専用メモリ（read only memory：ＲＯＭ）等を含む。本明細書に開示する例示的な実施形態は、コンピュータ上にインストールされたソフトウェア、ハードウェア、又はソフトウェア及びハードウェアの組合せによる動作環境で実現してもよい。
【００７２】
インターネットサービスは、インターネットサービスに接続された１つ以上の演算デバイスにインターネット接続を提供するように構成してもよく、演算デバイスは、１つ以上のプロセッサ、バス、メモリデバイス、表示デバイス、入出力デバイス等を含んでいてもよいことは、当業者の認識するところである。更に、インターネットサービスは、１つ以上のデータベース、レポジトリ、サーバ等に接続してもよく、これらを用いて、本明細書に開示した如何なる実施形態を実現してもよいことは、当業者の理解するところである。
【００７３】
特許請求の範囲における手段又はステップ・プラス・ファンクション・エレメント（step plus function elements）の全てに対応する構造、材料、動作及び均等物は、特定的に特許請求されている通り、他の特許請求された要素と連携してその機能を実行するためのあらゆる構造、材料及び動作を含むことを意図する。説明及び開示のために、本技術を記述したが、本明細書に開示した形式を本技術の全てであるとする意図、又は、本技術を本明細書に開示した形式に限定する意図はない。本技術の範囲及び精神を逸脱することなく、多くの修正及び変更が当業者にとって明らかである。本技術の原則及びその実用的なアプリケーションを最良に説明するために、及び当業者が本技術を理解し、特定の用途に適するように様々な修正を加えた様々な実施形態を想到できるように、例示的な実施形態を選択し、記述した。
【００７４】
以上では、本技術の実施形態に基づく方法、装置（システム）及びコンピュータプログラム製品のフローチャート実現例及び／又はブロック図を参照して、本技術の側面を記述した。フローチャート実現例及び／又はブロック図の各ブロック、又はフローチャート実現例及び／又はブロック図のブロックの組合せは、コンピュータプログラム命令によって実現してもよいことは明らかである。これらのコンピュータプログラム命令は、汎用コンピュータ、専用コンピュータ又はマシンを構成する他のプログラム可能なデータ処理装置のプロセッサに供給してもよく、命令は、コンピュータ又は他のプログラム可能なデータ処理装置のプロセッサによって実行されて、フローチャート及び／又はブロック図の１つ又は複数のブロックによって特定されている機能／動作を実現するための手段を構成する。
【００７５】
これらのコンピュータプログラム命令は、コンピュータ、他のプログラム可能なデータ処理装置又は他のデバイスに特定の方式で機能するように指示を与えるコンピュータ可読媒体に保存してもよく、これによって、コンピュータ可読媒体に保存された命令は、フローチャート及び／又はブロック図の１つ又は複数のブロックで特定されている機能／動作を実現する命令を含む製品を構成する。
【００７６】
コンピュータプログラム命令は、コンピュータ、他のプログラム可能なデータ処理装置又は他のデバイスにロードしてもよく、これによって、コンピュータ、他のプログラム可能な装置又は他のデバイスに、コンピュータによって実現される処理を実行させる一連の動作ステップを実行させ、コンピュータ又は他のプログラム可能な装置上で実行される命令は、フローチャート及び／又はブロックの１つ又は複数のブロックで指定されている機能／動作を実現する処理を提供する。
【００７７】
図に示すフローチャート及びブロック図は、本技術の様々な実施形態に基づくシステム、方法及びコンピュータプログラム製品の可能な具体例のアーキテクチャ、機能及び動作を例示する。これに関して、フローチャート又はブロック図内の各ブロックは、特定の論理機能を実現するための１つ以上の実行可能な命令を含むモジュール、セグメント又はコードの一部を表していてもよい。なお、幾つかの変形例では、ブロックに示した機能は、図に示す順序とは異なる順序で実行してもよい。例えば、連続して示される２つのブロックは、関係する機能に応じて、実際には、実質的に並行して実行してもよく、逆の順序で実行してもよい。また、例示したブロック図及び／又はフローチャートにおける各ブロック及び／又はフローチャートの複数のブロックの組合せは、特定の機能又は動作を実行する特定用途のハードウェアベースのシステムによって実現してもよく、特定用途のハードウェア及びコンピュータ命令の組合せによって実現してもよい。
【００７８】
以上では、例示を目的としてシステムの特定の実施形態及びこの具体例を記述したが、当業者が理解するように、システムの範囲内で、様々な等価な変更が可能である。例えば、処理又はステップを所与の順序で示したが、他の実施形態では、異なる順序のステップを有するルーチンを実行してもよく、幾つかの処理又はステップを削除し、移動し、追加し、再分割し、組合せ及び／又は変更して、代替又は下位の組合せを提供してもよい。これらの処理又はステップのそれぞれは、様々な異なる手法で実行してもよい。また、処理又はステップは、同じ時刻に順番に実行されるように示しているが、これらの処理又はステップは、並列的に実行してもよく、異なる時刻に実行してもよい。
【００７９】
様々な実施形態を記述してきたが、これらは、例示的なものに過ぎず、限定的なものではない。この説明は、本発明の範囲を本明細書に述べる特定の形式に制限することを目的としない。これとは反対に、この記述は、特許請求の範囲に定義され、或いは当業者にとって理解される本発明の思想及び範囲内に含まれるように、代替例、変形例及び等価物を包含することを意図する。このように、好ましい実施形態の幅及び範囲は、上述した例示的な実施形態の何によっても制限されない。
【図１】
2016528553.tif 000003
【図２】
2016528553.tif 000004
【図３】
2016528553.tif 000005
【図４】
2016528553.tif 000006
【図５】
2016528553.tif 000007
【図６】
2016528553.tif 000008
【図７】
2016528553.tif 000009
【国際調査報告】
2016528553.tif 000010
2016528553.tif 000011