Real-Time Exploration of Large Spatiotemporal Datasets Based on Order Statistics

問題定義

解決大型時空資料集的互動式的可視分析和探索。能夠實時進行的操作總是有限的，是以實作兩個interactive的操作就夠了。

為了達到實時性，預計算是一種常用的思路（突然想到Games202，漫反射，鏡面反射沒懂，全局環境光LVM）。就像解決全局光照，通常會花大量時間先渲染好光照貼圖，然後在運作時查詢貼圖。這樣問題就變成了設計合适的資料結構，并将一些耗時的操作進行預處理。

總而言之，作者提出一種新的資料結構，減小記憶體占用，支援實時切片，以及cdf，分位數統計量的查詢。

這圖就把工作介紹了，除了切片，機場延誤時間的分位數（4号那天50%延誤時間在50min）。

related work

巧妙的提升了工作的價值，mean std這些統計量不行，分布，行！通過分布能檢視出異常事件。

常用的兩種政策：采樣（思想都是相通的，可惜自己是想不出啥創新。這在RayTracing，反走樣中特别基本的思想，雖然思想就這，但是具體怎麼做就是另一回事了）+ 預計算。

需求還有一個困難在于需要更新動态的更新，多個資料集融合？

t-digest 資料結構

A new data structure for accurate online accumulation of rank-based statistics such as quantiles and trimmed means. The t-digest algorithm is also very friendly to parallel programs making it useful in map-reduce and parallel streaming applications implemented using, say, Apache Spark.

t-digest精度配置設定不是均勻的。能夠高效的對基于rank的資料進行查詢。

hashcube

把raw資料看成一維數組，遞歸的按照每個次元進行排序，劃分子數組，遞歸。這樣，在每個次元上有一個索引連結清單（相當于），查詢時在每一維找到滿足條件的樞紐，将這些東西合并起來，實際上将p-digest合并，得到一個result表。

我的了解是：索引的每個細分樞紐都指定一個pdigest，然後最後需要将這些滿足條件的pdigest合并成一個，合并的同時既要保證效率，又要維護結果的順序統計量誤差不能太大。

作者改進：

digest用數組實作，同時針對資料特點，做了一些小優化。

索引方式：添加次要樞紐數組，使得在查找上更友善也更麻煩，通過一些複用減輕memory。