圖流近似處理研究

任何收存和保管本論文各種版本的單位和個(gè)人，未經(jīng)將本論文轉(zhuǎn)借他人，亦不得隨意復(fù)制、抄錄、拍照或以任何I圖流是一個(gè)由不斷到達(dá)的數(shù)據(jù)項(xiàng)組成的序列，每一個(gè)數(shù)據(jù)項(xiàng)表示兩個(gè)點(diǎn)之間的一條邊。這些數(shù)據(jù)項(xiàng)組成了一個(gè)持續(xù)變化的動(dòng)態(tài)圖。圖流在社交網(wǎng)絡(luò)、網(wǎng)絡(luò)測量、網(wǎng)絡(luò)安全等領(lǐng)域都有廣泛應(yīng)用。圖流的更新速度快，數(shù)據(jù)規(guī)模大，這使得對其進(jìn)行精確的存儲與查詢十分困難。相比之下，代價(jià)更小的近似算法更受青睞。本文以圖流近似處首先，本文提出了適用于滑動(dòng)窗口模型的數(shù)據(jù)流摘要算法框架Slidingsketch。圖流是廣義數(shù)據(jù)流的一種，也就是隨著時(shí)間不斷到達(dá)的數(shù)據(jù)項(xiàng)組成的序列。數(shù)據(jù)流中的些數(shù)據(jù)流查詢的摘要算法，它們雖然存在一定的誤差，但是具有高更新速度和低空間一般是最新的數(shù)據(jù)，過于老舊的數(shù)據(jù)會被認(rèn)為過期失效。因此，實(shí)際應(yīng)用中需要能夠其適用于最常用的數(shù)據(jù)老化模型——滑動(dòng)窗口模型。該框架可以應(yīng)用于多種已有摘要算法，使它們支持滑動(dòng)窗口模型。通過將其應(yīng)用于不同的摘要算法，Slidingsketch可以支持包括存在性查詢、頻率查詢、高頻項(xiàng)查詢在內(nèi)的多種查詢。實(shí)驗(yàn)表明，Sliding數(shù)據(jù)項(xiàng)查詢的數(shù)據(jù)流摘要算法，圖流摘要算法可以支持復(fù)雜的面向圖結(jié)構(gòu)的查詢。目前的圖流摘要算法中，能同時(shí)支持多種圖查詢的摘要算法大多基于點(diǎn)和邊的聚合。它是這類摘要算法處理更新的速度很慢，不足以滿足圖流高速更新的需求。而另一類算法則是通過哈希方法將圖流中的點(diǎn)進(jìn)行聚合，將圖流壓縮為更小的摘要圖并存儲。這類算法雖然更新速度快且空間占用可控，但是查詢準(zhǔn)確率較低。本文提出了一種新的圖流摘要算法GSS，其屬于哈希聚合的摘要算法，但是設(shè)計(jì)了獨(dú)創(chuàng)的緊湊數(shù)據(jù)結(jié)構(gòu)保存哈希壓縮后的摘要圖。相比已有的摘要算法，GSS可以在相同的空間內(nèi)保存更大的摘要圖，從而取得更高的查詢精確度。此外，GSS通過支持邊查詢、一跳前驅(qū)查詢和一跳后繼查詢?nèi)N基本查詢算子，實(shí)現(xiàn)了對多種圖查詢的支持，并且能夠支持高速的邊增刪。實(shí)驗(yàn)證明GSS的空間占用可以達(dá)到經(jīng)典圖存儲方法鄰接鏈表的30更新速度可以達(dá)到鄰接鏈表的141倍以上，且在多種查詢中具有遠(yuǎn)高于已有摘要算法最后，本文以三角形計(jì)數(shù)為例研究圖流上的近似持續(xù)查詢算法，設(shè)計(jì)了滑動(dòng)窗口要算法的主要目的是以小空間、高速度存儲圖流數(shù)據(jù)，在查詢時(shí)，則需要在存儲數(shù)據(jù)上運(yùn)行各種查詢算法得到結(jié)果，這帶來了一定的響應(yīng)時(shí)延。而持續(xù)查詢算法則能在圖流更新過程中實(shí)時(shí)維護(hù)查詢結(jié)果。由于圖查詢的復(fù)雜性，精確的持續(xù)查詢算法往往需要大量的空間消耗，并且處理更新的速度有限。作為替代，近似查詢算法則以較小的可控誤差為代價(jià)，取得了更小的空間占用和更快的更新速度。其中的一類代表性算法便是三角形近似計(jì)數(shù)算法。圖流上的三角形近似計(jì)數(shù)算法大多以采樣算法為核心。通過采樣技術(shù)抽取部分邊，構(gòu)造出一個(gè)較小的樣本圖，根據(jù)實(shí)時(shí)維護(hù)的樣本圖上的三角形數(shù)目，實(shí)現(xiàn)對圖流中三角形數(shù)目的實(shí)時(shí)估算。大部分現(xiàn)有工作假設(shè)圖流中不存在重復(fù)邊，而且邊不會過期。然而在實(shí)際應(yīng)用中，圖流中的邊往往會重復(fù)出現(xiàn)，而且圖流數(shù)據(jù)也需要進(jìn)行老化，刪除老舊的數(shù)據(jù)以避免影響新近數(shù)據(jù)的分析。因此，本文設(shè)計(jì)了一種同時(shí)支持重復(fù)邊和滑動(dòng)窗口的三角形近似計(jì)數(shù)算法SWTC，其具有限定大小的空間消耗，而且支持多種三角形計(jì)數(shù)語義，如二項(xiàng)計(jì)數(shù)、帶權(quán)計(jì)數(shù)、全局計(jì)數(shù)和局部計(jì)數(shù)。實(shí)驗(yàn)表明SWTC相比簡單的固定概率采樣方案和通過組合已有技術(shù)實(shí)總結(jié)來說，本文圍繞圖流近似處理，由淺入深展開研究。本文從圖流的近似存儲算法入手，首先研究了支持簡單的數(shù)據(jù)項(xiàng)查詢的數(shù)據(jù)流摘要算法，之后又進(jìn)一步研究了支持復(fù)雜的圖結(jié)構(gòu)查詢的圖流摘要算法。為了提高查詢時(shí)效性，本文又以三角形近似計(jì)數(shù)為例研究了圖流上的近似持續(xù)查詢算法。本文在這些問題上提出了多個(gè)原創(chuàng)算ApproximateGraphStreamProcessingXiangyangGou(ComputerAABSTRACTAgraphstreamisacontinuoussequeriesindatastreams,likequeriesaboutpfdataitems,arealsoimportantingraphsmembershipquery,frequencyquertheSlidingsketchhashigheraccuracAmongexistinggraphstreamsketches,thosewithareusuallybasedongroupingnusage,theiraccuracyispoor.Thisrshcompression.ComparedtopriorwhenprocessingedgeinsertionsanddeletimuchhigheraccuracythanpriorartofgraphstrAtlast,thispaperusesappimatealgorithmsforcontinuousqueries,andproposesaspeedandsmallmemoryusage.Theyneedtocarryoutquemarizeddatawhenquerying.Thereforeittakestimebeforethequhighmemoryconsumptionheseapproximatealgorithms,aptrepresentativekinds.Approximatetrianglecountingalgorithmsingrapsamplegraph.Thentheymaintainanapproximationofthetriabasedonthissamplegraph.ofrecentdata.Therefore,thispaperproposesanalgorithmforapproximatetriaVboundedmemoryconsumptionandsupportsmultipletrianglecountingcounting,weightedcounting,localcountingandglobalcounting.thatSWTChasahigheraccuracythanthebaselinemethod,whichisacombinationofffaroundthesetopics,andexperimentalresultscon?rmtheirsuperioritycomparKEYWORDS:Graph,GraphStream,D 3.1數(shù)據(jù)流摘要通用模型 3.5.1支持存在性查詢的算法: 3.5.2支持頻率查詢的算法: 5.2.3滑動(dòng)窗口內(nèi)互異邊數(shù)目的估計(jì) X 6.1.2基于哈希聚合的圖流摘要算法 3.1數(shù)據(jù)流摘要實(shí)驗(yàn)中使用的算法的縮寫 4.5GSS在SSSP查詢中的平均相 3.5存在性查詢的錯(cuò)誤率 3.6支持存在性查詢的摘要的更新速度 3.7頻率查詢的平均相對誤差 3.8支持頻率查詢的摘要的更新速度 3.9高頻項(xiàng)查詢的錯(cuò)誤率 3.10高頻項(xiàng)查詢的平均相對誤差 3.11支持高頻項(xiàng)查詢的摘要的更新速度 4.2哈希函數(shù)值域大小對算子正確率的影響 4.4使用平方哈希后的GSS矩陣結(jié)構(gòu) 4.6異構(gòu)圖流處理系統(tǒng)架構(gòu) 4.8一跳前驅(qū)查詢準(zhǔn)確率 4.9一跳后繼查詢準(zhǔn)確率 5.2基準(zhǔn)方案的算法框架 5.7不同種類的有向三角形 5.10精確度隨滑動(dòng)窗口長度的變化 5.11精確度隨樣本率的變化 5.12精確度隨重復(fù)邊比例的變化 5.13有向三角形類型A估算效果 5.14有向三角形類型B估算效果 5.15局部三角形估算 5.16帶權(quán)計(jì)數(shù)估算效果 5.17不同算法的處理速度 1組，表示兩個(gè)實(shí)體之間的關(guān)聯(lián)關(guān)系。根據(jù)是否區(qū)分邊的方向，圖可以分為有向圖和無向圖兩大類，圖1.1分別展示了有向圖和無向圖的示意圖。由于圖結(jié)構(gòu)同時(shí)包含了實(shí)體的屬性信息和實(shí)體之間的復(fù)雜聯(lián)系，大量不同的查詢可以在圖結(jié)構(gòu)上進(jìn)行，例如可v3v3v1v1v2v5v5v5v5v4v4v2/v4v3/有向圖無向圖近年來，隨著信息技術(shù)的不斷發(fā)展，圖數(shù)據(jù)的規(guī)模和實(shí)時(shí)性都不斷增加，圖流得到了愈發(fā)廣泛的關(guān)注。圖流是一個(gè)持續(xù)不斷到達(dá)的數(shù)據(jù)項(xiàng)序列，序列中的每一個(gè)數(shù)據(jù)項(xiàng)都代表了圖中的一條邊。這個(gè)數(shù)據(jù)項(xiàng)序列組成了一個(gè)持續(xù)不斷變化的動(dòng)態(tài)圖。圖流在互聯(lián)網(wǎng)環(huán)境中具有廣泛的應(yīng)用，下面列舉幾個(gè)應(yīng)用示例。1.一個(gè)社交網(wǎng)絡(luò)中的所有用戶組成了一個(gè)點(diǎn)集合，而用戶之間的發(fā)送信息，點(diǎn)贊等互動(dòng)則組成了一個(gè)持續(xù)到達(dá)的邊序列，從而形成了一個(gè)圖流數(shù)據(jù)集。該圖流形成了表示用戶間交互的動(dòng)態(tài)圖。在該動(dòng)態(tài)圖上可以通過計(jì)數(shù)三角形進(jìn)行社區(qū)2.互聯(lián)網(wǎng)中的IP地址組成了一個(gè)點(diǎn)集合，而IP之間的數(shù)據(jù)包通信則組成了持續(xù)到達(dá)的邊序列，它們一起組成了一個(gè)圖流數(shù)據(jù)集。在這樣的圖流數(shù)據(jù)集中，可23.電商平臺上的用戶和商家組成了一個(gè)點(diǎn)集合，而交易行為則組成了一個(gè)不斷到達(dá)的邊序列，其中的每一條邊代表一個(gè)用戶在一個(gè)商家處完成了一次購買，該邊序列組成了一個(gè)圖流數(shù)據(jù)集，并構(gòu)成了表示電商交易數(shù)據(jù)的動(dòng)態(tài)圖。在此動(dòng)態(tài)圖上可以進(jìn)行子圖匹配來發(fā)現(xiàn)刷單行為，通過環(huán)路檢測來發(fā)現(xiàn)可能的洗錢活1.更新速度快：圖流中數(shù)據(jù)到達(dá)的速度非常高，在大型社交網(wǎng)絡(luò)和數(shù)據(jù)中心，圖流數(shù)據(jù)的吞吐量可以高達(dá)每秒數(shù)萬甚至數(shù)十萬[14]。這要求數(shù)據(jù)結(jié)構(gòu)和算法能夠2.數(shù)據(jù)規(guī)模大：圖流數(shù)據(jù)組成的動(dòng)態(tài)圖可以有數(shù)億條邊。例如在twitter上，每天有超過一億用戶登錄，超過5億tweet被發(fā)布1，這些tweet在被轉(zhuǎn)發(fā)或評論時(shí)3.查詢復(fù)雜度高：圖流形成的圖具有復(fù)雜的拓?fù)浣Y(jié)構(gòu)，在其上進(jìn)行的查詢具有多項(xiàng)式級[1,9]甚至指數(shù)級[7-8]的復(fù)雜度，在高速更新的場景下對這些查詢的支4.單輪實(shí)時(shí)處理：每當(dāng)一條邊到達(dá)時(shí)，需要根據(jù)已到達(dá)的數(shù)據(jù)對該邊進(jìn)行實(shí)時(shí)處理，例如持續(xù)查詢問題中需要根據(jù)新邊實(shí)時(shí)更新查詢結(jié)果，而在圖采樣算法中則需要實(shí)時(shí)決定新邊是否被采樣。此外，算法只能在圖流數(shù)據(jù)的一輪到達(dá)中對在圖流場景下，數(shù)據(jù)存儲和查詢都面臨著新的挑戰(zhàn)：從存儲的角度看，圖流同時(shí)具有圖和數(shù)據(jù)流兩方面的特性，二者的存儲方法在圖流場景下都有應(yīng)用，但也都有不Row，稀疏行壓縮)等形式。這些結(jié)構(gòu)能夠同時(shí)保存圖中的點(diǎn)和邊的信息,以及圖的拓?fù)浣Y(jié)構(gòu)，從而支持各種復(fù)雜的圖查詢，但是，它們在圖流場景下空間和時(shí)間效率卻不盡人意。鄰接矩陣的存儲空間是o(|V|2)的，|V|為圖流中點(diǎn)集合的大小，而其他兩個(gè)數(shù)據(jù)結(jié)構(gòu)的存儲空間都是o(|E|)的，|E|為圖流中邊集合的大小。在應(yīng)用中，大規(guī)模圖往往十分稀疏，也就是說點(diǎn)集合的規(guī)模十分巨大，這使得鄰接矩陣o(|V|2)的復(fù)雜o(|V|)的,在更新速度較高的圖流場景，這樣的更新速度并不令人滿意。此外，很多1https://www.websitehostingratin3情況下，圖流處理需要在資源緊張的嵌入式設(shè)備環(huán)境下進(jìn)行，例如在路由器或者交換一些研究工作設(shè)計(jì)了將圖數(shù)據(jù)進(jìn)行摘要存儲以壓縮空間占用的方案[15-17]。但是，這些另一方面，傳統(tǒng)的數(shù)據(jù)流存儲方案則側(cè)重于對于獨(dú)立數(shù)據(jù)項(xiàng)的存儲和查詢，并追求高空間效率和高更新速度。經(jīng)典數(shù)據(jù)結(jié)構(gòu)如哈希表及其各種變體[18-19]、平衡二叉搜索樹[20]等可以用于保存數(shù)據(jù)流中的數(shù)據(jù)項(xiàng)，而通過引入可控誤差來獲取更高時(shí)間和空間效率的摘要方案[21-23]也得到了廣泛的研究。使用這些數(shù)據(jù)流摘要方案來對圖流中的點(diǎn)或者邊信息保存時(shí)，可以達(dá)到線性（o(|E|或者o(|v|)）的空間占用以及常數(shù)級外的復(fù)雜查詢。雖然研究者們近年也提出了一些專門為圖流設(shè)計(jì)的摘要方案[24-25]，但是它們或者更新速度較低，或者在查詢時(shí)具有較高的誤差。綜上所述，圖流數(shù)據(jù)的存儲問題依然上文這些存儲算法在圖流數(shù)據(jù)到達(dá)的過程中不斷更新數(shù)據(jù)存儲，而當(dāng)需要回答查詢時(shí)，則在當(dāng)前存儲的數(shù)據(jù)上運(yùn)行靜態(tài)圖查詢算法得到結(jié)果。因此查詢需要一定的響應(yīng)時(shí)間。而在一些應(yīng)用中需要實(shí)現(xiàn)持續(xù)查詢，也就在圖流數(shù)據(jù)項(xiàng)不斷到達(dá)情況下實(shí)時(shí)或者任意時(shí)刻都能立刻報(bào)告答案的目的。這使得本已較為復(fù)雜的圖查詢變得更有挑戰(zhàn)性。在這樣的圖流查詢算法研究中，除了精確查詢的算法外[26-28]，研究者們也提出了一些近似查詢的算法[29-30]。這些近似算法通過引入一部分的誤差來提升處理圖流更新本文的研究從存儲方法和查詢算法兩方面展開，分別研究數(shù)據(jù)流和圖流上的摘要本文將以圖流數(shù)據(jù)近似處理為核心，由淺入深，從三個(gè)方面展開研究。首先，本邊的信息存儲。雖然目前已有多種數(shù)據(jù)流摘要算法，但是這些摘要算法大多不支持?jǐn)?shù)據(jù)老化機(jī)制。本文設(shè)計(jì)了一種數(shù)據(jù)流摘要算法框架，其能夠應(yīng)用于多種已有數(shù)據(jù)流摘要算法，使它們支持經(jīng)典數(shù)據(jù)老化模型——滑動(dòng)窗口模型。通過應(yīng)用于不同的摘要算法，該框架可以支持多種經(jīng)典數(shù)據(jù)流查詢，并取得高精確度。上述數(shù)據(jù)流摘要算法雖4然能夠保存圖流中點(diǎn)和邊的信息，但是卻不能保存圖的拓?fù)浣Y(jié)構(gòu)，不能支持前驅(qū)/查詢，路徑查詢等更復(fù)雜的查詢。因此，第四章進(jìn)一步研究了圖流摘要算法GSS，該一種基于采樣的近似三角形計(jì)數(shù)算法SWTC。該算法支持對圖流中的三角形數(shù)目的持續(xù)查詢，也就是隨著圖流更新實(shí)時(shí)維護(hù)三角形數(shù)目的估算值。相比已有三角形近似計(jì)數(shù)算法，該算法可以應(yīng)用于更加復(fù)雜的真實(shí)場景，支持重復(fù)邊以及滑動(dòng)窗口模型，并例如給定一條邊，查詢邊在圖流中是否存在，或者找到作為邊源點(diǎn)出現(xiàn)頻率最高的一批點(diǎn)。這些查詢雖然簡單，但是卻在網(wǎng)絡(luò)安全[31-32]等領(lǐng)域著重要的應(yīng)用。舉例來說，互聯(lián)網(wǎng)的通信數(shù)據(jù)組成了一個(gè)圖流，其中每一個(gè)點(diǎn)代表了一個(gè)IP，一條撲結(jié)構(gòu)，所以可以將每個(gè)數(shù)據(jù)項(xiàng)獨(dú)立存儲。這時(shí)圖流被作為更廣泛意義上的數(shù)據(jù)流看比使用哈希表等精確數(shù)據(jù)結(jié)構(gòu)，這些摘要算法的空間占用更小，可以保存入cache等然而，目前存在的大部分?jǐn)?shù)據(jù)流摘要算法只能處理單增模型，也就是只能處理數(shù)據(jù)項(xiàng)的添加，不能支持?jǐn)?shù)據(jù)項(xiàng)的刪除或者老化。而在現(xiàn)代圖流應(yīng)用中，很多場景需要?jiǎng)h除過于老舊的數(shù)據(jù)，而只關(guān)注最新的數(shù)據(jù)。例如在網(wǎng)絡(luò)安全領(lǐng)域，管理者更希望發(fā)現(xiàn)新近發(fā)生的黑客攻擊以進(jìn)行阻止，而對很久之前的攻擊的關(guān)注度則較低。這種情況在數(shù)據(jù)老化模型里，最常見的模型為滑動(dòng)窗口模型。該模型使用一個(gè)窗口，只將最近一段時(shí)間內(nèi)到達(dá)的數(shù)據(jù)項(xiàng)包含在內(nèi)，并將其視為有效。而窗口之外的數(shù)據(jù)則是無效的過期數(shù)據(jù)。摘要算法若希望支持該模型，一般需要設(shè)計(jì)機(jī)制去刪除窗口外的數(shù)據(jù)。目前已有的支持滑動(dòng)窗口的數(shù)據(jù)流摘要算法包括ForgetfulBloom?lter[34]、ECM等。然而，這些算法在處理滑動(dòng)窗口模型時(shí)，因?yàn)闊o法及時(shí)刪除所有的過期數(shù)據(jù)，會在第三章中，本文設(shè)計(jì)了一種處理滑動(dòng)窗口模型的數(shù)據(jù)流摘要算法框架Slidingsketch。該框架可以應(yīng)用于多種已有的，不支持滑動(dòng)窗口模型的摘要算法，如Bloom5?lter和CMsketch，并使它們支持滑動(dòng)窗口模型。精確刪除所有過期數(shù)據(jù)需要保存窗因此處理滑動(dòng)窗口模型的算法一般都選擇保存一個(gè)接近于滑動(dòng)窗口的數(shù)據(jù)流片段。但是如何讓這個(gè)片段足夠接近滑動(dòng)窗口是一個(gè)嚴(yán)苛的挑戰(zhàn)。為了解決這一挑戰(zhàn)。Slidingsketch利用了已有的一類摘要算法的相似點(diǎn)。這些摘要算法都將每個(gè)數(shù)據(jù)項(xiàng)使用哈希函數(shù)映射到多個(gè)存儲位置，在其中保存多份相關(guān)信息，在查詢時(shí)返回其中最準(zhǔn)確的一個(gè)。Slidingsketch通過使用異步老化的機(jī)制，讓每個(gè)數(shù)據(jù)項(xiàng)的不同映射位置保存不同數(shù)據(jù)流片段內(nèi)的信息，最終實(shí)現(xiàn)任何時(shí)刻查詢時(shí)，總有一個(gè)映射位置保存了一個(gè)足夠通過應(yīng)用于不同的摘要算法，Slidingsketch可以支持包括存在性查詢，頻率查詢和高頻項(xiàng)查詢在內(nèi)的多種查詢。實(shí)驗(yàn)結(jié)果表明Slidingsketch在上述的數(shù)據(jù)流摘要算法只能回答圖流中的點(diǎn)和邊信息查詢，但是沒有保存圖的拓?fù)浣Y(jié)構(gòu)，不能回答例如路徑查詢等更復(fù)雜的圖結(jié)構(gòu)查詢。進(jìn)一步的，在第四章本文研目前已有的圖流摘要算法可以分為兩類，其中一類是基于數(shù)據(jù)抽取的摘要算法，它們從圖流中抽取部分?jǐn)?shù)據(jù)保存，每種摘要只能支持特定的查詢。另一類則是將點(diǎn)和聚合類摘要算法可以進(jìn)一步細(xì)分為兩類，一類尋找拓?fù)浣Y(jié)構(gòu)上相似的點(diǎn)進(jìn)行合并以實(shí)在第四章中，本文設(shè)計(jì)了一種具有高更新速度、高空間效率，支持多種查詢，并圖流中的多個(gè)點(diǎn)可能會得到相同的哈希值，這些點(diǎn)會被映射到摘要圖中的同一個(gè)點(diǎn)。與這些點(diǎn)相連的邊也會被聚合。通過設(shè)置哈希函數(shù)值域，GSS可以控制壓縮后的摘要6這使得它可以使用相同的空間保存更大的摘要圖，以達(dá)到更高的精確度。該數(shù)據(jù)結(jié)構(gòu)還具有極高的更新效率，可以滿足圖流數(shù)據(jù)高速更新的需求。本文還進(jìn)一步提出了核上述圖流摘要算法雖然可以支持多種查詢，但是這些查詢需要在摘要數(shù)據(jù)上運(yùn)行靜態(tài)圖查詢算法得到結(jié)果，從發(fā)起查詢到得到結(jié)果需要一定的響應(yīng)時(shí)間。而一些應(yīng)用需要持續(xù)查詢，也就是在圖流更新的過程中實(shí)時(shí)維護(hù)特定查詢的查詢結(jié)果。例如在電商場景中，需要持續(xù)維護(hù)圖流中的環(huán)路集合以發(fā)現(xiàn)可能的洗錢行為[36]。這樣的場景需要專門為圖流設(shè)計(jì)的持續(xù)查詢算法。由于圖查詢復(fù)雜度高，同時(shí)很多圖流處理都需要在資源緊張的嵌入式設(shè)備上進(jìn)行，除了精確的持續(xù)查詢算法，空間占用更低，計(jì)算代價(jià)更小的近似查詢算法也得到了廣泛的關(guān)注[29-30]。在近似持續(xù)查詢算法中，最具有代表性的一類研究便是近似三角形計(jì)數(shù)算法。三角形計(jì)數(shù)在社區(qū)發(fā)現(xiàn)[37]、話題檢測[38]和異常檢測[39]等領(lǐng)域都有著廣泛應(yīng)用。在這些應(yīng)用中，三角形的數(shù)目不需要完全精確，一定的誤差是可以接受的。此外，相比其他查詢，三角形計(jì)數(shù)問題更容易通過采樣方法來估算，也就是從圖流中采樣出一部分的邊組成一個(gè)較小的樣本圖，并以樣本圖中的三角形數(shù)目為依據(jù)來估算圖流中的三角形數(shù)目。這使得基于采樣的三角形近似計(jì)數(shù)一直是近年來的研究熱點(diǎn)之一。本文以圖流雖然基于采樣的圖流三角形近似計(jì)數(shù)問題已經(jīng)有多項(xiàng)研究工作[30,40]。但是這些研究工作往往假設(shè)一個(gè)十分理想的場景：圖中的邊不會被刪除，而且同一條邊不會重復(fù)出現(xiàn)。在實(shí)際應(yīng)用中，情況往往復(fù)雜的多。圖流中的數(shù)據(jù)可能需要被老化，同一條邊也可能在圖流中多次出現(xiàn)。例如在社交網(wǎng)絡(luò)中，每一個(gè)用戶是一個(gè)點(diǎn)，兩個(gè)用戶之間的一次交互是一條邊，用戶交互數(shù)據(jù)組成了一個(gè)高速更新的圖流。由于兩個(gè)用戶之間會多次交互，所以圖流中存在重復(fù)邊。在這樣的社交網(wǎng)絡(luò)中進(jìn)行話題檢測時(shí)，近期的熱門話題價(jià)值更高，所以過去的數(shù)據(jù)需要被老化掉。而在數(shù)據(jù)老化的模型中，最常見的是滑動(dòng)窗口模型。因此，本文希望設(shè)計(jì)一種支持滑動(dòng)窗口模型和重復(fù)邊的三角形近7counting即只考慮互異三角形的數(shù)目，以及帶權(quán)計(jì)數(shù)（weightedcou重復(fù)邊組成不同的三角形。本文希望算法同時(shí)支持兩種查詢語義。目前已有的摘要算法在該場景下都有各自的問題，一些工作不能處理邊刪除[41-42]，還有一些工作則會受到重復(fù)邊的干擾，不能支持二項(xiàng)計(jì)數(shù)[30,43]。此外，本文希望算法的空間消耗具有限定大小，而不是隨著圖流的流量不受限制地變化，以防止在資源緊張的應(yīng)用中超出預(yù)留在第五章中，本文設(shè)計(jì)了一種基于采樣的三角形近似計(jì)數(shù)方法，SWTC（Sliding似計(jì)數(shù)，而且具有限定大小的空間消耗。SWTC算法同時(shí)支持二項(xiàng)計(jì)數(shù)和帶權(quán)計(jì)數(shù)兩和局部三角形計(jì)數(shù)（localcounting即計(jì)數(shù)整個(gè)圖流中的三角形，或者三角形。SWTC使用了一種獨(dú)創(chuàng)的滑動(dòng)窗口模型下生成無偏樣本圖的方法。該方法基于定長切片(?xed-lengthslicing即選取一系列的固定時(shí)間點(diǎn)，將圖流切分為連續(xù)的長度相同的片段，通過片段組合來實(shí)現(xiàn)對滑動(dòng)窗口的查詢。SWTC算法融合了定長切片和優(yōu)先級采樣，從而設(shè)計(jì)出了具有限定空間消耗的無偏采樣的方案。基于定長切片的方案，本文也設(shè)計(jì)出了一種估算滑動(dòng)窗口內(nèi)邊數(shù)的方法，并以樣本圖中的三角形數(shù)目和滑動(dòng)窗口內(nèi)的邊數(shù)為依據(jù)，估計(jì)滑動(dòng)窗口內(nèi)的三角形數(shù)目。本文也對SWTC了一系列的改進(jìn)方案，包括避免速度低谷的計(jì)數(shù)預(yù)測方案和穩(wěn)定精確度的分組異步采樣方案。SWTC是第一個(gè)滿足本文設(shè)計(jì)要求的三角形近似計(jì)數(shù)方法。實(shí)驗(yàn)表明SWTC近似存儲領(lǐng)域。第三章的研究工作為滑動(dòng)窗口模型下支持?jǐn)?shù)據(jù)項(xiàng)查詢的數(shù)據(jù)流摘要算法，第四章的研究工作則進(jìn)一步結(jié)合了圖流中的拓?fù)浣Y(jié)構(gòu)信息，設(shè)計(jì)了圖流數(shù)據(jù)專用的摘要算法。這兩項(xiàng)工作的主要目的是以高更新速度和高空間效率存儲數(shù)據(jù)，對查詢的時(shí)效性要求不高。而第三項(xiàng)工作（第五章）則屬于圖流上的近似持續(xù)查詢算法。該工作在圖流不斷更新的過程中持續(xù)維護(hù)三角形數(shù)目的估算值，在任意時(shí)刻都能實(shí)時(shí)報(bào)本文研究了圖流數(shù)據(jù)的近似存儲和近似查詢算法，分別從數(shù)據(jù)流摘要算法，圖流1.本文研究了支持獨(dú)立數(shù)據(jù)項(xiàng)查詢的數(shù)據(jù)流摘要算法，設(shè)計(jì)了在滑動(dòng)窗口模型下8哈希表哈希表鄰接鏈表二叉搜索樹二叉搜索樹鄰接矩陣數(shù)據(jù)流摘要算法支持圖結(jié)構(gòu)查詢圖流摘要算法（第四章）精確子圖匹配精確子圖匹配精確正則路徑查詢近似三角形計(jì)數(shù)近似頻繁子圖挖掘精確算法近似算法數(shù)據(jù)存儲持續(xù)查詢圖流處理其支持滑動(dòng)窗口模型。通過將該框架應(yīng)用于不同的摘要算法，Slidingsketch可以支持圖流中邊和點(diǎn)的存在性查詢、頻率查詢和高頻項(xiàng)查詢等。而且，通過應(yīng)用獨(dú)創(chuàng)的異步老化的機(jī)制，Slidingsketch以較低的代價(jià)實(shí)現(xiàn)了對滑動(dòng)窗口模型2.本文研究了支持圖結(jié)構(gòu)查詢的圖流摘要方法，設(shè)計(jì)了圖流摘要算法GSS，GSS首先基于哈希方法將原圖流壓縮為一個(gè)較小的摘要圖，然后設(shè)計(jì)緊湊數(shù)據(jù)結(jié)構(gòu)對摘要圖進(jìn)行存儲。GSS具有高更新速度和高空間效率，且同時(shí)支持圖流上的3.本文研究了圖流上的近似持續(xù)查詢算法，設(shè)計(jì)了滑動(dòng)窗口模型下，面向有重復(fù)算法基于持續(xù)維護(hù)的無偏樣本圖，能夠支持圖流中全局和局部的三角形數(shù)目的持續(xù)查詢。該算法基于定長切片方案，具有限定大小的空間占用，而且能夠同本論文在的結(jié)構(gòu)如下：第二章將介紹相關(guān)研究現(xiàn)狀，包括本文研究中使用的數(shù)據(jù)模型定義，問題定義和相關(guān)工作簡介。第三章將介紹滑動(dòng)窗口模型下的數(shù)據(jù)流摘要框架Slidingsketch，第四章將介紹基于哈希聚合的圖流摘要算法GSS，第五章將介紹滑動(dòng)窗口模型下，面向有重復(fù)邊的圖流的三角形近似計(jì)數(shù)算法SWTC。最后，第六章將9本章將給出本文中使用的數(shù)據(jù)模型和問題的正式定義，并簡要介紹這些問題相關(guān)項(xiàng)可以是任意形式的數(shù)據(jù)。在實(shí)際應(yīng)用中，數(shù)據(jù)流一般是從數(shù)據(jù)源持續(xù)接收的，例如從互聯(lián)網(wǎng)上收到的網(wǎng)絡(luò)包或者社交網(wǎng)絡(luò)服務(wù)器收到的用戶通訊記錄?，F(xiàn)代應(yīng)用中的數(shù)據(jù)流具有更新速度快，數(shù)據(jù)規(guī)模大的特點(diǎn)，此外，對于數(shù)據(jù)流中的數(shù)據(jù)項(xiàng)的處理需要按照其到達(dá)順序?qū)崟r(shí)進(jìn)行，而且處理時(shí)沒有被保存的數(shù)據(jù)項(xiàng)將在之后丟失，因此算法圖流是數(shù)據(jù)流和圖結(jié)合而產(chǎn)生的數(shù)據(jù)模型。圖流一般被定義為一個(gè)有持續(xù)到達(dá)的個(gè)點(diǎn)同時(shí)到達(dá)的還有它的完整的鄰居列表。第一種模型被稱邊流：邊流模型下，圖流為一個(gè)持續(xù)不斷到達(dá)的數(shù)據(jù)項(xiàng)序列S={e1,e2,e3ex},點(diǎn)流：點(diǎn)流模型下，圖流為一個(gè)持續(xù)不斷到達(dá)的數(shù)據(jù)項(xiàng)序列S={u絡(luò)、電商數(shù)據(jù)等示例中，圖流都被維護(hù)為邊流模型，大部分的圖流研究[25,30,44]也使用了邊流模型。只有少數(shù)以圖流劃分算法為主的相關(guān)工作中[45-46]中使用了點(diǎn)流模型。本t1t2t3t4v2v1v1v2↓v4!v3v3v3v1!v4!v5v5v5v2點(diǎn)流t1v1v4t2v1v2t3v3v1t4v2v3t5v3v4邊流t6v3v5t7v5v2圖流中不斷到達(dá)的數(shù)據(jù)項(xiàng)組成了一個(gè)持續(xù)不斷變化的動(dòng)態(tài)圖。圖2.1中的兩種形與一般的數(shù)據(jù)流相比，圖流不僅同樣具有更新速度快，數(shù)據(jù)規(guī)模大，需要單輪實(shí)時(shí)處理的特點(diǎn)，同時(shí)還結(jié)合了圖數(shù)據(jù)的復(fù)雜性。數(shù)據(jù)流中的數(shù)據(jù)項(xiàng)被認(rèn)為是互相獨(dú)立的，而圖流中的邊卻通過共同的端點(diǎn)互相關(guān)聯(lián)，最終形成了復(fù)雜的圖結(jié)構(gòu)，而在這樣的圖結(jié)構(gòu)上，可以進(jìn)行的查詢也更加多樣，復(fù)雜度也更高，這使得對圖流數(shù)據(jù)的存儲舉例來說，社交網(wǎng)絡(luò)分析可能只關(guān)心最近的用戶交互，因?yàn)橛脩舻纳缃恍袨樵诓粩嘧冊谶@種情況下時(shí)，可以使用滑動(dòng)窗口模型?；瑒?dòng)窗口模型分為基于時(shí)間的滑動(dòng)窗基于時(shí)間的滑動(dòng)窗口：一個(gè)長度為N的滑動(dòng)窗口包含所有時(shí)間戳在(T-N,T]范在實(shí)際應(yīng)用中，基于時(shí)間的滑動(dòng)窗口更加常見也更加復(fù)雜。基于計(jì)數(shù)的滑動(dòng)窗口可以看作是一種簡化的基于時(shí)間的滑動(dòng)窗口，也就是每一個(gè)時(shí)間單元內(nèi)有且只有一條圖流在滑動(dòng)窗口模型下導(dǎo)出的動(dòng)態(tài)圖中只包含在滑動(dòng)窗口內(nèi)的邊，滑動(dòng)窗口之外的邊被認(rèn)為失效。隨著時(shí)間推移，滑動(dòng)窗口內(nèi)會不斷有新邊加入和舊邊被刪除，從而導(dǎo)致其形成的的動(dòng)態(tài)圖不斷發(fā)生變化。圖2.2展示了滑動(dòng)窗口和t7時(shí)刻滑動(dòng)窗口中的邊組成的動(dòng)態(tài)圖的示例。本文用W?N表示T時(shí)刻長度為N的滑動(dòng)窗口。更一般地，t1v1v4Wt2t3t4t5t6t7v1v2v3v1v2v3v3v4v3v5v5v2v5v2v4v3一些應(yīng)用會明確地給出指示，刪除之前到達(dá)的數(shù)據(jù)項(xiàng)。例如在電商數(shù)據(jù)中，可以的一條邊。同一條邊可以在圖流中的不同時(shí)刻被多次加入或者刪除。多次加入可視作同一條邊的多個(gè)副本，而每一個(gè)刪除項(xiàng)ei=(u,U,?,ti)在不特殊指明的情況下，表示滑動(dòng)窗口模型也可以應(yīng)用在含刪除的圖流上。當(dāng)使用了滑動(dòng)窗口模型時(shí)，刪除項(xiàng)注意顯式刪除和滑動(dòng)窗口模型有所不同，顯式刪除中，每一個(gè)數(shù)據(jù)項(xiàng)的刪除是通過圖流中數(shù)據(jù)項(xiàng)指明的，刪除已有的數(shù)據(jù)項(xiàng)的順序可以是任意的。而在滑動(dòng)窗口模型中，數(shù)據(jù)項(xiàng)的刪除是隱式的，隨著時(shí)間的流逝舊的數(shù)據(jù)項(xiàng)會自發(fā)地過期，這樣的過期事件需要算法自身去發(fā)現(xiàn)，而數(shù)據(jù)項(xiàng)過期的順序是固定的。這樣的區(qū)別使得處理顯式刪除模型和滑動(dòng)窗口模型的算法難以通用。將顯式刪除模型的算法用于滑動(dòng)窗口模型時(shí)，可能需要額外的數(shù)據(jù)結(jié)構(gòu)去維護(hù)數(shù)據(jù)項(xiàng)的時(shí)間順序，以確定每一個(gè)數(shù)據(jù)項(xiàng)過期的時(shí)刻。而滑動(dòng)窗口模型的算法可能由于不能處理任意順序的刪除而無法用于顯式刪除本節(jié)對本文研究的問題給出定義，并介紹不同問題的已有研究工作。首先，2.2.1節(jié)將介紹數(shù)據(jù)流上的常見查詢和摘要算法，并介紹本文研究的關(guān)注重點(diǎn)，滑動(dòng)窗口下的數(shù)據(jù)流摘要的已有算法。因?yàn)閳D流自身是數(shù)據(jù)流的一種，這些數(shù)據(jù)流摘要算法也可以應(yīng)用于圖流中，對圖流上的邊和點(diǎn)的頻率等屬性進(jìn)行存儲和查詢。但是當(dāng)以更復(fù)雜圖結(jié)構(gòu)查詢?yōu)槟繕?biāo)時(shí)，需要更加復(fù)雜的存儲結(jié)構(gòu)，2.2.2節(jié)將介紹常見的精確圖存儲結(jié)構(gòu)，這些存儲結(jié)構(gòu)為之后的圖流近似存儲奠定了基礎(chǔ)。2.2.3節(jié)和2.2.4節(jié)將進(jìn)一步介紹圖和圖流的摘要算法，相比精確存儲結(jié)構(gòu)，這些摘要算法雖然可能引入誤差，但具有更低的空間消耗，可以用來存儲大規(guī)模圖數(shù)據(jù)。最后，2.2.5節(jié)關(guān)注圖流上的持續(xù)查圖流是數(shù)據(jù)流的一類，數(shù)據(jù)流中的一些常見查詢在圖流中同樣重要。本文重點(diǎn)研究三種數(shù)據(jù)流基本查詢：存在性查詢、頻率查詢和高頻項(xiàng)查詢。下文將分別介紹這些有在它們?nèi)珵?時(shí)才給出肯定回答，否則便給出否定回答。Bloom?l即使數(shù)據(jù)項(xiàng)不在數(shù)據(jù)集中，它也有概率給出肯定回答。后續(xù)行了多種改進(jìn)以使其支持不同的場景，例如Bloomier?lter[21][22]CMsketch由一個(gè)被均分為k段的計(jì)數(shù)器數(shù)組組成。所有的計(jì)數(shù)器都被初始化為說報(bào)告出的結(jié)果只會比真實(shí)結(jié)果高，不會比真實(shí)結(jié)果低。CUsketc有和CMsketch相似的數(shù)據(jù)結(jié)構(gòu)，但是不同的更新策略。它們具有更小的誤差，但是包括Pyramidsketch[53]、Augmentedsketch[一些應(yīng)用只關(guān)心頻率較高的數(shù)據(jù)項(xiàng)，例如在網(wǎng)絡(luò)異常檢查中，發(fā)出IP包數(shù)目大，也就是作為邊源點(diǎn)出現(xiàn)頻率高的IP較為可疑。高頻項(xiàng)查詢便是找出頻率較高的數(shù)據(jù)項(xiàng)的查詢。根據(jù)對“高頻率”的定義方法的不同，高頻項(xiàng)查詢可以分為Top-K查詢和heavyhitter查詢兩種語義。Top-K查詢?yōu)檎页鲱l率最大的K個(gè)數(shù)據(jù)項(xiàng)，而heavyhitter查詢則為找出頻率超出一個(gè)給定閾值的查詢。大部分支持高頻項(xiàng)查詢的摘要同時(shí)支持兩種查詢。由于heavyhitter查詢的頻率閾值在應(yīng)用中難以確定，Top-K查詢使用得更雖然上一節(jié)介紹的頻率查詢摘要也能應(yīng)用于高頻項(xiàng)查詢，但是專門為高頻項(xiàng)查詢設(shè)計(jì)的摘要算法通過犧牲對于低頻項(xiàng)的支持獲得了更小的空間占用。當(dāng)前最好的高頻項(xiàng)查詢摘要算法是HeavyKeeper[58]。它對于數(shù)據(jù)流中的數(shù)據(jù)項(xiàng)頻率提供查詢支持，并且為高頻項(xiàng)的查詢結(jié)果給出精確度保證。它使用一個(gè)被稱為指數(shù)衰減（count-而在高頻項(xiàng)查詢中達(dá)到了高精確度。其他的高頻項(xiàng)查詢算法包括Frequent[59]、Lossycounting[60]、Space-Saving[3通，在滑動(dòng)窗口模型下，即使是支持顯式刪除的算法需要輔助數(shù)據(jù)結(jié)構(gòu)來按時(shí)序保存滑動(dòng)窗口內(nèi)的所有數(shù)據(jù)項(xiàng)。這樣的輔助數(shù)據(jù)結(jié)構(gòu)消耗的空間遠(yuǎn)大于摘要算法自身。因本文根據(jù)支持的查詢，將滑動(dòng)窗口模型下的摘要算法分為三類：第一類是支持存在性查詢的算法，這些算法一般是在Bloom?lter上增加不同的改進(jìn)機(jī)制以適應(yīng)滑動(dòng)窗口。例如，F(xiàn)orgetfulBloom?lter[34]用多個(gè)Bloom?lter來記錄不要，這些數(shù)據(jù)流片段和滑動(dòng)窗口相交，可以使用這些片段的摘要來實(shí)現(xiàn)對于滑動(dòng)窗口?lter[63]等。第二類是支持頻率查詢的摘要算法，這類算法一般以CMsketch為基礎(chǔ)進(jìn)行改進(jìn)，如ECM（ExponentialCout-Min）sketch[35]將CMsketch數(shù)組的每一個(gè)位置從計(jì)數(shù)器更換為一個(gè)指數(shù)直方圖（ExponentialHistogram[64]指數(shù)直方圖是一種用于滑動(dòng)窗口中數(shù)據(jù)項(xiàng)數(shù)目估算的數(shù)據(jù)結(jié)構(gòu)，ECMsketch用每一個(gè)位置的指數(shù)直方圖來估算映射到該位置的數(shù)據(jù)項(xiàng)在滑動(dòng)窗口中的頻率，并結(jié)合CMsketch的更新和查詢機(jī)制來支持有精確度保證的頻率查詢。其他的相關(guān)工作包括SplitterWindowedCount-Min數(shù)據(jù)項(xiàng)設(shè)置一個(gè)窗口計(jì)數(shù)器（windowcounter該結(jié)構(gòu)包含一個(gè)頻率計(jì)數(shù)器以及一個(gè)時(shí)間戳隊(duì)列，每當(dāng)該數(shù)據(jù)項(xiàng)在數(shù)據(jù)流中到達(dá)時(shí)便增加頻率計(jì)數(shù)器，頻率計(jì)數(shù)器的值達(dá)到特定閾值時(shí)將其清空，并在隊(duì)列中記錄到達(dá)閾值的時(shí)刻。之后，算法可以根據(jù)隊(duì)列中時(shí)間戳的數(shù)量和計(jì)數(shù)器值來計(jì)算數(shù)據(jù)項(xiàng)的總頻率。通過定期清理滑動(dòng)窗口外的時(shí)間戳記錄，可以實(shí)現(xiàn)對于過期數(shù)據(jù)的刪除，而通過對所有數(shù)據(jù)項(xiàng)的windowcounter進(jìn)行衰減,則可以在內(nèi)存達(dá)到可用上限時(shí)去除低頻項(xiàng)，保持空間占用可控。Hung等人[69]結(jié)合了WindowCounter和數(shù)據(jù)流切片方案，提高了算法的更新速度，而之后的Window目前已有的滑動(dòng)窗口模型下的數(shù)據(jù)流摘要算法大多只能應(yīng)用于特定的查詢，不具有通用性。此外，它們?yōu)榱酥С只瑒?dòng)窗口模型引入的改進(jìn)機(jī)制仍然會消耗大量的存儲資源，導(dǎo)致其在可用空間較小時(shí)精度不佳。本文的第三章將利用已有摘要算法的共同特點(diǎn)，提出一種摘要算法框架，其可以應(yīng)用于多種已有的摘要算法，使它們支持滑動(dòng)窗口模型，并且通過應(yīng)用于不同的摘要算法，可以支持存在性查詢、頻率查詢和高頻數(shù)據(jù)流摘要算法具有更新速度高、空間占用小的優(yōu)點(diǎn)，可以保存在高速度，小容成數(shù)據(jù)緩存[71-72]和cache控制[73-75]等功能，也可以在存儲資源緊張的嵌入式環(huán)境，如路由器上部署，從而節(jié)省寶貴的存儲空間,完成IP查找[76-77]和異常檢測[78]等。在圖流場景下，這些數(shù)據(jù)流摘要算法可以用于保存圖流中的點(diǎn)和邊的信息，從而支持對于點(diǎn)和邊的高速查詢。但是，當(dāng)需要支持圖拓?fù)浣Y(jié)構(gòu)相關(guān)的查詢時(shí)。便要使用專門為圖設(shè)計(jì)的，更加復(fù)雜的存儲結(jié)構(gòu)。下文將分別介紹精確圖存儲結(jié)構(gòu)，圖摘要算法，和已有對于圖數(shù)據(jù)的存儲方式已經(jīng)有了大量研究。最常見的精確圖存儲數(shù)據(jù)結(jié)構(gòu)包括鄰其他位置則被填充0。鄰接矩陣只需要o(1)的時(shí)間便能定位到一條邊，對其進(jìn)行修改或查詢。通過進(jìn)行行掃描或者列掃描，鄰接矩陣還可以支持o(|V|)時(shí)間內(nèi)的點(diǎn)前驅(qū)/后繼查詢。但是鄰接矩陣存儲圖的空間代價(jià)為o(|V|×|V|),實(shí)際應(yīng)用中的大規(guī)模稀疏圖常常具有百萬甚至千萬以上的點(diǎn)，這種情況下上述空間代價(jià)是不可接受的，這也限鄰接鏈表是另一種常見的圖存儲結(jié)構(gòu)，它使用一個(gè)點(diǎn)表存放圖中的所有點(diǎn)。點(diǎn)表中的每個(gè)點(diǎn)具有一個(gè)后繼鏈表，以單鏈表的形式來存儲自己的后繼鄰居。而如果要在圖上進(jìn)行前驅(qū)查詢，還需要額外為每一個(gè)點(diǎn)建立一個(gè)前驅(qū)鏈表。在鄰接鏈表中，存儲空間代價(jià)為o(|E|),相比鄰接矩陣，這一空間代價(jià)即使在存儲大規(guī)模圖數(shù)據(jù)時(shí)也是可以被接受的。但是鄰接鏈表查找或修改一條邊的代價(jià)則為與邊源點(diǎn)的度數(shù)，也就是源接鏈表查找或修改一條邊的代價(jià)是o(|V|)的。在大規(guī)模圖中，很多點(diǎn)的度數(shù)十分高。這使得邊更新的代價(jià)較為高昂。除此之外，鄰接鏈表還可以通過定位到查詢點(diǎn)并讀取前驅(qū)/后繼鏈表的形式來進(jìn)行點(diǎn)前驅(qū)/后繼查詢，時(shí)間代價(jià)依的圖流應(yīng)用和系統(tǒng)都以鄰接鏈表為基礎(chǔ)[79-80]。鄰接鏈表的空間消耗雖然已經(jīng)是o(|E|)的，但是大量指針的使用使其仍會占用較多的內(nèi)存，此外，使用鏈表形式保存鄰居使得同一個(gè)點(diǎn)的鄰居在存儲上并不連續(xù)，缺加明顯。CSR則改善了這一問題。它使用一個(gè)點(diǎn)表存儲所有點(diǎn)，同時(shí)使用一個(gè)連續(xù)的邊表存儲全部的邊。每一個(gè)點(diǎn)發(fā)出的邊在邊表中占據(jù)一段連續(xù)的區(qū)域，在其中存儲邊的后繼點(diǎn)，且同一個(gè)點(diǎn)的鄰邊可以按照后繼點(diǎn)的ID排序存儲。點(diǎn)表中的每一個(gè)點(diǎn)存儲有自己的鄰邊集合的末尾在邊表中的偏移量，結(jié)合點(diǎn)表中上一個(gè)點(diǎn)的偏移量，便可以定位出該點(diǎn)的鄰邊集合的起始和結(jié)束，從而找到所有的鄰邊。與鄰接鏈表相同，當(dāng)同時(shí)要進(jìn)行前驅(qū)和后繼查詢時(shí)，還需要另外一個(gè)邊表存儲每個(gè)點(diǎn)的前驅(qū)集合。與鄰接鏈表相比，CSR中沒有使用指針，且每個(gè)點(diǎn)的鄰居連續(xù)存儲，因此具有更小的空間消耗和更好的局部性。通過對每個(gè)點(diǎn)的后繼進(jìn)行排序存儲，CSR還可以使用二分查找在O(log(|V|))的時(shí)間內(nèi)定位到一條邊。CSR進(jìn)行前驅(qū)/后繼查詢時(shí)的時(shí)間代價(jià)也保持在O(|V|)。但是CSR無法支持邊的添當(dāng)圖數(shù)據(jù)規(guī)模過大，或者存儲資源緊張時(shí)，可以選擇使用摘要算法來進(jìn)一步壓縮數(shù)據(jù)，節(jié)省存儲空間。目前已有的靜態(tài)圖摘要算法可以分為三類，基于數(shù)據(jù)聚合的方基于聚合的圖摘要算法在圖中尋找拓?fù)浣Y(jié)構(gòu)上相似的點(diǎn)或者邊，將它們聚合為超點(diǎn)(supernode)和超邊(superedge)來實(shí)現(xiàn)圖壓縮。例如，F(xiàn)an等人[17]針對不同查詢設(shè)計(jì)了不同的函數(shù)來聚合在該查詢上等價(jià)的點(diǎn)，以實(shí)現(xiàn)對該查詢無誤差的圖摘要。Raghavan等人[81]為網(wǎng)絡(luò)圖提出了一個(gè)雙層的壓縮表示，其中低層為若干較小的有向圖，每個(gè)有向圖描述了一組網(wǎng)頁及它們之間的關(guān)聯(lián)，而高層則為一個(gè)超點(diǎn)和超邊組成的有向圖，每一個(gè)超點(diǎn)代表了低層的一個(gè)有向圖，超邊則描述了這些網(wǎng)頁組之間的關(guān)聯(lián)。Riondato等人[82]則在圖摘要和代數(shù)聚類算法之間建立了聯(lián)系，設(shè)計(jì)了一種高效且誤差可控的基于點(diǎn)聚合的圖摘要算法。其他相關(guān)工作還包括發(fā)掘緊密連接的點(diǎn)簇并聚合的算法[83-84]和聚合高度數(shù)點(diǎn)周圍相似邊的算法[85-86]?；诔槿〉膱D摘要算法則關(guān)注特定的查詢，并且通過抽取和這些查詢相關(guān)的圖數(shù)證給出的近似解不超過兩點(diǎn)間真實(shí)距離的k倍。Sp了被稱為sparsi?er的結(jié)構(gòu)，可以為邊割集計(jì)算提供近似解。其點(diǎn)或者邊過濾的圖可視化的方法[87-88]等。比特壓縮的方法則通過點(diǎn)和邊的重排序以及壓縮編碼方式來達(dá)到壓縮存儲的目的。例如GBASE[89]中先將圖中點(diǎn)根據(jù)拓?fù)湎嗨菩詣澐譃槎鄠€(gè)子集，使得每兩個(gè)點(diǎn)集之間的連接盡量同質(zhì)化，也就是兩個(gè)點(diǎn)集中的點(diǎn)的連接或者特別密集，或者特別稀疏，之后使用zipblock編碼對每兩個(gè)點(diǎn)集之間的鄰接矩陣進(jìn)行壓縮編碼。Apostolico等人[90]則使用寬度優(yōu)先搜索順序?qū)D中點(diǎn)進(jìn)行排序，從而保證有邊相連的兩點(diǎn)之間的序號盡可能接近，而序號相鄰的點(diǎn)的鄰居集合也盡量相近，之后使用增量編碼的方式對所有點(diǎn)的鄰居列表進(jìn)行編碼以壓縮空間。其他工作包括利用社交網(wǎng)絡(luò)和網(wǎng)頁鏈接的特性對點(diǎn)集進(jìn)行排序并壓縮編碼的方案[91-93]以及對邊進(jìn)行重排序和壓縮編碼的方案[94]等[95-96]。相比靜態(tài)圖摘要算法，圖流摘要算法需要支持對摘要的動(dòng)態(tài)更新，上述三類靜態(tài)圖摘要算法中，基于比特壓縮的方案不適用于動(dòng)態(tài)更新的場景。因此圖流摘要算法主要分為基于抽取和基于聚合的兩大類?；跀?shù)據(jù)抽取的摘要算法在圖流場景下已有多篇研究工作，例如在圖流上抽取部分?jǐn)?shù)據(jù)以構(gòu)建spanner和sparsi?er[97-98],估算最大匹基于聚合的圖流摘要算法又可以進(jìn)一步分為兩大類，第一類以MoSSo[24]為代表，這類算法挖掘圖流中具有相似鄰居集合的點(diǎn)，將它們合并為超點(diǎn)以壓縮存儲。通過存儲修正集，也就是記錄壓縮后的圖和原圖相比的差異部分，它們可以做到無損壓縮。但是，尋找具有相似鄰居的點(diǎn)較為費(fèi)時(shí)，而且在圖流更新過程中，點(diǎn)的聚合結(jié)果可能第二類算法以TCM[25]為代表，這類算法基于哈希聚合，也就是通過哈希算法對點(diǎn)和邊進(jìn)行合并。它們雖然具有較高的更新速度和可控的空間占用，但是查詢誤差較的點(diǎn)和邊將被聚合，被聚合的邊權(quán)重將被加和。經(jīng)過哈希映射，圖流將被壓縮為一個(gè)更小的摘要圖，圖2.3展示了一個(gè)摘要圖產(chǎn)生的示例。之后，TCM選擇使用鄰接矩陣為圖流數(shù)據(jù)是實(shí)時(shí)到達(dá)的，無法提前預(yù)知最終的映射情況，因此TCM需要一個(gè)大小然而，如上文所述，鄰接矩陣在保存大規(guī)模稀疏圖時(shí)的空間效率十分低下。為了將空 多個(gè)不同哈希函數(shù)產(chǎn)生多份摘要，在查詢時(shí)從多個(gè)摘要的查詢結(jié)果中選擇最準(zhǔn)確的一份報(bào)告，但是它在涉及圖拓?fù)浣Y(jié)構(gòu)的查詢，如點(diǎn)的前驅(qū)和后繼查詢中，依然具有很大t7t8t1t2t3t4t5t7t8v2v3v3v5v1v1vv2v3v3v5v1v1v112v4v2v311112311112v3v4v4vv3v4v4v5v2v1v1v13vv412111v21v23vv366v1,5v2,4v1,5v2,42424vv3度較低的問題。本文的第四章將提出圖流摘要算法GSS，它使用了和TCM相似的方法產(chǎn)生摘要圖，但是設(shè)計(jì)了更加緊湊的數(shù)據(jù)結(jié)構(gòu)來保存摘要圖，因此能夠在相同空間上文主要介紹了圖流的近似存儲方法。而圖流上的近似查詢算法今年來也得到了廣泛的關(guān)注。這些算法的目標(biāo)查詢往往具有較高的復(fù)雜度，并且需要支持持續(xù)查詢，數(shù)[30,42]等。這些算法大多從圖流中抽取部分和查詢相關(guān)的數(shù)據(jù)并保存，從而為特定查圖流上的三角形計(jì)數(shù)問題即為持續(xù)監(jiān)視在任意時(shí)刻圖流中的三角形數(shù)目。由于定義三角形時(shí)并不考慮邊的方向，所以三角形計(jì)數(shù)問題一般將圖流形成的動(dòng)態(tài)圖考慮為無向圖，并且不考慮權(quán)重等屬性。圖流中邊是否能重復(fù)出現(xiàn)，在不同的工作中有不同的定義，一些算法[40,105]假設(shè)圖流中沒有重復(fù)邊，而另一些工作[30,42]則假設(shè)圖流中一條邊可以出現(xiàn)多次。當(dāng)圖流中存在重復(fù)邊時(shí)，對于重復(fù)邊的處理方法也分為帶權(quán)計(jì)數(shù)(weightedcounting)和二項(xiàng)計(jì)數(shù)(binarycounting)兩種。具體來說，在圖流中的三角形互異三角形的權(quán)重和作為結(jié)果。圖2.4展示了一個(gè)三角形計(jì)數(shù)的示例。圖中每條邊上1v1v21v1v1v21v3v1v1v1v21v3v5v21v3v51312v4v4v31從另一個(gè)角度來看，二項(xiàng)計(jì)數(shù)可以被看作在去除重復(fù)邊的圖流中進(jìn)行的三角形計(jì)數(shù)，而帶權(quán)計(jì)數(shù)則是將重復(fù)出現(xiàn)的邊視作不同的平行邊，使其生成復(fù)數(shù)的三角形。舉重復(fù)邊，而在帶權(quán)計(jì)數(shù)中，重復(fù)邊和互異邊對計(jì)數(shù)結(jié)果具有相同的貢獻(xiàn)。因此，不考慮重復(fù)邊的算法一般也可以經(jīng)過少許改進(jìn)后應(yīng)用在帶權(quán)計(jì)數(shù)中，而二項(xiàng)計(jì)數(shù)則需要更常檢測[39]等[106-109]都是以此問題為基礎(chǔ)的。已經(jīng)證明圖上的三角形計(jì)數(shù)問題的復(fù)雜度是O(|E|1.5),其中|E|表示圖上的邊數(shù)。由于此復(fù)雜此往往以近似三角形計(jì)數(shù)算法[110-112]作為替代，這些算法一般使用采樣算法，從圖中抽取出一部分邊，維護(hù)一個(gè)小規(guī)模的樣本圖，在樣本圖中計(jì)數(shù)三角形，然后再計(jì)算原圖中每一個(gè)三角形被采樣到樣本中的概率，從而根據(jù)樣本中三角形的數(shù)目，計(jì)算出原近年來在圖流上進(jìn)行三角形計(jì)數(shù)的算法包括MASCOT[113]，一種使用固定概率獨(dú)立采樣圖流中的每一條邊，并同時(shí)估算局部和全局三角形的算法，以及Pavan等人的基于鄰居采樣的三角形計(jì)數(shù)算法[40]、Jha等人的基于雙邊采樣的三角形計(jì)數(shù)算法[105]、Ahmed等人提出的適用于圖流的通用圖采樣方案[114]等。然而上述這些算法并不考慮用了被稱為蓄水池采樣[115]的方案并且具有固定大小的空間消耗。通過使用被稱為隨機(jī)配對（randompairing）[116]的方案，它也實(shí)現(xiàn)了對顯式邊刪除的支持。此外，它也支持含重復(fù)邊圖流中的帶權(quán)計(jì)數(shù)。但是一方面它不能過濾掉重復(fù)邊，因此不能支持二項(xiàng)計(jì)數(shù)。另一方面，TRIST可以處理顯式刪除，也就是說它需要被明確告知每一條邊的刪除。然而滑動(dòng)窗口中的邊的刪除是隱式的，隨著時(shí)間推移，舊的邊會自動(dòng)過期。把TRIST應(yīng)用于滑動(dòng)窗口模型時(shí)，需要用額外空間完整保存滑動(dòng)窗口內(nèi)所有邊的時(shí)序，以確保能及時(shí)發(fā)現(xiàn)所有過期邊，并對其調(diào)用刪除函數(shù)，這樣才能保證樣本集無偏。然而，保存滑動(dòng)窗口內(nèi)所有邊所需的空間代價(jià)比算法本身維護(hù)樣本圖的代價(jià)要高出數(shù)倍作PartitionCT[42]通過過濾掉重復(fù)邊來在圖流中實(shí)現(xiàn)二項(xiàng)三角形計(jì)數(shù)。它使用哈希函數(shù)將圖流切分為若干個(gè)子流。在每一個(gè)子流中，它使用另一個(gè)哈希函數(shù)來進(jìn)行優(yōu)先級采樣（prioritysampling并從每一個(gè)子流中選出一條邊組成樣本圖。PartitionCT也通過結(jié)合計(jì)算出的邊優(yōu)先級和StreamingHyperloglog算法[117]實(shí)現(xiàn)了對圖流內(nèi)互異邊數(shù)目的估計(jì)，從而計(jì)算出每條邊被采樣的概率，實(shí)現(xiàn)從樣本圖中三角形數(shù)目到圖流中三角形它們或者不支持邊刪除，或者不支持二項(xiàng)計(jì)數(shù)，而且正如上文所說，即使是支持顯示刪除的算法，在滑動(dòng)窗口模型下效果也不理想。據(jù)本文作者所知，目前沒有限定空間消耗的，滑動(dòng)窗口模型下的含重復(fù)邊圖流中的三角形近似計(jì)數(shù)方法。因此，本文的研究目標(biāo)之一，便是提出適用于滑動(dòng)窗口模型 SeTG=(V,E)Ww2時(shí)刻到達(dá)的數(shù)據(jù)項(xiàng)組成的集合wNw?NGsGhlnewloldH(·)MmdkAFXBtestR(·)在圖流數(shù)據(jù)上可以進(jìn)行的最簡單的查詢是不涉及圖拓?fù)浣Y(jié)構(gòu)的，對于點(diǎn)和邊等獨(dú)立數(shù)據(jù)項(xiàng)的查詢，例如查詢某條邊在圖流中是否出現(xiàn)、某個(gè)點(diǎn)出現(xiàn)的頻率等。這時(shí)圖流可以作為數(shù)據(jù)流進(jìn)行摘要和查詢。數(shù)據(jù)流中的數(shù)據(jù)項(xiàng)可以是圖流中的邊，也可以是圖流中每條邊的源點(diǎn)或者目的點(diǎn)。關(guān)于數(shù)據(jù)流摘要的算法已經(jīng)得到了多年的研究，相比精確存儲算法，這些摘要算法具有更小的空間占用，可以存入cache等更小更快的存儲結(jié)構(gòu)，或者在資源緊張的嵌入式設(shè)備中使用。然而，支持?jǐn)?shù)據(jù)老化機(jī)制，如滑動(dòng)窗口模型的摘要算法目前仍十分稀少。本章將提出滑動(dòng)窗口模型下的數(shù)據(jù)流摘要框架它們可以被應(yīng)用于滑動(dòng)窗口模型。通過應(yīng)用于不同的摘要算法，Slidingsketch可以支本節(jié)首先介紹一種數(shù)據(jù)流摘要的通用模型，k-hash模型，許多經(jīng)典的數(shù)據(jù)流摘要數(shù)據(jù)結(jié)構(gòu):k-hash模型的數(shù)據(jù)結(jié)構(gòu)如圖3.1所示。它由一個(gè)等分為k段的數(shù)組組eAh1(x)h2(x)h3(x)h4(x)A口映射格子用一個(gè)查詢策略stq根據(jù)k個(gè)格子保存的信息計(jì)算出查詢結(jié)果。不同摘要的查詢策略使用CMsketch舉例：不同摘要算法的更新和查詢策略不同，下面以CMsketch計(jì)數(shù)器都增加1，因此一個(gè)數(shù)據(jù)項(xiàng)的頻率被累加到了它映射到的每一個(gè)格子上。而它的查詢策略則是報(bào)告k個(gè)映射格子中計(jì)數(shù)器的最小值，因?yàn)槊恳粋€(gè)映射格子的值都是映射到它的數(shù)據(jù)項(xiàng)的頻率和，所以該值不小于被查詢的數(shù)據(jù)項(xiàng)的真實(shí)頻率，而且k個(gè)Slidingsketch可以應(yīng)用于所有符合k-hingsketch用在一種摘要算法時(shí)，本文稱改進(jìn)前的算法為基礎(chǔ)摘要，改進(jìn)后的算法用個(gè)槽，A[i][0]和A[i][1]，每一個(gè)槽是一個(gè)和基礎(chǔ)摘要相同的數(shù)據(jù)結(jié)構(gòu)，如比特或者計(jì)更新：當(dāng)一個(gè)新的數(shù)據(jù)項(xiàng)e到達(dá)時(shí)，Slidingsketch使i<k}將其映射到k個(gè)位置{A[hi]|0≤i<k}，每段一個(gè)（也就是說hi(·)是在子的A[hi][0]槽。掃描：掃描操作用于刪除過期數(shù)據(jù)。Slidingsketch使用一個(gè)掃描指針勻速重復(fù)掃描數(shù)組A。每當(dāng)指針掃描到數(shù)組結(jié)尾時(shí)，它返回?cái)?shù)組開頭并開始新一輪掃描。掃描數(shù)指針每個(gè)時(shí)間單元內(nèi)掃描個(gè)格子。每當(dāng)指針掃描到一個(gè)格子時(shí)路標(biāo)時(shí)刻。在一個(gè)格子的路標(biāo)時(shí)刻，Slidingsketch刪除A[i][1]中的值，將A[i][0]的值賦給A[i][1]，并將A[i][0]清空。查詢:查詢一個(gè)數(shù)據(jù)項(xiàng)e時(shí)，Slidingsketch找到它映射的k個(gè)格子{A[hi]|0≤i<k}。在每一個(gè)格子里，Slidingsketch算法把兩個(gè)槽的值求和，最終得到k個(gè)和CMsketch找到k個(gè)映射的格子后，把每個(gè)格子兩個(gè)槽中的值加和，最終找到k個(gè)和中這些序列把整個(gè)數(shù)據(jù)流分為了若干等長的片段。每個(gè)片段可以比喻為一天，而不同的每一個(gè)格子的兩個(gè)槽位分別記錄了該格子在最近兩個(gè)片段內(nèi)收到的信息。而在一個(gè)數(shù)據(jù)項(xiàng)映射到的k個(gè)格子中，路標(biāo)序列的偏差導(dǎo)致了保存信息的時(shí)間異步，而Slidingsketch能保證總有一個(gè)格子里保存的信息足夠接近滑動(dòng)窗口內(nèi)的信息。下一節(jié)中會對由于掃描操作，每一個(gè)格子A[i]具有一個(gè)路標(biāo)時(shí)刻序列{lj|j=0,1,2....}對任意正整數(shù)j≥0，有l(wèi)j+1?lj=N，這些路標(biāo)將整個(gè)數(shù)據(jù)流切分成了若干等長片段{w+1|j=0,1,2....}。假設(shè)對于當(dāng)前時(shí)刻有l(wèi)t<T≤lt+1，下文設(shè)Slidingsketch用槽A[i][0]保存在當(dāng)前片段中被映射到格子A[i]的數(shù)據(jù)項(xiàng)的信作為對滑動(dòng)窗口內(nèi)映射到格子A[i]的數(shù)據(jù)項(xiàng)信圖3.2展示了一個(gè)格子A[i]的路標(biāo)序列對圖流進(jìn)行片段切分的示例，當(dāng)前片段為片段3，時(shí)差為，滑動(dòng)窗口包含了當(dāng)前的片段3和片段2的后。而片段3加片段2T=14滑動(dòng)窗口(N=6)t=1t=3t=4t=5t=6t=7t=9t=11t=12e1e2e3e4e5e6e7e8e9e10e113片段1片段2片段3061218在每一個(gè)格子A[i]中，A[i][0]+A[i][1]存儲了一個(gè)長度為N+δN個(gè)時(shí)間單元的數(shù)去估算滑動(dòng)窗口中數(shù)據(jù)項(xiàng)信息的誤差便越小。由于掃描指針勻速掃描整個(gè)數(shù)組，δ的值取決于格子和掃描指針之間的距離。假設(shè)這些格子中的時(shí)差足夠小，可以保證估算精度。準(zhǔn)確來說，可以證明一個(gè)數(shù)據(jù)項(xiàng)e總有一個(gè)映射格子A[hj1]使得0。詳細(xì)推導(dǎo)會在3.4節(jié)中給出。段中的頻率，加上哈希沖突（多個(gè)數(shù)據(jù)項(xiàng)映射到一個(gè)格子）帶來的誤差。當(dāng)數(shù)組中的格子數(shù)足夠大時(shí)，哈希沖突帶來的誤差可以被控制在較低的水平，對滑動(dòng)窗口進(jìn)行近似帶來的誤差是估算誤差的主要組成部分。由于CMsketch的查詢策略會選擇最小的上一節(jié)假設(shè)數(shù)組每一個(gè)格子被分為2個(gè)槽位，更一般的情況下，Slidingsketch在每個(gè)格子中使用d(d≥2)個(gè)槽位{A[i][j]|0≤j<d}。這些槽位記錄了最近d個(gè)片段內(nèi)映射到該格子的數(shù)據(jù)項(xiàng)的信息。如果假設(shè)當(dāng)前片段為wtt+1，那么槽位A[i][j]記錄的是片段wtt+1中的信息。在這種情況下，應(yīng)當(dāng)有l(wèi)j+1?lj=也就說每個(gè)片段是i<k}，數(shù)組每段一個(gè)。之后使用基礎(chǔ)摘置A[i][j]=A[i][j?1](1≤j<d)，A[i][0]=0。i<k}，然后計(jì)算k個(gè)和{sum(A[hi])=ΣA[hi][j]|0≤i<k}，最后將基礎(chǔ)摘要的是說每一個(gè)片段是滑動(dòng)窗口長度的。當(dāng)前片段為片段5，時(shí)差為，滑動(dòng)窗口和片段T=14滑動(dòng)窗口(N=6)t=1t=3t=4t=5t=6t=7t=9t=11t=12t=13e1e2e3e4e5e6e7e8e9e10e11片段1片段2片段3片段4片段503691215當(dāng)使用多槽位時(shí)，Slidingsketch的精確度可能會提高個(gè)片段都是滑動(dòng)窗口長度的，所以這d個(gè)片段的和是滑動(dòng)窗口長度的來精度提升，因?yàn)閮?nèi)存占用不變的情況下，增加每個(gè)格子的槽位數(shù)目也意味著格子數(shù)目的降低，哈希沖突帶來的誤差會提升。槽位數(shù)目和格子數(shù)組之間的權(quán)衡根據(jù)基準(zhǔn)算的哈希函數(shù)來完成地址計(jì)算，但是k個(gè)哈希函數(shù)有一定的計(jì)算代價(jià)，為了進(jìn)一步降低4.a,b,都比p小。之后使用g2(e)作為一個(gè)偏移量計(jì)算出映射地址{hi(e)=(ri(e)+g2(e))%+i× 機(jī)序列，而即使兩個(gè)數(shù)據(jù)項(xiàng)e和e′出現(xiàn)了g1(e)=g1(e′)，只要g2(e)≠g2(e′)，映射地址序列依然不會相同。而g1(e)=g1(e′)且g2(e)=g實(shí)驗(yàn)結(jié)果表明，使用偽隨機(jī)算法可以在不影響精確度的情況下把Slidingsketch水和低能耗的優(yōu)勢。一塊FPGA加速板由一個(gè)FPGA芯片和數(shù)塊板上內(nèi)存組成。每一存占用大部分情況下很小，應(yīng)用中可以嘗試將其放在FPGA上實(shí)現(xiàn)Slidingske來數(shù)組中的每一個(gè)格子被變形為矩陣的一列了便利掃描操作的進(jìn)行。FPGA在一次存儲訪問中可以讀寫64字節(jié)的每一個(gè)槽位小于4字節(jié)，所以，在掃描操作中可以一起操作多個(gè)相鄰列，也就是同格子更新和查詢操作可以同時(shí)使用并行和流水加速。一次更新操作可以并行訪問數(shù)據(jù)項(xiàng)在矩陣不同段的映射格子，完成對它們的更新。查詢操作也可以并行讀取不同映射格子中的值，然后再把得到的值進(jìn)行比較以選出最終結(jié)果。此外，一批更新或者查詢操作可以進(jìn)行流水線加速，也就是把更新/查詢函數(shù)在芯片上的執(zhí)行邏輯分為若干單該單元。如此可以實(shí)現(xiàn)兩個(gè)更新/查詢操作間隔的時(shí)鐘周期數(shù)小于完成一次更新/查詢需要的周期數(shù)，從而提高操作吞吐量。兩個(gè)操作之間的間隔被稱為啟動(dòng)間隔II。在最理想的情況下啟動(dòng)間隔可以為1個(gè)時(shí)鐘周期。Slidingsketch的查詢操作可以達(dá)到該間因此，啟動(dòng)間隔等于完成更新所需的時(shí)鐘周期數(shù)。3.6.7節(jié)中的實(shí)驗(yàn)表明，使用FPGA本節(jié)對Slidingsketch的性能給出分析。3.4.1節(jié)將Slidingsketch的空間復(fù)雜度是O(md),m是數(shù)組的格子數(shù)目而d是每個(gè)格子的槽位數(shù)目。在應(yīng)用中，m的長度一般和滑動(dòng)窗口長度線性相關(guān)，而sketch算法中，每一個(gè)數(shù)組格子被分為d個(gè)槽位，每個(gè)槽位的數(shù)據(jù)結(jié)構(gòu)都和基礎(chǔ)摘要Slidingsketch每個(gè)槽位中的數(shù)據(jù)結(jié)構(gòu)要比基礎(chǔ)摘要簡單。例如HeavyKeeper的每個(gè)格一個(gè)格子仍然只記錄一個(gè)數(shù)據(jù)項(xiàng)的ID，而d個(gè)槽位在最近d個(gè)片段內(nèi)的頻率。這種情況下SlidingHeavyKeeper的內(nèi)更新算子的時(shí)間復(fù)雜度是O(k)的，因?yàn)槠湫枰业絢個(gè)格子，但在每一個(gè)格子中只更新一個(gè)槽位。而查詢算子的復(fù)雜度是O(kd)的，因?yàn)槠湫枰业綌?shù)據(jù)項(xiàng)映射的k個(gè)格子，在每一個(gè)格子中需要計(jì)算d個(gè)槽位的和（注意在FPGA加速方案中，由于對于數(shù)組中的每個(gè)格子A[i]，其時(shí)差δ表示了當(dāng)前片段的長度相比完整片段長度的比例，可以根據(jù)格子和掃描指針之間的距離計(jì)算。假設(shè)一個(gè)格子在矩陣中的序號為1)hj1<q時(shí)，A[hj1]擁有所有映射位置中最小的時(shí)差。q?hj1小于數(shù)組一段的長這種情況下k個(gè)映射格子中最大的時(shí)差出現(xiàn)在相鄰的下一段中，假設(shè)這一段中的格子為A[hj2]，也就是說j2=(j1+1)%k。因?yàn)閔j2?q小于