SwiftTuna: 對大規模高維資料的快速響應的增量式視覺化探索 (SwiftTuna: Responsive and Incremen...

圖1. SwiftTuan視覺化系統概覽圖

R1. 大規模資料處理

系統應該能夠以可擴充套件的方式處理大規模資料。很難用具體的數字來定義大規模資料或大資料的含義。此外，即使有一個具體的定義，它可能會跨域變化，或隨著技術的進步而變化。該論文將10億個實體視為大規模資料的最小尺寸。該數字是用於評估資訊視覺化中大規模資料分析的互動系統的最大條目數。

R2. 響應式互動

眾所周知，較短的互動延遲可以促進洞察力的產生。但是，查詢大規模資料通常需要幾分鐘甚至幾個小時，這太長時間不能引起使用者的注意。為了支援流暢的資料探索而不會丟失使用者對正在進行的任務的關注，系統應該在不到10秒的時間內響應查詢。

R3. 互動式多維探索

多維度是大規模資料探索的另一個重要方面，因為大多數真實世界的大規模資料集都具有兩個或多個屬性。系統應該能夠照亮這些資料集的各個方面，使使用者能夠通過視覺化探索多個維度之間的關係。通過允許使用者生成多維資料的感知有效的1D或2D投影，使用者將能夠獲得涵蓋資料的多個維度的有意義的見解。此要求還包括多維度的互動; 例如，使用者應該能夠通過應用過濾器深入研究一小組有趣的資料。

R4. 可擴充套件的視覺化

並非所有傳統的視覺化技術都適用於大規模資料分析。當應用於大規模資料時，大多數傳統視覺化可能遭受嚴重的過度繪製或混亂問題。因此，視覺化設計人員必須更嚴肅地考慮其視覺化的可擴充套件性，以使使用者能夠感知和理解大規模資料的視覺化。

根據其計算方案（即預處理或增量），系統型別（即單機或分散式）以及測試的最大資料大小，可以對以前的方法進行分類，旨在解決四個要求的子集

圖2. 對於以前處理大規模高緯視覺化資料方法的分類

預處理原始資料和構建特定資料結構（例如，資料立方體）以進行快速查詢的預處理方案是實現大規模資料探索的主要方法（圖2中的左欄）。例如，imMens 預先計算了多變數資料切片，用於在視覺化中進行響應性刷洗和連結。然而，預處理方案的侷限性在於：1）預處理必須在分析之前進行2）在多維資料中建立具有所有維度的預計算資料結構通常是不可行的，因為禁止記憶體足跡，以及3）因此，只能回答某組維度上的某組查詢。

相比之下，增量處理方案可以作為克服這些缺點的可行解決方案。在此方案中，查詢以分散式和增量方式線上處理，而不使用預構建的資料結構。

SwiftTuna系統設計

SwiftTuna採用客戶端 – 伺服器架構。客戶端是單頁Web應用程式，使用者可以在其中建立查詢，實時監控查詢進度，並與結果互動以探索資料。

為了支援大規模資料的響應式反饋，伺服器提供快速響應，並逐步處理查詢。當來自客戶端的查詢到達時，伺服器首先返回包含查詢的低保真結果的提示響應，該結果是從一小部分資料構建的。為了逐步處理資料，伺服器將整個資料分成 ñ 塊， B 0 至 B n  –  1 。反過來，伺服器將傳入的查詢拆分為n個作業，每個作業對應於每個資料塊。這些作業將插入作業佇列中。伺服器接受第一個工作，包括B 0 。從佇列中執行後端工作人員的工作。此後，伺服器每200ms輪詢一次工作人員以檢查作業是否完成。完成後，伺服器從工作人員收集結果並將其傳送回客戶端。佇列中剩餘的工作（即 n  –  1 覆蓋的工作 B 1 至 Bn –  1  ） 以相同的方式逐個處理。

從客戶端的角度來看，針對單個查詢會出現一系列錯開的響應。客戶端累積並組合部分結果。例如，假設有一個查詢計算分類維度的頻率直方圖，nat_cd表示國家/地區的名稱。第一部分答覆僅包含國家/地區的頻率B 0 。當第二個結果到來時，它涵蓋了B 1 ，客戶通過比較國家名稱來累積頻率。然後，客戶端更新進度條和相應的視覺化。

圖3. SwiftTuna系統的視覺化卡片

圖4. 尾部圖表和點圖。受梯度圖的啟發，採用漸變來視覺化置信區間。（a）尾部梯度圖通過在視覺空間的一半中將它們視覺化來優先考慮突出的類別（例如，最常見的五個類別），而其餘類別在另一半的空間中用線條（即尾部）等）。梯度顯示估計值的95％置信區間。（b）當處理所有資料時，梯度最終收斂，並且有點點圖替換有尾梯度圖。（c）梯度圖。（d）點圖。當x軸上的類別數量很小（即，等於或小於8）時，我們使用先前的梯度圖和點圖而不是它們的尾部版本。

圖5. 視覺化卡提供兩個協調檢視，焦點檢視和上下文檢視，以及視覺化特定功能，例如使用對數刻度而不是線性刻度或使用雙變數顏色方案。（a）擴充套件梯度圖（從圖4c擴充套件）。（b）擴充套件的尾梯度圖。（c）擴充套件密度圖。密度圖不提供刷選的上下文檢視，但使用者可以直接刷上焦點檢視。

SwiftTuna目前支援四個與視覺化相關的查詢，Frequency Histogram，Binned Histogram，Pivot Dot Plot和Density Plot，以及兩個與資料相關的查詢，Count和Load Raw Data。該論文選擇的四個視覺化的概念都是基於區間的概念產生，而區間的概念可以無視資料量大小很好地傳達全域性模式和異常值。視覺化顯示在視覺化卡（ 圖3 ）中，該視覺化卡用作分析的基本單元。Frequency Histogram（圖4a）和Binned Histogram（圖4c）分別提供了分類或數字維度的單變數摘要。另一方面，Pivot Dot Plot（圖5b）和Density Plot（圖5c）適合於視覺化兩個維度之間的關係。透視點圖使用指定的聚合函式（MIN，MEAN，MAX或SUM）聚合數字維，按行分類維對行進行分組。密度圖視覺化兩個數值維度的關係。

由於SwiftTuna將資料分成塊並逐個處理每個塊，因此在該過程的中間只能獲得部分結果。為了允許使用者快速訪問結果，該論文根據已知的統計程式估算部分結果的最終結果。例如，由於部分結果來自總體樣本，該論文使用樣本統計資料估算人口統計資料（例如，使用樣本均值和樣本標準差來估計總體均值）。在特殊情況下，決定不估計使用MIN或MAX聚合的樞軸點圖的最終結果，因為這些統計資料對異常值非常敏感，因此無法進行穩健估計。

響應式查詢

該論文采用增量查詢方法來實現對每種視覺化的視覺化相關查詢的響應式查詢。

查詢流程

當需要更新視覺化卡時（例如，使用者啟用過濾器或新增新卡），客戶端請求對應於每個卡的每個查詢的查詢。例如，如果使用者對資料應用過濾器，則應更新所有可見的視覺化卡; 因此，客戶端請求與可見卡一樣多的查詢。

要了解SwiftTuna的查詢流程，假設分析師發出了兩個查詢， 查詢 1 對於分類維度的頻率直方圖和查詢 2 對於數字維年齡的分箱直方圖。當查詢到達伺服器時，每個查詢都被分成n個工作，n是一個可調數量的塊。為了減輕原始資料中可能的偏差，處理索引（從0到 n  –  1 ）隨機分配給每個塊而不重複，並以此隨機順序處理塊。對於查詢Qi和塊Bj，我們把該查詢工作表示為  J ( Q i ,  B j ) 。

然後，建立的作業按特定順序插入作業佇列。SwiftTuna支援兩種排程模式：塊順序和列表順序。預設的塊順序優先於塊查詢。按此順序，伺服器首先執行具有較小處理索引的作業。例如，完成第一份工作j(Q1 ， B 0) 後 ，伺服器執行j(Q2, B0)，而不是J(Q1, B1)。在獲取所有查詢的早期結果時，塊順序很有用。相反，列表順序優先考慮塊上的查詢，這意味著伺服器完成與第一個查詢相關的所有作業並移動到下一個查詢。例如，在列表順序中，J(Q1, B0) 之後執行J(Q1, B1)。使用者可以切換排程模式並在卡列表面板中重新排序查詢的優先順序（ 圖6c ）。

圖6. 卡片列表面板。（a）卡片列表顯示視覺化卡列表。最初，提供每個維度的卡片。（b）進度列表說明了每張帶有進度條的卡的進度。使用者可以分別通過單擊停止和播放圖示來停止或繼續處理卡的查詢。（c）使用者可以使用兩個選項確定查詢的優先順序：塊順序和列表順序。（d）每次使用者刷上視覺化時，表示刷洗區域的過濾器將新增到過濾器列表中。使用者可以單擊漏斗圖示以啟用過濾器。（e）使用者可以通過單擊卡片列表底部的加號圖示為二維建立一張新卡片（例如，兩個數字維度之間的密度圖）。

當用戶應用過濾器時，會發生另外兩個過程。首先，伺服器使用SQL語法表示過濾器，並將其作為引數附加到所有作業。這允許工作人員過濾掉資料。其次，計算作業（計算滿足過濾器的行數）將作為作業佇列的字首。計數作業的結果將傳送到客戶端並用於顯示已過濾行的數量。

基本上，伺服器需要一份工作，J(Qi, Bj)，從作業佇列中並在群集上執行它。在這裡，由於我們只有一個作業和多個工作人員，我們需要將作業再次拆分為任務以利用Apache Spark的並行處理。伺服器分隔塊Bj到指定數量的子塊（例如，叢集中的工作者的數量），並建立與每個子塊對應的每個任務的任務。然後，工作人員並行執行任務。伺服器從工作程式收集結果，並將它們作為查詢的增量響應傳送回客戶端Qi。請注意，此時客戶端具有查詢的增量響應Qi在塊上B0至Bj。如果查詢未完成（即，J <  n  –  1 ），客戶端使用錯誤指示符（例如，梯度圖）視覺化響應並顯示不完整的進度條。

即時響應

由於在之前的研究中提倡快速響應的重要性，SwiftTuna提供了快速響應，使使用者能夠在分析的早期階段直觀地確認查詢。查詢的提示響應是根據儲存在伺服器上的整個資料的一小部分樣本構建的，而不會將查詢傳遞給工作人員。此功能允許伺服器幾乎立即對查詢做出反應，幫助使用者將注意力集中在分析上。當請求兩個或多個查詢時，伺服器會打包查詢的所有提示響應，並立即將打包結果傳回，從而減少網路開銷。

當客戶端收到查詢的快速響應時，它會根據提示響應顯示初始視覺化。幾秒鐘後，當查詢的第一個增量響應到達客戶端時，客戶端會丟棄提示響應並將其替換為第一個增量響應。這是因為當查詢使用分箱（例如，分箱直方圖）時，由於箱的不同尺寸和範圍，不可能合併兩個響應（即，快速響應和第一增量響應）。

增量響應

雖然第一個增量響應取代了快速響應，但客戶端會累積剩餘的增量響應並估計最終結果。具體過程因查詢型別而異。在本節中，我們將解釋每種查詢型別的累積估計。

對於諸如頻率直方圖之類的計數查詢，累積過程很簡單。給定兩個增量響應，我們比較每個類別的頻率，如果兩個響應中存在相同的類別，則將兩個頻率相加。對於估計，由於我們已經知道資料中所有行的數量，我們估計最終結果及其95％置信區間。

分箱直方圖和密度圖類似於頻率直方圖，因為它們計算行數。但是，為了累積這些查詢的增量響應，必須在處理之前選擇響應中使用的bin的大小和範圍。我們可以為每個數字維度使用固定範圍，但我們發現使用固定範圍通常會產生不令人滿意的分級結果，尤其是當資料中的多行被過濾掉時。作為一種補救措施，SwiftTuna增加了一項額外的工作，一項範圍工作，在處理這些查詢之前，這些查詢僅在過濾後的剩餘行中計算數字維度的最小值和最大值。然後，通過均勻地劃分尺寸的最小值和最大值之間的間隔來確定箱的尺寸和範圍。估計步驟與頻率直方圖查詢的步驟相同，因為它們都是計數估計。然而，在測試中，對全部資料計算最小值與最大值會消耗數分鐘，對於即時的查詢極為不利，因此改為只計算第一塊的數字維度的最小值和最大值，這樣耗時大約為2秒，在實際的測試中這種處理也不會因為漏掉其他塊的統計對分箱產生影響。

對樞軸點圖的累積響應有點不同。樞軸點圖在分類維上聚合數值維。目前，支援四種聚合函式：MIN，MAX，MEAN和SUM。合併MIN和MAX函式的兩個增量響應非常簡單。對於兩個響應中的類別，我們比較響應中的兩個MIN（或MAX）值，並根據聚合函式選擇較小（或較大）的值。如前所述，我們決定不估算最終的MIN和MAX值，因為它們對異常值非常敏感。

對於MEAN和SUM函式，伺服器為增量響應中的每個類別提供三個值：類別的頻率，特定數字維度的總和以及維度的平方和。選擇SUM函式時，可直接顯示第二個值（即sum）。否則，對於MEAN函式，我們通過將第二值（即，和）除以第一值（即，類別的頻率）來計算平均值。平方和用於計算平均值和總和估計值的方差和95％置信區間。

測試結果

經過測試，平均而言，無論查詢維度的範圍和查詢的型別如何，使用者都能夠在0.5秒內收到快速響應。當資料被分成2,400個區塊時（即N =  2  ， 400  ） ，一塊大約覆蓋175萬行。需要大約兩秒來計算第一個塊上的維度範圍（以確定箱的範圍）或為一個塊構建分箱直方圖。這意味著使用者可以在收到快速響應後的四秒鐘內掌握175萬行的第一個增量響應，並且每兩秒進行一次下一個增量響應。

關於塊的粒度，較小的塊 （N   =  2  ， 400  ） 產生了更快的反應。然而，就吞吐量而言，較大尺寸的塊是優選的。例如，當N是2,400,需要1.78秒來掃描一個塊中的175萬行並建立一個分箱直方圖，但是，當N是240，處理十倍的行（1750萬行）只需要兩倍的時間（3.52秒）。這意味著存在無法有效並行化的開銷，例如網路延遲或節點之間通訊所花費的時間。

結論

總而言之，本文討論了SwiftTuna這一使用低保真度即時響應和高保真度增量式響應的針對大規模高緯度資料的視覺化系統，在使用資料立方體的預先處理方式的系統之外，又提供了一個另外的角度，十分有趣。

參考文獻：