曖昧な場所に基づくルーティング情報提供
ルーティングサーバは、ルーティング情報を要求するリクエストを受け取る。前記リクエストは、1つまたは複数の場所を指定する。指定される場所は曖昧であることがある。曖昧な場所については、前記ルーティングサーバは、1組のマッチしている可能性がある場所を見つけ出し、任意の測定尺度に従って、これらの見つけ出した場所を順位付けする。前記ルーティングサーバは、曖昧な場所にマッチするもののうち最上位に順位付けされた場所について、ルーティング情報を返す。ルーティング情報を要求するリクエストが2つの場所を指定するものであり、前記場所の少なくとも1つが曖昧である場合、前記ルーティングサーバは、クエリーに基づいて、マッチしている可能性がある場所をペア化し、各ペアごとに測定尺度を算出する。1つの例において、前記測定尺度は、該ペアにおける場所間の距離である。前記ルーティングサーバは、前記測定尺度に基づいてペアを順位付けし、最上位に順位付けされたペアについてのルーティング情報を返す。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータ化されたマッピングに関し、特に、指定された場所の間での方向またはその他のルーティング(経路設定)情報を提供するシステムに関する。
【背景技術】
【０００２】
運転方向、列車運行スケジュール等のルーティング情報を得るためにインターネット上のウェブサイトを使用することが普通になってきている。ほとんどのウェブサイトでは、方向を求めているエンドユーザは始点場所および終点場所を与え、前記ウェブサイトは、前記2つの場所間でのルーティング情報を返す。該サイトは、地図および推定旅行時間等の追加情報をも返してもよい。
【０００３】
ルーティング情報を算出する際に遭遇する一般的な問題点は、場所の曖昧さである。しばしば、エンドユーザは、2つの場所の一方または両方の部分的な住所のみを与える。しばしば、同じ名前を有する多数の場所が存在するので、部分的な住所は識別するのが困難である。例えば、インディアナ州のセーレム(Salem)とイリノイ州のシカゴとの間の運転方向を求めているエンドユーザは、“セーレム”という始点場所および/または“シカゴ”という終点場所を指定するルーティングリクエストをウェブサイトに与える。米国には“セーレム”という名前の市が少なくとも10個存在し、“シカゴ” という名前の市が少なくとも2個存在する。その結果、前記ウェブサイトでは、前記曖昧な場所を識別するために前記ルーティングリクエストをより細かく述べるようエンドユーザに要求する。
【０００４】
典型的には、前記ウェブサイトは、曖昧な場所に一致(マッチ)する場所のリストをエンドユーザに与え、該エンドユーザにリストされた前記場所の中からいずれかを選択するよう要求する。例えば、前記ウェブサイトは、イリノイ州のシカゴおよびウイスコンシン州のシカゴ中からいずれかを選択するよう要求する。前記エンドユーザと前記ウェブサイトとの間の上記のインタラクションは、面倒で、時間がかかる。このような問題は、前記エンドユーザが低速の通信リンクを介して前記ウェブサイトと通信している場合、および/または、小さな表示スクリーンまたは制限されたユーザインターフェースを有するモバイル装置を使用している場合、特に深刻である。
【発明の概要】
【０００５】
従って、当該技術において、従来より、曖昧な場所を指定するルーティング情報リクエストを識別するためのより効率的な方法が必要とされている。
【０００６】
上記の課題は、ルーティング情報を要求するリクエストであって少なくとも1つの曖昧な場所を指定するリクエストを受け取る、ルーティング情報を提供する方法、システムおよびコンピュータプログラム製品によって達成される。前記ルーティング情報を提供する方法、システムおよびコンピュータプログラム製品は、曖昧な場所にマッチしている可能性がある場所を見つけ出し、任意の測定尺度に基づいて前記マッチしている可能性がある場所を順位付けし、前記マッチしている可能性がある場所のうちの最上位に順位付けされた場所についてルーティング情報を提供する。
【図面の簡単な説明】
【０００７】
【図１】本発明の一実施の形態に従うコンピューティング環境を示す高レベルブロック図。
【０００８】
【図２】本発明の一実施の形態に従う、図1の環境に示されたもののようなクライアントまたはサーバに使用される典型的なコンピュータの機能を示す高レベルブロック図。
【０００９】
【図３】本発明の一実施の形態に従うルーティング情報モジュール内のモジュールを示す高レベルブロック図。
【００１０】
【図４】一実施の形態に従うルーティング情報モジュールおよび/またはルーティングサーバによって実行されるステップを示すフローチャート図。
【００１１】
図は、本発明の一実施の形態を例示目的でのみ示すものである。下記の説明から、ここで説明される構造および方法の他の実施の形態が本発明の原理から逸脱することなく用いられてよい、ことが当業者に理解されよう。
【発明を実施するための形態】
【００１２】
図1は、本発明の一実施の形態に従うコンピューティング環境100を示す高レベルブロック図である。図1は、ネットワーク114によって接続された3つのクライアント110とルーティングサーバ112とを示している。図1およびその他の図においては、同様な参照数字を使用して同様な要素を示している。“110A”のような参照数字の後の文字は、該特定の参照数字を有する要素に言及していることを示す。“110”のような後続する文字のない参照数字は、図における該参照数字を有する要素のいずれかまたはすべてに言及している(例えば、110”は、図における“110A”、“110B”および/または“110C”に言及している)。図1はクライアント110を3つだけ示しているが、本発明の実施の形態は、前記サーバ112とインタラクトする何千または何百万ものクライアントを有するものであってもよい。しかし、本発明を簡略化し明確化するためにクライアント110を3つだけ示している。同様な理由で、ネットワーク114に接続されてよいその他のサーバは図1に示されていない。
【００１３】
前記クライアント110は、ルーティングリクエストを与え、その返答としてのルーティング情報を得るため、ネットワーク114を介してサーバ112とインタラクトするためにエンドユーザによって使用される装置を示す。一実施の形態において、前記クライアント110は、標準的なネットワーク関連機能を有するコンピュータである。ある実施の形態において、前記クライアント110は、ノート型コンピュータ、モバイル電話、パーソナル・ディジタル・アシスタント(PDA)、携帯eメール装置、携帯ゲーム装置、自動ナビゲーションシステム、または同等機能を有するその他の種類の装置である。前記クライアント110は、コンピュータおよび/またはモバイル通信プロトコルを使用する有線および/または無線のネットワークを含む標準的なネットワーク関連技術を使用して、サーバ112と通信する。
【００１４】
前記クライアント110は、前記サーバ112に対してルーティングリクエストを出すための機能と、受け取ったルーティング情報をエンドユーザに与えるための機能とを有する。実施の形態によっては、前記クライアント110は、リクエストを入力するためのキーボードと、ルーティング情報を見るための表示器とを有する。多くのモバイル電話およびその他のモバイル装置は、使用するのが難しい小さなキーボードを有する。他の実施の形態においては、前記クライアント110は、タッチスクリーンに基づく入力装置および/またはオーディオ出力装置のような、これらのタスクを実行するための付加的および/またはこれらと異なる機能を含む。
【００１５】
一実施の形態において、前記クライアント110は、標準的なインターネット通信技術を使用して前記サーバ112とメッセージを交換することを可能にするウェブブラウジング機能を含む。例えば、前記クライアント110は、MICROSOFT INTERNET EXPLORER (登録商標)等のウェブブラウザ、OPERA MOBILE(商標)およびOPERA MINI(商標)等のモバイル用に最適化されたブラウザ、および/または、エンドユーザがウェブサーバおよび/または他のネットワーク114上のコンピュータシステムからコンテンツを取り出して、表示することを可能にするブラウザを実行することができる。
【００１６】
前記ルーティングサーバ112は、クライアント110からルーティングリクエストを受け取り、ルーティング情報を返す。一実施の形態において、前記ルーティングサーバ112は、クライアント110にウェブページを提供し、クライアントから与えられたデータを受け取るために使用されるウェブサーバとして機能するコンピュータを含む。前記ルーティングサーバ112は、ルーティングリクエストを受け取り、ルーティング情報を発生するためのルーティング情報モジュール300を含む。
【００１７】
しばしば、前記クライアント110から受け取られるルーティングリクエストは始点場所および終点場所を含み、前記ルーティングサーバ112は、前記始点場所から終点場所にまで行く方法を説明するルーティング情報を発生する。前記ルーティング情報は、例えば、運転方向および地図、列車の運行スケジュールおよび方向、飛行機の飛行スケジュール等を含むことができる。ここでの説明ではしばしば2つの場所を有するルーティングリクエストに言及しているが、前記ルーティングサーバ112は、どのような数の場所を有するリクエストにも対応可能である。例えば、前記ルーティングサーバ112は、1つの場所を通過するバス、列車および/または飛行機の飛行スケジュールを記述する該1つの場所に関するルーティング情報を提供することができる。
【００１８】
一実施の形態において、前記ルーティングサーバ112は、一致(マッチ)する可能性がある場所のペア(対)の間の距離を算出し、最も近い場所のペア(すなわち、距離が最も小さい場所のペア)に関するルーティング情報を返すことによって、曖昧な場所(例えば、地名が“セーレム”および“シカゴ”)に対応する。このようにして、“セーレム”と“シカゴ”との間の運転方向に関するリクエストを受け取る前記ルーティングサーバ112の一実施の形態は、インディアナ州のセーレムとイリノイ州のシカゴの間の運転方向を自動的に提供する。というのは、これらの場所が同じ名前を有する他のすべてのペアの市より近距離であるからである。さらに、前記ルーティングサーバ112は、該ルーティングサーバ112によって選択されたペアが前記エンドユーザが意図するものではない場合、該エンドユーザが異なる場所のペアを指定するのを可能にするユーザインターフェース(UI)を提供する。
【００１９】
前記ネットワーク114は、前記クライアントと前記ルーティングサーバ112のとの間の通信経路を示すものである。一実施の形態において、前記ネットワーク114はインターネットである。該ネットワーク114は、必ずしもインターネットの一部ではない専用または私用の通信リンクを使用することもできる。一実施の形態において、前記ネットワーク114は、標準的な通信技術および/またはプロトコルを使用する。従って、前記ネットワーク114は、Ethernet 802.11、総合デジタル通信網(ISDN)、ディジタル加入者線(DSL)、非同期転送モード(ATM)等の技術を使用するリンク、ならびに、モバイル電話通信技術を使用するリンクを含むことができる。同様に、前記ネットワーク114上で使用されるネットワークプロトコルは、マルチプロトコルラベルスイッチング(MPLS)、transmission control protocol/Internet protocol(TCP/IP)、hypertext transport protocol (HTTP)、simple mail transfer protocol(SMTP)、file transfer protocol(FTP)、short message service(SMS) プロトコル等を含むことができる。前記ネットワーク114を介して授受されるデータは、hyper text markup language(HTTP)、extensible markup language(XML)、extensible hypertext markup language(XHTML)、compact HTML(cHTML)等を含む技術および/またはフォーマットを使用して表される。さらに、リンクのすべてまたは一部は、secure sockets layer(SSL)、HTTP over SSL(HTTPS)および/または仮想プライベートネットワーク(VPNs: virtual private networks)等の従来の暗号化技術を使用して暗号化可能である。他の実施の形態において、前記クライアント110およびルーティングサーバ112は、上記のものの代わりにまたはその追加として、カスタムメイドおよび/または専用のデータ通信技術を使用する。
II. システムアーキテクチャ
【００２０】
図2は、本発明の一実施の形態に従う図1の環境100に示されたもののようなクライアント110またはサーバ112に使用される典型的なコンピュータ200の機能を示す高レベルブロック図である。図2には、バス204に接続された少なくとも1つのプロセッサ202が示されている。また、バス204には、メモリ206と、記憶装置208と、キーボード210と、グラフィックスアダプタ212と、ポインティングデバイス214と、ネットワークアダプタ216とがさらに接続されている。表示器218は、前記グラフィックスアダプタ212に接続されている。
【００２１】
前記プロセッサ202は、INTELx86系CPUのような任意の汎用プロセッサであってよい。前記記憶装置208は、一実施の形態において、ハードディスクであるが、書き込み可能なコンパクトディスク(CD)もしくはDVD、またはソリッドステートメモリデバイスのような、データを記憶することが可能な任意の装置であってよい。前記メモリ206は、例えば、ファームウエアの読み取り専用メモリ(ROM)、非揮発性ランダムアクセスメモリ(NVRAM)および/またはRAMであってよく、プロセッサ202によって使用される命令およびデータを保持する。前記ポインティングデバイス214は、マウス、トラックボールまたはその他の種類のポインティングデバイスであってよく、データをコンピュータシステム200に入力するために、前記キーボード210と共に使用される。前記グラフィックスアダプタ212は、表示器218に画像およびその他の情報を表示する。
【００２２】
当該技術分野において公知のように、前記コンピュータ200は、コンピュータプログラムモジュールを実行するよう構成されている。ここで、“モジュール”という用語は、指定された機能を実現するためのコンピュータプログラム論理および/またはデータを意味する。モジュールは、ハードウエア、ファームウエアおよび/またはソフトウエアの形態で実現され得る。一実施の形態において、前記モジュールは、前記記憶装置208に記憶され、前記メモリ206にロードされ、前記プロセッサ202によって実行される。
【００２３】
図1の構成要素によって使用されるコンピュータ200の種類は、実施の形態および前記構成要素によって使用される処理能力に応じて可変である。例えば、前記クライアント110は、典型的には、前記ルーティングサーバ112より低い処理能力を必要とする。従って、前記クライアント110は、標準的なパーソナルコンピュータまたは携帯電子デバイスであってよい。対照的に、前記ルーティングサーバ112は、高能力のコンピュータおよび/またはここに説明する機能を実現するために共働するより多数のコンピュータからなっていてよい。同様に、前記コンピュータ200は、上記の構成要素のうちのいくつかを欠いていてよい。例えば、クライアント110として機能するモバイル電話はポインティングデバイスを欠いていてよく、前記ルーティングサーバ112として機能するコンピュータはキーボードおよび表示器を欠いていてよい。
【００２４】
図3は、本発明の一実施の形態に従うルーティング情報モジュール300内のモジュールを示す高レベルブロック図である。他の実施の形態は、図3に示したものとは異なるおよび/またはこれらの追加としてのモジュールを有する。さらに、他の実施の形態では、異なる態様で、前記モジュール間で機能が分散される。
【００２５】
リクエスト受領モジュール310は、前記クライアント110および/またはその他のソースからルーティング情報を受け取る。一実施の形態において、ルーティングリクエストは、その間でのルーティング情報が要求される2つ以上の場所を指定する。さらに、前記ルーティングリクエストは、要求されるルーティング情報の種類(例えば、運転方向または列車の運行スケジュール)、ルーティング情報が要求される日時、当該ルートに高速道路、急行列車または飛行機を使用するのか等を記述するパラメータ等のデータを含んでいてよい。
【００２６】
リクエスト解析モジュール312は、ルーティングリクエストを解析し、指定された場所を抽出する。場所は、典型的には、名前および/または住所によって指定されるが、地理的座標のような他の手段よって指定されてもよい。一実施の形態において、前記場所は、前記ルーティングリクエストによって明確に特定される。例えば、前記ルーティングサーバ112がクライアント110に提供するウェブページは、始点場所および目的場所の情報を名前、ストリート名、市、州/行政区(province)/県(prefecture)、および郵便コードに分離する。他の実施の形態において、前記場所のうちの一部またはすべてが暗黙的に特定される。例えば、前記ルーティングリクエストは、“東京と鎌倉との間の運転方向”のような自由形式文字列に含ませてよい。前記自由形式のリクエストを受け取ると、リクエスト解析モジュール312は、通常の表現および/またはその他の技術を使用して前記リクエストを解析し、そこで言及された場所に関する情報を抽出する。
【００２７】
解析される場所は、不明確および/または不完全な情報を使用して指定されることがある。エンドユーザが前記リクエストに前記情報を含めなかったため、および/または、解析上の困難のために、もちろんこのような情報欠如は発生し得る。例えば、前記ルーティングリクエストは、ストリートの住所および市の名前を使用して場所を指定できるが、前記市が存在する州または県の名前が含まれていない。同様に、前記リクエストは、駅の名前(例えば、“えびす駅”)を使用して場所を指定できるが、該駅が存在する市の名前が含まれていない。
【００２８】
場所検索モジュール314は、場所データベース316において、前記ルーティングリクエストから抽出された場所を検索する。一実施の形態において、前記場所データベース316は、複数のルーティングリクエストによって指定される可能性がある複数の場所を記述した情報を含むものである。さらに、前記場所データベース316は、1つまたは複数の国のストリートマップを記述したデータを含んでいてよい。例えば、前記場所データベース316は、列車、飛行機、バス、フェリーおよびその他の交通路線を記述したデータを含んでいてよい。さらに、前記場所データベース316の一実施例は、リアルタイムのまたは過去のストリート交通情報、交通スケジュール、料金表等の関連情報を含む。一実施の形態において、分離した複数のデータベースの1つまたは複数が前記ルーティングサーバ112の外部に設けられていてもよい。
【００２９】
一実施の形態において、前記場所データベース316は、該データベースにおける複数の場所の順位付けおよび/または比較を可能にするデータを有するメトリクス(測定)モジュール318を含む。一実施の形態において、測定尺度は距離であり、前記測定モジュール318は、前記データベースにおける複数の場所の地理的位置を記述するデータを有する。さらに、前記メトリクスモジュール318(または、その他のモジュール)は、2つ以上の指定された場所間の距離を算出する。一実施の形態において、前記測定モジュール318は、前記データベースにおける複数の場所を緯度/経度座標に変換し、該緯度/経度座標間の距離を算出する。他の実施の形態において、測定尺度は人口および/または表面積であり、前記測定モジュール318は、前記データベースにおいて特定された様々な場所の人口および表面積および/または地域(例えば市)を記述するデータを有する。さらに他の実施の形態において、測定尺度は人気であり、前記測定モジュール318は、前記データベースにおける様々な場所の人気を記述するデータを有する。該人気は、これらの場所がルーティングリクエストに現われる頻度、エンドユーザによる順位付け、該場所を通過する交通量(例えば、列車の駅を通過する乗客の数)および/またはその他の基準に基づく。
【００３０】
前記場所検索モジュール314は、前記リクエストから解析された場所間のルーティング情報を得るために前記場所データベース316にアクセスする。前記リクエストによっては、指定された場所は、曖昧、明白または不明であるかもしれない。曖昧な場所とは、前記場所検索モジュール314が前記場所データベース316において2つ以上のマッチを見つけるような場所である。例えば、前記ルーティングリクエストが当該場所を“シカゴ”と特定した場合、その場所は、前記リクエストがイリノイ州のシカゴに言及しているのかウイスコンシン州のシカゴに言及しているのか不明確なので曖昧である。他の例において、前記リクエストが当該場所を“えびす駅” と特定した場合、該場所が東京の恵比寿駅に言及しているのか兵庫県の恵比寿駅に言及しているのか不明であるので曖昧である。第3の例においては、前記ルーティングリクエストがタイプミス(例えば、“Chicagp”)を含む場合、その場所は曖昧と言える。前記場所検索モジュール314は、該当場所について1組のマッチ候補を見つけるであろうが、タイプミスのために1つのマッチも見つけられないかもしれない。
【００３１】
一方、明白な場所とは、前記場所検索モジュール314が前記場所データベース316において1つのマッチを見つけるような場所である。また、不明の場所とは、前記場所検索モジュール314が前記場所データベース316においてマッチする場所を1つも見つけられないような場所である。一実施の形態において、前記場所検索モジュール314は、前記ルーティングリクエストを拒絶し、エンドユーザにさらなる情報を与えるよう要求することによって、不明な場所に対処する。
【００３２】
曖昧場所順位付けモジュール320は、前記測定モジュール318によって提供された測定尺度に基づいて、ルーティングリクエストにおける曖昧な場所を順位付けする。ルーティングリクエストが2つの場所を指定するものである実施の形態において、前記曖昧場所順位付けモジュール320は、前記リクエストにおけるマッチしている可能性がある場所(マッチ候補場所)のペアを算出し、測定モジュール318からの測定尺度を使用して前記算出したマッチ候補場所のペアを順位付けする。例えば、ルーティングリクエストが、始点場所をインディアナ州(IN)のセーレム(Salem)と明白に指定し、終点位置を“シカゴ”と曖昧に指定した場合を想定する。前記曖昧場所順位付けモジュール320は、以下のようにマッチ候補場所のペアを算出する。
始点場所 終点位置
インディアナ州セーレム イリノイ州シカゴ
インディアナ州セーレム ウイスコンシン州シカゴ
【００３３】
上記のペアを仮定した場合、前記曖昧場所順位付けモジュール320は、測定モジュール318からの1つまたは複数の測定尺度を使用して前記ペアを順位付けする。例えば、前記測定尺度が距離であり、場所間の距離が以下のようであると仮定する。
始点場所 終点位置 距離
インディアナ州セーレム イリノイ州シカゴ 329マイル
インディアナ州セーレム ウイスコンシン州シカゴ 347.5マイル
距離に基づき、前記曖昧場所順位付けモジュール320は、“インディアナ州セーレム/イリノイ州シカゴ”のペアを1位と、“インディアナ州セーレム/ウイスコンシン州シカゴ”のペアを2位と順位付けする。イリノイ州シカゴはウイスコンシン州シカゴよりはるかに大きな市であるので、人口および人気等のその他の測定尺度に基づく順位付けも、上記と同じ結果を出す可能性が高い。
【００３４】
報告モジュール322は、要求されたルーティング情報を報告する。前記ルーティングリクエストは曖昧な場所を全く含んでいないので、前記報告モジュール322の一実施例は、要求されたルーティング情報のみを与える。例えば、前記ルーティング情報は、運転方向、列車方向および運行スケジュール、等からなっていてよい。前記ルーティングリクエストが少なくとも1つの曖昧な場所を含む場合、前記報告モジュール322の一実施例は、最上位に位置付けされた場所ペアに関するルーティング情報を与え、所望の場合にはエンドユーザが異なる場所ペアを選択できるようにするUI(ユーザインターフェース)を提供する。このようにして、上記のセーレム/シカゴの例においては、前記報告モジュール322は、インディアナ州セーレムからイリノイ州シカゴへのルーティング情報を与え、所望の場合には、エンドユーザがインディアナ州セーレムからウイスコンシン州シカゴへのルーティング情報を選択できるようにするUIを提供する。
【００３５】
図4は、一実施の形態に従うルーティング情報モジュール300および/またはルーティングサーバ112によって実行されるステップを示すフローチャート図である。その他の実施の形態は、図4に示したステップ以外の追加的なステップおよび/または図4に示したステップとは異なるステップを実行する。さらに、その他の実施の形態は、前記ステップを図示したもの以外の順序で実行する。一実施の形態において、前記ルーティング情報モジュール300は、同時に何千または何百ものルーティングステップに対応し、従って同時に多数のステップを実行する。
【００３６】
まず、ステップ410において、前記ルーティング情報モジュール300は、クライアント110またはその他のソースからルーティングリクエストを受け取る。例えば、前記ルーティングサーバ112またはその他のサーバは、前記クライアント110に対して、エンドユーザがルーティングリクエストを作成して前記ルーティングサーバに送ることを可能にするウェブページを提供する。ステップ412において、前記ルーティング情報モジュール300は、前記リクエストを解析して該リクエスト内で指定された場所を抽出する。
【００３７】
ステップ414において、前記ルーティング情報モジュール300は、場所データベース316において前記解析した場所を検索し、マッチ候補場所を見つける。ただ1つのマッチを有する場所は、明白に指定された場所である。2つ以上のマッチを有する場所は、曖昧に指定された場所である。マッチの無い場所は認識不能の場所であるので、前記ルーティング情報モジュール300は、リクエストした人が更なる情報を与えるまで前記ルーティングリクエストの処理を停止する(このステップは図4に示されていない)。
【００３８】
ステップ416において少なくとも1つの曖昧な場所がある場合、前記ルーティング情報モジュール300は、マッチ候補場所のペアを発生する。ステップ418において、前記ルーティング情報モジュール300は、各ペアについての測定尺度を算出する。一実施の形態において、前記測定尺度は、該ペアの場所間の距離である。他の実施の形態において、前記測定尺度は、人口または人気等の1またきは複数の他のファクタに基づく。
【００３９】
ステップ420において、前記ルーティング情報モジュール300は、前記算出された測定尺度に基づくマッチ候補場所ペアを順位付けする。例えば、前記測定尺度が距離である場合、前記ルーティング情報モジュール300は、各ペアにおける場所間の距離に基づく順序で複数の前記ペアを順位付けする。そして、ステップ422において、前記ルーティング情報モジュール300はその結果を報告する。最上位に順位付けされたペア(すなわち、2つの場所間の距離が最小のペア)は、当該エンドユーザが意図したルーティングリクエストとして扱われ、前記ルーティング情報モジュール300は、このペアについてのルーティング情報を報告の一部として提供する。加えて、前記ルーティング情報モジュール300は、他のマッチ候補場所ペア(または少なくとも最上位に順位付けされたペア)をリストし、所望の場合前記エンドユーザが他の場所ペアを選択することを可能にするユーザインターフェースを与える。
【００４０】
前記ルーティング情報モジュール300は、前記リクエストにおいて指定された場所が曖昧な場合であっても、前記エンドユーザが意図するものであると思われる場所についてのルーティング情報を提供する。前記ルーティング情報モジュール300が正しくない場所についてのルーティング情報を提供した場合、前記エンドユーザによって容易に選択可能なよう、正しい場所を含む場所のペアがユーザインターフェースにリストされることが多い。この技術は、前記エンドユーザのルーティングサーバ112とのインタラクションを最少化し、ルーティング情報をリクエストするためにモバイル電話の小型キーボードのような面倒な入力装置を使用する手数を減少させる。
【００４１】
以上本発明の好ましい実施の形態の作用について説明したが、上記説明は本発明の範囲を制限することを意図するものではない。本発明の範囲は、次の請求の範囲によってのみ限定されるものである。上記説明から、本発明の精神および範囲に包含される多くの変更例が当業者に明白であろう。
【符号の説明】
【００４２】
310 リクエスト受け取りモジュール
314 場所検索モジュール
320 曖昧場所順位付けモジュール
322 報告モジュール
【技術分野】
【０００１】
本発明は、コンピュータ化されたマッピングに関し、特に、指定された場所の間での方向またはその他のルーティング(経路設定)情報を提供するシステムに関する。
【背景技術】
【０００２】
運転方向、列車運行スケジュール等のルーティング情報を得るためにインターネット上のウェブサイトを使用することが普通になってきている。ほとんどのウェブサイトでは、方向を求めているエンドユーザは始点場所および終点場所を与え、前記ウェブサイトは、前記2つの場所間でのルーティング情報を返す。該サイトは、地図および推定旅行時間等の追加情報をも返してもよい。
【０００３】
ルーティング情報を算出する際に遭遇する一般的な問題点は、場所の曖昧さである。しばしば、エンドユーザは、2つの場所の一方または両方の部分的な住所のみを与える。しばしば、同じ名前を有する多数の場所が存在するので、部分的な住所は識別するのが困難である。例えば、インディアナ州のセーレム(Salem)とイリノイ州のシカゴとの間の運転方向を求めているエンドユーザは、“セーレム”という始点場所および/または“シカゴ”という終点場所を指定するルーティングリクエストをウェブサイトに与える。米国には“セーレム”という名前の市が少なくとも10個存在し、“シカゴ” という名前の市が少なくとも2個存在する。その結果、前記ウェブサイトでは、前記曖昧な場所を識別するために前記ルーティングリクエストをより細かく述べるようエンドユーザに要求する。
【０００４】
典型的には、前記ウェブサイトは、曖昧な場所に一致(マッチ)する場所のリストをエンドユーザに与え、該エンドユーザにリストされた前記場所の中からいずれかを選択するよう要求する。例えば、前記ウェブサイトは、イリノイ州のシカゴおよびウイスコンシン州のシカゴ中からいずれかを選択するよう要求する。前記エンドユーザと前記ウェブサイトとの間の上記のインタラクションは、面倒で、時間がかかる。このような問題は、前記エンドユーザが低速の通信リンクを介して前記ウェブサイトと通信している場合、および/または、小さな表示スクリーンまたは制限されたユーザインターフェースを有するモバイル装置を使用している場合、特に深刻である。
【発明の概要】
【０００５】
従って、当該技術において、従来より、曖昧な場所を指定するルーティング情報リクエストを識別するためのより効率的な方法が必要とされている。
【０００６】
上記の課題は、ルーティング情報を要求するリクエストであって少なくとも1つの曖昧な場所を指定するリクエストを受け取る、ルーティング情報を提供する方法、システムおよびコンピュータプログラム製品によって達成される。前記ルーティング情報を提供する方法、システムおよびコンピュータプログラム製品は、曖昧な場所にマッチしている可能性がある場所を見つけ出し、任意の測定尺度に基づいて前記マッチしている可能性がある場所を順位付けし、前記マッチしている可能性がある場所のうちの最上位に順位付けされた場所についてルーティング情報を提供する。
【図面の簡単な説明】
【０００７】
【図１】本発明の一実施の形態に従うコンピューティング環境を示す高レベルブロック図。
【０００８】
【図２】本発明の一実施の形態に従う、図1の環境に示されたもののようなクライアントまたはサーバに使用される典型的なコンピュータの機能を示す高レベルブロック図。
【０００９】
【図３】本発明の一実施の形態に従うルーティング情報モジュール内のモジュールを示す高レベルブロック図。
【００１０】
【図４】一実施の形態に従うルーティング情報モジュールおよび/またはルーティングサーバによって実行されるステップを示すフローチャート図。
【００１１】
図は、本発明の一実施の形態を例示目的でのみ示すものである。下記の説明から、ここで説明される構造および方法の他の実施の形態が本発明の原理から逸脱することなく用いられてよい、ことが当業者に理解されよう。
【発明を実施するための形態】
【００１２】
図1は、本発明の一実施の形態に従うコンピューティング環境100を示す高レベルブロック図である。図1は、ネットワーク114によって接続された3つのクライアント110とルーティングサーバ112とを示している。図1およびその他の図においては、同様な参照数字を使用して同様な要素を示している。“110A”のような参照数字の後の文字は、該特定の参照数字を有する要素に言及していることを示す。“110”のような後続する文字のない参照数字は、図における該参照数字を有する要素のいずれかまたはすべてに言及している(例えば、110”は、図における“110A”、“110B”および/または“110C”に言及している)。図1はクライアント110を3つだけ示しているが、本発明の実施の形態は、前記サーバ112とインタラクトする何千または何百万ものクライアントを有するものであってもよい。しかし、本発明を簡略化し明確化するためにクライアント110を3つだけ示している。同様な理由で、ネットワーク114に接続されてよいその他のサーバは図1に示されていない。
【００１３】
前記クライアント110は、ルーティングリクエストを与え、その返答としてのルーティング情報を得るため、ネットワーク114を介してサーバ112とインタラクトするためにエンドユーザによって使用される装置を示す。一実施の形態において、前記クライアント110は、標準的なネットワーク関連機能を有するコンピュータである。ある実施の形態において、前記クライアント110は、ノート型コンピュータ、モバイル電話、パーソナル・ディジタル・アシスタント(PDA)、携帯eメール装置、携帯ゲーム装置、自動ナビゲーションシステム、または同等機能を有するその他の種類の装置である。前記クライアント110は、コンピュータおよび/またはモバイル通信プロトコルを使用する有線および/または無線のネットワークを含む標準的なネットワーク関連技術を使用して、サーバ112と通信する。
【００１４】
前記クライアント110は、前記サーバ112に対してルーティングリクエストを出すための機能と、受け取ったルーティング情報をエンドユーザに与えるための機能とを有する。実施の形態によっては、前記クライアント110は、リクエストを入力するためのキーボードと、ルーティング情報を見るための表示器とを有する。多くのモバイル電話およびその他のモバイル装置は、使用するのが難しい小さなキーボードを有する。他の実施の形態においては、前記クライアント110は、タッチスクリーンに基づく入力装置および/またはオーディオ出力装置のような、これらのタスクを実行するための付加的および/またはこれらと異なる機能を含む。
【００１５】
一実施の形態において、前記クライアント110は、標準的なインターネット通信技術を使用して前記サーバ112とメッセージを交換することを可能にするウェブブラウジング機能を含む。例えば、前記クライアント110は、MICROSOFT INTERNET EXPLORER (登録商標)等のウェブブラウザ、OPERA MOBILE(商標)およびOPERA MINI(商標)等のモバイル用に最適化されたブラウザ、および/または、エンドユーザがウェブサーバおよび/または他のネットワーク114上のコンピュータシステムからコンテンツを取り出して、表示することを可能にするブラウザを実行することができる。
【００１６】
前記ルーティングサーバ112は、クライアント110からルーティングリクエストを受け取り、ルーティング情報を返す。一実施の形態において、前記ルーティングサーバ112は、クライアント110にウェブページを提供し、クライアントから与えられたデータを受け取るために使用されるウェブサーバとして機能するコンピュータを含む。前記ルーティングサーバ112は、ルーティングリクエストを受け取り、ルーティング情報を発生するためのルーティング情報モジュール300を含む。
【００１７】
しばしば、前記クライアント110から受け取られるルーティングリクエストは始点場所および終点場所を含み、前記ルーティングサーバ112は、前記始点場所から終点場所にまで行く方法を説明するルーティング情報を発生する。前記ルーティング情報は、例えば、運転方向および地図、列車の運行スケジュールおよび方向、飛行機の飛行スケジュール等を含むことができる。ここでの説明ではしばしば2つの場所を有するルーティングリクエストに言及しているが、前記ルーティングサーバ112は、どのような数の場所を有するリクエストにも対応可能である。例えば、前記ルーティングサーバ112は、1つの場所を通過するバス、列車および/または飛行機の飛行スケジュールを記述する該1つの場所に関するルーティング情報を提供することができる。
【００１８】
一実施の形態において、前記ルーティングサーバ112は、一致(マッチ)する可能性がある場所のペア(対)の間の距離を算出し、最も近い場所のペア(すなわち、距離が最も小さい場所のペア)に関するルーティング情報を返すことによって、曖昧な場所(例えば、地名が“セーレム”および“シカゴ”)に対応する。このようにして、“セーレム”と“シカゴ”との間の運転方向に関するリクエストを受け取る前記ルーティングサーバ112の一実施の形態は、インディアナ州のセーレムとイリノイ州のシカゴの間の運転方向を自動的に提供する。というのは、これらの場所が同じ名前を有する他のすべてのペアの市より近距離であるからである。さらに、前記ルーティングサーバ112は、該ルーティングサーバ112によって選択されたペアが前記エンドユーザが意図するものではない場合、該エンドユーザが異なる場所のペアを指定するのを可能にするユーザインターフェース(UI)を提供する。
【００１９】
前記ネットワーク114は、前記クライアントと前記ルーティングサーバ112のとの間の通信経路を示すものである。一実施の形態において、前記ネットワーク114はインターネットである。該ネットワーク114は、必ずしもインターネットの一部ではない専用または私用の通信リンクを使用することもできる。一実施の形態において、前記ネットワーク114は、標準的な通信技術および/またはプロトコルを使用する。従って、前記ネットワーク114は、Ethernet 802.11、総合デジタル通信網(ISDN)、ディジタル加入者線(DSL)、非同期転送モード(ATM)等の技術を使用するリンク、ならびに、モバイル電話通信技術を使用するリンクを含むことができる。同様に、前記ネットワーク114上で使用されるネットワークプロトコルは、マルチプロトコルラベルスイッチング(MPLS)、transmission control protocol/Internet protocol(TCP/IP)、hypertext transport protocol (HTTP)、simple mail transfer protocol(SMTP)、file transfer protocol(FTP)、short message service(SMS) プロトコル等を含むことができる。前記ネットワーク114を介して授受されるデータは、hyper text markup language(HTTP)、extensible markup language(XML)、extensible hypertext markup language(XHTML)、compact HTML(cHTML)等を含む技術および/またはフォーマットを使用して表される。さらに、リンクのすべてまたは一部は、secure sockets layer(SSL)、HTTP over SSL(HTTPS)および/または仮想プライベートネットワーク(VPNs: virtual private networks)等の従来の暗号化技術を使用して暗号化可能である。他の実施の形態において、前記クライアント110およびルーティングサーバ112は、上記のものの代わりにまたはその追加として、カスタムメイドおよび/または専用のデータ通信技術を使用する。
II. システムアーキテクチャ
【００２０】
図2は、本発明の一実施の形態に従う図1の環境100に示されたもののようなクライアント110またはサーバ112に使用される典型的なコンピュータ200の機能を示す高レベルブロック図である。図2には、バス204に接続された少なくとも1つのプロセッサ202が示されている。また、バス204には、メモリ206と、記憶装置208と、キーボード210と、グラフィックスアダプタ212と、ポインティングデバイス214と、ネットワークアダプタ216とがさらに接続されている。表示器218は、前記グラフィックスアダプタ212に接続されている。
【００２１】
前記プロセッサ202は、INTELx86系CPUのような任意の汎用プロセッサであってよい。前記記憶装置208は、一実施の形態において、ハードディスクであるが、書き込み可能なコンパクトディスク(CD)もしくはDVD、またはソリッドステートメモリデバイスのような、データを記憶することが可能な任意の装置であってよい。前記メモリ206は、例えば、ファームウエアの読み取り専用メモリ(ROM)、非揮発性ランダムアクセスメモリ(NVRAM)および/またはRAMであってよく、プロセッサ202によって使用される命令およびデータを保持する。前記ポインティングデバイス214は、マウス、トラックボールまたはその他の種類のポインティングデバイスであってよく、データをコンピュータシステム200に入力するために、前記キーボード210と共に使用される。前記グラフィックスアダプタ212は、表示器218に画像およびその他の情報を表示する。
【００２２】
当該技術分野において公知のように、前記コンピュータ200は、コンピュータプログラムモジュールを実行するよう構成されている。ここで、“モジュール”という用語は、指定された機能を実現するためのコンピュータプログラム論理および/またはデータを意味する。モジュールは、ハードウエア、ファームウエアおよび/またはソフトウエアの形態で実現され得る。一実施の形態において、前記モジュールは、前記記憶装置208に記憶され、前記メモリ206にロードされ、前記プロセッサ202によって実行される。
【００２３】
図1の構成要素によって使用されるコンピュータ200の種類は、実施の形態および前記構成要素によって使用される処理能力に応じて可変である。例えば、前記クライアント110は、典型的には、前記ルーティングサーバ112より低い処理能力を必要とする。従って、前記クライアント110は、標準的なパーソナルコンピュータまたは携帯電子デバイスであってよい。対照的に、前記ルーティングサーバ112は、高能力のコンピュータおよび/またはここに説明する機能を実現するために共働するより多数のコンピュータからなっていてよい。同様に、前記コンピュータ200は、上記の構成要素のうちのいくつかを欠いていてよい。例えば、クライアント110として機能するモバイル電話はポインティングデバイスを欠いていてよく、前記ルーティングサーバ112として機能するコンピュータはキーボードおよび表示器を欠いていてよい。
【００２４】
図3は、本発明の一実施の形態に従うルーティング情報モジュール300内のモジュールを示す高レベルブロック図である。他の実施の形態は、図3に示したものとは異なるおよび/またはこれらの追加としてのモジュールを有する。さらに、他の実施の形態では、異なる態様で、前記モジュール間で機能が分散される。
【００２５】
リクエスト受領モジュール310は、前記クライアント110および/またはその他のソースからルーティング情報を受け取る。一実施の形態において、ルーティングリクエストは、その間でのルーティング情報が要求される2つ以上の場所を指定する。さらに、前記ルーティングリクエストは、要求されるルーティング情報の種類(例えば、運転方向または列車の運行スケジュール)、ルーティング情報が要求される日時、当該ルートに高速道路、急行列車または飛行機を使用するのか等を記述するパラメータ等のデータを含んでいてよい。
【００２６】
リクエスト解析モジュール312は、ルーティングリクエストを解析し、指定された場所を抽出する。場所は、典型的には、名前および/または住所によって指定されるが、地理的座標のような他の手段よって指定されてもよい。一実施の形態において、前記場所は、前記ルーティングリクエストによって明確に特定される。例えば、前記ルーティングサーバ112がクライアント110に提供するウェブページは、始点場所および目的場所の情報を名前、ストリート名、市、州/行政区(province)/県(prefecture)、および郵便コードに分離する。他の実施の形態において、前記場所のうちの一部またはすべてが暗黙的に特定される。例えば、前記ルーティングリクエストは、“東京と鎌倉との間の運転方向”のような自由形式文字列に含ませてよい。前記自由形式のリクエストを受け取ると、リクエスト解析モジュール312は、通常の表現および/またはその他の技術を使用して前記リクエストを解析し、そこで言及された場所に関する情報を抽出する。
【００２７】
解析される場所は、不明確および/または不完全な情報を使用して指定されることがある。エンドユーザが前記リクエストに前記情報を含めなかったため、および/または、解析上の困難のために、もちろんこのような情報欠如は発生し得る。例えば、前記ルーティングリクエストは、ストリートの住所および市の名前を使用して場所を指定できるが、前記市が存在する州または県の名前が含まれていない。同様に、前記リクエストは、駅の名前(例えば、“えびす駅”)を使用して場所を指定できるが、該駅が存在する市の名前が含まれていない。
【００２８】
場所検索モジュール314は、場所データベース316において、前記ルーティングリクエストから抽出された場所を検索する。一実施の形態において、前記場所データベース316は、複数のルーティングリクエストによって指定される可能性がある複数の場所を記述した情報を含むものである。さらに、前記場所データベース316は、1つまたは複数の国のストリートマップを記述したデータを含んでいてよい。例えば、前記場所データベース316は、列車、飛行機、バス、フェリーおよびその他の交通路線を記述したデータを含んでいてよい。さらに、前記場所データベース316の一実施例は、リアルタイムのまたは過去のストリート交通情報、交通スケジュール、料金表等の関連情報を含む。一実施の形態において、分離した複数のデータベースの1つまたは複数が前記ルーティングサーバ112の外部に設けられていてもよい。
【００２９】
一実施の形態において、前記場所データベース316は、該データベースにおける複数の場所の順位付けおよび/または比較を可能にするデータを有するメトリクス(測定)モジュール318を含む。一実施の形態において、測定尺度は距離であり、前記測定モジュール318は、前記データベースにおける複数の場所の地理的位置を記述するデータを有する。さらに、前記メトリクスモジュール318(または、その他のモジュール)は、2つ以上の指定された場所間の距離を算出する。一実施の形態において、前記測定モジュール318は、前記データベースにおける複数の場所を緯度/経度座標に変換し、該緯度/経度座標間の距離を算出する。他の実施の形態において、測定尺度は人口および/または表面積であり、前記測定モジュール318は、前記データベースにおいて特定された様々な場所の人口および表面積および/または地域(例えば市)を記述するデータを有する。さらに他の実施の形態において、測定尺度は人気であり、前記測定モジュール318は、前記データベースにおける様々な場所の人気を記述するデータを有する。該人気は、これらの場所がルーティングリクエストに現われる頻度、エンドユーザによる順位付け、該場所を通過する交通量(例えば、列車の駅を通過する乗客の数)および/またはその他の基準に基づく。
【００３０】
前記場所検索モジュール314は、前記リクエストから解析された場所間のルーティング情報を得るために前記場所データベース316にアクセスする。前記リクエストによっては、指定された場所は、曖昧、明白または不明であるかもしれない。曖昧な場所とは、前記場所検索モジュール314が前記場所データベース316において2つ以上のマッチを見つけるような場所である。例えば、前記ルーティングリクエストが当該場所を“シカゴ”と特定した場合、その場所は、前記リクエストがイリノイ州のシカゴに言及しているのかウイスコンシン州のシカゴに言及しているのか不明確なので曖昧である。他の例において、前記リクエストが当該場所を“えびす駅” と特定した場合、該場所が東京の恵比寿駅に言及しているのか兵庫県の恵比寿駅に言及しているのか不明であるので曖昧である。第3の例においては、前記ルーティングリクエストがタイプミス(例えば、“Chicagp”)を含む場合、その場所は曖昧と言える。前記場所検索モジュール314は、該当場所について1組のマッチ候補を見つけるであろうが、タイプミスのために1つのマッチも見つけられないかもしれない。
【００３１】
一方、明白な場所とは、前記場所検索モジュール314が前記場所データベース316において1つのマッチを見つけるような場所である。また、不明の場所とは、前記場所検索モジュール314が前記場所データベース316においてマッチする場所を1つも見つけられないような場所である。一実施の形態において、前記場所検索モジュール314は、前記ルーティングリクエストを拒絶し、エンドユーザにさらなる情報を与えるよう要求することによって、不明な場所に対処する。
【００３２】
曖昧場所順位付けモジュール320は、前記測定モジュール318によって提供された測定尺度に基づいて、ルーティングリクエストにおける曖昧な場所を順位付けする。ルーティングリクエストが2つの場所を指定するものである実施の形態において、前記曖昧場所順位付けモジュール320は、前記リクエストにおけるマッチしている可能性がある場所(マッチ候補場所)のペアを算出し、測定モジュール318からの測定尺度を使用して前記算出したマッチ候補場所のペアを順位付けする。例えば、ルーティングリクエストが、始点場所をインディアナ州(IN)のセーレム(Salem)と明白に指定し、終点位置を“シカゴ”と曖昧に指定した場合を想定する。前記曖昧場所順位付けモジュール320は、以下のようにマッチ候補場所のペアを算出する。
始点場所 終点位置
インディアナ州セーレム イリノイ州シカゴ
インディアナ州セーレム ウイスコンシン州シカゴ
【００３３】
上記のペアを仮定した場合、前記曖昧場所順位付けモジュール320は、測定モジュール318からの1つまたは複数の測定尺度を使用して前記ペアを順位付けする。例えば、前記測定尺度が距離であり、場所間の距離が以下のようであると仮定する。
始点場所 終点位置 距離
インディアナ州セーレム イリノイ州シカゴ 329マイル
インディアナ州セーレム ウイスコンシン州シカゴ 347.5マイル
距離に基づき、前記曖昧場所順位付けモジュール320は、“インディアナ州セーレム/イリノイ州シカゴ”のペアを1位と、“インディアナ州セーレム/ウイスコンシン州シカゴ”のペアを2位と順位付けする。イリノイ州シカゴはウイスコンシン州シカゴよりはるかに大きな市であるので、人口および人気等のその他の測定尺度に基づく順位付けも、上記と同じ結果を出す可能性が高い。
【００３４】
報告モジュール322は、要求されたルーティング情報を報告する。前記ルーティングリクエストは曖昧な場所を全く含んでいないので、前記報告モジュール322の一実施例は、要求されたルーティング情報のみを与える。例えば、前記ルーティング情報は、運転方向、列車方向および運行スケジュール、等からなっていてよい。前記ルーティングリクエストが少なくとも1つの曖昧な場所を含む場合、前記報告モジュール322の一実施例は、最上位に位置付けされた場所ペアに関するルーティング情報を与え、所望の場合にはエンドユーザが異なる場所ペアを選択できるようにするUI(ユーザインターフェース)を提供する。このようにして、上記のセーレム/シカゴの例においては、前記報告モジュール322は、インディアナ州セーレムからイリノイ州シカゴへのルーティング情報を与え、所望の場合には、エンドユーザがインディアナ州セーレムからウイスコンシン州シカゴへのルーティング情報を選択できるようにするUIを提供する。
【００３５】
図4は、一実施の形態に従うルーティング情報モジュール300および/またはルーティングサーバ112によって実行されるステップを示すフローチャート図である。その他の実施の形態は、図4に示したステップ以外の追加的なステップおよび/または図4に示したステップとは異なるステップを実行する。さらに、その他の実施の形態は、前記ステップを図示したもの以外の順序で実行する。一実施の形態において、前記ルーティング情報モジュール300は、同時に何千または何百ものルーティングステップに対応し、従って同時に多数のステップを実行する。
【００３６】
まず、ステップ410において、前記ルーティング情報モジュール300は、クライアント110またはその他のソースからルーティングリクエストを受け取る。例えば、前記ルーティングサーバ112またはその他のサーバは、前記クライアント110に対して、エンドユーザがルーティングリクエストを作成して前記ルーティングサーバに送ることを可能にするウェブページを提供する。ステップ412において、前記ルーティング情報モジュール300は、前記リクエストを解析して該リクエスト内で指定された場所を抽出する。
【００３７】
ステップ414において、前記ルーティング情報モジュール300は、場所データベース316において前記解析した場所を検索し、マッチ候補場所を見つける。ただ1つのマッチを有する場所は、明白に指定された場所である。2つ以上のマッチを有する場所は、曖昧に指定された場所である。マッチの無い場所は認識不能の場所であるので、前記ルーティング情報モジュール300は、リクエストした人が更なる情報を与えるまで前記ルーティングリクエストの処理を停止する(このステップは図4に示されていない)。
【００３８】
ステップ416において少なくとも1つの曖昧な場所がある場合、前記ルーティング情報モジュール300は、マッチ候補場所のペアを発生する。ステップ418において、前記ルーティング情報モジュール300は、各ペアについての測定尺度を算出する。一実施の形態において、前記測定尺度は、該ペアの場所間の距離である。他の実施の形態において、前記測定尺度は、人口または人気等の1またきは複数の他のファクタに基づく。
【００３９】
ステップ420において、前記ルーティング情報モジュール300は、前記算出された測定尺度に基づくマッチ候補場所ペアを順位付けする。例えば、前記測定尺度が距離である場合、前記ルーティング情報モジュール300は、各ペアにおける場所間の距離に基づく順序で複数の前記ペアを順位付けする。そして、ステップ422において、前記ルーティング情報モジュール300はその結果を報告する。最上位に順位付けされたペア(すなわち、2つの場所間の距離が最小のペア)は、当該エンドユーザが意図したルーティングリクエストとして扱われ、前記ルーティング情報モジュール300は、このペアについてのルーティング情報を報告の一部として提供する。加えて、前記ルーティング情報モジュール300は、他のマッチ候補場所ペア(または少なくとも最上位に順位付けされたペア)をリストし、所望の場合前記エンドユーザが他の場所ペアを選択することを可能にするユーザインターフェースを与える。
【００４０】
前記ルーティング情報モジュール300は、前記リクエストにおいて指定された場所が曖昧な場合であっても、前記エンドユーザが意図するものであると思われる場所についてのルーティング情報を提供する。前記ルーティング情報モジュール300が正しくない場所についてのルーティング情報を提供した場合、前記エンドユーザによって容易に選択可能なよう、正しい場所を含む場所のペアがユーザインターフェースにリストされることが多い。この技術は、前記エンドユーザのルーティングサーバ112とのインタラクションを最少化し、ルーティング情報をリクエストするためにモバイル電話の小型キーボードのような面倒な入力装置を使用する手数を減少させる。
【００４１】
以上本発明の好ましい実施の形態の作用について説明したが、上記説明は本発明の範囲を制限することを意図するものではない。本発明の範囲は、次の請求の範囲によってのみ限定されるものである。上記説明から、本発明の精神および範囲に包含される多くの変更例が当業者に明白であろう。
【符号の説明】
【００４２】
310 リクエスト受け取りモジュール
314 場所検索モジュール
320 曖昧場所順位付けモジュール
322 報告モジュール
【特許請求の範囲】
【請求項１】
コンピュータによって実現される、ルーティング情報を提供する方法であって、
ルーティング情報を要求するリクエストであって少なくとも1つの曖昧な場所を指定するリクエストを受け取るステップと、
前記曖昧な場所にマッチしている可能性がある場所を見つけ出すステップと、
任意の測定尺度に基づいて前記マッチしている可能性がある場所を順位付けするステップと、
前記マッチしている可能性がある場所のうち最上位に順位付けされた場所についてのルーティング情報を提供するステップと、
を具備する方法。
【請求項２】
前記測定尺度が距離であり、前記順位付けするステップが、
前記曖昧な場所にマッチしている可能性がある各場所とその他の場所との間の距離を算出するステップと、
前記マッチしている可能性がある場所とその他の場所との間の距離に基づいて、前記マッチしている可能性がある場所を順位付けするステップと、
からなる請求項1に記載の方法。
【請求項３】
前記マッチしている可能性がある場所のうち最上位に順位付けされた場所が、前記その他の場所に最も近い距離を有するものである請求項2に記載の方法。
【請求項４】
前記測定尺度が、前記マッチしている可能性がある場所の人口である請求項1に記載の方法。
【請求項５】
前記測定尺度が、前記マッチしている可能性がある場所がルーティングリクエストに現れる頻度である請求項1に記載の方法。
【請求項６】
前記順位付けするステップが、
前記リクエストにおいて指定されている場所に基づいて、各々が前記曖昧な場所にマッチしている可能性がある少なくとも1つの場所を含む複数ペアの場所を発生するステップと、
前記複数ペアにおける場所の間の距離を算出するステップと、
算出された前記距離に基づいて前記複数ペアを順位付けするステップと、
からなる請求項1に記載の方法。
【請求項７】
前記ルーティング情報が、運転方向、列車の運行スケジュール、バスの運行スケジュールおよび飛行スケジュールからなる情報組のうちの1つまたは複数の種類の情報からなる請求項1に記載の方法。
【請求項８】
ルーティング情報を提供するシステムであって、
ルーティング情報を要求するリクエストであって少なくとも1つの曖昧な場所を指定するリクエストを受け取るリクエスト受け取りモジュールと、
前記曖昧な場所にマッチしている可能性がある場所を見つけ出す場所検索モジュールと、
任意の測定尺度に基づいて前記マッチしている可能性がある場所を順位付けする曖昧場所順位付けモジュールと、
前記マッチしている可能性がある場所のうち最上位に順位付けされた場所についてのルーティング情報を提供する報告モジュールと、
を具備するシステム。
【請求項９】
前記測定尺度が距離であり、前記曖昧場所順位付けモジュールが、さらに、
前記曖昧な場所にマッチしている可能性がある各場所とその他の場所との間の距離を算出し、
前記マッチしている可能性がある場所とその他の場所との間の距離に基づいて、前記マッチしている可能性がある場所を順位付けする、
よう構成されていることを特徴とする請求項8に記載のシステム。
【請求項１０】
前記マッチしている可能性がある場所のうち最上位に順位付けされた場所が、前記その他の場所に最も近い距離を有するものである請求項9に記載のシステム。
【請求項１１】
前記測定尺度が、前記マッチしている可能性がある場所の人口である請求項8に記載のシステム。
【請求項１２】
前記測定尺度が、前記マッチしている可能性がある場所がルーティングリクエストに現れる頻度である請求項8に記載のシステム。
【請求項１３】
前記曖昧場所順位付けモジュールが、さらに、
前記リクエストにおいて指定されている場所に基づいて、各々が前記曖昧な場所にマッチしている可能性がある少なくとも1つの場所を含む複数ペアの場所を発生し、
前記複数ペアにおける場所の間の距離を算出し、
算出された前記距離に基づいて前記複数ペアを順位付けする、
よう構成されていることを特徴とする請求項8に記載のシステム。
【請求項１４】
前記ルーティング情報が、運転方向、列車の運行スケジュール、バスの運行スケジュールおよび飛行スケジュールからなる情報組のうちの1つまたは複数の種類の情報からなる請求項8に記載のシステム。
【請求項１５】
ルーティング情報を提供するためのコンピュータプログラムコードを格納したコンピュータによって読み取り可能なコンピュータプログラム製品であって、
ルーティング情報を要求するリクエストであって少なくとも1つの曖昧な場所を指定するリクエストを受け取るリクエスト受け取りモジュールと、
前記曖昧な場所にマッチしている可能性がある場所を見つけ出す場所検索モジュールと、
任意の測定尺度に基づいて前記マッチしている可能性がある場所を順位付けする曖昧場所順位付けモジュールと、
前記マッチしている可能性がある場所のうち最上位に順位付けされた場所についてのルーティング情報を提供する報告モジュールと、
を具備するコンピュータプログラム製品。
【請求項１６】
前記測定尺度が距離であり、前記曖昧場所順位付けモジュールが、さらに、
前記曖昧な場所にマッチしている可能性がある各場所とその他の場所との間の距離を算出し、
前記マッチしている可能性がある場所とその他の場所との間の距離に基づいて、前記マッチしている可能性がある場所を順位付けする、
よう構成されていることを特徴とする請求項15に記載の製品。
【請求項１７】
前記マッチしている可能性がある場所のうち最上位に順位付けされた場所が、前記その他の場所に最も近い距離を有するものである請求項16に記載の製品。
【請求項１８】
前記測定尺度が、前記マッチしている可能性がある場所の人口である請求項15に記載の製品。
【請求項１９】
前記測定尺度が、前記マッチしている可能性がある場所がルーティングリクエストに現れる頻度である請求項15に記載の製品。
【請求項２０】
前記曖昧場所順位付けモジュールが、さらに、
前記リクエストにおいて指定されている場所に基づいて、各々が前記曖昧な場所にマッチしている可能性がある少なくとも1つの場所を含む複数ペアの場所を発生し、
前記複数ペアにおける場所の間の距離を算出し、
算出された前記距離に基づいて前記複数ペアを順位付けする、
よう構成されていることを特徴とする請求項15に記載の製品。
【請求項２１】
前記ルーティング情報が、運転方向、列車の運行スケジュール、バスの運行スケジュールおよび飛行スケジュールからなる情報組のうちの1つまたは複数の種類の情報からなる請求項15に記載の製品。
【請求項１】
コンピュータによって実現される、ルーティング情報を提供する方法であって、
ルーティング情報を要求するリクエストであって少なくとも1つの曖昧な場所を指定するリクエストを受け取るステップと、
前記曖昧な場所にマッチしている可能性がある場所を見つけ出すステップと、
任意の測定尺度に基づいて前記マッチしている可能性がある場所を順位付けするステップと、
前記マッチしている可能性がある場所のうち最上位に順位付けされた場所についてのルーティング情報を提供するステップと、
を具備する方法。
【請求項２】
前記測定尺度が距離であり、前記順位付けするステップが、
前記曖昧な場所にマッチしている可能性がある各場所とその他の場所との間の距離を算出するステップと、
前記マッチしている可能性がある場所とその他の場所との間の距離に基づいて、前記マッチしている可能性がある場所を順位付けするステップと、
からなる請求項1に記載の方法。
【請求項３】
前記マッチしている可能性がある場所のうち最上位に順位付けされた場所が、前記その他の場所に最も近い距離を有するものである請求項2に記載の方法。
【請求項４】
前記測定尺度が、前記マッチしている可能性がある場所の人口である請求項1に記載の方法。
【請求項５】
前記測定尺度が、前記マッチしている可能性がある場所がルーティングリクエストに現れる頻度である請求項1に記載の方法。
【請求項６】
前記順位付けするステップが、
前記リクエストにおいて指定されている場所に基づいて、各々が前記曖昧な場所にマッチしている可能性がある少なくとも1つの場所を含む複数ペアの場所を発生するステップと、
前記複数ペアにおける場所の間の距離を算出するステップと、
算出された前記距離に基づいて前記複数ペアを順位付けするステップと、
からなる請求項1に記載の方法。
【請求項７】
前記ルーティング情報が、運転方向、列車の運行スケジュール、バスの運行スケジュールおよび飛行スケジュールからなる情報組のうちの1つまたは複数の種類の情報からなる請求項1に記載の方法。
【請求項８】
ルーティング情報を提供するシステムであって、
ルーティング情報を要求するリクエストであって少なくとも1つの曖昧な場所を指定するリクエストを受け取るリクエスト受け取りモジュールと、
前記曖昧な場所にマッチしている可能性がある場所を見つけ出す場所検索モジュールと、
任意の測定尺度に基づいて前記マッチしている可能性がある場所を順位付けする曖昧場所順位付けモジュールと、
前記マッチしている可能性がある場所のうち最上位に順位付けされた場所についてのルーティング情報を提供する報告モジュールと、
を具備するシステム。
【請求項９】
前記測定尺度が距離であり、前記曖昧場所順位付けモジュールが、さらに、
前記曖昧な場所にマッチしている可能性がある各場所とその他の場所との間の距離を算出し、
前記マッチしている可能性がある場所とその他の場所との間の距離に基づいて、前記マッチしている可能性がある場所を順位付けする、
よう構成されていることを特徴とする請求項8に記載のシステム。
【請求項１０】
前記マッチしている可能性がある場所のうち最上位に順位付けされた場所が、前記その他の場所に最も近い距離を有するものである請求項9に記載のシステム。
【請求項１１】
前記測定尺度が、前記マッチしている可能性がある場所の人口である請求項8に記載のシステム。
【請求項１２】
前記測定尺度が、前記マッチしている可能性がある場所がルーティングリクエストに現れる頻度である請求項8に記載のシステム。
【請求項１３】
前記曖昧場所順位付けモジュールが、さらに、
前記リクエストにおいて指定されている場所に基づいて、各々が前記曖昧な場所にマッチしている可能性がある少なくとも1つの場所を含む複数ペアの場所を発生し、
前記複数ペアにおける場所の間の距離を算出し、
算出された前記距離に基づいて前記複数ペアを順位付けする、
よう構成されていることを特徴とする請求項8に記載のシステム。
【請求項１４】
前記ルーティング情報が、運転方向、列車の運行スケジュール、バスの運行スケジュールおよび飛行スケジュールからなる情報組のうちの1つまたは複数の種類の情報からなる請求項8に記載のシステム。
【請求項１５】
ルーティング情報を提供するためのコンピュータプログラムコードを格納したコンピュータによって読み取り可能なコンピュータプログラム製品であって、
ルーティング情報を要求するリクエストであって少なくとも1つの曖昧な場所を指定するリクエストを受け取るリクエスト受け取りモジュールと、
前記曖昧な場所にマッチしている可能性がある場所を見つけ出す場所検索モジュールと、
任意の測定尺度に基づいて前記マッチしている可能性がある場所を順位付けする曖昧場所順位付けモジュールと、
前記マッチしている可能性がある場所のうち最上位に順位付けされた場所についてのルーティング情報を提供する報告モジュールと、
を具備するコンピュータプログラム製品。
【請求項１６】
前記測定尺度が距離であり、前記曖昧場所順位付けモジュールが、さらに、
前記曖昧な場所にマッチしている可能性がある各場所とその他の場所との間の距離を算出し、
前記マッチしている可能性がある場所とその他の場所との間の距離に基づいて、前記マッチしている可能性がある場所を順位付けする、
よう構成されていることを特徴とする請求項15に記載の製品。
【請求項１７】
前記マッチしている可能性がある場所のうち最上位に順位付けされた場所が、前記その他の場所に最も近い距離を有するものである請求項16に記載の製品。
【請求項１８】
前記測定尺度が、前記マッチしている可能性がある場所の人口である請求項15に記載の製品。
【請求項１９】
前記測定尺度が、前記マッチしている可能性がある場所がルーティングリクエストに現れる頻度である請求項15に記載の製品。
【請求項２０】
前記曖昧場所順位付けモジュールが、さらに、
前記リクエストにおいて指定されている場所に基づいて、各々が前記曖昧な場所にマッチしている可能性がある少なくとも1つの場所を含む複数ペアの場所を発生し、
前記複数ペアにおける場所の間の距離を算出し、
算出された前記距離に基づいて前記複数ペアを順位付けする、
よう構成されていることを特徴とする請求項15に記載の製品。
【請求項２１】
前記ルーティング情報が、運転方向、列車の運行スケジュール、バスの運行スケジュールおよび飛行スケジュールからなる情報組のうちの1つまたは複数の種類の情報からなる請求項15に記載の製品。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公表番号】特表２０１０−５０３０５１（Ｐ２０１０−５０３０５１Ａ）
【公表日】平成２２年１月２８日（２０１０．１．２８）
【国際特許分類】
【出願番号】特願２００９−５２４８１７（Ｐ２００９−５２４８１７）
【出願日】平成１９年８月１７日（２００７．８．１７）
【国際出願番号】ＰＣＴ／ＵＳ２００７／０７６２０６
【国際公開番号】ＷＯ２００８／０２２３１１
【国際公開日】平成２０年２月２１日（２００８．２．２１）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＥＴＨＥＲＮＥＴ
【出願人】（５０５２８１０６７）グーグル インク． (58)
【氏名又は名称原語表記】ＧＯＯＧＬＥ ＩＮＣ．
【Ｆターム（参考）】
【公表日】平成２２年１月２８日（２０１０．１．２８）
【国際特許分類】
【出願日】平成１９年８月１７日（２００７．８．１７）
【国際出願番号】ＰＣＴ／ＵＳ２００７／０７６２０６
【国際公開番号】ＷＯ２００８／０２２３１１
【国際公開日】平成２０年２月２１日（２００８．２．２１）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＥＴＨＥＲＮＥＴ
【出願人】（５０５２８１０６７）グーグル インク． (58)
【氏名又は名称原語表記】ＧＯＯＧＬＥ ＩＮＣ．
【Ｆターム（参考）】
[ Back to top ]