How to achieve efficient matching between massive goods and business districts

まとめ

交通状況、商業施設の分布、住宅地の分布を総合的に考慮し、都市を商圏に分割します。杭州の一部エリアにおける商圏分割の例を次の図に示します。

商品はユーザーが投稿した GPS 情報に基づき、マップ上にランダムに分布するポイントデータです。ユーザーがある商圏内にいる場合、アプリはその商圏内に GPS が位置する商品をユーザーにレコメンドします。正確なレコメンドサービスを実現するには、各商品がどの商圏に属するかを算出する必要があります。

データベースにおいて、商圏は複数の点で囲まれた面データです。これらの面データは形状と大きさが異なり、互いに重なり合うことはありません。商品は GPS でマークされたポイントデータです。膨大な商品と商圏の帰属関係を、どのように迅速かつ効率的に判定できるでしょうか。従来の直接的な手法では、幾何学的な空間関係の計算式を用い、大量データに対して「点と面」の関係を直接計算し、各商品が各商圏内に位置するかどうかを判定します。

現在、商品データは 10 億件あり、日々急速に増加しています。全国の全都市の商圏総数は約 10,000 件で、各商圏のサイズは 10 から 80 までの頂点数で構成されます。幾何学的な点面関係演算を直接使用すると、必要な計算量は基本操作換算で約 200 京回に達します。このアプローチで Alibaba Group 内部のオフラインコンピューティングクラスターを使って計算を試みましたが、2 日以上実行してもクラスターは計算を完了できませんでした。

アルゴリズム改善後、GeoHash 完全一致に基づくアルゴリズムを採用し、GeoHash 近似一致と小規模な幾何学演算による精密マッチングを組み合わせることで、計算量を大幅に削減し、オフライン環境での大量ポイント-面データの包含関係計算を効率的に実現しました。10 億件の商品と 10,000 件の商圏データをマッチングする場合、1 日以内に結果を得られます。

■ポイントデータの GeoHash の原理とアルゴリズム

GeoHash は地理座標をエンコードする手法で、2 次元座標を文字列にマッピングします。各文字列は特定の矩形を表し、その矩形内のすべての座標が同一の文字列を共有します。文字列が長いほど精度が高く、対応する矩形範囲は小さくなります。

地理座標をエンコードする際、緯度の初期区間 [-90, 90] と経度の初期区間 [-180, 180] から始め、対象の経度と緯度がそれぞれ左区間と右区間のどちらに属するかを計算します。左区間に属する場合は 0、右区間に属する場合は 1 を付与します。その後、前ステップで得られた区間に対して同じ手法で半分に探索を続け、次のバイナリコードを取得します。コードの長さが業務の精度要件に達したら、「経度は偶数位、緯度は奇数位に配置する」というルールに従い、得られたバイナリコードを交互に結合して新しいバイナリ文字列を生成します。最後に base32 対照表に基づき、バイナリ文字列を文字列に変換し、対象の地理座標に対応する GeoHash 文字列を得ます。

座標「30.280245, 120.027162」を例に、GeoHash 文字列を計算します。まず緯度をバイナリエンコードします。

1. [-90, 90] を 2 分割し、「30.280245」が右区間 (0, 90) に属する場合、第 1 位は 1 です。
2. (0, 90] を 2 分割し、「30.280245」が左区間 (0, 45] に属する場合、第 2 位は 0 です。
3. 上記のステップを繰り返すことで、対象範囲はますます小さくなり、範囲の両端点は「30.280245」に近づきます。

次の図のプロセスは、最初の数回の反復の詳細を示しています。上記のプロセスに従い、エンコード桁数が業務の精度要件を満たすまで反復を続けます。完全な 15 桁のバイナリコード反復表は次のとおりです。

得られた緯度のバイナリコードは 10101 01100 01000 です。

同じプロセスに従い、経度のバイナリコードを計算します。具体的な反復の詳細は次のとおりです。得られた経度のバイナリコードは 11010 10101 01101 です。

「経度は偶数位、緯度は奇数位」のルールに従い、緯度と経度のバイナリコードを交互に配置します。完成したバイナリコードは 11100 11001 10011 10010 00111 00010 です。後続の base32 エンコーディングではバイナリ 5 桁が 32 進数 1 桁に対応するため、5 桁ごとに 10 進数に変換すると 28, 25, 19, 18, 7, 2 となります。base32 エンコーディングテーブルを参照すると、対応するエンコーディングは wtmk72 です。

上記の結果は geohash.org/ のウェブサイトで検証でき、検証結果は次のとおりです。検証結果の先頭数桁は計算結果と一致しています。バイナリ方式でバイナリエンコーディングを取得する際により多くの反復を行えば、検証サイトと同様に、より正確で長い桁数の結果が得られます。

GeoHash 文字列の長さと精度の対応関係は次のとおりです。

■面データの GeoHash エンコーディング実装

前節で説明した標準的な GeoHash アルゴリズムは、2 次元の点座標に対応する GeoHash コードの計算にのみ使用できます。本シナリオでは、面データ (GIS での POLYGON ポリゴンオブジェクト) に対応する GeoHash コードも計算する必要があり、拡張アルゴリズムが必要です。

アルゴリズムのアプローチは次のとおりです。まず対象ポリゴンの最小外接矩形 MBR を求め、MBR の南西角の座標に対応する GeoHash コードを計算します。次に GeoHash エンコーディングの逆算法で、このエンコーディングに対応する矩形の GeoHash ブロックを逆算します。この GeoHash ブロックから開始し、東方向と北方向に同じサイズの隣接 GeoHash ブロックをループで探索し、探索した GeoHash ブロックが MBR の範囲を完全に超えるまで続けます。このようにして得られた複数の GeoHash ブロックのうち、エッジ上のブロックは対象ポリゴンと完全に交差しない場合があり、この部分のブロックは計算で除外し、後続の不要な計算量を削減します。

上記の例で得られた最終結果の高解像度画像を次に示します。青い GeoHash ブロックは元のポリゴンと部分的に交差し、オレンジ色の GeoHash ブロックは元のポリゴンに完全に含まれています。

■隣接 GeoHash ブロックの高速探索アルゴリズム

前節の面データ GeoHash エンコーディングのフローチャートで緑色とオレンジ色でマークされた 2 つのステップは、それぞれ東方向と北方向の隣接 GeoHash 文字列を探索する処理です。

従来の手法では、現在の GeoHash ブロックの逆解情報に基づき隣接ブロック内部の点を求め、その点に対して GeoHash エンコーディングを実行して隣接ブロックの GeoHash エンコーディングとします。次の図に示すように、「wtmk72」の周囲 8 つの隣接ブロックのコードを計算する場合、まず GeoHash 逆算法で「wtmk72」の 4 頂点の座標 N1, N2, N3, N4 を逆算し、次にこれら 4 点を使って右側の隣接ブロック内部の任意の点の座標 N5 を計算し、N5 に対して GeoHash エンコーディングを実行します。得られた「wtmk78」が求める右側の隣接ブロックのエンコーディングです。同じ手法で、「wtmk72」の周囲 8 つの隣接ブロックのコードを合計で取得できます。

この手法はデコード 1 回と再エンコード 1 回が必要で時間を消費します。特に指定された GeoHash 文字列が長く、多数のループが必要な場合に顕著です。

GeoHash エンコーディングテーブルの規則を観察し、GeoHash エンコーディングで使用される Z オーダー曲線の特徴を組み合わせることで、テーブル参照により隣接 GeoHash 文字列を高速に探索する手法が検証されています。

GeoHash 文字列「wtmk72」を例にします。対応する 10 進数は「28, 25, 19, 18, 7, 2」で、バイナリに変換すると 11100 11001 10011 10010 00111 00010 です。そのうち、w は 11100 に対応し、5 つのバイナリ桁はそれぞれ「経度 緯度 経度 緯度 経度」を表します。t は 11001 に対応し、5 つのバイナリ桁はそれぞれ「緯度 経度 緯度 経度 緯度」を表します。ここから推測できるように、奇数位の文字 ('w', 'm', '7') が表すバイナリ桁はそれぞれ「経度、緯度、経度、緯度、経度」に対応し、偶数位の文字 ('t', 'k', '2') が表すバイナリ桁は「緯度、経度、緯度、経度、緯度」に対応します。

'w' のバイナリ値 11100 を方位に変換すると「右 上 右 下 左」となります。't' のバイナリ値 11001 は「上 右 下 左 上」となります。

この文字と方位の変換関係に基づき、奇数位の文字と位置の対照表は次のようになります。偶数位の文字と位置の対照表は次のようになります。ここで非常に興味深い現象が確認できます。奇数位の対照表と偶数位の対照表には転置と反転の関係があります。

上記 2 つの文字と位置の対照表を使えば、各文字の周囲 8 つの文字を素早く見つけられます。指定された GeoHash 文字列の周囲 8 つの GeoHash 値を計算する際、文字列の末尾文字がその方向で境界を超えない場合、先頭の文字はそのまま維持し、末尾文字をその方向の隣接文字に置き換えます。末尾文字がその方向で対照表の境界を超える場合、まず末尾から 2 番目の文字のその方向の隣接文字を計算し、次に末尾文字のその方向の隣接文字を計算します (対照表は環状に隣接文字が接続されています)。末尾から 2 番目の隣接文字もその方向で対照表の境界を超える場合、さらに前の文字のその方向の隣接文字を計算します。以下同様に続けます。

上記の「wtmk72」を例に、この GeoHash 文字列の 8 つの隣接文字列を求めることは、実際には末尾文字 '2' の隣接文字を求めることです。'2' は偶数位の対照表を適用し、8 つの隣接文字は '1', '3', '9', '0', '8', 'p', 'r', 'x' です。そのうち 'p', 'r', 'x' は対照表の下境界を超えており、偶数位対照表を上下に接続して環を形成することで得られる隣接関係です。したがって、境界を超えるこれら 3 つの「下」の隣接文字について、末尾から 2 番目の文字の下方向の隣接文字を求める必要があります。すなわち '7' の下の隣接文字です。'7' は奇数なので奇数対照表を適用します。対照表中の '7' の「下」の隣接文字は '5' です。よって「wtmk72」の 8 つの隣接 GeoHash 文字列は「wtmk71」「wtmk73」「wtmk79」「wtmk70」「wtmk78」「wtmk5p」「wtmk5r」「wtmk5x」となります。この隣接文字列の高速アルゴリズムを使用することで、前節のフローチャートにおける面データ GeoHash エンコーディングアルゴリズムの効率を大幅に向上できます。

■大量ポイントデータと面データの関連付けを効率的に確立する

大量ポイントデータと面データの関連付けを確立するアプローチは次のとおりです。まず上記のアルゴリズムに基づき、マッチング対象の商品の GPS データ (ポイントデータ) と商圏の AOI データ (面データ) について、同じ長さの GeoHash コードを計算します。各ポイントデータは一意の GeoHash 文字列に対応します。各面データは 1 つ以上の GeoHash コードに対応し、これらのコードは「完全包含文字列」または「部分包含文字列」のいずれかです。

a) 各商品の GeoHash 文字列と商圏の「完全包含文字列」を JOIN します。JOIN で得られた結果に出現する データは、「ある商品がある商圏に属する」という確定関係です。

b) 関係が未確定の残りの商品について、これらの商品の GeoHash 文字列と商圏の「部分包含文字列」を JOIN します。JOIN で得られた結果に出現する データは、「商品がある商圏に属する可能性がある」という候補関係です。次に、このバッチのデータの商品 GPS と商圏 AOI データに対して幾何学関係計算を実行し、「商品がある商圏に属する」という確定関係を抽出します。

図に示すように、商品 1 のポイントデータの GeoHash コードは「wtmk70j」で、面データの「完全包含文字列 wtmk70j」との JOIN が成功したため、商品 1 がこの面データに属すると直接判定できます。

商品 2 のポイントデータの GeoHash コードは「wtmk70r」で、面データの「部分包含文字列 wtmk70r」との JOIN が成功したため、商品 2 はこの面データに属する候補です。包含関係の有無は後続の点面幾何学計算で確定します。商品 3 のポイントデータの GeoHash コードは面データのどの GeoHash ブロックコードとも一致しないため、商品 3 が面データに属さないと迅速に判定できます。

実際のアプリケーションでは、大量商品の元の GPS 範囲は全国に散在し、大量の商圏データも全国の異なる都市に分布しています。ステップ a) の処理後、大部分の商品データは既に商圏との帰属関係が確定しています。残りの未マッチング商品データについて、ステップ b) の GeoHash マッチング後、「商品-商圏の幾何学計算」の計算量は、「1 商品 x 全国の全商圏」のデカルト積の規模から「1 商品 x 1 (または数件) の商圏」のデカルト積の規模に縮小され、非常に時間を消費する不要な幾何学演算の大部分を削減します。

実際の適用において、10 億件の商品と 10,000 件の商圏データの場合、本稿の高速アルゴリズムを使用すると、10 億回の GeoHash ポイントエンコーディング + 10,000 回の GeoHash 面エンコーディング + 500 万回の「点が面内にあるかどうか」の幾何学演算のみが必要です。基本操作回数に換算すると約 1,800 億回で、従来の手法に必要な 2,000 億回を大幅に下回ります。Alibaba のオフラインコンピューティングプラットフォームを使用し、本稿のアルゴリズムは 1 日以内にすべての計算を完了します。

なお、指定された点とポリゴンについて、幾何学による包含関係の計算アルゴリズムは複数存在し、最も一般的に使用されるのはレイ法です。簡単に言うと、点からレイを発射し、レイとポリゴンの交点の数が奇数か偶数かを判定します。奇数であれば点はポリゴン内部にあり、偶数であれば点はポリゴン外部にあります。

■拡張

大量の点面データの空間関係分割の問題に対し、本稿では GeoHash を通じて計算量を削減するアプローチを採用しています。これは本質的に空間インデックス化の思想を使用しています。実際、GIS 分野には R 木シリーズ (R 木、R+ 木、R* 木)、四分木、K-D 木、グリッドインデックスなど、さまざまな実用的な空間インデックスが存在します。これらのインデックスアルゴリズムにはそれぞれ特徴があります。本稿のアプローチは点面関係の問題だけでなく、点点関係、面面関係、点線関係、線線関係などの問題の高速処理にも応用できます。たとえば、大量のバス停と道路の帰属関係、複数の道路や鉄道の間に交差があるかどうか等です。