白話導讀
The Journal of Supercomputing
SCI · IF 2.557 · Q1
2022/02
資料又缺漏、又巨量，還要找出「最強的前 k 個」
Top-k Dominating Queries on Incomplete Large Dataset
Jimmy Ming-Tai Wu, Min Wei, Mu-En Wu*, Shahab Tayeb
一句話： Top-k dominating 查詢要在資料裡挑出「支配別人最多」的前 k 個物件。當資料既有缺失值、又非常巨量 時，作者提出 EHBIG ：用 BitMap 索引處理缺漏、用 MapReduce 處理規模、再用剪枝策略把時間與記憶體壓下來。
先問：這在解什麼問題？the problem
Top-k dominating（TKD）查詢 是一種「找出資料集裡最值得注意的物件」的方法——它回傳在給定資料集中支配（dominate）其他物件最多 的前 k 個。
難點有兩層。第一層是資料不完整 ：真實世界的資料常在某些維度上有缺失值，傳統為「完整資料」設計的資料探勘方法就派不上用場。BitMap Index Guided Algorithm（BIG） 是解這個問題的好選擇。第二層是資料太大 ：資料量一大，演算法的可行性與效能要求就變得非常高——在「又不完整、又巨量」的資料上做 TKD 查詢，難度是加乘的。
怎麼做？把 BitMap 索引搬上 MapReducethe method
作者提出 EHBIG（Efficient Hadoop BitMap Index Guided Algorithm） ：在整個流程 上套用 MapReduce，並加上剪枝策略（pruning strategy） 。BitMap 索引負責處理「不完整」，MapReduce 負責處理「巨量」，剪枝負責把不必要的計算砍掉。
在此之上，作者又提出改良版 IEHBIG ，把整個演算法流程再最佳化一次。
不完整的巨量資料
維度有缺失值
BitMap 索引
處理缺失值
MapReduce 全流程
處理資料量
剪枝策略
砍掉無用計算
Top-k 支配物件
EHBIG / IEHBIG
EHBIG 的組成：用 BitMap 索引克服缺失值、用 MapReduce 架構讓 TKD 查詢在巨量資料上可行、再用剪枝策略壓低成本；IEHBIG 則進一步最佳化整體流程。
結果如何？results
透過剪枝策略，執行時間與記憶體用量大幅降低 。實驗結果顯示，所提演算法能在「不完整的大型資料集」上完成 TKD 查詢，並在 Hadoop 運算叢集上有良好表現。
誠實補一句： 論文摘要以「大幅降低」「表現良好」描述效果，並未公布具體的加速倍數或記憶體數字，因此本頁不列任何數值。
閱讀原始論文（Springer） →