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

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

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

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