圖流近似處理研究

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