Hashedcubes：對於大數據的簡潔，低存耗，實時的可視探索

作者：Ma, Nan

互動式可視化系統的設計者現在正面對著大規模、多維度的數據的挑戰。這一工作為以下問題提供了一個肯定的答案：是否存在一個簡單的數據結構為一個更成熟的索引提供更豐富的性能，同時使空間消耗相對較低、執行方法較為簡便？

為了理解這篇工作的內容，首先介紹一些基礎的知識。第一，當我們改變一個數組的先後順序時，這個數組的大小並不會改變，所以我們可以自由的選擇數組的順序。第二，假設一個數組A，所有元素A[i] (b

讓我們先對這篇工作提出的Hashedcubes有一個初步的印象。首先，Hashedcubes加速了互動式可視化探索的請求過程，例如熱圖、時序圖、柱狀圖和散點圖；並且支持空間、類別和時間這三個維度上的刷選和聯接。Hashedcubes平衡了低空間消耗和快速處理時間和執行簡潔程度這三方面因素。

如圖一顯示了3個以Hashedcubes為支撐的可視化例子。最左面的圖顯示了2011.11至2012.06之間美國tweets情況的概覽；中間的圖顯示了2014.01至2015.06之間，NYC Green計程車的上車地點；最右的圖可視化了450萬個Brightkite登記信息的不同的方面。

圖片1 以Hashedcubes為支撐的三個例子

現在從一個更正式的方面來介紹Hashedcubes，Hashedcubes是一個數據結構，它能夠快速的幫助互動式可視化查詢大規模、多維度、時空的數據集。Hashedcubes支持空間查詢，類別查詢和時間查詢。

為了建立Hashedcubes，要求數據的一個維度順序，例如首先是空間維度，然後是類別維度，最後是時間維度。對於數據的每個分隔都用pivot來導引，每個分隔對於不同的維度都有不同的解釋。

對於建立數據結構的演算法，一個輸入數組全部屬於一個相同的分隔，用一個pivot代表。第一個維度接收一個根pivot作為它的輸入。每個分隔都會執行排序來組織元素。

圖片2 建立Hashedcubes的演算法示例

圖2是一個建立Hashedcubes的演算法示例。輸入數據包含了10個點，運用[[Latitude, Longitude], [Device], [Time]]的模式。在圖2(b)的第一步中，數組根據四叉樹的第一層屬性: 空間被重新排序，並分成3個分隔分別為0、2、3三個象限（包含點的象限）。建立了3個pivot（[0-5], [6-7], [8-9])）來劃分三個分隔。在第二步中，數組根據四叉樹的第一層屬性: 類別被重新排序，在這一步中，只有第一個象限被劃分，因此只有[0-5]這個分隔被更新為兩個新pivot[0-2]和[3-5]. 步驟3和步驟4和前面是相似的，只是分別使用類別和時間維度來進一步劃分數據。

圖2c的上方的圖片比較了輸入數組和最終獲得的分隔排序後的數組。圖2c的下方的圖片展示了通過每一步創建出來的並通過Hashedcubes存儲的pivot的列表。

與其他數據立方體不同的是，Hashedcubes不會跨越所有可能的維度集合提前計算。圖3是一個對於計算的Nanocubes和Hashedcubes之間的對比。Nanocubes提前計算的大多數的集合，這樣就導致了更少的查詢時間但是更多的存儲空間消耗。Hashedcubes相反消耗了更少的空間。

圖片3 Nanocubes和Hashedcubes對比示例

空間維度

空間維度被表示為一個四叉樹的形式。地理空間的數據經常會用一個分等級的數據結構表示，並且空間會被遞歸的分為4個地區。每個四叉樹節點為一個劃分該象限中物體的pivot。每個四叉樹有一個最小葉子尺寸，輸出的大小直接取決於輸入的大小。葉子的大小是一個與存儲空間和Hashedcubes表現有關的重要因素。

考慮一個關於通話的數據集，包含了兩個地理位置，一個是打電話的人所在的位置，一個是接收的人所在的位置。如圖4所示，在四叉樹的每一級，記錄通過當前層級的空間屬性被分割，通過屬性交替的分隔數據。

圖片4 通過成對地理位置交替分隔數據

時間維度

如圖5所示，Hashedcubes中每個pivot代表一個間隔，每個時間段被代表為一個時間戳pivot數組。每個黑色的圓代表一個被標記為特定間隔的記錄。

圖片5 時間維度的表示方法

對於這項工作，還有三個值得討論的方面：

第一，交換使數據排序的維度的順序會影響對於特定查詢的空間消耗和執行時間。這種交易可以為數據管理者選擇分布提供幫助。

第二，大型可視化系統例如imMens、Nanocubes和Hashedcubes使用的數據集合會丟失掉一些原始數據的信息。而Hashedcubes根本的概念允許結合外部的數據。

第三，葉子節點的尺寸與可視精度的平衡。空間維度採用最小四叉樹葉子尺寸來平衡運行時間、空間消耗和可視精度。

圖片6 基於Hashedcubes的熱圖可視化

圖6顯示了不同的基於Hashedcubes的熱圖可視化。葉子尺寸從32變化到8，影響了運行時間、空間消耗和可視精度。6(a)的pivot被表示為長方形，(b)和(c)用圓表示聚集地區的中心。

End.

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！