面向分布式環(huán)境的MinTopK算法設(shè)計.pdf

1、隨著互聯(lián)網(wǎng)行業(yè)的快速發(fā)展，如何快速高效處理大規(guī)模實時數(shù)據(jù)成為當(dāng)前研究重點?？沙掷m(xù)Top-K查詢算法主要是用于流數(shù)據(jù)的應(yīng)用上，基于某種函數(shù)關(guān)系實時選取得分最高的K項。這種算法在一些實時應(yīng)用中被廣泛使用的算法，例如，網(wǎng)絡(luò)監(jiān)控、金融分析和實時推薦。MinTopK算法是Di Yang在2011年提出來的可持續(xù)Top-K查詢算法，是解決以前的算法存在需要重計算的問題。由于重計算操作會需要大量計算資源。MinTopK算法，定義了最小Top-K候選集

2、合，保證后續(xù)的查詢窗口計算所需要的子集。MinTopK算法維持最小Top-K候選集合，消除需要重計算，比以往的算法有著更好的CPU和內(nèi)存利用。MinTopK算法是單機串行的算法。由于單機的網(wǎng)絡(luò)、CPU等資源的限制，無法滿足當(dāng)前大數(shù)據(jù)量的計算要求。分布式計算方法是一種常見有效的解決方式。
　　本文研究的是如何將MinTopK算法用于分布式計算，解決流數(shù)據(jù)的數(shù)據(jù)量大和計算復(fù)雜度高的問題。本文將連續(xù)的流數(shù)據(jù)轉(zhuǎn)化為離散的流數(shù)據(jù)來處理，設(shè)計

3、了并行化的 MinTopK算法的基本模型，同時滿足于 MapReduce架構(gòu)和Spark系統(tǒng)等分布式處理工具的編程模型。從算法的時間復(fù)雜度，空間復(fù)雜度和通信開銷三個方面來，說明本文設(shè)計的算法具有無鎖的、高效的、空間低和通信量小的特點。
　　通過實驗數(shù)據(jù)分析，并行化的MinTopK算法相對于原來的算法是具有良好的加速比和擴展性，能夠在slide的時間內(nèi)處理好數(shù)據(jù)，避免累計時間造成的用戶體驗不好的問題。通過實驗說明Super-Top-