Spatial Analytics at Any Scale With H3 and Photon | Databricks Blogの翻訳です。
本書は抄訳であり内容の正確性を保証するものではありません。正確な内容に関しては原文を参照ください。
離散、ベクトル、ハイブリッドのアプローチの比較
H3のグローバルインデクシングシステムは、様々な地理空間ユースケースにおける空間分析の新たなパターンをもたらしています。最近、Databricksでは、Photonで強化することで、お客様が最も高性能なH3 APIを活用し、任意のスケールでこれらのユースケースに取り組む準備ができるように、ビルトインのH3エクスプレッションを追加しました。本記事では、スケールが問題となる際に、従来のジオメトリドリブンのアプローチよりもH3がベストなパフォーマンスを提供し、洞察に至る時間を改善し、トータルコストオブオーナーシップを削減することを学びます。
空間分析における決定木
空間分析のアプローチを検証する際、取り組みに適したツールを選択できるように、最初にユースケースを理解する必要があります。地理空間分析の一般的なテーマの一つであるモビリティからスタートしましょう。多くの場合、モビリティは人間あるいは自動車として分類されます。小売、交通、保険、公共ポリシーなど、様々なドメインで活用されています。通常、モビリティデータは膨大で、レコードには緯度経度、タイムスタンプ、デバイスIDのフィールドが含まれており、これら全ては高頻度で捕捉されています。小売のサイト選定のケースでは、候補地を決定する助けとなる日中の様々な時間における人や自動車のトラフィックパターンを検討するために、モビリティデータを使いたいと考えることでしょう。さらに、様々な移動アクティビティを検知、理解するために、近隣の境界、都市のブロック、駐車場や建物の敷地のジオフェンス内にあるモビリティのみを参照するジオグラフィックな制約を組み込むかもしれません。
自動走行自動車のユースケースには、自動車AIアプリケーションで求められる非常に高い安全基準[road safety framework、long-haul trucking、EAVs]を満たすための位置トラッキングとコンテキストを踏まえた自動車位置特定を実現するために、GPSからの高密度なセンサーデータ、カメラからのHiDEF動画、LiDARやRADARの分析が含まれます。リアルタイムセンサーデータに対する同様のアプリケーションは、鉄道や海運でも生まれてきています。高密度センサーデータは、装置のオフロードをナビゲートしつつも、生産量を増加させるためのサイト固有の穀物管理のために産業AIを適用するような、精密農業でも活用されています。これらを含む多くのユースケースにおける学際的なアプローチは、ベクトル、ラスター、地理空間科学、気象データフォーマットをブレンドし、様々なルーチンや、温室ガスレベル、霧、雨、氷、雪、風、海面上昇、洪水、地震のような異常気象、地理条件、気象条件に企業や組織が監視、予測、対応できるようにします。
高度にスケーラブルなソリューションからメリットを得る、様々な業界の地理空間ユースケース
地理空間データ分析を効果的にするために、まず初めに最も重要なデータ処理の要素を理解したいと考えることでしょう。どのようにデータを集約するのが問題になるでしょうか？お手元のデータセットの一つにはジオメトリーが含まれているでしょうか？データはシンプル、あるいは複雑でしょうか？実施する分析はどれだけ正確でしょうか？SQLクエリーで活用できるように、空間データをグローバルグリッドインデックスに標準化しようとしているのでしょうか？重要な要素は、データタイプ、スケーラビリティ、精度であり、これらの要素に対するあなたの要件が、ご自身の空間分析アプローチを決定します。
我々はDatabricksレイクハウスプラットフォームで離散空間分析のための地理空間関数を直接実装しており、上述したようなモビリティの例のようにベクトルデータに対してもっともスケーラブルなソリューションを実現しています。H3のみを活用することには、いくつかのトレードオフを伴います。精度はお使いのインデックスの解像度に依存し、(h3_polyfillash3を使うなどして)ポリゴンのインデックス空間への変換は、ジオメトリの境界に対してインデクシングされないギャップを引き起こします。これらのギャップは空間joinの制度を決定づけます。これが、H3による離散空間分析を高度にスケーラブルで、近似分析向けのものであると分類している理由です。
Databricksレイクハウスでは、ベクトル空間分析を可能とするためにインストール、インポートできるいくつかのSparkベースのライブラリがあります。さらに、PythonにおけるapplyInPandasのようなUDFを通じて並列実行で活用できる言語固有のシングルノードライブラリが多数存在します。ジオメトリセントリックのアプローチは高精度の空間オペレーションを実現しますが、大きなトレードオフとしてパフォーマンスが存在し、対応がなされない場合には、データボリュームが増加、あるいは入力ジオメトリーがより複雑になると性能が悪化します。この記事では、ジオメトリセントリックアプローチを改善するためにH3グローバルグリッドインデクシングがある場合とない場合を比較します。
ジオメトリの境界ボックスを用いて階層型ツリーを構成するApache SedonaのQuad-TreeやR-Treeインデクシングのように、多くの空間ライブラリは様々なローカルインデクシングを提供します。EsriのGeoAnalytics Engineは、DBRクラスターにおける高性能空間処理を実現するためのローカルインデクシングを活用する最適化ジオメトリセントリックの処理の例です。ローカルインデクシングのデメリットは、データが変更されるとツリーのバランシングや再構築が必要となり、スケーリングの限界に到達する可能性のあるネストされた検索を必要とするということです。ここでH3が活躍することになり、H3セルIDはジオメトリに対して指定された解像度で一度計算するのみで良く、並列実行に非常に適しています。また、H3セルIDは単一の解像度(12など)や階層的に(h3_toparentを用いてオンザフライで)比較することができます。更なるメリットは、セルIDそれ自身が標準のSQL関数で利用でき、ジオメトリセントリックオペレーションでフィルターとして動作するフィールドデータ(列)となるということです。また、Delta Lakeテーブルに格納されたH3が計算されたカラムは、クエリー時間を劇的に改善するZORDERを用いて最適化することができます。インデックスされていないや最適化されていないという用語を使う際、ローカライズされていないインデックスが最適化されていないことのみを意味するのではなく、我々のテストにおいてH3グローバルグリッドインデックスがないことによるパフォーマンスの損失を特に意味しています。
また、H3のような離散インデクシングと他の数多くのライブラリが提供するジオメトリセントリック空間な空間的時間的述語(ST_)を活用するハイブリッドのアプローチもあります。ハイブリッドアプローチは、純粋なジオメトリセントリックアプローチと同様の精度を得ながらも、より高速であるようにスケールと偏りを解決するトレードオフのバランスをとりますが、H3セントリックアプローチによって達成される近似によるパフォーマンスよりも以前としてある程度は遅いものとなります。
H3セントリック、H3-ジオメトリのハイブリッド、最適化されず / インデックスが作成されないジオメトリセントリックアプローチを用いた離散およびベクトル空間分析を選択するためのフレームワークをウォークスルーする図1の決定木をご覧ください。
図1. スケーラビリティ、精度によって決定される空間joinの決定木
データ規模を大きくした際のそれぞれのアプローチのパフォーマンスをより理解するために、現実世界の例をより深く見ていきましょう。この記事では、地理空間データを取り扱う際の現行のアプローチを説明しますが、プラットフォームに更なるシンプルさ、スケーラビリティ、柔軟性をもたらすために、H3およびジオメトリセントリックアプローチの改善に取り組んでいるということをご承知おきください。続報をお楽しみに。
スケーラビリティの比較
ジオメトリセントリック、H3セントリック、H3-ジオメトリハイブリッドアプローチを比較する基盤を固めるために、NYCメトロポリタンエリアの260程度のタクシーゾーンにおける約1.6Bのトリップピックアップに対するポイントインポリゴンを実行しました(このポリゴンに包含されるポイントは実際には約1.222Bです)。ここでは、3つのアプローチの紹介、ジオメトリセントリックの実行時間の助けとなる比較的小規模なポリゴンによる実践的なワークロードを選択しています。今後のブログでは別のシナリオを検証します。
テストしたワークロードにおいては、グローバルインデックスが適用されておらず、ジオメトリセントリックは最適化されていません。完全なデータ規模を取り扱う際には、このオペレーションによるDBUとインスタンスコストの両方で、H3セントリックアプローチは、ジオメトリセントリックアプローチよりも最大90倍安価であり、H3-ジオメトリハイブリッドアプローチよりも2倍安価です。H3-ジオメトリハイブリッドアプローチは、ジオメトリセントリックアプローチよりも40倍安価です。 特定のワークロードにおける実際のパフォーマンスゲインは、ポリゴンの複雑性やデータの規模によって変動しますが、H3(セントリック+ハイブリッド)の方が有利です。DBR 11.3に組み込まれたPhotonパワードのH3 APIを活用することでこのレベルのパフォーマンスを達成しています。
データの理解
16億のポイントのトリップテーブルに対して、マンハッタンのミッドタウンのように他の地域よりもはるかに密な地域があるように、全体的な偏りを最小化するバランスの取れたH3インデックスの解像度を選択したいものとします。この記事に添付しているノートブックで議論しているいくつかのAdaptive Query Executionの設定を調整することで、計算資源の制約がある地理空間オペレーションにおける偏りをチューニングすることができます。また、密な領域を平準化するために、スマートにH3インデックス空間を活用することで、偏りに対処することができます。
解像度12におけるH3セルで区分けされたピックアップ位置
解像度8、10、12を考慮して、H3セントリックアプローチとH3-ジオメトリハイブリッドアプローチに適用可能な複数の解像度を評価しました。赤道においては、セルの領域は .737km2 から .015km2の間、あるいは、.457mi2 から .009mi2の間となります。NYCの緯度においては解像度12のセルの直径は約60フィート、18.3メートルとなります。この評価を行うために製品APIのh3_toparentを活用して、容易に子供から親に返還を行うことができ、最終的には3つすべての解像度をtripベーステーブルのフィールドとして追加することができました。
NYCトリップの解像度12は、特定のセル内のタクシーピックアップの数を検討する際、平均が400Kイベント以下であるのに対して、セルあたり最大1.7Mにもなるように元もスムーズな偏りの体験を提供します。解像度10は平均が2M以下で、2M-10Mの複数の外れ値を持つことになりました。解像度8は、平均3M以下、3M-60Mの多数の外れ値を引き起こしました。
異なるH3解像度におけるタクシートリッププロファイル: 解像度8(左上)、解像度10(右上)、解像度12(下)
NYCタクシーゾンのデータは、さまざまな形状、複雑度を持つポリゴンから構成されています。
NYCタクシーゾーンの境界
部分的データ
(最適化されていない)ジオメトリセントリックアプローチを用いて、完全な1.6Bのトリックからの部分的な(小規模から中規模の)結果でのみ作業したいと考えます。以下の表から、tripテーブルの1000万のポイントをインスタンスコストが$0.12で価格層をベースとして計算される0.37 DBUの(よりパワフルな)クラスターを用いて1分以内に計算することができます。規模が1億ポイントになると、コストメリットはより顕著なものとなり、インスタンスコストは$0.72で2.18 DBUとなります。以下に示すように、H3-ジオメトリハイブリットアプローチを用いて全体のデータセットを処理する際のベストタイムと比較して、ジオメトリセントリックアプローチによる約5%のデータセットの処理時間はすでに、2倍遅いものとなっています。 まとめると、最適化されていないジオメトリセントリック処理は、大規模データよりも小さいデータにスケールするツールといえます。
ジオメトリセントリックアプローチを用いたポイントインポリゴンの計測。m5d.4xlargeインスタンスの価格は時間あたり$0.904 + 時間あたり2.74 DBU(いずれもわずかな金額です)
完全なデータ
最初のテストではデフォルトのインスタンスタイプを使用し、AWSではメモリーと軽さのペレーションのバランスが取れ、汎用処理要件では堅実な選択肢となるi3.xlargeファミリーとなります。しかし、いくかの設定で実行した後、メモリーよりCPUの比率が高いインスタンスタイプにスイッチすることでよりコスト削減できることがわかりました。計算資源に制約のあるワークロードでは、効果を失うほど大きくならない程度のオートスケーリングを可能としつつも、シャッフルを削減する8-16のCPUを持つインスタンスをお勧めします。AWSでは(最適化されていない)ジオメトリセントリックの実行でも使用されたm5d.4xlargeに落ち着きました。Azure Databricksにおける同様のファミリーは、D16ads_v5やD16ds_v5のような汎用計算バーチャルマシンだと思いますが、ご自身のワークロードでいくつかの検証を行いたいと思うことでしょう。GPCでは、Photon有効化インスタンスから選択したいと思うかもしれません。ベストなコストパフォーマンスの設定は、以下で緑色で示しており、最速の設定は太字で表現しています。
完全な1.6Bレコードに対するH3セントリックアプローチとH3-ジオメトリハイブリッドアプローチを比較したポイントインポリゴンの計測。i3.xlargeインスタンスの価格は時間あたり$0.312 + 時間あたり1 DBU(両方とも課金はわずかです)。
ここでは表示していませんが、i3.xlargeの実行コストは4ワーカーでも8ワーカー(AWSのデフォルトインスタンスタイプ)でも同じであり、8ワーカーのオペレーションは4ワーカーとの1/2の時間で完了しており、同じ合計高ストになっていることを意味しています。ジオメトリセントリックはパフォーマンスが遅いため、これらの小規模インスタンスではテストしませんでした。実際、90分以内に完了するには、H3アプローチのベストなコストパフォーマンスの実行に必要だった2ワーカーではなく10台のm5d.4xlargeワーカーが必要となりました。
完全な1.6Bレコードに対するH3セントリックアプローチとH3-ジオメトリハイブリッドアプローチを比較したポイントインポリゴンの計測。m5d.4xlargeインスタンスの価格は時間あたり$0.904 + 時間あたり2.74 DBU(両方とも課金はわずかです)。
パフォーマンス試験ではない場合、特に実行間隔の生じるインタラクティブなノートブックからの実行の際には、効率性を高めるためにクラスターのオートスケーリングをオンにしたいと思うことでしょう。また、偏りやその他のパーティショニングの課題によって、クラスターでは定常的にすべての利用可能なワーカーを活用できない場合があります。このワークロードでは2-10+台のm5d.4xlargeワーカーが良い設定となることでしょう。
3つのアプローチの詳細
ジオメトリセントリック
インデクシングがユーザーやシステムによって取り扱われていない場合には、このアプローチは課題に直面します。中規模以上において、長時間実行するcross joinになるような処理の実行においては、最悪のパフォーマンスを体験することになります。ジオメトリセントリックにおいては、100K、1M、10Mの小規模から中規模のより適切な規模でテストし、より大規模な100Mや完全な1.6Bのトリップでもテストしました(上の結果をご覧ください)。以下の画像は、互いに形が似通っていない形状を持つNYC Financial Districtにおけるタクシーゾーンのポリゴンを示しています。
NYCタクシーゾーンのデータセットにおけるレベル詳細の例。
このアプローチではH3インデックスによるメリットは多くありませんが、少なくとも、特定のジオメトリに属するポイントのみが、より計算コストのかかるST_Containsオペレーションを用いて評価されるようにWHERE句の条件としてジオメトリのXY境界を活用することができます。すべてのライブラリが同じように作成されている訳ではありませんが、すべてのライブラリはインデックスなしにスケールを大きくした際に、同様の課題に苦しみます。 ジオメトリセントリックアプローチにおいては、Databricks LabsプロジェクトのMosaicを使用していますが、最適化されていないパフォーマンスを評価するために、グローバルグリッドインデックスのビルトインサポートは使用していません。H3のインデックスと組み合わせた際に、Mosaicが大規模データエンジニアリングで真に活躍するH3-ジオメトリハイブリッドアプローチをサポートするのかを説明します。
create or replace table taxi_zone_xy as (
select
st_xmin(geom_wkt) as x_min,
st_xmax(geom_wkt) as x_max,
st_ymin(geom_wkt) as y_min,
st_ymax(geom_wkt) as y_max,
*
from taxi_zone
)
さらに処理を改善するために、ST_Containsは計算コストが高くなるため、タクシーゾーンとトリップを平準化するために、デフォルト設定に加えて両方で/*+ REPARTITION() */ヒントを活用しました。完全なtripテーブルは大規模なものとなります(しかし、膨大というわけではありません)。10台のm5d.4xlargeワーカー(160コア)では完了に1.21時間程必要とし、正確に1.222Bのマッチを発見しています。 インデックスの欠如は、郊外に比べてマンハッタン中心で大きな偏りがあるタクシーピックアップのような大規模データでは課題に直面し始めます。それぞれのポイントの値に数値的な変動性があるため、(次のセクションで説明するH3セルの使用ではなく)skew joinのヒントを使用できる好適なカラムがありません。
select
t2.*,
t1.*
from (select /*+ REPARTITION(1600) */ * from trip) as t1
join (select /*+ REPARTITION(26) */ * from taxi_zone_xy) as t2
where pickup_longitude >= x_min and pickup_longitude <= x_max and
pickup_latitude >= y_min and pickup_latitude <= y_max and
st_contains(geom_wkt, st_point(pickup_longitude, pickup_latitude))
)
H3セントリック
トリップとタクシーゾーンの間のH3インデックスマッチを比較するだけで、h3_polyfillash3を用いてポイントインポリゴンを効率的に近似することができます。このデータはすでにtrip_h3とtaxi_zone_h3テーブルを作成するデータエンジニアリングの過程で、格納、ファイルの平準化のためにコンパクト化、z-orderされています。このアプローチによって、タクシーゾーン内のpolyfill近似によって最も迅速に結果を特定することができ、2台のm5d.4xlargeワーカー(AWS)では約3.9分、10台のワーカーでは約1.4分で完了しています。
以下の画像では、NYC Financial DistrictのタクシーゾーンのH3セルを示しており、南東の桟橋近辺では特にポリゴンがギザギザしており、近似の効果を示しており、結果に幾つかの境界情報が含まれておらず、結果の一部としてポリゴンよりも若干広い範囲をインデックス空間がキャプチャしています。
境界効果を示すH3 polyfillのモザイク
create table if not exists approx_pickup_zone as (
select
tz.*,
t.*
from (select /*+ SKEW('pickup_cell') */ * from trip_h3) as t
join (select * from taxi_zone_h3) as tz
on cell == pickup_cell
)
添付ノートブックでの設定調整(ここでは表示していません)を活用して、H3インデックス空間における適合設定を用いるための/*+ SKEW('pickup_cell') */の活用に注意してください。ポリゴンとセルはインデックスがないため、このヒントはジオメトリセントリックアプローチでは利用できません。また、H3セルの比較を助けるためにautoBroadcastJoinThresholdを増やすというメリットを享受することもできます。このアプローチは、実際のものよりも1.5M(0.1%)程度結果が不足するのみの近侍となっています。
H3-ジオメトリハイブリット
ジオメトリセントリックよりも遥かに高性能なアプローチとして、より計算コストの高いST_Contains述語を呼び出す前に、H3セルのインデックスマッチを検討することで、正確なポイントインポリゴンの結果を得ることも可能です。このハイブリッドアプローチは、我々の地理空間製品の機能と密に連携し、Databricks Runtimeを最大限活用するDatabricks LabsのMosaicプロジェクトを活用します。データエンジニアリングは、主にMosaicのGrid_TessellateExplode関数を用いて達成され、taxi_zone_h3_chipテーブルのインデックス構造体フィールドを生成するために呼び出されます。
タクシーゾーンに対するオペレーションにおいて2台のm5d.4xlargeワーカー(AWS)であればたった8.7分で1.222Bのピックアップを特定することができ、10ワーカーであれば2.1分で完了しています。 以下の画像では、NYC Financial districtのタクシーゾーンを示しており、南東の桟橋(明るい青のセルとチップ)のギザギザしたエリアを含めるために、近似のためのものですがチップから描画されている完全な境界セル情報(茶色)、および、ポリゴンの境界(黄色の線)における正確なチップのためのハイブリッドアプローチの能力を示しています。
grid_tessellateexplodeを使った後の結果ポリゴンチップを表示するH3のモザイク
select
taxi_zone_h3_chip.*,
t.*
from
(select /*+ SKEW('pickup_cell') */ * from trip_h3) as t
join taxi_zone_h3_chip
on cell == pickup_cell
where `index`.is_core or st_contains(`index`.wkb, st_point(pickup_longitude, pickup_latitude))
)
H3セントリックアプローチと同様に、調整された適応設定を活用するためのヒントのために/*+ SKEW('pickup_cell') */を使用しています。このアプローチでは、以下を追加しています:
WHERE `index`.is_core OR st_contains(`index`.wkb, st_point(pickup_longitude, pickup_latitude))
indexを使うこれらの句は、最終的には近似結果と正確な結果の違いとなります。
DatabricksのH3エクスプレッションを用いて、従来の地理空間処理や分析を実行するための別の手段をお客様に提供します。離散空間分析は、無制限の規模のデータに対処しつつも、劇的なコスト削減を実現する道筋を提供します。離散およびベクトル空間分析の両方がDatabricksのお客様にとって重要なものであり、プラットフォームにおけるH3セントリック、H3-ジオメトリハイブリット、ジオメトリセントリックアプローチの改善に取り組んでいきます。
Databricksにおける新たなエクスプレッション、H3がどのようにサポートされるのかの詳細については、ドキュメントをご覧ください[AWS | ADB | GCP]。この記事のサンプルの詳細に興味があるのであれば、ノートブックをご覧ください - NB01: Data Prep H3-Geometry Approaches | NB02: Compare H3-Geometry Approaches。