因之前研究了有關 map tile 的建立的方式，因此進一步了解 Strava 如何建立熱點圖的方式，因此在本篇中在這篇文章 Building the Global Heatmap 中 Strava 官方說明了建立 Strava Global Heatmap 的過程，在看完後覺得很有趣因此分享一下心得。本篇將專注在建立熱度圖的演算法上，並不涉及如何在 Cluster 上大量運算的方法。

Strava Heatmap

有的人對 Strava 這著名的運動 app 應該不陌生，能紀錄運動者的位置以及使用者心跳等資訊並上傳至雲端分享。而 Strava 營運到現在在全世界也累積了大量資料，依照 Building the Global Heatmap 所敘述，Strava 資料量至少有

  • 7 億筆運動紀錄。
  • 1.4 兆筆 GPS 座標位置
  • 7.7 兆個需要的繪製的像素
  • 5 TB 原始資料

可知資料量是非常龐大而且還在繼續增加當中。最初的 Strava 團隊是在 Single Machine 上建立 Heatmap，但每更新一次需要且讀取放在 Amazon S3 的原始資料成本非常高。因此 Strava 團隊將原先的 Code 以 Apache Spark 與 Scala 重新撰寫過，使得每個運算步驟更加平行化與高效能，讓原先在單機上的運算分散到數百台機器上，在數個小時內就能得出 heatmap 且花費只有數百美元。

詳細內容可參考 Strava 另一篇文章 From data streams to a data lake

此外最新版本的 Strava Heatmap 也在繪圖上做了很多改進，如

  • Rasterize 方式由單點資料轉變成線段資料
  • 改善 Normalization 方式與增加解析度，讓視覺化結果更好。

因後端架構在文章中並沒有詳細解釋，因此以下只簡單介紹將運動位置記錄 (Activity) 轉換成最後的 map tile 圖片的演算法。

How to do?

Input Data and Filtering

在真正繪製資料前，Strava 對 Activity 進行前處理排除掉錯誤的記錄資料，包含

  • 平均速度不合理的記錄（可能是在搭飛機或船）。
  • 移除虛擬裝置過來的資料，避免 Fake GPS data 影響結果。
  • 去除停止的點數，直到真正開始移動為止。

此外 Mobile device 時常會自動將 GPS 位置集中到道路上，在繪圖是會過於集中讓視覺效果不好看，因此會在每個 GPS 點位加入隨機位移資料 (2 meter normal distribution)，讓資料有模糊化效果。

Heat Rasterization

在資料過濾完畢後，Strava 團隊將每筆資料中的 GPS 位置轉換到 Zoom Level 16 的 Web Mercator Tile 座標。並將移動路線切成數個格式為 (Tile, Array[TilePixel]) 的 Segment Tuple。 Tile 為所在的圖磚座標，而 Array[TilePixel] 代表 Activity 在該 Tile 中的移動路線 (Point-to-Point)。假如資料座標跨越不同的 Tile，則在資料點之間建立中間點並將同一個 Tile 的資料點組成一個 Segment，確保每個 Segment 的 Tile Pixel 資料都在同一個 Tile 中。

當 Segment 轉換完畢後，使用 Bresenham’s line algorithm 計算 Array[TilePixel] 裡點與點之間的移動路徑與所對應到的 Pixels 並統計次數（count)。統計完畢後可將結果壓縮序列化存入磁碟中，因點為包還許多 count 數為零的資料，因此壓縮演算法可有效的降低資料大小。

因每個 Tile 資料都是獨立的，可將指定給不同機器平行處理資料，以加快運算速度。

Heat Normalization

將所有 Activity 的路徑資料轉換為在 Pixel 中的 count 的數量後，需將每個 Pixel 的數值範圍從

$$[0, inf)$$

正規化到

$$[0, 1]$$

之間。因對全部的 Tile 進行正規劃成本太高，且一般 Linear 或 Log 方式效果不好，因此 Strava 團隊使用 CDF (Cumulative Distribution Function) 方式（又稱 Histogram Equalization）統計最接近的 5 個 Tile ( 5 tile radius ) 範圍內的 Pixel 數值分佈來進行該 Heat Normalization。

雖然使用 Histogram Equalization 可確保顏色分佈均一且視覺化效果較好，但也無法正確表現出騎乘數量在所有 Tile 中的絕對關係，但在視覺化上效果上已經足夠好。

Interpolate Normalization Functions Across Tile Boundaries

使用 CDF 方法並繪製 Heat 分佈後圖片中的數值仍會有不連續的狀態，特別是在 Tile 與 Tile 的邊界處。因此 Strava 用 Bilinear interpolation 的方式來對每個 Pixel 進行重新計算數值，以得出連續的顯示效果。

Recursion Across Zoom Levels

在完成上述的計算後，可得到 zoom level 16 的所有 Tile 的 Heat 值。因 zoom 15 中的每個 Tile 可由 zoom 16 的組合出來，因此可用 Bottom-Up 方式由下方 Tile 組合出上層 Zoom 的 Heat 數值，並重新執行一次 Normalization 步驟直到 zoom 0 為止。

Serving It Up

計算完每個 zoom 以及每個 Tile 的數值後，將每個 heatmap data pixel 儲存為 single byte [0, 255]，並且將周圍的 tile group 成一個檔案並儲存到 Amazon S3 上，以減少檔案數量以及儲存容量。此外也不先轉換成圖片，而是等到該 Tile 真正被呼叫時才會轉換成對應的圖片，並存放在 Amazon Cloudfront CDN 服務上，以方便使用主存取圖片。

Reference