(57)【要約】サイトの検索又は比較に関連する形態。一つの形態は通勤期間に基づいて不動産の検索又は比較方法である。本方法は効果的に前記不動産資産及び乗り物駅の間の行程期間の計算のため、公共交通及び不動産資産データを所有する。これらの期間は蓄積される。リクエストフレームワークは、広範な検索又は比較リクエストを表現することを許容するよう導入される。リクエスト処理プロセスの間、本方法は全ての不動産資産に依存する通勤パスのパートを特定する。なぜならこれらのパートにとっての期間は予め計算し蓄積されるため、本方法は拡張可能なマナーで全ての不動産資産への通勤期間を決定する。結果として、本方法は今日存在する最も大きな大都会エリアの一つの不動産資産内での要求に素早く応答する。他の形態は、料金コスト、プライベートカーを使用する移動、及び不動産資産よりほかのサイトに基づいて検索又は比較することを含む。コンピュータシステム及びコンピュータサービスがまた本方法を具現化する。【選択図】図８
2021509985.tif 000002
【特許請求の範囲】
【請求項１】
輸送システム内の少なくとも1つのサイトと少なくとも1つの場所との間の少なくとも1つのルートまたはルートの長さを使用して少なくとも1つのサイトを検索または比較する方法であって、当該方法は以下を含む：
（ａ）各サイトが輸送システムに含まれる複数のサイトを受け取ること、複数のサイトは、少なくとも１つのサイトを含む;
（b）少なくとも1人の代表者を受け取り、各代表者は輸送システムに含まれている;
（c）少なくとも1つの事前計算されたルートまたはルート長をデータベースに格納し、各第1の事前計算されたルートまたはルート長は、複数のサイトに含まれるサイトと少なくとも1つに含まれる代表の間の輸送システム内の移動の記述を含む一人の代表者;;
（ｄ）少なくとも１つの場所を含む要求を受信し、ここで、各場所は輸送システムに含まれ、少なくとも１つの場所は少なくとも1つの開始/終了場所を含んでおり;;
（e）少なくとも1つのルートまたはルートの長さを計算し、
ここで、各経路または経路長は、少なくとも1つの場所に含まれる場所と少なくとも1つの場所に含まれる場所との間の輸送システム内の移動の記述を含み、
ここで、コンピューティングは
i.少なくとも1人の近くの代表者を決定し、ここにおいて各近所の代表者は、
A.少なくとも1人の代表者に含まれている、および
B．近くの代表者と少なくとも１つの開始／終了場所に含まれる開始／終了場所との間の移動の長さが閾値内である；そして
ii. 少なくとも1人の近くの代表者に含まれるそれぞれの近くの代表者のために、データベースに保存されている少なくとも1つの事前計算されたルートまたはルート長から取得し、近くの代表者および近くでないサイトの間の第二の事前計算されたルートまたはルート長であり、ここで近くのないサイトは複数のサイトに含まれ;そして
（ｆ）少なくとも１つの経路または経路長の表現を含む情報で要求に応答する。
【請求項２】
請求項１に記載の方法であって、
（ａ）少なくとも１つのサイトに含まれるサイトは不動産を表し、少なくとも１つの場所に含まれる場所は通勤先を表す、または
（ｂ）少なくとも１つのサイトに含まれるサイトは通勤目的地を表し、少なくとも１つの場所に含まれる場所は不動産を表す。
【請求項３】
請求項１に記載の方法であって、前記要求は、以下のうちの少なくとも１つをさらに含む方法、
（a）少なくとも1つのサイトに含まれる第2のサイトからの最初の出発時刻、
（b）少なくとも1つのサイトに含まれる3番目のサイトへの最初の到着期限、
（c）少なくとも１つの場所に含まれる第２の場所からの第２の出発時間、または
（d）少なくとも1つの場所に含まれる3番目の場所での2回目の到着期限。
【請求項４】
前記少なくとも１つの場所が以下を含む、請求項１に記載の方法：
（a）2≦i≦k-1の範囲の各iについて、閾値kが偶数の場合、場所Pi;
ここで、少なくとも1つの開始/終了場所には、
（b）閾値kの開始場所P1または終了場所Pk;ここで、ルートまたはルート長の計算はさらに以下を含む、
（c）それぞれが少なくとも1つのサイトに含まれる最初のサイトまたは最後のサイトを受信する;そして
（d）使用：
i.閾値kに対する、最初のサイトから開始場所P1への移動の説明、または終了場所Pkから最後のサイトへの移動の説明、そして
ii. 2≦i≦k-2の範囲の各偶数iについて、閾値kについて、場所Piから場所Pi + 1への移動の記述。
【請求項５】
ルートまたはルート長が、少なくとも１つのサイトに含まれる２つ以上のサイトを含む、請求項１に記載の方法。
【請求項６】
請求項１に記載の方法であって、
（a）少なくとも1つのルートまたはルート長には、サイト配置ルートまたはルート長が含まれ、
さらに以下を含み、
（b）サイトの場所のルートまたはルートの長さをデータベースに保存する、ここで、コンピューティングはさらに以下を含み、
（c）データベースからサイト配置ルートまたはルート長を取得する。
【請求項７】
請求項１に記載の方法であって、
（ａ）複数のサイトは、クラスタサイトを含み、クラスタサイトは、複数のサイトに含まれる１つまたは複数のサイトを表し、１つまたは複数のサイトは、以下のうちの少なくとも１つに基づいてクラスタ化され、
i.旅行の長さ;または
ii.地理的近接度、ここで、１つまたは複数のサイトは、地理的位置をさらに含む、または
（ｂ）少なくとも１つの代表は、クラスタ代表を含み、クラスタ代表は、少なくとも１つの代表に含まれる１つまたは複数の代表を表し、１つまたは複数の代表は、以下のうちの少なくとも１つに基づいてクラスタ化され、
i.旅行の長さ;または
ii.地理的近接度 ここで、1人または複数の代表は、地理的位置をさらに含む。
【請求項８】
前記複数のサイトが少なくとも１つのサイトコネクタを含む、請求項１に記載の方法であって、ここで
（a）近くにないサイトが少なくとも1つのサイトコネクタに含まれ、そして
（b）ルートまたはルート長の計算はさらに以下を含み：
i.近くにないサイトと第0サイト、第0サイトは少なくとも1つのサイトに含まれる。
【請求項９】
請求項１に記載の方法であって、
圧縮リストが１つまたは複数の第１の事前計算ルートまたはルート長を含み、少なくとも１つの事前計算ルートまたはルート長をデータベースに格納することが、圧縮リストを圧縮することをさらに含む。
【請求項１０】
請求項１に記載の方法であって、
（a）少なくとも1つの事前計算されたルートまたはルート長をデータベースに保存する、または
（b）少なくとも１つの経路または経路長を計算することは、以下をさらに含む：
（c）操作関数を受け取る、および
（d）操作関数を以下に適用：少なくとも1つの事前計算されたルートまたはルート長、または少なくとも1つのルートまたはルート長。
【請求項１１】
前記操作機能は、以下に含まれる第１の経路長を無限大に設定することを含む、請求項１０に記載の方法、
（a）少なくとも1つの事前計算されたルートまたはルートの長さ、または
（b）少なくとも1つのルートまたはルートの長さ、
最初のルートの長さは、最初の不動産と最初の学校の間であり、
（c）最初の不動産が少なくとも1つのサイトに含まれている、
（d）最初の学校が少なくとも1つの場所に含まれている、および
（e）最初の不動産が最初の学校のゾーンの外にある。
【請求項１２】
以下をさらに含む、請求項1に記載の方法：
（a）輸送システムに関するデータの受信、
i.複数の輸送要素;そして
ii.少なくとも１つのセグメント長、各セグメント長は、第１の輸送要素から第２の輸送要素までの移動の長さを表し、各輸送要素は、複数の輸送要素に含まれ、そして
（b）複数のグラフ頂点を含むグラフを作成し、
i.複数の輸送要素の頂点、各輸送要素の頂点は、複数の輸送要素の１つを表し、
ii.複数のサイト頂点、各サイト頂点は複数のサイトの1つを表し、そして
iii.少なくとも１つの代表的な頂点、各代表的な頂点は、少なくとも１つの代表的なものの１つを表し、
グラフは、複数のグラフエッジをさらに含み、グラフエッジソース頂点からグラフエッジターゲット頂点に至るグラフエッジを含み、グラフエッジの重みを含み、
iv.複数の輸送要素頂点に含まれる最初の輸送要素頂点を含むグラフエッジソース頂点、複数の輸送要素頂点に含まれる2番目の輸送要素頂点を含むグラフエッジターゲット頂点、含まれるセグメント長を表すグラフエッジの重みの中に 少なくとも１つのセグメント長、セグメント長は、第１の輸送要素頂点によって表される輸送要素から第２の輸送要素頂点によって表される輸送要素までの移動の長さを表し;
v.グラフエッジソース頂点とグラフエッジターゲット頂点は、第1グラフ頂点と第2グラフ頂点をいくつかの順序で含み、第1グラフ頂点は複数のサイト頂点に含まれ、第2グラフ頂点は複数のサイト頂点に含まれ、グラフの頂点と、最初のグラフの頂点で表されるサイトと2番目のグラフの頂点で表されるエンティティとの間の移動の長さを表すグラフエッジの重み、または
vi.グラフエッジソース頂点とグラフエッジターゲット頂点は、いくつかの順序で3番目のグラフ頂点と4番目のグラフ頂点を含み、3番目のグラフ頂点は少なくとも1つの代表頂点に含まれ、4番目のグラフ頂点は複数のグラフに含まれます頂点と、3番目のグラフ頂点で表される代表と4番目のグラフ頂点で表されるエンティティとの間の移動の長さを表すグラフエッジの重み、
ここで、第1の事前計算されたルートまたはルート長は、以下の表現を含む、
（c）少なくとも１つの代表的頂点に含まれる代表的頂点と複数のサイト頂点に含まれるサイト頂点との間のグラフ経路またはグラフ経路長。
【請求項１３】
前記複数のグラフ頂点は、以下のうちの少なくとも１つを表すグラフ頂点を含む、請求項１２に記載の方法、
（a）公共輸送車両のトランジット駅、
（b）車両の停止、
（c）車両の方向転換、
（d）散歩の停止、または
（e）散歩のターン、または
ここで、複数の輸送要素は時間をさらに含む輸送要素を含み、複数のグラフ頂点に含まれるグラフ頂点は時間を表す。
【請求項１４】
前記グラフエッジ重みは、以下のうちの少なくとも１つを表す、請求項１２に記載の方法、
（a）公共輸送車両間の多数の乗り換え、
（b）旅行の期間、
（c）交通費
（d）待機時間、
（e）待機の金銭的コスト、または
（f）移動距離、または
ここで、少なくとも１つのセグメント長は、第１の輸送要素からの輸送出発時間または第２の輸送要素での輸送到着時間、および輸送出発時間に始まる、または、輸送の到着時に終了する移動の長さを表すグラフエッジ重みをさらに含むセグメント長を含む。
【請求項１５】
代表的な頂点とサイト頂点との間のグラフ経路またはグラフ経路長が、以下のうちの少なくとも１つを適用することによって得られる、請求項１２に記載の方法、
（a）ダイクストラの最短経路アルゴリズム、または
（b）A *（スター）検索アルゴリズム、
（c）グラフ、または
（d）グラフのエッジが反転したグラフ。
【請求項１６】
前記複数のサイトが以下を含む、請求項１に記載の方法：
（a）1≦i≦mの範囲内の各i、閾値m≧1の場合、サイトSi ;;さらに含む：
（b）少なくとも1つの座標を受け取ります、各座標iは、閾値mに対して1≦i≦mの範囲であり、
ここで、少なくとも1つの事前計算されたルートまたはルート長は、
（c）少なくとも1つの座標に含まれる各座標iについて、近くの代表者からサイトSiへの移動の説明を含む最初の事前計算ルートまたはルート長を含む値v [i]を含むベクトルv、または
（d）少なくとも1つの座標に含まれる各座標iについて、サイトSiから近くへの移動の説明を含む最初の事前計算ルートまたはルート長を含む値v '[i]を含むベクトルv'代表。
【請求項１７】
請求項１６に記載の方法であって、
（ａ）少なくとも１つの座標は少なくとも２つの座標を含み、少なくとも１つの事前計算された経路または経路長を記憶することはさらに以下を含み、
レイアウト、少なくとも1つの座標に含まれる一連の座標iについて、
i.値v [i]または値v ′[i]、データベース内で順次、または
（ｂ）少なくとも１つの事前計算された経路または経路長を記憶することは、さらに少なくとも1つの座標に含まれる少なくとも1つの座標iについて、リストまたはハッシュマップを格納することを含み、
i.データベース内の値v [i]または値v ′[i]。
【請求項１８】
さらに以下を含む請求項16の方法：
少なくとも1つの座標に含まれる少なくとも1つの第1座標i
（a）重みwiを受け取り;;
ここで、第1の座標iについて、格納はさらに以下を含む：
（b）rsiで示される、近くの代理人からサイトSiまでの移動距離を決定する、そして
（c）サイトSiから近くの代表者までの、sriで表される移動の長さを決定し;
ここで、最初の座標iについて、
（d）重みwi、rsi、sriに対して値v [i]または値v '[i]は、wi・rsi +（1-wi）・sriに等しい移動距離を含む。
【請求項１９】
さらに以下を含む請求項16の方法：
少なくとも1つの座標に含まれる少なくとも1つの第2座標i
（a）下限lbi、上限ubi、およびスケーリング係数sfiを受け取り、
ここで、第2の座標iについて、格納はさらに以下を含む：
（b）サイトSiと近くの代理人との間の、bsriと示される移動の長さを決定すること;
ここで、2番目の座標iについて、
（c）値v [i]または値v '[i]は、以下に等しい移動距離を構成し：bsriにスケーリング係数sfiを掛け、整数に丸め、下限からの範囲内に制限上限ubiへのlbiにキャップされる。
【請求項２０】
少なくとも１人の近くの代表者が以下を含む、請求項１６に記載の方法、
（a）1≦j≦sの範囲内の各j、閾値s≧1の場合、近くの代表的なRj ;;
さらに含む：
（b）ベクトルの1つ以上の座標について、座標の値を使用して、数値の最初の合計を計算することを含む+演算を受け取り、そして
（c）１つまたは複数の座標について、複数のベクトルにわたる座標での値の第３の最小値を計算することを含む最小操作を受け取る、
ここで
（d）少なくとも１つの開始／終了場所は開始場所を含み、少なくとも１つの経路または経路長の計算はさらに以下を含む：
i.1≦j≦sの範囲内の各jについて、閾値sについて、近くの代表的なRjから開始地点までの移動の長さである移動の長さrpRを決定し、
ここで、少なくとも1つの事前計算された経路または経路長は、1≦j≦sの範囲の各jについて、閾値sについて、近くの代表が近くの代表Rjであるベクトルv 'であるベクトルvR'jを含み、
ここで、移動ベクトルvR 'の長さは、少なくとも1つの座標に含まれる少なくとも1つの第3座標iについて、3番目のベクトルvR'の値vR '[i]に含まれる移動の長さである値を含み、座標i;そして
ii. min演算と+演算を含む最初の数式を使用して最初の最小値を見つけ：
min1 ≦ j ≦ s  {（移動の長さrpRj）+（移動ベクトルの長さv'Rj）}
最初の最小値、少なくとも1つの座標に含まれる少なくとも1つの5番目の座標i
サイトSiから出発地までの移動の説明を表し、2番目の事前計算ルートまたはルート長を使用し、近くにないサイトはサイトSiであり; または
（e）少なくとも１つの開始／終了場所は終了場所を含み、少なくとも１つの経路または経路長の計算はさらに以下を含む：
i.範囲1≦j≦sの各jについて、閾値sについて、終点から近くの代表的なRjまでの移動の長さである移動の長さprRを決定し、
ここで、少なくとも1つの事前計算された経路または経路長は、1≦j≦sの範囲の各jについて、閾値sについて、近くの代表が近くの代表RjであるベクトルvであるベクトルvRjを含み、
ここで、移動ベクトルvRは、少なくとも1つの座標に含まれる少なくとも1つの第4の座標iについて、第4の座標iにおけるベクトルvRの値vR [i]に含まれる移動の長さである値を含む、そして
ii.最小演算と+演算を含む2番目の数式を使用して2番目の最小値を見つけ：
min1 ≦ j ≦ s {（移動の長さprRj）+（移動ベクトルの長さvRj）}
2番目の最小値、少なくとも1つの座標に含まれる少なくとも1つの6番目の座標i
は、最終地点からサイトSiへの移動の説明を表し、2番目の事前計算ルートまたはルート長を使用し、ここで近くにないサイトはサイトSiとなる。
【請求項２１】
請求項２０に記載の方法であって、
（a）+演算に含まれる計算には、以下の少なくとも1つが含まれ、
i.下限から上限までの範囲内の飽和算術演算
ii.整数を操作する算術演算、または
iii.浮動小数点数で動作する算術演算;
（b）第１の数式または第２の数式は、ハードウェアによってサポートされる少なくとも１つのベクトル演算をさらに含む、または
（c）第１の数式の使用または第２の数式の使用は、計算を複数のパーティションに分割すること、および複数のパーティションを並列に実行することをさらに含む。
【請求項２２】
請求項１に記載の方法であって、前記要求は、
（a）1≦i≦qの範囲内の各i、閾値q≧1の場合、ルート指定Li、ここで、ルート指定Liは1つ以上の場所を含み、1つ以上の場所は1つ以上の開始/終了を含む場所 ;;ここで、要求にはさらに以下が含まれ、
（b）導出器、ここで、導出器は、導出器入力が与えられると、導出器出力を計算するアルゴリズムを含む、
ここで、情報はさらに以下を含む：
（c）微分器の出力、ここで、微分器の入力は、閾値qのシーケンスT1、...、Tqを含み、1≦i≦qの範囲の各iについて、Tiは情報の一部を含み、
i.少なくとも1つの場所は、ルート指定Liに含まれる1つ以上の場所であり、
ii.少なくとも1つの開始/終了場所は、ルート指定Liに含まれる1つ以上の開始/終了場所である。
【請求項２３】
前記導出者は、以下のうちの1つを含む、請求項22に記載の方法、
（a）少なくとも1つのサイトに含まれる4番目のサイトについて、閾値qについて、1≦i≦qの範囲のiにわたって、4番目の最小値に等しいルート長である最小ルート長を含む派生出力、Tiに含まれる2番目のルートの長さのうち、4番目のサイトを含む2番目のルートの長さ;
（b）閾値qの重みw1、...、wqを、微分子入力の一部として受け取る、少なくとも1つのサイトに含まれる5番目のサイトについて、含まれる3番目のルート長のi全体で1≦i≦qの範囲の2番目の合計に等しいルート長である重み付きルート長を含む派生出力Tiでは、5番目のサイトを含む3番目のルートの長さ、3番目のルートの長さは、重みw1、...、wqに含まれる重みwiによって重み付けされ、または
（ｃ）少なくとも１つのサイトに含まれるサイトＳを導出者入力の一部として受信する、そして、派生物出力は、少なくとも1つのサイトに含まれる6番目のサイト、6番目のサイトを含む4番目のルートの長さとサイトSを含む5番目のルートの長さの差に等しいルート長、4番目のルートの長さと5番目のルート誘導入力に含まれる長さである。
【請求項２４】
請求項１に記載の方法であって、前記要求は、さらに、
（a）条件：少なくとも1つのサイト、または情報の一部、ここで、情報はさらに以下のフィルタリングを含む、
（b）少なくとも1つのサイト、または
（c）条件に一致する情報。
【請求項２５】
前記状態が、以下のうちの少なくとも１つを含む、請求項２４に記載の方法、
（a）最大通勤時間の閾値、または最大歩行距離、
（b）不動産タイプ、または不動産価格またはサイズ範囲、または
（c）ジョブタイプ、またはジョブの給与範囲。
【請求項２６】
請求項１に記載の方法であって、前記要求は、さらに、
（a）アグリゲーター、アグリゲーターは、アグリゲーター入力が与えられたときにアグリゲーター出力を計算するアルゴリズムを含み、
ここで、情報はさらに以下を含む：
（ｂ）アグリゲータ出力、ここでアグリゲータ入力はシーケンスI1、... 、Ir、閾値r≧1の場合、1≦i≦rの範囲の各iについて、閾値rの場合、Iiは情報の一部を構成する。
【請求項２７】
請求項２６に記載の方法であって、
アグリゲーター出力が、輸送システム内の第７のサイトの中心性を含み、第７のサイトが少なくとも１つのサイトに含まれる。
【請求項２８】
請求項１に記載の方法であって、前記要求は、さらに、
（a）コスト関数、ここで、コスト関数は、コスト関数入力が与えられた場合にコスト関数値を計算し、コスト関数入力は、
i.情報に含まれる経路長である探索経路長、そして
（b）探索アルゴリズム、探索アルゴリズムは、以下を計算するアルゴリズムを含み、
i.少なくとも1つのコスト関数入力のコスト関数値、および
ii.探査出力;;
ここで、情報はさらに以下を含む：
（c）探査出力。
【請求項２９】
請求項２８に記載の方法であって、
（a）コスト関数は、探索ルートの長さに依存する微分可能な関数、そして
（b）探索アルゴリズムは、コスト関数の勾配を計算する勾配降下アルゴリズムを含む。
【請求項３０】
請求項１に記載の方法であって、
前記格納または計算することが、多次元コストに基づいて多目的最適化検索を適用することをさらに含む。
【請求項３１】
前記多次元コストが、以下のうちの少なくとも１つを含む、請求項３０に記載の方法、
（a）少なくとも1つのサイトに含まれるサイトの価格またはサイズ、または
（b）経路の長さ、金額、待機時間、乗り換え回数、または徒歩距離：少なくとも1つの事前計算された経路または経路の長さ、または少なくとも1つの経路または経路の長さ。
【請求項３２】
輸送システム内の少なくとも1つのサイトと少なくとも1つの場所との間の少なくとも1つのルートまたはルート長を使用して、少なくとも1つのサイトを検索または比較するためのコンピュータシステムであって、前記コンピュータシステムは
（a）1つ以上のプロセッサ、
（b）１つまたは複数のプロセッサによる実行のための１つまたは複数のプログラムを格納するコンピュータ可読記憶媒体、そして
（c）請求項１から請求項３１のいずれか１項に記載の方法を実行するために１つまたは複数のプロセッサによって実行される命令を含む１つまたは複数のプログラム、を含む。
【請求項３３】
輸送システム内の少なくとも1つのサイトと少なくとも1つの場所との間の少なくとも1つのルートまたはルート長を使用して、少なくとも1つのサイトを検索または比較するための装置であって、前記装置は、
（a）ユーザーからリクエストを受信するように構成されたレシーバー、
（b）情報の一部でユーザーに応答するように構成された送信機、および
（c）請求項１から請求項３１のうちの１つの方法を実行するように構成された１つまたは複数のモジュールを備える。
【請求項３４】
前記受信機は、以下のうちの少なくとも１つを受信する、請求項３３に記載の装置、
（a）少なくとも1つの場所;
（b）状態;
（c）最初の出発時刻、最初の到着期限、2番目の出発時刻、または2番目の到着期限、または
（d）導出者;;
ここで、送信機はさらに、以下の少なくとも1つで応答する、
（e）以下の地理的位置：マップ上にレンダリングされた、少なくとも1つの場所に含まれる場所、または少なくとも1つのサイトに含まれるサイト;
（f）次の出発時刻または到着時刻：少なくとも1つの場所に含まれる場所、または少なくとも1つのサイトに含まれる場所;
（g）少なくとも1つのサイトに含まれるサイトの概要、または、サイトの名前、サイトのアドレス、サイトの価格、またはサイトのサイズの少なくとも1つ;
（h）近くのサイトのクラスタの概要、ここで、近くのサイトのクラスタは、旅行の長さまたは地理的近接性に基づいてクラスタ化された少なくとも１つのサイトに含まれるサイトを含む;
（i）近隣サイトのクラスターのレンダリング、レンダリングのサイズは近隣サイトのクラスター内のいくつかのサイトと相関する;
（j）サイトのスタッキング、各8番目のサイトは少なくとも1つのサイトに含まれ、情報に含まれ、8番目のサイトが関係するルート長のz-index順でのスタッキング 、地図上にレンダリングされる;
（k）ルートまたはルート長の要約、または経路の一部または経路の長さ、その一部は以下の少なくとも1つを含む：i.ルート：長さ、期間、金額、速度、または待機期間、 ii.名前：公共交通機関の車両、車両の道路、歩道、ストップ、ターン、またはトランジット駅、またはiii.地理的位置：金額、速度、待機時間、車両、車両の道路、歩道、停車場、曲がり角、または公共交通機関の乗り継ぎ駅;
（l）情報に含まれるルート長のヒストグラム、サイトを含むルート長、少なくとも1つのサイト全体、または、マップ上にレンダリングされた少なくとも1つのサイトにわたるルート長のヒートマップ;
（m）最小ルート長;少なくとも1つのサイトにわたる最小ルート長のヒストグラム、または、マップ上にレンダリングされた少なくとも1つのサイトにわたる最小ルート長のヒートマップ;
（n）加重ルート長;少なくとも1つのサイトにわたる重み付けされたルートの長さのヒストグラム、または、マップ上にレンダリングされた少なくとも1つのサイト全体の加重ルート長のヒートマップ;
（o）差分ルート長;少なくとも1つのサイト全体の差分ルート長のヒストグラム、または、マップ上にレンダリングされた少なくとも1つのサイトにわたる差分ルート長のヒートマップ;
（p）派生出力のレンダリング;
（q）情報に含まれる6番目のルートの長さを最小化する9番目のサイト、9番目のサイトを含む6番目のルート長は、少なくとも1つのサイト全体で最小化され、移動コストの閾値によって制約される;
（r）条件によって制約される上記の項目（e）から項目（q）の少なくとも1つ、または
（s）少なくとも1つのサイトに含まれるサイトを含む上位リスト
i.トップリストに含まれる各10番目のサイト、および
ii.情報に含まれ、10番目のサイトを含む7番目のルート長、
条件を満たす、7番目のルートの長さで並べ替えられたトップリスト。
【発明の詳細な説明】
【背景技術】
【０００１】
関連出願の相互参照
この出願は、以下の出願に基づき、及び優先日を主張する。
[国] [出願番号] [出願日]
米国 62/632,419 2018.2.20
米国 62/758,710 2018.11.12
米国 62/780,268 2018.12.16
米国 62/800,428 2019.2.2
米国 16274242 2019.2.13
これらは、ここでは参照として組み込まれる。
【０００２】
本願発明はサイトの検索又は比較に関する。検索の従来のゴールは、可能な代案の範囲内から、例えば、特定の行程要求を与えられたルート距離の最小化や探すサイトの好ましい特徴など、最適化目的を達成するサイトを見つけることである。例えば、要求された通勤目的地及び不動産資産の特徴が与えられた不動産資産を検索するとき、ゴールは最短の通勤期間を有する特徴に一致する不動産資産を列挙することである。他のゴールは、通勤期間を使用して不動産資産を比較することである。
【発明の概要】
【０００３】
実施形態はサイトの検索又は比較の方法、前記方法を実行及び達成するコンピュータシステム、及びユーザから検索又は比較リクエストを受信してサイトとルート情報を応答をするコンピュータサービスを含む。
【０００４】
本発明の実施形態によれば、ルート又はルート距離を使用して検索又は比較する方法が提供される。本方法は、各サイト及び交通システム内の代表の間のルート又はルート距離を予め計算及びデータベースに蓄積するために広範な広範な前処理を使用する。本方法は、サイトの検索又は比較フレームワークを導入する。ルート明細を含むリクエストが受信されるとき、予め計算されたデータが、各サイトのルート又はルート距離を素早く計算するため前記データベースから取得される。サイトは、ルート又はルート距離を使用して検索又は比較される。
【０００５】
本発明の実施形態によれば、ルート又はルート距離を使用してサイトの検索又は比較をするためのコンピュータシステムが提供される。前記システムは、ハードウェア及びソフトウェアの組み合わせである。それは、１以上のデータプロバイダから交通システム及びサイトに関するデータを得る。前記システムは、前記サイト及び前記交通システム内の代表の間の行程をモデル化したグラフを構築する。前記システムは、グラフパスを計算し、またグラフパス又はグラフパス距離を蓄積する。これは、リクエストが受信されたとき全てのサイトのためのルート又はルート距離を素早く計算し、及びルート又はルート距離を使用してサイトを検索又は比較することを可能にする。
【０００６】
本発明の実施形態において、ルート又はルート距離を使用してサイトを検索又は比較するコンピュータサービスが提供される。前記サービスは、前記ユーザが例えばスマートフォンのような装置上のユーザインタフェースを通して、検索を特定し又はリクエストを比較することを許容する。前記リクエストは、ルート明細及びフィルタリング条件を含む。応答では、前記サービスは、前記一致したサイトのためのルート又はルート距離に沿った前記フィルタリング条件に一致するサイトを紹介し、又は前記サービスはルート又はルート距離を使用してサイトを比較する。
【０００７】
それは、各サイトにおけるルート距離を素早く計算するために基本的に必要である。我々は、数学的証明をスケッチする。検索又は比較方法Мを考える。我々は、Мをどのような与えられたサイトのオーダリストにも応じさせて敵対するリクエストをデザインすることができる。前記敵対は、自由に使うことができる２つの機構を有する：（１）前記ルート距離に関するサイトのオーダを生成するルート明細を伴うリクエストを提供し、前記オーダは前記敵対によって選択されたものであり、及び（２）前記敵対によって選択されたサイトのサブセットに一致するサイト上のフィルタリング条件を伴うリクエストを提供する。このように、前記Мは、リクエスト時間で、前記敵対により任意に選択されたサイトのオーダリストに応答しなければならない。証明スケッチの詳細は、特許出願の範囲の外である。
【０００８】
前記方法、前記コンピュータシステム、及び前記コンピュータサービスのそれぞれは従来技術によって単純な一般的でもよく知られたものでもないタスクを一緒に実行する。従来技術は以下出願を含む：US 8,417,409 B2; 継続US 8,738,286 B2; 分割US 8,756,014 B2;; KR 10-1692501 B1; 継続PCT/KR2016/01083; WO 2017/065431 A1; US 2018/0232824 A1;; 及び KR 10-1905593 B1。
【０００９】
ここで紹介される本発明の実施形態は、説明の目的である；それらは網羅的となることを意図していない。多くの変更及びバリエーションが前記範囲及び実施形態のスピリットから離れることなく技術中に当業者にとって明らかとなる。
【００１０】
本願中において、用語“第一”、“第二”、“前記”、及び似たものはいかなる限定の意味で使用されるものではなく、しかし、前記文脈から明らかでない限り、分別の目的のためである。前記文脈から明らかでない限りにおいて、単数の表現は複数のフォームを含む。前記用語“有する”、“含む”、“含む”、及び似たものは構成や特徴の存在を示し、及び存在から又は加えられたものから他の構成や特徴を除いていない。
【図面の簡単な説明】
【００１１】
本願開示に含まれる図面は本発明の様々な特徴及び形態の有利な点を例示する。
【図１】図１は、本発明の形態に応じた通勤パスの行程期間の例示のカラー描写を示し、凡例：“２つの通勤パスを有する不動産資産の通勤パスの行程期間の例示のカラー描写：資産→geo.0.0→geo.0.1→資産、及び資産→geo.1.0→資産。我々は、グーグルによるマップタイルエンジンを使用したが、他のものも代わりに使用される。
【図２】図２は、本発明の形態に応じた例示の前処理の処理フロー及びデータの蓄積を描写し、凡例：“例示の前処理の処理フロー及びデータの蓄積”。
【図３】図３は、本発明の形態に応じた前処理された蓄積データを用いるリクエストに応答する例示の処理フローを描写し、凡例：“前処理された蓄積データを用いるリクエストに応答する例示の処理フロー”。
【図４】図４は、本発明の形態に応じた例示の通勤パスを描写し、凡例：“例示の通勤パス”。
【図５】図５は、本発明の形態に応じた最短グラフパスを予め計算するための公共交通システムグラフの例示の延長を示し、凡例：“最短グラフパスを予め計算するための公共交通システムグラフの例示”。
【図６】図６は、本発明の形態に応じた予め計算された最短行程期間の例示のテーブル／ベクトル蓄積を示し、凡例：“予め計算された最短行程期間の例示のテーブル／ベクトル蓄積”。
【図７】図７は、本発明の形態に応じた通勤パスの分解の例示を描写し、凡例：“３つの家H1, H2, 及びH3で説明された、ホーム依存パート（緑）及びホーム独立パート（黒）に分解された例示の通勤パスH→W1→W2→W3→W4→H”。
【図８】図８は、本発明の形態に応じた通勤パスの出発での最短行程期間の計算の例示を描写し、凡例：“通勤パスの出発での最短行程期間の計算の例示”。
【図９】図９は、本発明の形態に応じた通勤パスの到着での最短行程期間の計算の例示を描写し、凡例：“通勤パスの到着での最短行程期間の計算の例示”。
【図１０】図１０は、本発明の形態に応じた通勤パスの出発での最短行程期間を計算するための擬似コードの例示を描写し、凡例：“PathFromHomeDurations(→W)を計算するための仮コードの例示”。
【図１１】図１１は、本発明の形態に応じた計算システムのフローチャートの例示を描写し、凡例：“予め計算してデータベースに蓄積、及び前記データベースから取得されたデータを使用してリクエストを処理のための計算システムのフローチャートの例示”。
【図１２】図１２は、本発明の形態に応じたユーザのスマートフォン上のコンピュータサービスによるユーザリクエスト及び応答の例示を描写し、凡例：“ユーザのスマートフォン上のコンピュータサービスによるユーザリクエスト及び応答の例示”。
【００１２】
本図は説明の目的のみである。他の図面は当該技術の当業者によって容易に認識されるものであるため、本発明の原則から離れることがなく本発明を例示することができる。
【発明を実施するための形態】
【００１３】
４．詳細な記述
本発明は、任意の場所までのルートやルート距離を使用した任意の最適化目的を使用している任意のサイトを検索又は比較する一般的なケースに関する。しかしながら、提示を簡単にするため、我々は最初に不動産資産である特定のサイト、職場である特定の場所、及び不動産資産及び職場の間の通勤の行程期間を最小化する最適化目的を通じて本発明を説明する。この説明は限定していない。後述において、我々はどのように前記方法が一般ケースで働くか説明する。
４．１  不動産資産及び通勤パス
【００１４】
家を見つけることは複雑な努力である。人々は、重要な時間の努力及びお金を検索に費やす。しかしながら、テクノロジーは助けとなる。不動産資産のリストを集める幾つかの有用なオンラインのサービスがあり、ウェブブラウザやスマートフォンの便宜で、人々が例えば値段、地理的ロケーション、ベッドルームの数などの特定の特徴を伴う不動産資産を検索することを許可する。この検索は、人がそれから典型的に対面で詳しく調べるショートリストを生成する。
【００１５】
ロケーションは、不動産エージェントの“ロケーション、ロケーション、ロケーション”スローガンにより証拠とされるように、どのような不動産資産においても間違いなく最も重要な特徴である。我々の発明はこの特徴を心配する。
【００１６】
住民は職場、学校、又は他の場所に通勤する必要がある。これらの通勤の行程期間は、その特定の住民のために個人化された前記不動産資産の価値に関係する。加えて、より生産的な活動に割り当てられ得る時間、人々が動き回るなどに費やされる必要のないエネルギーに関して、大都市のエリアの全ての住民にとって前記行程期間を削減することに多くのグローバル的な経済価値がある。我々の発明は、これらの個人及びグローバル価値を渡すことを助ける。
【００１７】
シンプルな説明として、韓国の首都に住んでいる２の家族を考える。一人は市役所の公務員であり、及び他方の人はソウル国立大学のメイン図書館の司書である。彼らは現在350,000,000韓国ウォンの前払金を要する69スクエアメートルのサイズの2ベッドルーム、１バスルームのマンションに住む。前記マンションは緯度及び経度(37.5333, 127.0746)の近くである。彼らの結合された一日の往復の通勤は、１時間４１分である（平均、片道約２５分）。しかしながら、彼らは前記同じ特徴を有し、しかし(37.5041, 126.8888)の近くに位置するマンションに引っ越しした後に、行程期間をたった１時間１６分（２５分のセイビング）に減らすことができると判明する。全てのマンションで最も短い行程期間は５０分である。しかしながら、そのマンションは他の価格及びサイズを有する（2018.2.19として説明）。
【００１８】
なぜこれらの改善をすることが難しいのか？単純なアプローチは、前記家族によって要求される前記サイズ及び他の特徴を有するマーケットで有効な全ての不動産資産を考慮し、及び、与えられた職場を考慮し、オンラインにあるルーティングエンジンを検索することにより行程期間を計算する。しかしながら、このアプローチは量ることはない。一つの問題は、現代の大都会エリアでのマーケットで有効な不動産資産の多さである。他の問題は、改良を探したい家族／ユーザの多さである。我々がたとえルーティングエンジンで安価に検索ができると仮定したとしても、前記問題の２つの性質が未だに前記検索を総計で高価にする。
【００１９】
我々がどのようにこれらの改善をすることができるのか？我々の発明は説明する。それは以下の構成要素を備える：
１．本発明は、通勤パスのモデルを定義する。前記モデルは、例えば学校に行く、それからピアノ教室に行き、それから家に戻るなど、実際に生じる通勤パスの広範囲をカバーするため多目的に利用できる。我々のモデルの実用は、行程期間を最小化する不動産資産を素早く見つけるための我々の能力により高められる。
２．本発明は、行程期間を素早く計算する最適化方法を教示する。本発明は、どんな不動産資産にも依存したどんな通勤パスのパートも特定する。これらパートの行程期間は、予め計算され蓄積される。結果として、行程期間が通勤パスのために発見される必要があるとき、本発明は全てのどんな不動産資産のための行程期間を生産するための時間パートを素早く組み立てることができる。
３．本発明の実施形態は、ライブコンピュータサービスである。前記サービスは、ソウルの大都会エリアの２千５百万人の住民が行程期間を使用して不動産資産を検索し、又は比較することを可能とする。
４．２  方法の概要
【００２０】
我々は、用語行程を、動いている物体又はデータを含む広範な意味で使用する。行程の記述とは、当該技術分野の当業者がそのように名付けるすべてのものである。これは行程の記述の幾つかの例である：（１）“おいお前、１ブロック北へ行き、そしてそれからわずかに左に曲がる必要があるぞ”、及び（２）“５ドル”。我々は行程の記述を意味するとき、用語の行程パスを使うかもしれない。行程の距離は、例えば距離、お金の料金など、当該技術分野の当業者が行程と関連付けることができる数値である。他の例として、我々は、時間を示す行程の距離を意味するとき、用語の行程期間を使用するかもしれない。行程の距離は、それ自体で行程の記述である。行程の記述は、行程の距離のみでなく、行程の距離のみを含み、又は幾つかの他のデータもまた含むかもしれない。
【００２１】
我々は、本方法の幾つかの能力を説明し、及び後述で使用される用語を導入する。本方法は、全ての不動産資産における通勤パスの行程期間を算出する。 図１がこれを説明する。大都会エリアは、スクエアで色分けされる。前記色は、公共交通を使用して、各特定のエリアにおける不動産資産からどれぐらいの長さ通勤に要するかを示す：緑は短い通勤、黄色はより長い、及び赤色は最も長いものを示す。通勤パスは、資産で出発して、それから特定の場所geoを訪問し、そして最後に資産に戻る。ある意味、前記geoは固定されている一方、前記資産は自由に変動する。図１において、２つの通勤パスがあり、週２回の“オープンジャウ”通勤パスである資産→geo.0.0→geo.0.1→資産であり、及び週三回の“ラウンドトリップ”通勤パスである資産→geo.1.0→資産である。我々は、与えれたこれら２つの通勤パス及びこれらの頻度、最短の行程期間の小さく重み付けられた合計を伴う前記不動産資産が、驚きとして来ないかもしれない、可能な複雑な公共交通ルートが与えられた不規則なパッチ（深緑）を形成するのを見ることができる。
【００２２】
高いレベルで、本方法は２つのパートから構成される。第一のパートは、不動産資産及び交通システムの乗り物駅である代表の間の行程期間を計算する。これらの行程期間は、データベースに蓄積され、その結果、それらはリクエストが受信されるときに容易に取得されることができる。説明のため図２を参照する。第二のパートは、リクエストを処理する。リクエストは通勤パス及び不動産資産の要求される特徴を含む。リクエストが受信されるとき、適切な行程期間が前記データベースから取得され、そして前記要求される特徴を有する全ての不動産資産の前記通勤パスにとっての行程期間を生成するために他のデータと共に使用される。説明のために前記図３を参照する。この概要の詳細と変形は、後述のセクションにおいて述べられる。
４．３  通勤パス
【００２３】
通勤は我々が家と呼ぶサイトＨで出発する。このＨは、任意のロケーションである。それは、例えば、アパート、レンタルルーム、庭のある家、牧場、ホテルなどのどんな不動産資産でもある。それはまた人が働く場所のサイト、レストラン、ショップなどである。しかしながら、命名規則として、我々は本開示のほどんどでフレーズ“家”を用いる。この規則は限定していない。一つの形態において、通勤は様々な場所へ移動することであり、またそれから前記サイトＨに戻る。
【００２４】
一つの形態において、通勤は、例えば通勤者が朝にＨから出発して、同じ日の夕方にＨに戻るという一日内で続く。一つの形態において、通勤は、例えばもし人がナイトシフトで働き、又は２５時間のワークシフトを有するなら、一日以上続く。一つの形態において、どのような行程も特定の時間に出発し、又は例えば午前８時１２分など特定の時間に到着する。一つの形態において、どのような行程も例えば“午前中”など時間の範囲内で出発、又は到着する。
【００２５】
最も単純なフォームでは、通勤者はＨから我々が職場と呼ぶ場所Ｗまで移動する。前記Ｗは任意のロケーションである。それは、学校、祖父母の家、週末のゴルフコース、好みのレストラン、医者のオフィス、ワーシップの場所などを含む。 それはまた人が住む場所となる。しかしながら、命名規則として、我々は本開示のほどんどでフレーズ“職場”を用いる。この規則は限定していない。それから、前記通勤者はＷからＨに戻る。我々はこれらの２つの行程を、ラウンドトリップ通勤パスと呼ぶ。説明のために図４Ａを参照のこと。
【００２６】
オープンジャウ通勤パスは、より複雑な通勤の例である。説明のために図４Ｂを参照のこと。ここで、前記通勤者はＨから場所W1に移動する。それから、前記通勤者は前記場所W1から他の場所W2に移動する。最終的に、前記通勤者は前記場所W2からサイトＨに戻るよう移動する。一例では、人が学校に移動し、そしてそれからピアノクラスに移動するときである。
【００２７】
一般に、我々の方法は、任意の行程を許可する。図４Ｃにおいて、我々はW4からW2の喪失している行程、及びW2からW3の繰り返し行程を伴う通勤パスの説明を見る。図４Ｄにおいて、我々は“オープン”通勤パス：Ｈから出発した通勤パスで、しかしＨに戻らない；及び以前の出発フォームＨなしにＨに戻る通勤パス、の説明を見る。図４Ｅにおいて、我々は、“非接続”通勤パスの説明を見る。通勤パスは家から出発するが、しかし他の家で到着する。我々の方法は、以下のように通勤パスを定義する。
定義１  通勤パスは行程W2→W3, W4→W5, . . . , Wk-2→Wk-1, ここでk≧2（偶数である）の集合であり、任意の瞬間に起こるHfirst→W1又はWk→Hlast (従って、通勤パスは常に少なくとも１の家及び少なくとも１の職場を含む)を伴う。
【００２８】
通勤パスは、交通システム内のルート明細として見られることができる。定義１内の様々なW及びHは、前記通勤者が行くことを要求する場所を特定する。
【００２９】
一つの形態において、我々は単純に通勤パスをH→W1→W2→ . . . →Wk→H, ここで k≧1と考え、これは行程の間で共有するエンドポイントを有し、出発及び終着で同じ家を有する。我々は、本開示のほとんどにおいてこの単純なフォームを使用し、というのもそれは実際にとてもありふれたものであり、我々の提示を簡単にする。しかしながら、我々の方法が通勤パスの我々の（一般の）定義に適用するということを当該技術分野のどのような当業者においても明らかになるだろう。
【００３０】
我々の方法は、どんな通勤パスにも沿った最短の行程期間を見つける。これはそれ自体、様々な従来技術により対処されている。しかしながら、我々の方法は、劇的に減らした時間量で、全ての家にとっての行程期間を見つける。
４．４  交通システムの前処理
【００３１】
本方法は、全ての家にとっての行程を予め計算及び蓄積するために、公共交通システムに関してのデータを前処理する。
４．４．１  最短行程の計算
【００３２】
我々は、全ての家、及び公共交通駅の全てのロケーションの間の最短の行程を効率的に計算する方法を述べる。我々は、本開示のほとんどで前記駅をストップステーションと呼び、それらはバス停、地下鉄駅、又は両方を含む。
【００３３】
本方法は、公共交通システムをモデルとし、従来技術から得ることができる任意の公共交通システムグラフGTで出発する。前記グラフは、バス停、地下鉄駅、又は両方を示す頂点を含む。例えば乗り物の停止又は方向変換、又は徒歩の停止又は方向変換を示す他の頂点が前記グラフ中に存在する。乗り物の停止に対応する前記グラフ中の頂点は、sによる指標付きの
STOPSTATION_s,
で示される。直接に重み付けられたエッジがあり、それぞれエッジが前記エッジのソース頂点から前記エッジのターゲット頂点までセグメントに沿った行程期間を示している。他のエッジはグラフ中に存在するかもしれない。エッジは、一の乗り物から他の乗り物への乗り換えを示すかもしれない。前記グラフは、様々な公共交通乗り物の出発時間又は到着時間に関してのデータを含む。ダイクストラ最短グラフパスアルゴリズム、又はA*（Ａスター）検索アルゴリズムは、最短のグラフパス距離（重みの合計）を伴うグラフパスを計算するために一般的に使用され、どのようなｓ'及びｓ''にとっての、またもし行程が特定時間で出発し、特定時間で到着するとしても、
STOPSTATION_s'
から他の
STOPSTATION_s''
への、最短の行程期間を示している。
【００３４】
我々の方法は、前記公共交通システムグラフGTを延長する。説明のために図５を参照のこと。
【００３５】
第一の延長は、ストップステーションのクラスタを導入する。本方法は、いかなるクラスタリングアルゴリズムを使用しているストップステーションをクラスタ化する；一の形態において、本方法は、２つのストップステーションの地理的距離が最大で5メートルなどの閾値であるとき、又は２つのストップステーションの間の行程期間が最大で閾値であるとき、２のストップステーションを１のクラスタとして置く。我々は、我々が前記クラスタの中心など、クラスタ内での地理的ロケーションを意味するとき、クラスタのロケーションを参照する。それぞれのストップステーションクラスタｃにとって、本方法は、2つの頂点
STOPSTATION_CLUSTER_SOURCE_c
及び
STOPSTATION_CLUSTER_TARGET_c,
及び前記クラスタを、FirstWaitGetOnとラベル化された
STOPSTATION_CLUSTER_SOURCE_c ・ STOPSTATION_s'
であるGTのストップステーションに接続したエッジ、及びS´が前記クラスタC内であるときにはいつでも、そのようなS´にとって、Zeroでラベル化された
STOPSTATION_s' ・ STOPSTATION_CLUSTER_TARGET_c
を追加する。前記エッジはゼロ重みを有する。結果のグラフは、頂点VC及びエッジECを有するGCによって示される。全てのｃにとって頂点
STOPSTATION_CLUSTER_SOURCE_c
のサブセットは、VSによって示される。
【００３６】
第二の延長は、家のクラスタを導入する。本方法は、どのようなクラスタリングアルゴリズムを使用して家をクラスタ化する；一の形態において、本方法は、ストップステーションをクラスタ化するときと同じアルゴリズムを使用する。同様に、我々はホームクラスタのロケーションを参照する。それぞれのホームクラスタにとって、本方法は頂点
HOME_CLUSTER_SOURCE_s
及び頂点
HOME_CLUSTER_TARGET_s
を追加する。本方法は、それぞれのホームクラスタを、徒歩を使用しているストップステーションクラスタに接続する。特に、本方法は、Walkによってラベル化されたエッジ
HOME_CLUSTER_SOURCE_s ・ STOPSTATION_CLUSTER_SOURCE_c
もし前記ホームクラスタｓのロケーションから前記ストップステーションクラスタｃの前記ロケーションまで徒歩があるならば、どのようなｓ及びｃにとっても、徒歩の期間に設定されたエッジ重みを有し、及びWalkによってラベル化された“反対向きのエッジ”
STOPSTATION_CLUSTER_TARGET_c ・ HOME_CLUSTER_TARGET_t
もし前記ストップステーションクラスタｃから前記ホームクラスタｔのロケーションまでの反対向きの方向の徒歩があるならば、どのようなｃ及びｔにとっても、徒歩の期間に設定されたエッジ重みを有する。一の形態において、本方法は、例えば４ｋｍ／時間など特定のスピードで、例えば1時間など最大も閾値で続く最短の徒歩に、徒歩を限定する。結果のグラフはGによって示される。我々は、全てのｓにとっての、頂点のセット
HOME_CLUSTER_SOURCE_s,
をVHによって示す；及び全てのｓ及びｃにとってのエッジのセット
HOME_CLUSTER_SOURCE_s ・ STOPSTATION_CLUSTER_SOURCE_c
をEHによって示す。
【００３７】
我々は、各ストップステーションクラスタから各ホームクラスタまでの最短のグラフパス、及び各ホームクラスタから各ストップステーションクラスタまでの反対向きの方向の最短のグラフパスを計算することに興味がある。
【００３８】
我々は、最短グラフパスに関して本質的に同じであるロケーションを“統合すること”によって、クラスタリングが我々の方法を最短のグラフパスの計算の実行を大いに改善することを許容することを述べる。例えば、高い団地では、数百の家があり、そして我々の方法はそれらをたった一つのホームクラスタに統合するだろう。このように、最短グラフパスアルゴリズムは、何百で構成する家よりむしろ、たった一つのホームクラスタのための最短グラフパスを計算する必要がある。
【００３９】
しかしながら、ダイクストラアルゴリズムの標準アプリケーションは未だ不十分なパフォーマンスを生む。あのアプリケーションは、いかなる
HOME_CLUSTER_SOURCE_s
の頂点なしに、Ｇ内でそれぞれの
STOPSTATION_CLUSTER_SOURCE_c
からアルゴリズムを走り、そしてそれから、いかなる
HOME_CLUSTER_TARGET_t
の頂点なしに、Ｇ内でそれぞれの
HOME_CLUSTER_SOURCE_s
からアルゴリズムを走る。結合された漸近的時間計算法は
2021509985.tif 000003
である。
【００４０】
我々の方法は、この標準アプリケーションを改善する。我々は、大都会エリアにおいて、同じクラスタリング閾値を与えた際に、ホームクラスタの数が、ストップステーションクラスタの数より非常に多いケース|V H| ＞＞ |V S|が良くあるということを観察する。この観察を利用し、我々の方法は、ホームクラスタからの最短グラフパスを計算するために異なるアルゴリズムを使用する：本方法はＧのエッジを反対向きとし、そして、反対向きのグラフでは、それぞれの
STOPSTATION_CLUSTER_TARGET_c
にとって、ダイクストラアルゴリズム（どんな
HOME_CLUSTER_TARGET_t
頂点もが取り除かれることができる）を使用して全ての頂点
HOME_CLUSTER_SOURCE_s
までの最短グラフパスを計算する。これは望ましい効果を生む、なぜなら我々が反対向きのグラフで、
STOPSTATION_CLUSTER_TARGET_c 
から
HOME_CLUSTER_SOURCE_s
までの全ての最短のグラフパスのエッジを反対向きにするとき、我々は、オリジナルの（反対向きではない）グラフにおいて
HOME_CLUSTER_SOURCE_s
から
STOPSTATION_CLUSTER_TARGET_c
までの最短グラフパスを得られるからである。このように、我々の方法の漸近する置換の複雑さはたった
2021509985.tif 000004
である。実際には、我々の方法は、ソウル大都会エリアのグラフＧのトータルのランニングタイムの大きな削減を提示する。
【００４１】
本方法は、ホームクラスタの数より、ストップステーションクラスタの数が多い|V H| ＜ |V S|という反対のケースでは対称のアルゴリズムを使用する。あのケースでは、本方法は、ストップステーションクラスタからホームクラスタまでの最短グラフパスを計算するときに、エッジを反対向きにする。
【００４２】
一つの形態において、本方法は出発時間を使う。本方法では、前記
STOPSTATION_CLUSTER_SOURCE_c
からの与えられた出発時間にとって、各
STOPSTATION_CLUSTER_SOURCE_c
から全ての
HOME_CLUSTER_TARGET_t
までの最短グラフパスを計算する。あのケースにおいて、本方法は、公共交通乗り物の駅からの前記出発時間を特定することを許容する適切な従来技術のグラフＧＴを使用する；このケースは、時々、時間及び地理的ロケーションに対応する頂点、及びその時間での前記地理的ロケーションから出発する行程期間を代表するエッジを使用して代表される。同様に、本方法は、
STOPSTATION_CLUSTER_TARGET_c
での与えられた到着時間に基づいて反対向きのグラフ内で計算する。最短のグラフパス距離は、これらの到着時間を各
HOME_CLUSTER_SOURCE_s
からの出発時間に変換する。似たグラフが、到着時間が与えられた最短グラフパスを計算するために使用される。適切に構築されたグラフは、期限より前の到着の可能性を計算するために使用することができる。
【００４３】
一つの形態において、我々は、いかなる頂点
STOPSTATION_CLUSTER_SOURCE_c 
やいかなる頂点
STOPSTATION_CLUSTER_TARGET_c
なしにＧＴを延長しない。代わりに、我々は、いかなる頂点
STOPSTATION_s'
を伴う直接のWalkエッジにより、いかなる頂点
HOME_CLUSTER_SOURCE_s
及びいかなる頂点
HOME_CLUSTER_TARGET_t
を接続する。
【００４４】
一つの形態において、我々は、いかなる頂点
HOME_CLUSTER_SOURCE_s
やいかなる頂点
HOME_CLUSTER_TARGET_t
なしにＧＴを延長しない。代わりに、我々は、それぞれの家を示す頂点
HOME_s
を追加し、我々は、Walkエッジにより直接に、いかなる頂点
STOPSTATION_s'
に接続する。
【００４５】
一つの形態において、我々は家をクラスタ化しない。
【００４６】
一つの形態において、我々はストップステーションをクラスタ化しない。
【００４７】
一つの形態において、我々は到着時間が与えられた最短グラフパスを計算する：各ホームクラスタでの到着時間が与えられたストップステーションクラスタからホームクラスタまで、又は各ストップステーションクラスタでの到着時間が与えらえたホームクラスタからストップステーションクラスタまで。
【００４８】
一つの形態において、我々は、例えばA*（Ａスター）検索アルゴリズムなど、ダイクストラアルゴリズム以外のいかなる最短グラフパスアルゴリズムを使用する。一つの形態において、我々は、最短グラフパスのための近似アルゴリズムを使用する。我々は、前記パフォーマンスの改善なしにアルゴリズムを使用するかもしれない。
【００４９】
一つの形態において、幾つかのグラフエッジ重みは、行程期間の代わりに、行程の料金コストを示す。それから我々の方法は、通勤パスの料金コストに基づいて家を検索又は比較する。エッジ重みにはどのような意味も使用することができ、例えば、公共交通乗り物の間の乗り換えの数、待機の期間、待機の料金コスト、又は工程の距離などである。
【００５０】
一つの形態において、我々はマルチ次元コストに基づいて、マルチ目的最適化検索を適用する。例えば、我々は最短グラフパスを検索し、それらの距離が行程期間を示し、そのようにして前記グラフパスを示す料金コストが最大でも閾値である、又は料金コストがペナルティとして前記グラフパスの距離に追加されているとき、である。
【００５１】
一つの形態において、行程パスは、グラフパスによって代表される。我々は、最短グラフパスを使用している最短行程パスの様々な特徴を計算し、例えば前記最短のグラフパスの第一（例えば乗車）又は到着（例えば下車）ストップステーション、前記最短グラフパスの主な乗り換えストップステーション、乗り物の乗り換えの回数、行程（例えばバス1234）の間のほとんどの時間を過ごす乗り物、ストップステーションでのトータルの待ち時間、トータルの徒歩距離、前記特定の最短グラフパスがラッシュアワーの間に典型的に混雑しているか否か、又は前記グラフパスに沿った地理的なロケーションの配列、などである。これらの特徴は、リクエスト処理の間、前記リクエストで特定される条件に一致する特徴の行程パスを選別するために、使用される。
【００５２】
一つの形態において、我々は幾つかのグラフ頂点の間に、２以上のグラフパスを計算する。例えば、頂点uから頂点vの一つのグラフパスは、最大で１つのバスと共になり、そして前記頂点uから前記頂点vまでの他のグラフパスはいずれの地下鉄とも共にならず、しかし最短のグラフパスよりわずかに１０分以上長くなる。
【００５３】
一つの形態において、我々は、様々なフィルタリング条件に一致するグラフパスを計算する。例えば、最大で１の乗り換え、又は最大で特定の徒歩期間を有するグラフパスである。
【００５４】
一つの形態において、我々は家と公共交通駅の間の最短の行程を計算するためにルーティングエンジン（例えば従来技術）を使用する。このように、我々は時々、現行のセクション4.4.1に記述された前記グラフを使用する。
【００５５】
セクション4.4.1の記述された本方法は、各家から各ストップステーションまでの最短の行程、及び反対向きの最短行程を計算する。次に、我々は効果的な蓄積のためのデータ構造、及び我々の方法によって使用される最短の行程データの処理を記述する。
４．４．２  最短行程の蓄積
【００５６】
一つの形態において、我々の方法は、ベクトル形式で行程期間を蓄積する。本方法は、s1, . . . , snとしてストップステーションクラスタを配列し、例えばランダム規則など幾つかの規則で、h1, . . . , hmとしてホームクラスタを配列する。一つの形態において、これらの配列は固定される。それぞれのsiにとって、本方法は前記ホームクラスタ配列
2021509985.tif 000005
を用いて、siから前記ホームクラスタまでの最短の行程期間のベクトルを蓄積し、その結果、座標j, vi[j]で前記ベクトルの値はti,jであり、これは前記ストップステーションクラスタsiから前記ホームクラスタhjまでの前記最短の行程期間に等しい。説明のために図６を参照のこと。
【００５７】
前記ホームクラスタの配列は、各ホームクラスタまでの最短の行程期間の計算を簡易化する。例えば、もし通勤者がストップステーションクラスタsi1及び加えてストップステーションクラスタsi2から行く必要があるなら、我々は単純にベクトルvi1 及び vi2座標点を加算し、そして結果の合計は両方のストップステーションクラスタから各ホームクラスタh1, . . . , hmまでのトータルの行程期間を含む。
【００５８】
一つの形態において、本方法は、同じホームクラスタ配列を用いて、家からストップステーションまでの、反対向きの行程の期間を蓄積する。すなわち、本方法は、ベクトル
2021509985.tif 000006
を蓄積し、その結果、v´i [j] = t´i,jがホームクラスタhjからストップステーションクラスタsiまでの前記最短の行程期間である（前記交通に関して：たとえ行程が反対方向に向かうとしても、前記ベクトルv´iは必つ１のストップステーションクラスタのためである）。
【００５９】
一般に、同じストップステーションクラスタsiの２つのベクトルは等しくなく、vi≠v´iであり、なぜなら、家までの最小行程期間は家からとは異なる（行程は一般に対称ではない）。しかしながら、一つの形態において、本方法は２つのベクトルのたった一つを計算及び蓄積し、一方の代わりにそれを使用し、時間と空間をセーブすることができる。一つの形態において、本方法は２つのベクトルの座標点重み付け平均を蓄積し、最悪の場合のエラーを減らす。前記重みは0.5にセットされて、又は特定のホームクラスタからの行程、又は例えばリクエスト頻度に基づいて特定のホームクラスタへの行程を好む。
【００６０】
一つの形態において、本方法はコンピュータメモリの1バイトを使用して、0から254の署名されていない整数として示され、未知の又はあまりに大きな行程期間を示す255を伴い、最も近い分に丸められた行程期間を蓄積する。この蓄積は、ベクトル演算及び飽和算数（例えばAVX-512命令集合、又はＧＰＵイントリンシクス）のサポートで現代のコンピュータハードウェアを使用して効率的なベクトル加算を可能にする一方、最大で1/2分の実用的に許容可能なレベルでのエラーを保ち、及び4時間を超えるまでの一般的な行程期間をカバーする。どんな他の丸めも使用され、例えば秒の期間が１２０で割り算されて、2分の粒度で期間を示す整数に丸められる。
【００６１】
一つの形態において、、本方法は、クラスタにとってではないベクトルを蓄積する。例えば、s1, . . . , snの幾つかがストップステーション（ストップステーションクラスタではない）を示し、又はh1, . . . , hmの幾つかが家（ホームクラスタではない）を示す。
【００６２】
一つの形態において、本方法は、行程期間を蓄積したベクトルの他のフォームを使用する。例えば、ハッシュマップ、又は（座標の、値の）リストである。これらの疎らなフォームは、多くの未知の又はあまりに大きな行程期間があるときに有利なものとなる。
【００６３】
一つの形態において、本方法はホームクラスタ配列h1, . . . , hm,に従うベクトルを使用して、又は例えばハッシュマップ、又は（座標の、値の）リストなどのベクトルの他のフォームを使用して行程パスを蓄積する。これらの行程パスは、リクエストによって特定される条件に一致する特徴の行程パスを選別するリクエスト処理の間、使用される。
４．５  １の通勤パスの行程期間
【００６４】
我々は、我々の方法がいかにどのような通勤パスの最短の行程期間を計算するかを記述する。ホームクラスタＨから、k ≧ 1の職場を通って、ホームクラスタに戻るという通勤パスH→W1→W2→ . . . →Wk→Hを考える。我々は、全てのＨにとって、この通勤パスの最短の行程期間を発見したい。これは高額かもしれない、なぜならホームクラスタの数は非常に大きくなり、例えば数メートルのクラスタリング半径を与えられて500,000である。しかしながら、我々の方法は、劇的に検索を加速する技術を紹介する。本方法は、図７に示すように、どのような通勤パスもホームインディペンデントパート及びホームディペンデントパートに分解する。
４．５．１  中間パート：行程W1→W2→ . . . →Wk
【００６５】
本方法は、ホームクラスタを除いた行程W1→W2→ . . . →Wkにとっての最短行程期間を見つける。各セグメントWi→Wi+1において、本方法は、交通システム（例えば、徒歩を含む、地下鉄及びバス乗車、乗り換え、WiからWi+1までの直接徒歩を含む）を使用してWiからWi+1までの最短の行程期間を計算するルーティングエンジン（例えば従来技術）に問い合わせる。それから、本方法は異なるiを通して最短の行程期間を合計する。結果としての合計は、
2021509985.tif 000007
によって示される。ここで（ｋ−１）回のみ前記ルーティングエンジンへの問い合わせが必要とされる。この数は家の数に依存しない。
【００６６】
一つの形態において、本方法は前記ルーティングエンジンに問い合わせるとき、出発時間、到着時間、又はリクエストの他の部分を使用する。
【００６７】
次に、本方法は、通勤パスのオープンジャウパートにとっての最短行程期間を計算する：ホームクラスタを含む２つのセグメントH→W1及びWk→H がある。この計算は、特に素早くする必要があり、なぜならその結果は全てのホームクラスタにとって必要とされるためである。
４・５・２  出発パート：行程H→W1
【００６８】
本方法は、HからW1までに至る２つの方法を考える。説明のため図８を参照のこと。第一方法は、直接徒歩である。H及びW1が近所のとき、本当の最短行程はたびたび直接徒歩となる。このように、本方法は徒歩(H →W1)の最短徒歩期間を計算するための徒歩エンジン（例えば従来技術）に問い合わせる。第二方法は交通システムを使用することである。本方法は、セットＡによって示され、W1から例えば2000ｍなどの閾値距離内のストップステーションクラスタを見つける。前記セットＡは、全てのストップステーションクラスタ（図８中ではA = {s1, s2, s3}）の{s1, . . . , sn}のサブセットである。本方法は、Ａ内の各siにとっての、最短徒歩期間walk(si →W1)を取得するための徒歩エンジンに問い合わせる。H及びW1が近所にないとき、真の最短行程は度々、前記セットＡのストップステーションを通過し、そしてそれから対応する徒歩に沿って続く。我々が適用する2方向アプローチにより、その結果の行程期間は度々、最短行程期間である。
【００６９】
前記２方向アプローチは、各ホームクラスタに適用されることができる。我々は、連続するホームクラスタからストップステーションクラスタsiの最短行程期間を含むベクトルv´iを思い出す。従って、本方法はデータベースからベクトルv´iを取得し、また以下の等式
2021509985.tif 000008
（等式１）
を使用することにより、ホームクラスタhjからの最短行程期間を計算する。
【００７０】
一つの形態において、本方法は、ホームクラスタHj からW1までの距離が2000ｍ等の閾値以下であるときに限って、又はホームクラスタHjからW1までの行程期間が閾値以下であるときに限って、walk(Hj→W1)を計算する。そのようなホームクラスタのセットはＪによって示される。
【００７１】
一つの形態において、v´のベクトル代表のため、本方法は、以下としてv´に対するベクトル演算を使用して、全てのホームクラスタからの行程期間を一緒に計算する。
2021509985.tif 000009
【００７２】
一つの形態において、本方法は数学公式を使用し、
2021509985.tif 000010
ここにおいて、前記“+”演算はベクトルの各座標で数を値に加算し、及び前記“min” 演算は幾つかのベクトルを通しての各座標での最小値を計算する。
【００７３】
行程期間のベクトル(a1, . . . , am)は、
2021509985.tif 000011
によって示される。
【００７４】
PathFromHomeDurationsを計算するための擬似コードの一例は、図１０において説明される。
【００７５】
一つの形態において、uint8ナンバーフォーマットがaj, v´i [j]又はwを蓄積するために使用される。一つの形態において、数のユニットが分で蓄積される。一つの形態において、v´i [j] + wの合計, ここでjはいくつか,が0から例えば255などの閾値の範囲内において飽和算数を用いて実行される。一つの形態において、被加数v´i [j]が最初により広範な数のフォーマット、例えばfp16フォーマット又はuint16フォーマットに変換されて、そしてそれから加算の間の算術オーバーフローを防止するために、wに加算されるのみである。一つの形態において、算数公式に含まれる幾つかの計算が、ベクトル演算（テンソル演算を含む）、例えばハードウェアにサポートされたAVX-512命令集合、又はＧＰＵイントリンシクスなどのための少なくとも１つの指令を使用して実行される。一つの形態において、算数公式に含まれる幾つかの計算は分割され、前記分割は並行に実行される。
【００７６】
一つの形態において、本方法は例えばKD-treeなどの最近接点データ構造を、リクエスト処理の間にセットＡを素早く計算するために、ストップステーションクラスタロケーションに関して使用する。
【００７７】
一つの形態において、本方法は、セットＡを、例えば最大で１００など、最も近いW1であるストップステーションクラスタの最大での一定の数に限定する。
【００７８】
一つの形態において、本方法は、セットＡを、例えば2000ｍなど、W1までの最大での或る一定の距離の徒歩内のストップステーションクラスタの限定する。
【００７９】
一つの形態において、本方法は、各ホームクラスタロケーションから閾値内のポイント及びホームクラスタロケーションの間の徒歩の最短期間を予め計算し、又はストップステーションクラスタロケーションからの閾値距離内のポイント及びステーションクラスタロケーションの間の徒歩の最短期間を予め計算する。それから、リクエスト処理の間、本方法は徒歩エンジンに問い合わせず、しかし代わりに前記予め計算された徒歩期間を使用する。
【００８０】
一つの形態において、徒歩の最短期間は、どのような障害も無視した測地線ラインを使用して推定される。これは、精度を犠牲にしてwalk(si→W1)の計算をスピード化する。
【００８１】
一つの形態において、行程パスは等式１に使用される。例えば、もしユーザリクエストが乗り物乗り換えの回数を制限する条件を特定するなら、我々は前記等式のsi 及び jを選別する：我々は行程パスに蓄積された乗り換えの回数を調査し、そしてその数が前記制限を超える場合に、我々は等式中の前記特定のsi 及び jを無視する。
【００８２】
一つの形態において、我々がv´iでしたように、ストップステーションsiによる行程期間のグループ化が、データアクセスパフォーマンスを改善する。実際、セットＡが前もって知られていないユーザリクエストに依存するものだが、セットＡ中の各siにとって、予想通りに、行程期間の大半の数はアクセスされる必要がある。
【００８３】
一つの形態において、iの集合のためのベクトルv´iは、異なる処理ユニットを通して、ランダムに分配される。これは、ベクトル(a1, . . . , am)を計算することの待ち時間を減らす、というのもセットＡを含むストップステーションは度々、前記処理ユニットを通して均等に分割されるからである。
【００８４】
一つの形態において、iの集合のためのベクトルv´iは、処理ユニット内で地理的にグループ化される。これは、ベクトル(a1, . . . , am)を計算することの情報量を減らす、というのもセットＡが度々、互いに近くに位置するストップステーションから成るという事実のため、データ転送の必要の減少のためである。
４．５．３  到着パート：行程Wk→H
【００８５】
前記計算はアナログで、しかしベクトルv´ではなくｖを使用する。説明のために図９を参照のこと。本方法は、Wk (図９中において B = {s4, s5})から閾値距離内のストップステーションクラスタのセットＢを計算するそれから、本方法は
2021509985.tif 000012
（等式２）
として、ホームクラスタhjまでの最短の行程期間を計算する。
【００８６】
上記同様に、一つの形態において、前記vのベクトル代表の理由で、本方法は等式２に応じてｖに関したベクトル演算を使用して各ホームクラスタまでの行程期間を一緒に計算する。一つの形態において、本方法は数学公式
2021509985.tif 000013
を使用する。
【００８７】
行程期間の前記ベクトル(b1, . . . , bm)は
2021509985.tif 000014
によって示される。
【００８８】
本方法は、セクション4.5.2中と似たような形態を使用する。例えば、一つの形態において、本方法は、前記ベクトル(a1, . . . , am)の一部及び前記ベクトル(b1, . . . , bm)の一部を一緒に計算するベクトル演算を使用する。
４．５．４  出発、中間、及び到着パートの結合
【００８９】
最後に、本方法は各ホームクラスタの通勤パスの最短の行程期間を計算する。本方法は単に２つのベクトルを加算して、座標での値を変更する。我々は、
2021509985.tif 000015
（等式３）
によって結果のベクトルを示す、ここで第一の“+”はベクトルの座標点加算であり、及び第二の“+”はベクトルの各座標での値への数の加算である。
【００９０】
一つの形態において、本方法は、どんな通勤パスに沿った地理上のロケーションからの特定の出発時間、又はそこへの特定の到着時間が与えられた行程期間を計算する。
【００９１】
一つの形態において、本方法は、特定の通勤パスとしてPathDurationsを予め計算する。例えば、本方法は、学校である各Ｗにとっての
2021509985.tif 000016
及び
2021509985.tif 000017
を計算し及び蓄積する。リクエスト処理の間、本方法は、等式１、等式２及び等式３でそれらを計算する代わりに、データベースから予め計算されたベクトルを取得する。
【００９２】
一つの形態において、PathDurationsの値は変えられる。学校Ｗがある特定の家のみが子供たちをその学校に送ることができるという風に特定する区域要求を有することを考える。これは、単純に、その学校の区域外のこれらのホームクラスタにおいてベクトルPathFromHomeDurations(→W)の座標値を無限に設定することによって単純に達成でき、また同様にベクトルPathToHomeDurations(W→)の座標値を設定する。Ｗが限定された配達エリアを伴うレストランであるとき、又は政府事務所が限定された管区を有するとき、同じような変更がなされる。このように、変更された値が蓄積され、リクエスト処理の間、取得される。
【００９３】
一つの形態において、我々の方法は、ベクトルvi, v´iの座標値に、又はPathDurationsに対して任意の“操作”機能を適用する。例えば、これは災害によって影響を受けた特定の経済区域の大都市エリアのある部分から、又は当該部分までの通勤のための交通料金を削減する政府の政策を実行するのを手助けすることができる。アプリケーションは、リクエストを処理（例えば、グローバル政策）する前、又はリクエストを処理（例えばユーザに個別化された政策）している間、実行される。
【００９４】
一つの形態において、本方法はホームクラスタのサブセットのためのPathDurationsを計算する。例えば、前記サブセットはユーザリクエストによって特定される家の特徴の条件から決定される。一つの形態において、我々はホームクラスタの配列h1, . . . , hmを選別し、その結果これらのサブセットは度々、データ転送を減らす前記配列の短いセグメント中に存在する。
４．６  一つの家の検索
【００９５】
我々の方法は、通勤を使用している家をいかに効果的に検索するかを教える。我々は例えば、我々が一つの家の一般的な検索リクエストを紹介する以前に、第一に幾つかの例の検索リクエストを示す。
４．６．１  重み付けされた合計リクエスト
【００９６】
週に５階geo1に位置する場所に働きに行く一方の親、及び週に3回geo２に位置する場所に働きに行く他方の親のある家族を考える。この家族は、週間で短い行程期間の家を見つけたい。我々は、下記の
2021509985.tif 000018
のように、2つのベクトルの重み付けられた合計として各ホームクラスタの、前記家族にとっての週間の行程期間を見つける。
４．６．２  最小リクエスト
【００９７】
家から働くシングルマザーで、子供を学校に送っていることを考える。その母は、学校Ｅからどの学校でも近くなる家を発見したい。我々は、下記の
2021509985.tif 000019
として、ベクトルの座標点最少として各ホームクラスタにおいてその子供にとっての一日の行程期間を見つけることができる。
４．６．３  一つの家の一般検索
【００９８】
一つの形態において、我々の方法はリクエストを通勤パスの配列path1, . . . , pathqとして定義し、ｑは何でもよく、及びファンクションドライバ：ｑの数のベクトルを一つの数にマップするRq → R。本方法は行程期間ベクトル（ゼロから、予め計算されたベクトルを受信することによって、又は両方）
2021509985.tif 000020
及び、ファンクションドライバの座標点を、各ホームクラスタのため“派生された”行程期間を伴うベクトルを生成するために、ベクトルに適用する。
2021509985.tif 000021
【００９９】
一つの形態において、前記ファンクションドライバは、重みW1, . . . , wqにおいて、重み付けられた数の合計
2021509985.tif 000022
である。重みは正又は負になることができる。もし行程期間が行程のお金の料金として解釈されるのなら、例えば、もし通勤者が特定の通勤（例えば小包の配達）を実行することからの利益を得ることを予測されるなど、それなら負の重みはお金の取得として解釈される。重みは通勤パスの相対的な重要性を示すことができ、例えば、社長の通勤パスは、第一線マネージャの通勤パスよりもより高い重みを有する。
【０１００】
一つの形態において、前記ファンクションドライバは、数の最小
2021509985.tif 000023
である。
【０１０１】
一つの形態において、前記ファンクションドライバは、重み付けられた合計及び最小である。
2021509985.tif 000024
【０１０２】
一つの形態において、前記ファンクションドライバは、例えば条件付きの
2021509985.tif 000025
又はいかなるアルゴリズムである。
４．７  2以上の家の比較
【０１０３】
我々の方法は、通勤を使用する複数の家をいかに効果的に比較するかを教える。我々は、我々が一般的な比較リクエストを紹介する前に、幾つかの例に関しての方法を説明する。
４．７．１  現在の家
【０１０４】
現在、家に住んでいる家族を考える。前記家族のメンバーは、職場、学校、及び他の場所への特定の通勤パスを有する。前記家族は、他の家に引っ越しすることを考え、現在の家のトータルの行程期間及び他の見込みの家のトータルの行程期間を比較したい。我々の方法は、そのような比較をかなりシンプルにする。
【０１０５】
一つの形態において、本方法は、前記家族の現在の家Sのホームクラスタhjを含む、全てのホームクラスタにとっての行程期間を計算する。
2021509985.tif 000026
本方法は、それから“差分”ベクトルに応答する：本方法は、各座標
2021509985.tif 000027
からｊ番目の座標での値を引く。“差分”ベクトルの座標での負の値は、前記座標に対応する家が、現在の家Sと比較してより短い行程期間を有することを示す。
【０１０６】
一つの形態において、本方法は前記現在の家にとっての幾つかの通勤パス、しかし他の家にとっての他の通勤パスを使用する。このように、本方法は、“万が一我々が職場を変えて、幾つかの他の家に引っ越ししたら。新しい通勤期間を我々の現在の通勤期間をどのように比較するのか”というもしかしてシナリオを家族が評価することを助ける。
４．７．２  2以上の家の一般比較
【０１０７】
母と父が同じ職場に（職業を変えない）通勤を続けなくてはならないが、子供は学校を変えることができる家族を考える。両親及び母方の両親という2つの家族の他の例を考える。彼らは、お互いに30分程度以内に2つの家を探したい、その結果、一つの家は病院の近く、及び他の家は特定の学校や職場の近くである。我々の方法は、より簡単に、そのような家と他の家との比較をする。
【０１０８】
一つの形態において、本方法は、通勤パスの範囲でのホームクラスタにとっての行程期間PathDurationsを計算する。
2021509985.tif 000028
それから、本方法は、セクション4.6.3でのような座標点の操作をしない“一般化された”ファンクションドライバを適用し、しかし代わりに一緒に全てのq'm行程期間で操作して、そして1以上の数のベクトルを生成する。言い換えると、前記一般化されたファンクションは、幾つかのｙでの
2021509985.tif 000029
である。
４．８  検索又は比較
【０１０９】
一つの形態において、ファンクションドライバは、例えばランダム化されたアルゴリズムなど、どのような入力も受ける（例えば、通勤パス、最短行程パス、最短行程期間、家やユーザリクエストによって特定されるいかなる条件）いかなるアルゴリズムであり、及びそのような出力（例えば、最短行程期間によってソートされ、ユーザ条件を満たす家を含む“トップリスト”、及びユーザの状況をも満たす最短の行程を有する）をも生成する。
４．９  変形
【０１１０】
多くの調整や変形は前記形態の範囲及び精神から離れない従来技術の当業者において明らかである。我々は、説明のため幾つかの変形を提示する。
４．９．１  行程の延長
【０１１１】
一つの形態において、本方法は不完全な最短行程を計算し、そしてそれから選択されたホームクラスタにそれらを延長する。これは、追加の処理及び蓄積内で減少のため蓄積、及びベクトルvi及びv´i中での幾つかのホームクラスタによる処理を取引する。
【０１１２】
本方法は、交通システムの幾つかの要素であるホームコネクタを決定する。一つの形態において、前記ホームコネクタは、セクション4.4.1で記述されたクラスタとは異なるかもしれないホームクラスタ又はストップステーションクラスタである。それから、本方法は、セクション4.4のこれらと似た形態を用いて、前記ストップステーションクラスタ及び前記ホームクラスタの間の最短行程を予め計算してデータベースに蓄積する。
【０１１３】
リクエストが受信されるとき、本方法はリクエストに含まれる職場Ｗ及び選択されたホームクラスタの間の最短行程を計算する、この目的のため、本方法は前記職場の近所のストップステーションクラスタを決定し、セクション4.5と同じように、前記職場Ｗ及びホームクラスタの間の最短行程を計算するため、前記近所のストップステーションクラスタ及び前記ホームコネクタの間の予め計算された最短行程を取得する。一つの形態において、この計算はこれらのセクション4.5.2及び4.5.3と似たベクトル演算を使用する。それから、これらの最短行程は、前記職場Ｗ及び選択されたホームクラスタの間の最短行程を形成するため、ホームクラスタを超えて延長される。これは単純に、各ホームクラスタにとって、例えば2000ｍ以内など、前記ホームクラスタの近所のホームコネクタを通過する最少延長行程（単なる徒歩ではないかもしれない）を見つけること、そして時には前記職場Ｗ及び前記ホームクラスタ（セクション4.5.2及び4.5.3と似た）の間の直接最短行程を見つけることにより達成され得る。一つの形態において、重複エリアで、本方法は前記ホームコネクタ及び前記ベクトルvi及びv´iを使用する。
【０１１４】
延長行程のパフォーマンスは、ホームコネクタの総数に比例し、そしてまた、選択されたホームクラスタの近所のホームコネクタの数に比例する。一つの形態において、前記延長は、前記2つの量が低くなるような、大都会エリアのまばらな場所に使用される。一つの形態において、本方法は、パフォーマンスコストファンクションを、（１）ホームコネクタを決定、（２）ホームクラスタの選択、及び（３）前記選択されたホームクラスタのそれぞれの近所のホームコネクタのサブセットを決定するために使用する。
４．９．２  車による通勤
【０１１５】
一つの形態において、我々は公共交通によるものよりむしろ、車での通勤パスの行程期間を計算する。これは、前述のセクションへの簡単な変更によって達成される。
【０１１６】
家にとっての交通システムを予め処理するとき、セクション4.4、公共交通システムのグラフとなるＧＴを取得するのに変えて、我々はカードライブシステムのグラフとなるＧＴを取得する。このカードライブグラフは、例えば従来技術より得ることができる。あのグラフは、道路上の地理的ロケーションを示す頂点、及び車の運転又は車の向きを変えることを示すエッジ、例えばラッシュアワーの間など一日の様々な時間での運転期間に関するデータを含むエッジなどを有する。
【０１１７】
我々は、ＧＴを延長する。各ホームクラスタsにとって、我々は頂点
HOME_CLUSTER_SOURCE_s
及び
HOME_CLUSTER_TARGET_s
を追加する。我々は、各ホームクラスタを、少なくとも１つのrにおいて頂点
CONNECTOR_r
を追加することによって、例えば100ｍなどの閾値距離内である幾つかの道路に接続する。一つの形態において、前記頂点は閾値内である道路上でのホームクラスタロケーションの最短距離プロジェクションを示し、前記道路は前記ホームクラスタに割り当てられたカーパーキング内にあるかもしれない。前記頂点は、重み0を伴うZeroにラベル化されたエッジによって、２つのホームクラスタ頂点に接続される。前記頂点はまた、前記道路のセグメントの端点を示す頂点に接続される。ストップステーションクラスタを追加する代わりに、我々はするべきではなく、なぜなら今ＧＴは地下鉄駅もバス停をもモデルにしておらず、我々はs´ 及びt´の集合のため頂点
REPRESENTATIVE_SOURCE_s'
及び
REPRESENTATIVE_TARGET_t'
を追加し、これらの頂点は、最短行程中でのよく生じるロケーションを示し、前記ロケーションは例えば従来技術をしようして得られる。これらの頂点は、クラスタを示す。これらの頂点は、エッジを使用する他の頂点と適切に接続される。
【０１１８】
我々は、前記延長GTを、可能ならセクション4.4.1で述べられたこれらに似た形態を用いて、各
REPRESENTATIVE_SOURCE_s'
から各
HOME_CLUSTER_TARGET_s
及び各
HOME_CLUSTER_SOURCE_s
から各
REPRESENTATIVE_TARGET_t'
までのグラフパスの最短期間を計算するために使用する。これらの行程期間は、セクション4.4.2で述べられたベクトルフォームvi及びv´i内に蓄積される。
【０１１９】
通勤パスの行程期間を計算するとき、我々はセクション4.5内での徒歩を使用する代わりに、カーライドを使用する。
【０１２０】
行程の出発パートのため、我々はセクション4.5.2に以下の変更を作る。walk(Hj→ W1)の代わりに、我々は例えば従来技術より得られたホームクラスタHjからW1までのカーライドの期間を使用し、一つの形態において、前記Hj及びW1の間の距離が閾値以上のとき、我々は代わりにこの期間を無限大に設定する。前記セットAは、W1から閾値距離内の頂点
REPRESENTATIVE_TARGET_t'
のセットである。各頂点si∈Aにとって、我々は例えば従来技術を使用して、siから W1までのカードライブ期間を計算する。
【０１２１】
行程の到着パートにとって、我々は、しかしセクション4.5.3ではない似た変更を行う。walk(Wk→Hj)の代わりに、我々は例えば従来技術より得られたW1からホームクラスタHjまでのカーライドの期間を使用し、一つの形態において、前記Wk及びHjの間の距離が閾値以上のとき、我々は代わりにこの期間を無限大に設定する。前記セットBは、Wkから閾値距離内の頂点
REPRESENTATIVE_SOURCE_s'
のセットである。各頂点si∈Bにとって、我々は例えば従来技術を使用して、W1からsi までのカードライブ期間を計算する。それから我々はこれらの変更を等式２に適用する。
【０１２２】
我々は、セクション4.5で述べた他の形態を使用する。例えば、我々は測地線を用いてカーライドの行程期間を推定する。
【０１２３】
セクション4.6の検索フレームワークは、どんな種類の乗り物が各通勤パスにとって使用されるべきかを制限することを許容するため単純に延長されることができる。結果として、例えば、我々は、週に５階geo1に位置する場所に車で働きに行く一方の親、及び週に3回geo２に位置する場所に公共交通で働きに行く他方の親のある家族にとって、各家における通勤パスの行程期間を決定することができる。
【０１２４】
セクション4.7の比較フレームワークは単純に延長されることができる。結果として、例えば、我々は人が車によって通勤する新しい家を検索でき、公共交通による現在の行程期間と比較をすることができる。我々の方法の結果は、引っ越しのために、車を購入するインセンティブとして使用されるかもしれない。
４．９．３  他の手段による通勤
【０１２５】
一つの形態において、本方法は、例えば、徒歩のみ、自転車のみ、高速バス及び徒歩のみ、地下鉄及び徒歩のみ、高速バス、地下鉄及び徒歩のみ、共有バン及び徒歩のみ、ボート、飛行機などの他の手段による通勤パスを使用する。我々は単純にセクション4.9.2で述べられたこれらに類似する変形を使用する。一つの形態において、本方法は、他の家及び行程の他の手段、及び現在の家及び現在の行程の手段を比較して利益を説明して、ユーザにこれらを推薦する。
【０１２６】
与えられたグラフでの最短グラフパスは、前記グラフの様々な頂点の地理的なロケーションを知ることなしに計算されることができる。このように、一つの形態において、本方法はその様々な要素が地理的ロケーションを欠いた交通システムを使用する。
【０１２７】
前記交通システムは、物理的に動く物体を必要としない。本方法は単に前記交通システムの要素の間のルート又はルート距離を決定することができる必要がある。このように、データを移動するコンピュータネットワークは、交通システムの一例であり、この交通システムは、ワイヤ／ライン（道路に類似して）、及びハブ／スイッチ（停止／方向変更に類似して）のこれらの交通要素から成る。交通システムの多くの他の例は、従来の当業者に明らかである。
４．９．４  行程パスの条件
【０１２８】
我々は、行程パスにおける様々なフィルタリング条件を単純に理解することができる。例えば、我々は地下鉄ラインの間に乗り換えがなく、しかしホームクラスタ及びステーションクラスタの間で徒歩を有するグラフGを構築できる。セクション4.9.2で述べたこれらの類似する変形に沿って、本方法は、それから通勤者が家及び職場（前記家及び前記職場は共に１つの地下鉄ラインの地下鉄駅から徒歩距離内であるという必要はない）の間の乗車の間ずっと座るとき、検索又は比較をする。単純に、我々はGを構築し、最大で一つの乗り換えに、又は地下鉄―バス乗り換え、又はバス―地下鉄乗り換え、又はタイムウインドウなしに起こる乗り換え、又は通勤者によって共通に使用される行程パスのタイプにグラフパスを限定するために最短のグラフパスアルゴリズムを変更する。行程パスをフィルタリングするための他の変形は、従来の当業者に明らかであるとして、我々の方法の範囲内になる。
４．９．５  家の条件
【０１２９】
一つの形態において、本方法は、家の様々な特徴のフィルタリング条件を受信し、そして前記条件に一致する特徴の家を検索又は比較する。前記特徴は、タイプ（例えば隣接する家、又は構想マンション）、取引タイプ（例えば販売又は賃貸）、価格、不動産エージェントの業務委託料、税、最大銀行ローン額、ベッドルーム又はバスルームの数、家のエリア／サイズ、窓の地理的方向、家の階数、前記建物の階数、典型的な月の管理費などである。単純に、本方法は各家の特徴リストを保持し、条件を与え、前記条件に一致する特徴の家を決定する。これら家と一致する前記行程期間は、ホームクラスタの行程期間から得られる。家をフィルタリングするための他の変形は、従来の当業者に明らかであるとして、我々の方法の範囲内になる。
４．９．６  メタ検索又は比較
【０１３０】
一つの形態において、本方法は、従来の検索又は比較リクエスト及び応答のアンサンブルを使用して家を検索又は比較する。これは、メタ方法（それ自体を使用する方法）をみなされる。それは、例えば提案された新しい不動産の発展の価値を評価するために有用である。
【０１３１】
我々は、前記メタ方法の形態を記述する。我々は、通勤パスpath1, . . . , pathuの幾つかの数uを受信する。一つの形態において、前記通勤パスは家を検索又は比較するためにコンピュータサービスの有用なログから来て、各通勤パスは前記サービスの異なるユーザによって提供されるかもしれない。各通勤パスpathkのため、我々はセクション4.5に従い全てのホームクラスタPathDurations(pathk)の行程期間を計算する。それから、我々は前記行程期間を処理するアグリゲータを適用する。一つの形態において、各通勤パスpathkのため、我々は重みWkのベクトルを受信する。一つの形態において、各重みは、ユーザがホームクラスタに対応して家をクリックする可能性であり、それは不動産資産の条件、又は前記ユーザのリクエスト内で特定される行程パスの条件によって影響されるかもしれない。それから、我々は下記公式内として、座標点の集合を計算する。
2021509985.tif 000030
ｊ番目の集合は、ホームクラスタHjの平均重み付け行程期間である。一つの形態において、ｊ番目の集合は、完全な大都会エリアのトータル行程期間に対するホームクラスタの標準化された寄与を示し、ある意味、前記大都会エリア内でのホームクラスタの中心である。なぜなら、我々の方法はPathDurations(pathk)を素早く計算し、我々は素早く前記集合を計算できる。これは、通勤に関して各不動産資産の好ましさの素早い計算を可能にする。
【０１３２】
メタ方法の多くの他の形態では、従来の当業者において明らかである。一つの形態において、通勤パスは家及び職場の地理的ロケーションから生成される。一つの形態において、前記重みは最も低い行程期間のホームクラスタの幾つかの数のとってはゼロでなく設定され、他はゼロに設定される。一つの形態において、データ科学者は、もしかしてシナリオを評価し、なぜなら我々の方法の有利点であり、これらのシナリオは素早く評価される。一つの形態において、前記アグリゲータは任意のアルゴリズムであり、例えば、相違、分位、累積分配ファンクション、又は閾値を超える可能性を計算するものである。
４．９．７  ２以上の家を含む通勤パス
【０１３３】
一つの形態において、通勤パスは2以上の家を含む。これは、例えば2以上の家族のための家を一緒に検索又は比較するときに、有効である。
【０１３４】
一つの形態において、H1及びH2は2つのホームクラスタである。我々は、H1から出発し、しかしH1とは異なるだろうH2で終了するいかなるH1→path→H2の通勤パスの行程期間を計算することができる。我々は単純に等式１のH1に対応するｊ、しかし等式２のH2に対応するｊを使用する。
【０１３５】
一つの形態において、我々は両方のベクトル(a1, . . . , am)及び(b1, . . . , bm)を予め計算し、そしてそれから我々は、単純にH1に対応する座標(a1, . . . , am)での値を、Hjに対応する座標(b1, . . . , bm)の値に加算することにより任意の2つのホームクラスタHi及びHjの行程期間、プラス前記パス（Hi及びHjから独立している）の中間パートの行程期間を見つける。我々は、m2ペアから、ホームクラスタのどんなペアの行程期間が直線O(m)空間のみを使用して定数O(1)内に見つけられることを認める。これはなぜなら行程期間の付加構造のため、前記パスがいかなる2つのホームクラスタの間のセパレータとして働くという事実である。
【０１３６】
一つの形態において、ホームクラスタのセットは、H1のために許可されるホームクラスタのセットが、H2のために許可されるホームクラスタのセットとは異なるかもしれない。例えば、ユーザ条件は、H1が市の東にあることを限定し、一方H2が市の西側にあることを限定する。この場合、我々はｍとは異なる距離ｍ´のベクトル(b1, . . . , bm´ )を使用する。
【０１３７】
より一般的には、本方法はホームクラスタH1→path1→H2→path2→ . . . → pathk-1→ Hk，k ≧ 2のいかなる配列のために行程期間を計算する。予め計算することを使用して、これはO(k)時間、及びO(m・k)空間でなされることができる。
【０１３８】
一つの形態において、通勤パスはこの例の通勤パスH1→path1→Hx→Hy→path2→H2内として、ホームクラスタHx→Hyの間の直接行程を含む。この例で、我々の方法は計算を3つのパートに分割し（１）H1→path1→Hxの行程期間の計算、（２）Hx→Hyの行程期間の計算、及び（３）Hy→path2→H2の行程期間の計算である。パート（１）及び（３）は、現行のセクション4.9.7中で前述した方法を使用して実行される。パート（２）は単純に職場としてのHx又はHyのどちらかを観念的に扱うことにより実行できる。例えば、Hxに対応する座標でのベクトルv´iを使用して、我々は前記ホームクラスタHxから各ストップステーションクラスタまでの行程期間を所得して。これらは予め計算されたベクトルv´i, 1≦i≦nの縦の一列として取得されることができる。それから我々は、セクション4.5.2に類似して、例えば図８及び等式１をみて、完全行程を形成するHyからHyまでの閾値距離内で各ストップステーションクラスタから延長する。我々の方法のために予め計算されるために、前記（３）は前記閾値距離内のストップステーションクラスタの数に比例した時間内で実行される。一つの形態において、前記ホームクラスタが前もって知られているために、我々は、ホームクラスタの各ペアの間の行程期間を予め計算し、そしてそれから単純に定数O(1)時間で行程期間を取得する。自然に、類似の分割がホームクラスタの間の1以上の直接行程を含むいかなる通勤パスにも適用する。
４．９．８  空間探索
【０１３９】
我々の方法は、パフォーマンスの高い空間探索アルゴリズムを紹介する。通勤者が特定のコストを有する特定の通勤パスH1→path→H2に沿って移動するときのケースを考え、前記コストファンクションは、2つの家H1及びH2に依存する。通勤者は、前記コストを最小化する家H1及びH2を探す。これは、例えば家族が2人の両親の職場ロケーション（H1及びH2）を同時に変えたいとき、一方で２つの体の問題として知られる家族の現行の家のロケーション（パス内）からのトータルの通勤期間を最小化するときに有用である。
【０１４０】
空間探索の一つの形態では、勾配降下アルゴリズムである。コストファンクションは微分可能関数となることができ、例えば、固定パスが与えられ、前記ファンクションは入力として２つの家H1及びH2を取り、そして通勤パスH1→path→H2の行程期間によって乗算された２つの家H1及びH2の間の距離を、出力として返す（このファンクションは、例えば家及び外挿の地理的ロケーションを介した、家のペアの別々のドメインの外側に適切に延長されることができる）。勾配降下アルゴリズムの与えられたステップで、前記アルゴリズムは、与えられた家のペアのコストファンクションの勾配を計算し、そしてそれから前記アルゴリズムの次のステップのために勾配の方向に沿って家のペアを選ぶ。前記勾配は、例えば、2つの値を必要とする2点公式を使用して、コストファンクションの値を使用して計算される。一つの形態において、前記勾配降下アルゴリズムの出力は、前記勾配が水準に十分に小さいものを有する場合に家のペアである。
【０１４１】
一つの形態において、我々は直線O(m)空間を消費しているベクトル(a1, . . . , am) 及び(b1, . . . , bm) を予め計算し、各ステップで我々の方法は定数O(1) 時間中の勾配を計算する。このために、前記勾配降下アルゴリズムは、度々素早い進歩を作る。
【０１４２】
一つの形態において、我々は(a1, . . . , am)及び(b1, . . . , bm)を予め計算しない、しかしその代わりに要求に応じて、等式１及び等式２毎に必要とされる値を生産する。そのようなアプローチは、家の数がとても多くて(a1, . . . , am)又は(b1, . . . , bm)の予めの計算が実行不可能であるときに使用される。
【０１４３】
一つの形態において、空間探索アルゴリズムは、家の上での制約を有する。例えば、もし我々が一つの家へのラウンドトリップを要求するならば、制約はH1＝H2である。我々はH1のために許容される、又はH2のために許容される地理的領域を制約する。
【０１４４】
一つの形態において、空間勾配アルゴリズムは、H1→path又はpath→H1の一つの家のみを含む通勤パスを使用する。他の形態において、空間探索アルゴリズムは、セクション4.9.7のような、2以上の家を含む通勤パスを使用する。
【０１４５】
一つの形態において、コストファンクションは、家及び職場に依存する。例えば、そのようなコストファンクションは、個人が消費された時間やお金のブレンドを最小化するために探しているときに使用されることができる。一つの形態において、前記コストファンクションは、H及びWの間の行程期間、プラスHの賃貸の料金コスト、マイナスWによって支払われる給料、可能ならば成分の相対的重要性を示す重み、である。一つの形態において、我々の方法の有利な点のために、勾配加工はそのようなコストファンクションの下で家及び職場を探すための検索するために効果的に使用される。
４．１０  一般的なケース
【０１４６】
一つの形態において、単語“家”及び“職場”は任意の意味に関する意味を有する。例えば、人が、前記人の現在の家の近くに位置する職場を探しているケースを考える。前記人は、異なる家に引越ししたくない、しかし単に現在の家に近くの職場を見つけたい。この場合、我々の方法が単純に適用される。大都会エリアを通して人々が働くサイト（例えば様々なオフィスや工場など）の範囲が与えられると、本方法は全てのワークサイトクラスタ及び各ストップステーションクラスタの間の行程期間を計算する。このように本方法は、“通勤を使用する職場検索又は比較”方法と見做すことができる。一つの形態において、本方法はユーザの特定の仕事タイプ、又は給料レンジ、及び前記ユーザの現在の家からの行程期間に基づいて職場サイトを検索又は比較する。他の例として、本部を新しいロケーションに引っ越したい会社を考える。我々の方法は、大都会エリアを通しての前記本部の全ての新しいロケーションのトータルでの“会社の行程期間”を計算するために使用される。このように、前記会社は、どのように全ての新しいロケーションが従業員の通勤に影響するを決定する。新しいロケーションは、例えば（１）最悪のケースの通勤期間が限定され、及び（２）平均通勤期間が低く、このために個人や社会的目的がを満たしているものが選択される。
【０１４７】
結局、我々の記述は、主に検索又は比較目的として行程期間に関して話した。しかしながら、本方法は他のいかなる目的、例えば行程の料金コスト、メートル距離、行程パスの特定の特徴又は属性、例えば乗り換えの数、又は徒歩距離、又は例えば価格、サイズ、又はタイプなどの家の特徴などを使用することができる。一つの形態において、これは単純にグラフを構築して、適切なエッジ重みを設定することにより達成される。様々な目的は、例えば行程の料金コストによってペナルティされる行程期間を最小化する家を検索するなど、マルチ次元コストに基づくマルチ目的最適化検索に結合される。
【０１４８】
一般に、本方法は任意のサイトS1, . . . , Sm（サイトは前述セクションでは家と呼ばれた）及び任意の場所P1, . . . , Pk（場所は前述のセクションでは職場と呼ばれた）を使用し、本方法は幾つかの前記サイトで始まり又は到着し、また前記サイト及び前記場所を含んでいる任意のルート明細（ルート明細は前述のセクションでは通勤パスと呼ばれた）によって特定されるものとして、前記場所の幾つかを訪れるルート又はルート距離（前述のセクションではルートは工程の記述と呼ばれ、またルート距離は工程の距離と呼ばれた）を使用して前記サイトS1, . . . , Smを検索又は比較する。前記検索又は比較はセクション4.9で述べたいかなる変形も使用する。このように、本方法はルート又はルート距離、又はそれらの代表に応答する。本方法の一つの形態で計算される情報は、本方法のいかなる形態への入力として、繰り返し使用される。
４．１１  コンピュータシステム
【０１４９】
本発明の形態の一つは、通勤を使用して不動産資産を検索又は比較するコンピュータシステムである。我々は、図１１において前記コンピュータシステムの形態を説明する。
【０１５０】
我々は、我々の記述中で用語“モジュール”を使用する。当該技術において前記用語は、幾つかの特定の機能を提供するコンピュータ（サブ）システムを意味する。コンピュータシステムを前記特定のモジュールに分割する我々の選択は、例示であり強制ではない。 当該技術の当業者は、前記システムは本発明の範囲から離れない他のマナーでモジュールに編成されることを理解する。
【０１５１】
一つの形態において、どのような通勤パスに沿った各工程は、特定の出発時間を有する。
【０１５２】
前記システムの１のモジュール（1101）は、データソース（1102）から交通システムに関するデータを読み、グラフＧを構築する。前記構築の間、前記モジュールは不動産データソース（1103）から家に関するデータを取得し、そして他のデータソース（1104）から近くのホームクラスタ及びストップステーションクラスタの間の最短徒歩を取得する。グラフＧは乗り物に関する時間データを含む。前記モジュールは、いかなる
HOME_CLUSTER_SOURCE_s
の頂点（1105）なしに前記グラフを出力し、及びまたいかなる
HOME_CLUSTER_TARGET_s
の頂点しかし反対向きのエッジを有する（1106）ものなしに前記グラフを出力する。前記モジュールはまた、いかなる与えられた地理的ロケーションからの閾値距離内のストップステーションクラスタを見つけることができる最も近い近所のデータ構造（1107）を構築する。
【０１５３】
しばらくの間、前記システムの他のモジュール（1109）は2つのグラフを読み、そして最短グラフパスを計算する。前記モジュールは、一つの形態では5分毎で、一日内での時間の範囲を考える。各出発時間において、前記モジュールは（1105）を使用してストップステーションクラスタからホームクラスタまでの最短行程期間を伴う一つのテーブル（1110）、及び（1106）を使用してホームクラスタからストップステーションクラスタまでの最短行程期間を伴う他のテーブル（1111）を生成する。一つの形態において、最も近い分で往復される、各行程期間がC++プログラミング言語のuint8_t タイプとして蓄積され、未知の又はあまりに大きな行程期間を示すために255の最大値を伴い保存される。一つの形態において、前記テーブルはＨＤＤに行優先順でのＨＤＤディスク上に展開される。一つの形態において、前記システムは、ＨＤＤディスク、ＳＤＤディスク及びメインメモリを含むキャッシュ階層を使用する。一つの形態において、前記テーブル及びそれらのパートは、例えばデルタ圧縮などのいかなる圧縮アルゴリズムを使用して圧縮される。我々は、ホームクラスタ、及びストップステーションクラスタから成るいかなるペアのため、行程期間が度々期間の間、似ていることを観察する。この類似はまた、前記ペアの近所で度々行う。一つの形態において、我々はホームクラスタの配列h1, . . . , hmを選択し、その結果、前記配列に近接するいかなるhi 及びhi+1が度々ホームクラスタの近所であり、又はストップステーションクラスタの配列s1, . . . , snを選択し、その結果、前記配列に近接するいかなるsi 及びsi+1が度々ホームクラスタの近所である。
【０１５４】
前記モジュール（1101）及び（1109）は連続で操作する。結果として、前記システムは出発時間が与えらえれた行程期間に関しての新鮮なデータを維持する。
【０１５５】
同時に、パス期間モジュール（1112）はPathDurationsを計算する。出発時間を伴う通勤パスを与えると、前記モジュール（1113）は、すでに予め計算されたいかなる関係するPathDurationsを問い合わせる。どのような失われたものもゼロから計算され、前記モジュールは、どのような家をも含まない通勤パスのパートのPathNonHomeDurationを計算するためにナビゲーションデータソース（1114）に問い合わせる。前記モジュールはまた、行程期間PathFromHomeDurations、最も近いストップステーション（1107）を問い合わせることにより、家を含むPathToHomeDurations、徒歩（1108）、及び出発時間でのホーム行程期間ベクトル（1110及び1111）を計算する。
【０１５６】
同時に、前記リクエスト処理モジュール（1115）は不動産資産を検索又は比較する。どのようなリクエスト（1116）もが通勤パス及び出発時間に沿った地理的ロケーション、及びドライバを含む通勤パスを含む。リクエストがユーザから受信されるとき、前記モジュールはパス期間モジュール（1112）からPathDurationsを取得して、前記ドライバに適用して、前記ドライバ（1117）の出力を示す情報を伴う前記ユーザに応答する。
【０１５７】
本発明の側面はハードウェアの形態、ソフトウェアの形態、又は2つの組み合わせの形態のフォームを取るかもしれない。例えばフローチャートのブロックなど、本発明のステップは、機能または最適化に応じて、規則に外れて実行され、部分的に同時に又はキャッシュから保存される。側面は、連続的なシステムのフォーム、又は並行／分配システムのフォームを取り、ここで各構成要件は幾つかの側面を、他の構成要件と共に重複に具現化し、及び構成要件は例えばいかなる種類のネットワークを使用して伝える。本発明は、特定のプログラミング言語を参照して記述されない。本発明の側面のための操作を実行しているコンピュータプログラムは、例えばC++,Java又はJavaScriptなどのいかなるプログラミング言語でも記述される。いかなるプログラムが、例えば中央処理ユニット（CPU）又はグラフィック処理ユニット（GPU）、及びメモリや蓄積装置に関連した任意のハードウェアプラットフォームで実行する。プログラムは、アンドロイド又はiOSオペレーティングシステム, 又は例えばFirefox, Chrome, Internet Explorer, 又はSafariのウェブブラウザを含み、しかしこれに限定するものではないが、1以上のソフトウェアプラットフォームで、本発明の側面を実行する。
４．１２  コンピュータサービス
【０１５８】
本発明の形態の１つは、通勤を使用して不動産資産を検索又は比較するためのコンピュータサービスである。前記サービスは、例えばスマートフォンアプリケーション又はウェブブラウザなどのユーザアクセス装置を介してユーザに有用である。それは、本発明はこれらの装置に限定されないことは当該技術の当業者において明らかであるだろう。それは、我々の図面中のサービスの提示が、本発明の範囲を外れることなく、変更（例えば再配置、リサイズ、色や形の変更、構成要件の追加又は削除）されることは明らかであるだろう。
【０１５９】
一つの形態において、本サービスはスマートフォンアプリケーションを介してアクセスされる。説明のために図１２を参照のこと。ユーザはリクエストを入力する。一つの形態において、前記リクエストは以下を含む。
・例えば“３つのベッドルーム、高い建物、高い階”などの不動産資産（1201）の好ましい特徴
・通勤パス（1202,1203，“タウンゼントの学校又はジェリコ高校”1204）、出発時間（1205,1206）、及び各通勤パス（1207,1208）の頻度、及び
・ユーザの現在の家（1209）の地理的ロケーション
【０１６０】
応答で、前記サービスは行程期間を示す情報を返す。例えば、前記サービスは前記ユーザリクエスト（1210）に一致する不動産資産の地理的ロケーションを描写する。前記サービスは、これらの不動産資産から行程期間は、現在の家からの行程期間と比較して、いかなるかを描写する。前記サービスは、例えば価格など、各不動産資産に一致するサマリーを描写する。不動産資産は、二次元マップ上に積み重ねられ、その結果より低い行程期間を伴う不動産資産が、より高い行程期間を伴うこれらの不動産資産の上に現れる。マップ上にクラッタがあるとき、前記サービスは代わりにクラッタ又は不動産資産を描写し、そのサイズは、前記クラッタ中の不動産資産に相関する。前記クラッタは、例えば数、又はクラッタ中の不動産資産の典型特徴などのサマリーを表示する。
【０１６１】
一つの形態において、前記サービスは最短行程期間を伴う不動産資産を描写する。不動産資産のサマリーがまた描写される（1211）。前記不動産資産は行程期間によってソートされる。
【０１６２】
一つの形態において、前記サービスは領域の最小など、大都会エリアの各領域からの行程期間を示すために色を使用した“ヒートマップ”を描写する。ヒートマップは、どのような家における行程期間及びユーザの現在の家における行程期間の間の差分を描写する。一つの形態において、ヒートマップは不動産資産のユーザの要求される特徴に一致する不動産資産のみを描写する。
【０１６３】
一つの形態において、前記サービスは行程期間（1212）のヒストグラムを描写する。前記ヒストグラムは、一軸に行程期間、他の軸にこの行程期間を生む不動産資産の一部を有する。一つの形態において、ヒストグラムは、不動産資産のユーザの好ましい特徴に一致する不動産資産のみを描写する。一つの形態において、ユーザは、ヒストグラムを通じてヒストグラムのいかなるセクションにもスクロール（1213）でき、前記サービスはこの特定のセクションの行程期間のための結果を描写する。一つの形態において、本方法は例えば円グラフなどヒストグラムの他のフォームを使用する。
【０１６４】
一つの形態において、ユーザは例えばユーザスライダ（1214）を使用して、例えばトータルの徒歩期間、乗り換え回数を限定することにより、行程パスを制限する。
【０１６５】
一つの形態において、前記サービスは不動産資産の行程期間のサマリーを描写する。
【０１６６】
一つの形態において、前記サービスは以下の少なくとも一つをユーザに応答する：
（ａ）マップ上に描写された場所、又はサイトの地理的ロケーション
（ｂ）場所、又はサイトのための出発時間又は到着時間
（ｃ）サイトのサマリ：サマリーはサイトの名前または住所、サイトの価格、又はサイトのサイズの少なくとも１つを含む
（ｄ）近所のサイトのクラスタを形成する際とのサマリ―
（ｅ）近所のサイトのクラスタの描写、近所のサイトのクラスタ中のサイトの数に相関されている描写のサイズ
（ｆ）ルート距離のz-インデックス順序でのサイズの積み重ね、マップ上に描写された、より短いルート距離、より高い前記積み重ね
（ｇ）ルート又はルート距離の情報：情報は以下の少なくとも1つを含む：（i）ルート：距離、期間、料金コスト、又は待ち期間；（ii）乗り物の名前、乗り物の道路、徒歩パス、駅、ターン、又は公共交通乗り物の乗り換え駅；（iii）以下の地理的ロケーション：料金コスト、スピード、待ち期間、乗り物、乗り物道路、徒歩パス、駅、ターン、又は公共交通乗り物の乗り換え駅
（ｈ）サイトを横切るルート距離のヒストグラム：又はマップ上に描写されたサイトを横切るルート距離のヒートマップ
（ｉ）最少ルート距離；サイトを横切る最少ルート距離のヒストグラム；又はマップ上に描写されたサイトを横切る最少ルート距離のヒートマップ
（ｊ）重み付けルート距離：サイトを横切る重み付けルート距離のヒストグラム；又はマップ上に描写されたサイトを横切る重み付けルート距離のヒートマップ
（ｋ）差分ルート距離：サイトを横切る差分ルート距離のヒストグラム；又はマップ上に描写されたサイトを横切る差分ルート距離のヒートマップ
（ｌ）ドライバによって返された出力の描写
（ｍ）工程の料金コストの限定の下、サイトを横切るルート距離を最小化するサイト
（ｎ）ユーザによる特定される条件により強制される上記（ａ）〜（ｍ）のひとつ
（ｏ）これらのサイト、ルートの間から、サイトのトップリスト、及びルート距離によってソートされた条件を満たすルート距離
４．１３  特許請求の範囲に関する注意事項
【０１６７】
当該技術の当業者は様々な変形を作り、また代用が本発明の範囲から離れることなしに、本質的に同等のものを伴い作られる。その上、特定の状況は、その範囲から離れることなしに、本発明の教示に適用される。従って、本発明が開示された形態を参照して述べられたという事実にも関われず、本発明はこれらの発明に限定されるべきではない。むしろ、本発明は、付属の請求の範囲内に落ちる全ての形態を含む。
４．１４  用語解説
【０１６８】
我々は、請求の範囲内に記載の選択されたフレーズの用語解説を含み、また明細書に参照を例として示す。これらの参照は網羅的であることを意図せず、他の参照が存在する。前記詮索されたフレーズは、前記フレーズが請求の範囲内に最初に現れる順に従う。
【０１６９】
前記請求の範囲はまた下記のフレーズを使用し、それらの意味を我々は説明する。
１．フレーズ“少なくとも１つのＡ”は“#A ≧ 1, ここで#Aの数はA”と等しい。
２．フレーズ“1以上のＡ”は“#A ≧ 1, ここで#Aの数はA”と等しい。
３．フレーズ“複数のＡ”は“#A ≧ ２, ここで#Aの数はA”と等しい。
４．フレーズ“少なくとも２のＡ”は“#A ≧ ２, ここで #Aの数はA”と等しい。
５．フレーズ“Ａ又はＢのひとつ”は“#A + #B = 1, ここで#Aの数はA、#Bの数はB”と等しい。
６．フレーズ“Ａ又はＢの少なくともひとつ”は“#A + #B ≧ 1, ここで#Aの数はA、#Bの数はB”と等しい、及び
７．フレーズ“Ｂ又はＣの少なくともひとつ”は“少なくとも１のＡ、ここで各Ａは（Ｂ又はＣ）”と等しい。
2021509985.tif 000031
2021509985.tif 000032
2021509985.tif 000033
【図１】
2021509985.tif 000034
【図２】
2021509985.tif 000035
【図３】
2021509985.tif 000036
【図４】
2021509985.tif 000037
【図５】
2021509985.tif 000038
【図６】
2021509985.tif 000039
【図７】
2021509985.tif 000040
【図８】
2021509985.tif 000041
【図９】
2021509985.tif 000042
【図１０】
2021509985.tif 000043
【図１１】
2021509985.tif 000044
【図１２】
2021509985.tif 000045
【手続補正書】
【提出日】令和2年8月28日(2020.8.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
少なくとも１のサイトを検索又は比較する方法であって、
前記方法は、交通システム内の前記少なくとも１のサイト及び少なくとも１の場所の間の少なくとも１のルート又はルート距離を使用しており、
前記方法は、
（a）前記交通システムに含まれる少なくとも１の代表を受信し、ここにおいて、多くの代表は、多くても、予め定められた割合で乗算された前記交通システムのサイズであり、
（b）前記少なくとも１のサイト及び前記少なくとも１の場所を含むリクエストを受信し、及び
（c）前記少なくとも１のルート又はルート距離を使用して得られた情報を伴う前記リクエストに応答する、
ことを含み、
前記方法はステップによって特徴付けられ、ここにおいて、前記ステップは以下の事を含む、
（d）少なくとも１の予め計算されたルート又はルート距離を決定し、それをデータベースの中に蓄積し、
ここにおいて、それぞれの第一の予め計算されたルート又はルート距離は、前記少なくとも１のサイト内に含まれる第一サイト及び前記少なくとも１の代表に含まれる第一の代表の間で、前記交通システム内の行程の記述を含み、及び
（e）前記少なくとも１のルート又はルート距離を計算し、前記少なくとも１のルート又はルート距離は、前記少なくとも１のサイト内に含まれる出発／到着サイト、及び前記少なくとも１の場所内に含まれる出発／到着場所の間の前記交通システム内の行程の記述を含み、
ここにおいて、前記出発／到着サイト、又は前記出発／到着場所は、前記少なくとも１の代表に含まれず、及び、
ここにおいて、前記計算は、
i. 前記少なくとも１の代表に含まれる少なくとも１の近所の代表を決定し、ここにおいて、各近所の代表及び前記出発／到着場所の間の行程の距離は、第一閾値内であり、
ii. 前記少なくとも１の予め計算されたルート又はルート距離から、前記出発／到着サイト及び前記近所の代表の間の第二の予め計算されたルート又はルート距離を取得し、
iii. 前記近所の代表及び前記出発／到着場所の間で、前記交通システム内での行程の記述を決定する。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００３５
【補正方法】変更
【補正の内容】
【００３５】
第一の延長は、ストップステーションのクラスタを導入する。本方法は、いかなるクラスタリングアルゴリズムを使用しているストップステーションをクラスタ化する；一の形態において、本方法は、２つのストップステーションの地理的距離が最大で5メートルなどの閾値であるとき、又は２つのストップステーションの間の行程期間が最大で閾値であるとき、２のストップステーションを１のクラスタとして置く。我々は、我々が前記クラスタの中心など、クラスタ内での地理的ロケーションを意味するとき、クラスタのロケーションを参照する。それぞれのストップステーションクラスタｃにとって、本方法は、2つの頂点
STOPSTATION_CLUSTER_SOURCE_c
及び
STOPSTATION_CLUSTER_TARGET_c,
及び前記クラスタを、FirstWaitGetOnとラベル化された
STOPSTATION_CLUSTER_SOURCE_c→STOPSTATION_s'
であるGTのストップステーションに接続したエッジ、及びS´が前記クラスタC内であるときにはいつでも、そのようなS´にとって、Zeroでラベル化された
STOPSTATION_s'→STOPSTATION_CLUSTER_TARGET_c
を追加する。前記エッジはゼロ重みを有する。結果のグラフは、頂点VC及びエッジECを有するGCによって示される。全てのｃにとって頂点
STOPSTATION_CLUSTER_SOURCE_c
のサブセットは、VSによって示される。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００３６
【補正方法】変更
【補正の内容】
【００３６】
第二の延長は、家のクラスタを導入する。本方法は、どのようなクラスタリングアルゴリズムを使用して家をクラスタ化する；一の形態において、本方法は、ストップステーションをクラスタ化するときと同じアルゴリズムを使用する。同様に、我々はホームクラスタのロケーションを参照する。それぞれのホームクラスタにとって、本方法は頂点
HOME_CLUSTER_SOURCE_s
及び頂点
HOME_CLUSTER_TARGET_s
を追加する。本方法は、それぞれのホームクラスタを、徒歩を使用しているストップステーションクラスタに接続する。特に、本方法は、Walkによってラベル化されたエッジ
HOME_CLUSTER_SOURCE_s→STOPSTATION_CLUSTER_SOURCE_c
もし前記ホームクラスタｓのロケーションから前記ストップステーションクラスタｃの前記ロケーションまで徒歩があるならば、どのようなｓ及びｃにとっても、徒歩の期間に設定されたエッジ重みを有し、及びWalkによってラベル化された“反対向きのエッジ”
STOPSTATION_CLUSTER_TARGET_c→HOME_CLUSTER_TARGET_t
もし前記ストップステーションクラスタｃから前記ホームクラスタｔのロケーションまでの反対向きの方向の徒歩があるならば、どのようなｃ及びｔにとっても、徒歩の期間に設定されたエッジ重みを有する。一の形態において、本方法は、例えば４ｋｍ／時間など特定のスピードで、例えば1時間など最大も閾値で続く最短の徒歩に、徒歩を限定する。結果のグラフはGによって示される。我々は、全てのｓにとっての、頂点のセット
HOME_CLUSTER_SOURCE_s,
をVHによって示す；及び全てのｓ及びｃにとってのエッジのセット
HOME_CLUSTER_SOURCE_s→STOPSTATION_CLUSTER_SOURCE_c
をEHによって示す。
【国際調査報告】
2021509985.tif 000046
2021509985.tif 000047
2021509985.tif 000048