李友煥，鄒磊

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

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

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

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

盡管移動應(yīng)用數(shù)據(jù)蘊(yùn)含著高價值的信息，但這些數(shù)據(jù)卻具有結(jié)構(gòu)復(fù)雜、規(guī)模龐大、高速增長等特點(diǎn)。人們對不同應(yīng)用有不同的需求，這決定了移動應(yīng)用數(shù)據(jù)是復(fù)雜多樣的，而針對同一應(yīng)用產(chǎn)生的數(shù)據(jù)，不同的數(shù)據(jù)分析方也會有不同的數(shù)據(jù)需求。例如，針對社交網(wǎng)絡(luò)的數(shù)據(jù)，研究社交心理的人更關(guān)注用戶以及用戶間的好友關(guān)系與交互行為，而廣告媒體的從業(yè)人員則更關(guān)心平臺上發(fā)文內(nèi)容中的產(chǎn)品或話題信息。人們對數(shù)據(jù)的多樣化的需求決定了移動應(yīng)用數(shù)據(jù)的復(fù)雜性。數(shù)量眾多的軟件及其龐大的用戶量決定了相關(guān)數(shù)據(jù)的海量規(guī)模。例如，微信的月活躍用戶數(shù)已超過了10億，而用戶之間的交互則會帶來更大規(guī)模的數(shù)據(jù)，包括語音、視頻、圖片以及相關(guān)的文本等。這些大規(guī)模的復(fù)雜數(shù)據(jù)還在實時地高速增長，如社交網(wǎng)絡(luò)每天以億級別的發(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è)計成本較高，既定的數(shù)據(jù)框架結(jié)構(gòu)很難適應(yīng)數(shù)據(jù)種類、格式的頻繁變化；另一方面，關(guān)系型數(shù)據(jù)庫中，基于關(guān)聯(lián)信息的計算代價很高，如表格的聯(lián)結(jié)操作等，這使得在大規(guī)模數(shù)據(jù)場景下關(guān)系型數(shù)據(jù)庫管理模型難以滿足數(shù)據(jù)分析處理的需求。

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

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

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

2 流計算系統(tǒng)

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

（1）Storm

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

（2）Spark Streaming

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

（3）Samza

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

（4）Flink

Flink是跟Storm比較相似的系統(tǒng)，其整個數(shù)據(jù)處理過程稱為Stream Dataflow，既定的數(shù)據(jù)流動框架類似于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ù)流是高度對應(yīng)的。兩者比較大的區(qū)別在于容錯機(jī)制。Flink的容錯機(jī)制是檢查點(diǎn)（checkpoint），通過異步實現(xiàn)，并不會打斷數(shù)據(jù)流，因此Flink的檢查點(diǎn)的開啟與關(guān)閉對吞吐量的影響很小。而Storm采用的是ACK機(jī)制，開銷更大，而且對吞吐量的影響更明顯。另外，F(xiàn)link提供的API相對Storm的API來說更高級，而Storm的API則更基礎(chǔ)。Storm的優(yōu)勢主要是具有比較成熟的社區(qū)支撐和經(jīng)過較長期迭代之后的穩(wěn)定性，目前Flink成熟度較低，仍有部分功能需要完善，如在線的動態(tài)資源調(diào)整等。

（5）Kafka Stream

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

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

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

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

3.1 圖的流式計算

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

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

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

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

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

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

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

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

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

顯然，目前的圖數(shù)據(jù)流模型雖然都是針對大規(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)實中的意義有限，給定一個圖的邊集就能明確地獲得非孤立點(diǎn)的點(diǎn)集。因此，本文以無限邊序列作為圖數(shù)據(jù)流的一般定義。

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

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

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

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

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

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

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

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

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

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

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

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

4.1 問題的角度

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

4.2 方法的角度

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

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

目前還沒有針對圖數(shù)據(jù)流模型的管理系統(tǒng)，結(jié)合圖數(shù)據(jù)流管理的需求和研究前景，本節(jié)設(shè)計了圖數(shù)據(jù)流管理系統(tǒng)的大致框架，如圖4所示。框架主要分為3層，分別是圖數(shù)據(jù)流的基本數(shù)據(jù)層、算法和索引的邏輯層以及向上支撐的各種應(yīng)用的應(yīng)用層。首先是基本數(shù)據(jù)層，該層負(fù)責(zé)管理圖數(shù)據(jù)流的最基本的邊序列的存儲、增刪和基本的訪問。其中訪問操作包括圖數(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)典計算以及圖數(shù)據(jù)流下邊的行為分析等。同時，還需要提供圖數(shù)據(jù)流一般性的聚集查詢與相關(guān)數(shù)據(jù)統(tǒng)計等邏輯接口。邏輯層之上則是需要支撐的應(yīng)用層，針對現(xiàn)實應(yīng)用數(shù)據(jù)的分析需求，定制更為復(fù)雜的計算接口。例如進(jìn)行基于子圖挖掘的事件偵測、城市交通的智能分析與管理和信息或話題的傳播跟蹤等。

5 結(jié)束語

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

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