圖數(shù)據(jù)流的模型、算法和系統(tǒng)

李友煥，鄒磊

北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)研究所，北京 100080

1 大規(guī)模流數(shù)據(jù)的機(jī)遇與挑戰(zhàn)

圖數(shù)據(jù)流是最近幾年才受到廣泛關(guān)注的前沿科研領(lǐng)域，其興起主要是源于新時(shí)代下移動(dòng)應(yīng)用實(shí)時(shí)產(chǎn)生的大規(guī)模復(fù)雜數(shù)據(jù)。

過去十幾年，隨著智能手機(jī)的普及以及移動(dòng)互聯(lián)網(wǎng)的發(fā)展，移動(dòng)應(yīng)用層出不窮。這些應(yīng)用涉及即時(shí)通信、社交網(wǎng)絡(luò)以及網(wǎng)絡(luò)購物等各個(gè)方面，并實(shí)時(shí)地產(chǎn)生大量的數(shù)據(jù)。這些數(shù)據(jù)本質(zhì)上是現(xiàn)實(shí)世界人、事、物及其交互的一種深入量化。對(duì)這些數(shù)據(jù)的及時(shí)分析與挖掘能夠產(chǎn)生高價(jià)值的信息，進(jìn)而改進(jìn)人們生活的多個(gè)方面。例如，微信、微博等社交網(wǎng)絡(luò)上有龐大的活躍用戶，這些用戶對(duì)社交網(wǎng)絡(luò)而言更像是分布在各地的“傳感器”，將各自的活動(dòng)區(qū)域內(nèi)的熱點(diǎn)見聞“報(bào)告”在社交網(wǎng)絡(luò)上。如在地震等自然災(zāi)害發(fā)生時(shí)，人們可以通過社交網(wǎng)絡(luò)實(shí)時(shí)傳遞和獲取相關(guān)的災(zāi)情[2]。因此，這些應(yīng)用數(shù)據(jù)具有極大的分析研究?jī)r(jià)值。

盡管移動(dòng)應(yīng)用數(shù)據(jù)蘊(yùn)含著高價(jià)值的信息，但這些數(shù)據(jù)卻具有結(jié)構(gòu)復(fù)雜、規(guī)模龐大、高速增長(zhǎng)等特點(diǎn)。人們對(duì)不同應(yīng)用有不同的需求，這決定了移動(dòng)應(yīng)用數(shù)據(jù)是復(fù)雜多樣的，而針對(duì)同一應(yīng)用產(chǎn)生的數(shù)據(jù)，不同的數(shù)據(jù)分析方也會(huì)有不同的數(shù)據(jù)需求。例如，針對(duì)社交網(wǎng)絡(luò)的數(shù)據(jù)，研究社交心理的人更關(guān)注用戶以及用戶間的好友關(guān)系與交互行為，而廣告媒體的從業(yè)人員則更關(guān)心平臺(tái)上發(fā)文內(nèi)容中的產(chǎn)品或話題信息。人們對(duì)數(shù)據(jù)的多樣化的需求決定了移動(dòng)應(yīng)用數(shù)據(jù)的復(fù)雜性。數(shù)量眾多的軟件及其龐大的用戶量決定了相關(guān)數(shù)據(jù)的海量規(guī)模。例如，微信的月活躍用戶數(shù)已超過了10億，而用戶之間的交互則會(huì)帶來更大規(guī)模的數(shù)據(jù)，包括語音、視頻、圖片以及相關(guān)的文本等。這些大規(guī)模的復(fù)雜數(shù)據(jù)還在實(shí)時(shí)地高速增長(zhǎng)，如社交網(wǎng)絡(luò)每天以億級(jí)別的發(fā)文、軌道交通應(yīng)用形成的大規(guī)模定位與軌跡信息以及網(wǎng)絡(luò)通信中的數(shù)據(jù)傳播等。

傳統(tǒng)的關(guān)系型數(shù)據(jù)管理模型雖然已有眾多標(biāo)準(zhǔn)規(guī)范和技術(shù)積淀，但仍難以管理復(fù)雜多變的數(shù)據(jù)。一方面，數(shù)據(jù)的關(guān)系框架的設(shè)計(jì)成本較高，既定的數(shù)據(jù)框架結(jié)構(gòu)很難適應(yīng)數(shù)據(jù)種類、格式的頻繁變化；另一方面，關(guān)系型數(shù)據(jù)庫中，基于關(guān)聯(lián)信息的計(jì)算代價(jià)很高，如表格的聯(lián)結(jié)操作等，這使得在大規(guī)模數(shù)據(jù)場(chǎng)景下關(guān)系型數(shù)據(jù)庫管理模型難以滿足數(shù)據(jù)分析處理的需求。

圖模型的點(diǎn)、邊元素非常適用于建模復(fù)雜數(shù)據(jù)中的對(duì)象以及對(duì)象間的關(guān)聯(lián)和交互，點(diǎn)和邊上的屬性、標(biāo)簽以及相關(guān)數(shù)據(jù)等的自由定義使得圖模型能夠很容易地以統(tǒng)一的形式表達(dá)不同的對(duì)象及其間的交互行為。例如，在社交網(wǎng)絡(luò)上，基于用戶好友關(guān)系建模的圖和以文本關(guān)鍵字共現(xiàn)關(guān)聯(lián)建模的圖可以很容易通過增加用戶與文本的發(fā)表關(guān)系快速融合成一個(gè)圖。因此，圖模型非常適合用來建模大規(guī)模復(fù)雜數(shù)據(jù)。然而，圖模型上的計(jì)算卻很難應(yīng)對(duì)圖數(shù)據(jù)高速更新的場(chǎng)景。圖數(shù)據(jù)上的計(jì)算往往通過構(gòu)建復(fù)雜的索引來加速查詢。在靜態(tài)圖數(shù)據(jù)上，因?yàn)樗饕恍枰x線構(gòu)建一次，所以高構(gòu)建代價(jià)對(duì)整體性能的影響有限。而在圖數(shù)據(jù)高速更新的場(chǎng)景下，索引也需要頻繁更新，越是復(fù)雜的索引往往更新越困難，甚至需要完全重新構(gòu)建。盡管索引能夠加速查詢，但在流場(chǎng)景下的頻繁索引更新也會(huì)嚴(yán)重影響整體性能。

數(shù)據(jù)流模型及其相關(guān)研究雖然都有針對(duì)數(shù)據(jù)更新的設(shè)計(jì)，但已有的數(shù)據(jù)流模型中缺少對(duì)圖結(jié)構(gòu)數(shù)據(jù)的支持。數(shù)據(jù)流中的元素往往具有統(tǒng)一簡(jiǎn)單的格式，并且元素之間相對(duì)獨(dú)立，缺少對(duì)對(duì)象關(guān)聯(lián)的建模。因此，數(shù)據(jù)流模型的相關(guān)算法也很難擴(kuò)展到需要圖模型建模的復(fù)雜數(shù)據(jù)上。

在大規(guī)模復(fù)雜數(shù)據(jù)流的場(chǎng)景下，已有的圖與數(shù)據(jù)流相關(guān)的模型和算法均有明顯缺陷。盡管大規(guī)模實(shí)時(shí)更新的復(fù)雜數(shù)據(jù)給人們帶來了獲取高價(jià)值信息的重大機(jī)遇，但也帶來了數(shù)據(jù)管理和計(jì)算上的巨大挑戰(zhàn)。人們急需一種既能夠?yàn)閺?fù)雜數(shù)據(jù)建模，又能夠應(yīng)對(duì)更新挑戰(zhàn)的新的數(shù)據(jù)模型、技術(shù)來滿足相應(yīng)的信息管理需求。

2 流計(jì)算系統(tǒng)

在圖數(shù)據(jù)流模型受到廣泛關(guān)注之前，有幾種流式計(jì)算工具興起，并在一定程度上彌補(bǔ)了傳統(tǒng)技術(shù)應(yīng)對(duì)大規(guī)模復(fù)雜數(shù)據(jù)流的不足，其中包括Storm[3]、Spark Streaming、Samza、Flink以及Kafka Stream。本章將分別簡(jiǎn)要介紹和分析這幾種系統(tǒng)，而后總結(jié)分析這些系統(tǒng)對(duì)大規(guī)模復(fù)雜數(shù)據(jù)流處理的相對(duì)優(yōu)勢(shì)及其仍然存在的重要不足。

（1）Storm

Storm是Twitter開源的一個(gè)流系統(tǒng)。在Storm初始化時(shí)，需要用戶定義一個(gè)實(shí)時(shí)計(jì)算的框架，這個(gè)框架的結(jié)構(gòu)其實(shí)是一個(gè)有向圖，圖中點(diǎn)是集群中的計(jì)算節(jié)點(diǎn)，而點(diǎn)與點(diǎn)之間的邊則對(duì)應(yīng)整體計(jì)算邏輯中數(shù)據(jù)的傳輸。這個(gè)圖框架也被稱為拓?fù)?。在一個(gè)拓?fù)渲?，傳輸?shù)臄?shù)據(jù)單元是一系列不可修改的鍵值對(duì)（tuple），鍵值對(duì)從消息源（spout）點(diǎn)中輸出，形成流數(shù)據(jù)，并傳輸?shù)较⑻幚碚撸╞olt）點(diǎn)中進(jìn)行計(jì)算，進(jìn)而產(chǎn)出新的輸出流，bolt輸出流也可以傳輸給其他bolt節(jié)點(diǎn)，形成流水線式的計(jì)算處理流。

（2）Spark Streaming

流式Spark其實(shí)是Spark核心應(yīng)用程序編程接口（application programming interface，API）的一個(gè)擴(kuò)展，其對(duì)流式處理的支持其實(shí)是將流數(shù)據(jù)分割成離散的多個(gè)小批量的RDD（RDD是Spark的數(shù)據(jù)單元）數(shù)據(jù)，然后再進(jìn)行處理。這些小批量的數(shù)據(jù)被稱為DStream（D為discretized，即離散化的意思）。DStream數(shù)據(jù)既可以被自定義的函數(shù)并發(fā)地處理，也可以在移動(dòng)窗口的數(shù)據(jù)模型下進(jìn)行計(jì)算。

（3）Samza

Samza系統(tǒng)處理的流數(shù)據(jù)單元實(shí)質(zhì)是類型相同或相近的消息，這些消息在產(chǎn)生之后是不可修改的。新產(chǎn)生的消息將被追加到流中，而流中的消息也不斷地被讀取。每條消息可以有相應(yīng)的鍵值，這些鍵值可以用來對(duì)流中的所有消息進(jìn)行分割。Samza的工作過程是對(duì)一組輸入流中的消息數(shù)據(jù)進(jìn)行按需計(jì)算轉(zhuǎn)換（或過濾），并將計(jì)算結(jié)果以消息數(shù)據(jù)的形式附加到輸出流中。因此，Samza的運(yùn)行工作負(fù)載可能包含多個(gè)工作組，工作組之間可能有流數(shù)據(jù)的依賴關(guān)系，進(jìn)而將整體的Samza計(jì)算抽象成一個(gè)數(shù)據(jù)流圖框架，其中點(diǎn)都是流式的消息，而消息之間的邊則為完成消息邏輯轉(zhuǎn)化的計(jì)算任務(wù)的工作組。

（4）Flink

Flink是跟Storm比較相似的系統(tǒng)，其整個(gè)數(shù)據(jù)處理過程稱為Stream Dataflow，既定的數(shù)據(jù)流動(dòng)框架類似于Storm的拓?fù)?。此外，F(xiàn)link提取數(shù)據(jù)流的操作（source operator）、數(shù)據(jù)轉(zhuǎn)換（map，aggregate）的操作（transformation operator）以及數(shù)據(jù)流輸出的操作（sink operator）跟Storm架構(gòu)中spout與bolt之間、bolt和bolt之間的數(shù)據(jù)流是高度對(duì)應(yīng)的。兩者比較大的區(qū)別在于容錯(cuò)機(jī)制。Flink的容錯(cuò)機(jī)制是檢查點(diǎn)（checkpoint），通過異步實(shí)現(xiàn)，并不會(huì)打斷數(shù)據(jù)流，因此Flink的檢查點(diǎn)的開啟與關(guān)閉對(duì)吞吐量的影響很小。而Storm采用的是ACK機(jī)制，開銷更大，而且對(duì)吞吐量的影響更明顯。另外，F(xiàn)link提供的API相對(duì)Storm的API來說更高級(jí)，而Storm的API則更基礎(chǔ)。Storm的優(yōu)勢(shì)主要是具有比較成熟的社區(qū)支撐和經(jīng)過較長(zhǎng)期迭代之后的穩(wěn)定性，目前Flink成熟度較低，仍有部分功能需要完善，如在線的動(dòng)態(tài)資源調(diào)整等。

（5）Kafka Stream

Kafka Stream是Apache Kafka中的一個(gè)輕量級(jí)流式處理類庫，用來支撐Kafka中存儲(chǔ)數(shù)據(jù)的流式計(jì)算與分析，利用這個(gè)類庫進(jìn)行計(jì)算的結(jié)果既可以寫回Kafka，也可以作為數(shù)據(jù)源向外輸出。目前的流式計(jì)算系統(tǒng)基本都支持以Kafka Stream的輸出作為數(shù)據(jù)源，如Storm的Kafka Spout。作為一個(gè)Java類庫，Kafka Stream并不是一個(gè)系統(tǒng)，但卻是討論流計(jì)算的工具中不得不提的對(duì)象。它可以非常方便地嵌入任意Java應(yīng)用中，也可以以任意方式打包和部署，除了Kafka之外，并沒有任何外部依賴。同流計(jì)算系統(tǒng)相比，使用Kafka受到的邏輯限制較少，開發(fā)者能夠更好地控制和使用Kafka Stream上的應(yīng)用。

這些流系統(tǒng)和流計(jì)算庫的核心思想都是針對(duì)流式的輸入利用集群進(jìn)行協(xié)作計(jì)算，而整體的數(shù)據(jù)依賴所形成的框架則為一個(gè)有向無環(huán)圖，因此集群的整體協(xié)作更像是流水線的協(xié)作，計(jì)算框架中的數(shù)據(jù)依賴所形成的數(shù)據(jù)流動(dòng)方向基本上是單一既定的。除了數(shù)據(jù)處理的先后關(guān)系之外，這些流系統(tǒng)對(duì)不同工作組之間的數(shù)據(jù)的獨(dú)立性要求往往更高，進(jìn)而能實(shí)現(xiàn)較好的并行效果。然而對(duì)于很多圖計(jì)算而言，計(jì)算的邏輯并不是流水線式的流系統(tǒng)能容易處理的。圖具有很強(qiáng)的表達(dá)能力，數(shù)據(jù)與數(shù)據(jù)之間的關(guān)聯(lián)緊密，路徑、連通分量等圖計(jì)算使數(shù)據(jù)間的獨(dú)立性比較低，單條邊的變化可能對(duì)整個(gè)圖的結(jié)構(gòu)特征產(chǎn)生全局的影響。而且，圖數(shù)據(jù)計(jì)算中的中間結(jié)果較多（如子圖查詢中的部分解），在分布式集群下的傳輸代價(jià)很高。因此，流式系統(tǒng)往往難以支撐大規(guī)模圖數(shù)據(jù)流的計(jì)算。

3 圖數(shù)據(jù)流模型

已有的相關(guān)模型、算法和流式計(jì)算系統(tǒng)均無法滿足大規(guī)模復(fù)雜數(shù)據(jù)流的管理需求，圖數(shù)據(jù)流應(yīng)運(yùn)而生。目前的相關(guān)工作缺乏針對(duì)圖數(shù)據(jù)流的統(tǒng)一的形式化定義。后文首先介紹早期圖的流式計(jì)算以及已有的少量圖數(shù)據(jù)流的研究工作，然后再結(jié)合圖數(shù)據(jù)流研究現(xiàn)狀以及現(xiàn)實(shí)應(yīng)用的背景，給出圖數(shù)據(jù)流一般性的形式化定義。

3.1 圖的流式計(jì)算

圖的流式計(jì)算是指給定一個(gè)靜態(tài)的圖，在一遍或多遍順序地讀取對(duì)應(yīng)的圖數(shù)據(jù)的過程中，獲得預(yù)期數(shù)據(jù)信息或完成既定操作的計(jì)算問題。圖的流式計(jì)算的研究初衷在于圖的規(guī)模遠(yuǎn)大于內(nèi)存容量時(shí)，無法一次性將整個(gè)大圖載入內(nèi)存中計(jì)算，只能每次定量地載入一部分圖數(shù)據(jù)到內(nèi)存中，直到讀完整個(gè)大圖，在不斷順序讀的過程中完成相關(guān)計(jì)算。在一次遍歷圖數(shù)據(jù)無法獲取相應(yīng)計(jì)算結(jié)果的情況下，可以多次進(jìn)行完整的順序讀操作，也就是流式計(jì)算。隨著存儲(chǔ)的發(fā)展，計(jì)算空間開銷帶來的挑戰(zhàn)明顯降低，因此當(dāng)前很少有圖的流式計(jì)算的研究工作，已有研究工作主要出現(xiàn)在20世紀(jì)90年代末到21世紀(jì)初內(nèi)存資源相對(duì)有限的時(shí)期。

流式計(jì)算涉及很多經(jīng)典的圖計(jì)算問題，包括多種圖的屬性特征計(jì)算和相關(guān)的圖結(jié)構(gòu)操作等。這些圖的基本問題的計(jì)算方法往往是解決其他應(yīng)用問題的重要基礎(chǔ)，故這類問題的研究也比其他圖數(shù)據(jù)流上的應(yīng)用問題要早得多。這類問題的形式化模型往往很明確，同具體應(yīng)用并沒有直接的聯(lián)系。其關(guān)注的重點(diǎn)主要是在空間有限無法載入整個(gè)大圖時(shí)，如何多次遍歷圖數(shù)據(jù)完成相應(yīng)圖計(jì)算。圖流式訪問的研究問題包含眾多圖計(jì)算的經(jīng)典問題，本文主要從其中的三角形計(jì)算、可達(dá)性和最短路徑等問題做出簡(jiǎn)要介紹。

Bar-Yossef Z等人[4]結(jié)合relative-近似和ratio-近似，提出了一個(gè)基于歸約（reduction）的流式訪問模型下的流算法，其中就以三角形計(jì)數(shù)流算法作為應(yīng)用來分析，主要提到了兩種流訪問的形式：一種是以邊為項(xiàng)的鄰接邊流（adjacency流），邊的前后順序任意；另一種是以點(diǎn)及其鄰居的星狀點(diǎn)流（incidence流），每個(gè)項(xiàng)是一個(gè)頂點(diǎn)及其鄰居形成的星狀結(jié)構(gòu)。其后的聚焦在相同問題的兩個(gè)工作[5-6]基本沿著近似的思路以及adjacency流和incidence流的模型研究流式訪問的三角形計(jì)數(shù)問題，并給出了更優(yōu)的時(shí)間和空間上的相應(yīng)算法的復(fù)雜度。

Unel G等人[7]使用區(qū)間標(biāo)記解決流式訪問的圖可達(dá)性問題。首先在必要時(shí)對(duì)圖進(jìn)行可達(dá)性上等價(jià)的去環(huán)轉(zhuǎn)化，轉(zhuǎn)化過程是線性的。其次，根據(jù)圖的去環(huán)轉(zhuǎn)化的過程將頂點(diǎn)從前到后打上時(shí)間標(biāo)簽，然后流式訪問時(shí)就按這個(gè)時(shí)間標(biāo)簽從前到后進(jìn)行，也就是說這個(gè)圖數(shù)據(jù)流模型是設(shè)定了流的順序進(jìn)行訪問的，因?yàn)槟繕?biāo)在于對(duì)大圖的可達(dá)性的計(jì)算，所以這種假設(shè)除了離線的時(shí)間開銷外并沒有實(shí)際限制。這種情況下，去環(huán)的圖可以轉(zhuǎn)化為樹，從而將圖數(shù)據(jù)流上的可達(dá)性轉(zhuǎn)化為樹上的可達(dá)性問題，而顯然后者是有高效算法的，而且樹的空間效率相比圖也有很大的提高。

有向圖流式訪問上的最短路徑問題最早是在Demetrescu C等人[8]的一個(gè)工作中提出的，是圖數(shù)據(jù)流上空間復(fù)雜度和計(jì)算所需的遍歷次數(shù)的權(quán)衡問題下的一個(gè)圖算法的應(yīng)用。研究的結(jié)論是在給定比特的空間下，有向圖的單源最短路徑問題可以在O(n·logn)次遍歷過程中解決。

有學(xué)者將這類圖的流式計(jì)算稱為圖數(shù)據(jù)流[9]，但考慮到數(shù)據(jù)仍是已知的靜態(tài)圖，只是讀取的方式是流式的，因此本文將這類能夠多遍順序讀取圖的計(jì)算模型稱為圖的流式計(jì)算模型。顯然，圖的流式計(jì)算并不能滿足當(dāng)前大規(guī)模復(fù)雜數(shù)據(jù)流的計(jì)算需求。一方面，大規(guī)模復(fù)雜數(shù)據(jù)流很難進(jìn)行多遍讀取。圖的流式計(jì)算中，全局的數(shù)據(jù)是給定的，而當(dāng)前應(yīng)用中實(shí)時(shí)產(chǎn)生的大量圖結(jié)構(gòu)數(shù)據(jù)則是無限增長(zhǎng)的。另一方面，流式計(jì)算很難應(yīng)對(duì)數(shù)據(jù)的過期更新操作。高速增長(zhǎng)的數(shù)據(jù)往往具有鮮明的時(shí)效性，人們的信息獲取也常常聚焦在近期的數(shù)據(jù)，因此當(dāng)部分?jǐn)?shù)據(jù)失去時(shí)效性時(shí)，需要結(jié)合既定的計(jì)算邏輯刪除與這部分?jǐn)?shù)據(jù)相關(guān)的計(jì)算結(jié)果，避免這部分過期數(shù)據(jù)的影響，而圖的流式計(jì)算顯然并不支持?jǐn)?shù)據(jù)的刪除更新。以節(jié)約內(nèi)存為初衷而出現(xiàn)的圖的流式計(jì)算，盡管結(jié)合了圖模型和類似于數(shù)據(jù)流模型的流式計(jì)算，但顯然并不適用于大規(guī)模圖結(jié)構(gòu)數(shù)據(jù)流的場(chǎng)景。

3.2 圖數(shù)據(jù)流算法

目前有少量關(guān)于圖數(shù)據(jù)流模型的研究工作，但這些工作并沒有給出一個(gè)統(tǒng)一的圖數(shù)據(jù)流形式化的定義。本節(jié)通過總結(jié)分析已有的圖數(shù)據(jù)流工作以及存在的各種圖數(shù)據(jù)流模型定義，給出同這些圖數(shù)據(jù)流模型基本相融的、更具一般性的圖數(shù)據(jù)流的定義。本文提出的圖數(shù)據(jù)流模型同時(shí)還能夠很好地為現(xiàn)實(shí)應(yīng)用中的大規(guī)模復(fù)雜數(shù)據(jù)流進(jìn)行建模。

已有的圖數(shù)據(jù)流模型可以分為3種，第一種是基于邊流，即邊的增刪的圖數(shù)據(jù)流。Song C Y等人[10]提出圖數(shù)據(jù)流下的強(qiáng)仿真計(jì)算，對(duì)應(yīng)的圖數(shù)據(jù)流定義為一個(gè)包含頂點(diǎn)集、邊集、標(biāo)簽集以及時(shí)間戳函數(shù)的有向圖，其中流動(dòng)的元素為按時(shí)間戳先后順序排列的邊，并且在邊流上引入了時(shí)間窗的概念。Angel A等人[1]最先研究了在實(shí)時(shí)更新的邊流上維護(hù)密集子圖的算法，其邊流定義為一個(gè)無限序列，序列中的每個(gè)元素為給定邊及其邊權(quán)的變化值（增/減）。邊本身沒有時(shí)間戳的概念，但是邊權(quán)更新的操作帶有時(shí)間戳。此外，F(xiàn)AN W F等人[11]以及Choudhury S等人[12]各自的圖數(shù)據(jù)流子圖同構(gòu)中的模型均屬于第一種模型。第二種是基于子圖流，即數(shù)據(jù)流中的元素為一個(gè)個(gè)小的子圖，邊本身沒有時(shí)間戳的概念，而流中的子圖元素才有。IBM Watson研究中心的Aggarwal C C等人[13]利用Min-Hash的相似度衡量方法，將以子圖流為形式的圖數(shù)據(jù)流采樣成一個(gè)靜態(tài)的抽樣集，進(jìn)而把研究圖數(shù)據(jù)流上的子圖模式挖掘轉(zhuǎn)換成了靜態(tài)的抽樣集的頻繁模式挖掘的問題。這個(gè)工作中的圖數(shù)據(jù)流模型不支持刪除操作，只考慮不斷新增的小圖，這些小圖是作為整個(gè)圖數(shù)據(jù)流對(duì)應(yīng)的子圖而定義的，彼此之間并不是獨(dú)立的圖。第三種則是圖數(shù)據(jù)流中，元素是定義在不同點(diǎn)或邊集上的獨(dú)立圖數(shù)據(jù)。Valari E等人[14]提出了一個(gè)給定動(dòng)態(tài)的大圖集合的模型，即大圖的數(shù)量是一個(gè)固定的常數(shù)，每次集合都將按增加一個(gè)新大圖、刪除一個(gè)最舊的大圖的方式更新，進(jìn)而形成動(dòng)態(tài)的大圖集合，然后在大圖集合上研究Top k的密集子圖的計(jì)算算法。值得注意的是，這個(gè)圖數(shù)據(jù)流模型中，不同的大圖是定義在不同的頂點(diǎn)集之上的，并不存在這些大圖的公共超圖的語義。

顯然，目前的圖數(shù)據(jù)流模型雖然都是針對(duì)大規(guī)模高速生成的圖數(shù)據(jù)的，但缺乏統(tǒng)一的形式化定義以及普適的一般性含義。

3.3 圖數(shù)據(jù)流模型定義

已有的相關(guān)圖數(shù)據(jù)流工作中的模型定義雖然有所區(qū)別，但核心在于圖模型與數(shù)據(jù)流模型的融合，即數(shù)據(jù)流模型下的數(shù)據(jù)元素為圖模型定義的元素，圖數(shù)據(jù)中點(diǎn)的意義主要通過邊來體現(xiàn)，孤立點(diǎn)在現(xiàn)實(shí)中的意義有限，給定一個(gè)圖的邊集就能明確地獲得非孤立點(diǎn)的點(diǎn)集。因此，本文以無限邊序列作為圖數(shù)據(jù)流的一般定義。

定義1 圖數(shù)據(jù)流：圖數(shù)據(jù)流是一個(gè)無限地隨時(shí)間不斷變長(zhǎng)的邊序列，其中每條邊在序列中都有一個(gè)對(duì)應(yīng)的時(shí)間戳，序列中邊的時(shí)間戳從前往后是非降序的。

圖1給出了圖數(shù)據(jù)流的示例。其中邊兩端的頂點(diǎn)字母為頂點(diǎn)標(biāo)簽，而字母上標(biāo)為對(duì)應(yīng)的頂點(diǎn)標(biāo)識(shí)符（ID）。雖然也有相關(guān)工作的圖數(shù)據(jù)流模型是由無限的小圖序列定義的，但小圖均可以分解為一系列的邊（孤立點(diǎn)除外），因此以無限邊序列定義的圖數(shù)據(jù)流更具一般性和統(tǒng)一性。

現(xiàn)實(shí)應(yīng)用高速生成數(shù)據(jù)的同時(shí)往往伴隨已有數(shù)據(jù)的高速失效。例如利用社交網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行廣告投放時(shí)，過時(shí)數(shù)據(jù)的參考價(jià)值顯然沒有新近數(shù)據(jù)高，而大量的過時(shí)數(shù)據(jù)又會(huì)帶來高的處理開銷，因此，往往可以利用時(shí)間窗的概念來聚焦更有時(shí)效性的數(shù)據(jù)。時(shí)間窗主要分為兩種：基于數(shù)據(jù)規(guī)模的時(shí)間窗[15]和基于時(shí)間跨度的時(shí)間窗[16]。

定義2 時(shí)間窗：給定一個(gè)圖數(shù)據(jù)流，基于數(shù)據(jù)規(guī)模的時(shí)間窗定義為包含最近的給定N條數(shù)據(jù)邊的邊序列區(qū)間，時(shí)間窗內(nèi)的數(shù)據(jù)則是最近的N條邊；基于時(shí)間跨度的時(shí)間窗定義為以當(dāng)前時(shí)間為結(jié)尾的一個(gè)給定時(shí)間段(T1, T2)內(nèi)的數(shù)據(jù)邊所形成的邊序列區(qū)間，而窗口內(nèi)的邊即為過去T2-T1時(shí)間內(nèi)的所有數(shù)據(jù)邊。

圖2給出了帶時(shí)間窗口的圖數(shù)據(jù)流的模型示例。給定時(shí)間窗口后，在時(shí)間窗口內(nèi)的邊所生成的圖稱為當(dāng)前時(shí)間下的圖數(shù)據(jù)流的快照，如圖3所示。

3.4 圖數(shù)據(jù)流與動(dòng)態(tài)圖

圖數(shù)據(jù)流與動(dòng)態(tài)圖[17]既有聯(lián)系，又有明顯區(qū)別。帶有時(shí)間窗口和快照概念的圖數(shù)據(jù)流跟動(dòng)態(tài)圖的概念非常接近，甚至是動(dòng)態(tài)圖的細(xì)分概念。動(dòng)態(tài)圖是指給定一個(gè)大圖，在大圖上出現(xiàn)數(shù)據(jù)增刪的動(dòng)態(tài)行為的模型。因此，快照可以看作一個(gè)動(dòng)態(tài)圖，區(qū)別在于快照內(nèi)的邊帶有時(shí)間戳，并且有時(shí)序先后的概念。同時(shí)快照新增的邊往往帶有最大的時(shí)間戳，而刪除的邊則是帶有最舊的時(shí)間戳。動(dòng)態(tài)圖不需要具有時(shí)間戳，但針對(duì)圖的更新操作（增邊或刪邊的操作，不是數(shù)據(jù)邊本身）是具有時(shí)間的概念的。而圖數(shù)據(jù)流中，組成的數(shù)據(jù)元素不一定都定義在同一個(gè)點(diǎn)集和邊集，例如之前提到的大圖流[14]。此外，圖數(shù)據(jù)流具有的時(shí)間信息更貼合現(xiàn)實(shí)世界的交互與聯(lián)系，而動(dòng)態(tài)圖強(qiáng)調(diào)圖結(jié)構(gòu)隨時(shí)間的變化，并不一定強(qiáng)調(diào)數(shù)據(jù)自身的時(shí)間信息。因此圖數(shù)據(jù)流跟動(dòng)態(tài)圖的概念互有交集，但作為帶有明確時(shí)間信息的圖數(shù)據(jù)流，與動(dòng)態(tài)圖又有明顯不同。

4 圖數(shù)據(jù)流的研究前景：算法和系統(tǒng)

圖1 圖數(shù)據(jù)流示例

圖2 帶時(shí)間窗的圖數(shù)據(jù)流示例

圖3 圖數(shù)據(jù)流中的快照示例

基于大規(guī)模圖數(shù)據(jù)流的管理需求，針對(duì)圖數(shù)據(jù)流模型的研究有廣大的前景。傳統(tǒng)的圖計(jì)算的問題在這一模型下仍然會(huì)有研究?jī)r(jià)值，包括三角形計(jì)算[18-19]、最短路徑[20-21]、子圖查詢[22]、子圖挖掘[23]以及圖分類[24]、圖聚類[25]等。鑒于這部分圖計(jì)算問題已有充足的討論和總結(jié)，本文聚焦在基于圖數(shù)據(jù)流自身獨(dú)特特點(diǎn)的相關(guān)研究前景，主要從研究問題和研究方法兩個(gè)角度探討，之后討論圖數(shù)據(jù)流管理系統(tǒng)需要的相關(guān)技術(shù)和框架。

4.1 問題的角度

從研究問題的角度分析圖數(shù)據(jù)流的研究前景需要結(jié)合圖數(shù)據(jù)流的重要特征。圖數(shù)據(jù)流的一個(gè)非常本質(zhì)的特征就是邊的時(shí)間信息，這將為很多圖計(jì)算問題賦予新的語義。首先是基于邊的時(shí)序信息豐富查詢語義?，F(xiàn)實(shí)世界對(duì)象間的關(guān)聯(lián)關(guān)系和交互行為往往有明確的先后關(guān)系，例如好友關(guān)系的傳播、交通路徑的遞增時(shí)間戳等。因此，圖數(shù)據(jù)流的查詢問題可以引入時(shí)序的限制。例如，在子圖查詢中引入對(duì)邊的時(shí)序限制[10]。除了時(shí)序限制，還可以引入基于邊的時(shí)間間隔限制等，以豐富圖數(shù)據(jù)流相關(guān)查詢的語義。其次是利用圖數(shù)據(jù)流的時(shí)間維度分析和挖掘數(shù)據(jù)的變化行為。對(duì)于兩個(gè)頂點(diǎn)而言，在給定的時(shí)間段內(nèi)可能出現(xiàn)多條相連的邊，在時(shí)間維度上會(huì)有不同的行為表現(xiàn)。以社交網(wǎng)絡(luò)的好友關(guān)系分析為例，假設(shè)將用戶建模成點(diǎn)，而用戶間的交互為邊，那么在給定的一段時(shí)間內(nèi)，兩個(gè)用戶的交互頻率在時(shí)間維度上是上升還是下降對(duì)客戶的好友關(guān)系有明顯不同的意義。此外，兩個(gè)用戶之間交互內(nèi)容的主題或者關(guān)鍵字等在時(shí)間維度上的變化也包含描述兩者關(guān)系的潛在信息。因此，流場(chǎng)景使邊有了行為的概念，相應(yīng)的行為分析對(duì)圖數(shù)據(jù)流的分析有很大的價(jià)值。還有就是充滿挑戰(zhàn)但又有極大研究?jī)r(jià)值的圖數(shù)據(jù)流上的行為預(yù)測(cè)，即根據(jù)已有的圖數(shù)據(jù)流上的數(shù)據(jù)分布、行為變化，綜合關(guān)聯(lián)的結(jié)構(gòu)信息，預(yù)測(cè)未來一段時(shí)間可能出現(xiàn)的圖數(shù)據(jù)特征，包括分布、關(guān)聯(lián)等。例如，在交通網(wǎng)絡(luò)上將交通站點(diǎn)建模成頂點(diǎn)，站點(diǎn)間的車流建模成邊，這個(gè)模型下一個(gè)值得研究的問題就是如何根據(jù)過去幾個(gè)小時(shí)的車流信息預(yù)測(cè)未來一個(gè)時(shí)間段內(nèi)各條道路可能的車流密度。在網(wǎng)絡(luò)信息傳輸管道上，如何根據(jù)當(dāng)前的網(wǎng)絡(luò)狀況預(yù)測(cè)接下來的網(wǎng)絡(luò)流量擁堵情況，進(jìn)而進(jìn)行更合理的路由調(diào)度等，也是值得研究的問題。

4.2 方法的角度

從研究方法的角度看圖數(shù)據(jù)流的研究前景，則要結(jié)合目前技術(shù)上處理圖數(shù)據(jù)流遇到的核心挑戰(zhàn)：加速計(jì)算帶來的更新開銷。以圖數(shù)據(jù)流上的子圖查詢?yōu)槔?，如果通過構(gòu)建復(fù)雜的索引來加速子圖查詢，那么在數(shù)據(jù)更新時(shí)必然需要更新相應(yīng)的索引。如果不構(gòu)建索引，則更新發(fā)生時(shí)，為了處理子圖查詢需要重新進(jìn)行計(jì)算，而實(shí)際上一次更新往往涉及的只是局部的數(shù)據(jù)，完全重新計(jì)算將會(huì)有大量計(jì)算結(jié)果同上一個(gè)時(shí)間點(diǎn)的計(jì)算結(jié)果重疊，造成冗余計(jì)算。因此，處理圖數(shù)據(jù)流上的計(jì)算的關(guān)鍵是如何避免冗余計(jì)算，同時(shí)還能加速查詢的響應(yīng)。首先，需要考慮保存哪些已有的計(jì)算結(jié)果。盡量避免或刪除對(duì)之后的計(jì)算缺乏利用價(jià)值的計(jì)算結(jié)果，優(yōu)先考慮能夠多次重復(fù)利用的計(jì)算結(jié)果，進(jìn)而能夠更大限度地提高性能。其次，在確定需要保存的計(jì)算結(jié)果上，要相應(yīng)地保存組織的策略，即如何優(yōu)化空間開銷。對(duì)于有重疊的中間結(jié)果，需要盡量避免重復(fù)占用存儲(chǔ)開銷。因此，圖數(shù)據(jù)流計(jì)算的首要研究思路就是加速計(jì)算的中間結(jié)果的選取與保留數(shù)據(jù)的組織形式。其次則是利用并行技術(shù)加速圖數(shù)據(jù)流的更新與計(jì)算。在高速更新的圖數(shù)據(jù)上，單個(gè)更新往往涉及的只有部分圖數(shù)據(jù)，多個(gè)更新可能彼此之間不涉及讀寫沖突，通過并行技術(shù)加速這些無沖突的更新顯然能夠大幅提高系統(tǒng)的吞吐量。

4.3 圖數(shù)據(jù)流管理系統(tǒng)

目前還沒有針對(duì)圖數(shù)據(jù)流模型的管理系統(tǒng)，結(jié)合圖數(shù)據(jù)流管理的需求和研究前景，本節(jié)設(shè)計(jì)了圖數(shù)據(jù)流管理系統(tǒng)的大致框架，如圖4所示?？蚣苤饕譃?層，分別是圖數(shù)據(jù)流的基本數(shù)據(jù)層、算法和索引的邏輯層以及向上支撐的各種應(yīng)用的應(yīng)用層。首先是基本數(shù)據(jù)層，該層負(fù)責(zé)管理圖數(shù)據(jù)流的最基本的邊序列的存儲(chǔ)、增刪和基本的訪問。其中訪問操作包括圖數(shù)據(jù)的一些基本操作，如訪問節(jié)點(diǎn)度數(shù)、節(jié)點(diǎn)的鄰居等。其次是包含核心算法和相應(yīng)的索引數(shù)據(jù)的邏輯層。其包含的索引數(shù)據(jù)能夠根據(jù)數(shù)據(jù)層的增刪而進(jìn)行更新，從而保持與數(shù)據(jù)層的邏輯一致性。而核心算法則涉及圖相關(guān)的基本算法，包括路徑、子圖等的經(jīng)典計(jì)算以及圖數(shù)據(jù)流下邊的行為分析等。同時(shí)，還需要提供圖數(shù)據(jù)流一般性的聚集查詢與相關(guān)數(shù)據(jù)統(tǒng)計(jì)等邏輯接口。邏輯層之上則是需要支撐的應(yīng)用層，針對(duì)現(xiàn)實(shí)應(yīng)用數(shù)據(jù)的分析需求，定制更為復(fù)雜的計(jì)算接口。例如進(jìn)行基于子圖挖掘的事件偵測(cè)、城市交通的智能分析與管理和信息或話題的傳播跟蹤等。

5 結(jié)束語

高度數(shù)字化的社會(huì)生活帶來了大量高速生成的應(yīng)用數(shù)據(jù)，分析挖掘這些應(yīng)用數(shù)據(jù)能給人們的生產(chǎn)生活帶來極大的正反饋。然而目前主流的數(shù)據(jù)管理模型和技術(shù)（包括傳統(tǒng)的關(guān)系模型和圖模型等）難以應(yīng)對(duì)大規(guī)模復(fù)雜數(shù)據(jù)流的管理需求，圖數(shù)據(jù)流應(yīng)運(yùn)而生。圖數(shù)據(jù)流是圖模型和數(shù)據(jù)流模型相融合形成的數(shù)據(jù)模型，一方面具備圖模型對(duì)復(fù)雜數(shù)據(jù)的強(qiáng)表達(dá)能力，另一方面又結(jié)合數(shù)據(jù)流的更新場(chǎng)景來建模復(fù)雜數(shù)據(jù)的高速生成行為。因此，圖數(shù)據(jù)流模型及其研究具有非常重要的現(xiàn)實(shí)意義。目前，關(guān)于圖數(shù)據(jù)流的研究工作較少，已有的工作焦點(diǎn)分散并且不系統(tǒng)，因此圖數(shù)據(jù)流的研究前景廣闊。未來針對(duì)圖數(shù)據(jù)流的研究工作有3個(gè)較為重要的路線：一是基于已有的大量圖算法/算子等，研究圖數(shù)據(jù)流場(chǎng)景下相關(guān)計(jì)算操作的實(shí)現(xiàn)和優(yōu)化；二是基于圖數(shù)據(jù)流場(chǎng)景獨(dú)自的特點(diǎn)和現(xiàn)實(shí)應(yīng)用需求，提出新的圖數(shù)據(jù)流研究問題及其解決方案；三是針對(duì)圖數(shù)據(jù)流模型本身的數(shù)據(jù)管理系統(tǒng)，研究其存儲(chǔ)、索引、數(shù)據(jù)的增刪改查的基本操作、并發(fā)管理以及一致性保證等問題，進(jìn)而設(shè)計(jì)結(jié)合現(xiàn)實(shí)需求的圖數(shù)據(jù)流管理系統(tǒng)。圖數(shù)據(jù)流的研究具有重要的現(xiàn)實(shí)意義和廣闊的研究前景。

圖4 圖數(shù)據(jù)流管理系統(tǒng)框架