圖資料庫發展
來自專欄 NoSQL技術剖析
本文大部分文本（90%）來自《CCF2014-2015中國計算機科學技術發展報告》，互聯網上無電子版，由本人進行OCR並粗略校驗。
1. 引言
隨著社交網路分析、Web語義分析、生物信息網路分析以及交通導航等新興應用的快速增長，不同領域出現了規模龐大、內部結構複雜、查詢需求多樣的大圖數據。2015年最新公布的統計數據顯示，全球最大的社交網路 Facebook擁有14.15億月活躍用戶。用戶之間的好友關係超過2000億條邊，日均記錄分享量也達到了數十億級別，65%以上用戶為日活躍用戶;國內領先的QQ社交網站註冊用戶為也超過了8.29億。
不同領域大圖數據應用過程中存在通用的數據操作。例如，在社交網路中，發現影響力最大的用戶，能夠更加有效地推送廣告;在交通網路中，發現兩點間滿足不同標準的路徑，有助於客戶行程規劃;在金融交易網路中，發現特定的模式，有助於發現異常的交易行為;在社交網路中，發現關聯關係密切、特徵相近的用戶群體，有助於商品的銷售。這些大圖數據操作不僅僅涉及數據節點自身的信息，而且涉及數據節點之間的結構關係。我們可以將大圖數據操作抽象為獲取特定節點、獲取特定路徑、獲取特定子圖等，通過實現這些通用操作，構建大圖數據管理系統。
圖數據管理在資料庫領域是一個經典的研究問題，其研究歷史呈現一個波浪式前進的過程。早在20世紀70年代，由於圖數據模型表達能力強，數據管理領域的研究人員就提出圖模型對客觀世界的數據進行建模，並設計了相關的圖數據管理原型系統。Charles W. Bachman還由於其在圖數據模型方面的貢獻於1973年獲得圖靈獎。之後，由於圖數據查詢在表達和執行方面的複雜度都很高，圖數據管理系統在應用方面存在挑戰，研究趨緩。在這一階段，關係資料庫由於其操作介面簡單，查詢優化技術實現突破，逐漸成為數據管理中的主流。2000年之後，隨著社交網路等真實大圖數據的迅猛增長和其上應用需求的推動，圖數據的相關研究工作重新成為熱點。例如，在VLDB2014國際會議中(http://www.vldb.org)，出現了4個圖數據管理的專題討論。國際T巨頭，包括 Google、 Facebook、微軟等正在進行分散式大圖數據管理系統的研發，支持包括海量Web網頁重要性排序、社區發現等操作。
圖數據管理也得到計算機方向其他研究領域的關注。例如，在2014年系統軟體專委會所撰寫的《面向新型計算模型的系統軟體研究新進展與趨勢》文中，上海交通大學陳海波團隊也將《圖並行計算系統的研究進展與趨勢》作為重要內容進行論述。本報告將側重從數據管理的角度對大圖數據管理的相關技術展開論述。部分關鍵技術或系統如在《圖並行計算系統的研究進展與趨勢》論述過，本報告將不再贊述。
2. 大圖數據管理面臨的挑戰
大圖數據是大數據的重要形態，具有大數據的4V特性：
- 首先大圖數據規模龐大，不僅僅包含大量圖數據節點及其節點屬性，而且包含圖數據節點之間複雜的關聯關係;
- 其次，大圖數據表達靈活，不同類型節點結構異構，每個節點和邊上屬性模式信息各不相同，很難抽象出相對固定的模式。例如，在客戶購物關係圖中，每個客戶或者商品的屬性不同，客戶(或者商品)內部存在關聯關係，客戶與商品之間也存在關聯關係。
- 再次，大圖數據處於動態變化中。隨著時間不斷的變化和演進，大圖的內容信息發生變化大圖的結構信息也發生變化，如節點/邊的新增和刪除等。
- 最後，大圖數據中也蘊含著豐富的價值，通過分析大圖數據中的結構、關係、時序等信息，為不同領域的大圖數據應用決策提供支持。
大圖數據還具有複雜性C的特性。由於大圖數據表達方式靈活，任意數據節點之間都可能存在關聯關係，假定節點數量為n，單一類型關聯關係最多為n2，多類型關係景下，關聯關係就更加豐富。整個大圖看作一個複雜網路。大圖數據操作往往涉及全局數據，計算代價高。
大圖數據的4V+C的特點使得大圖數據的管理面臨巨大挑戰。
第一，大圖數據環境中圖操作代價高。和傳統的關係數據或者XML樹狀數據相比，圖數據缺乏結構約束，操作複雜。以圖數據中的兩點最短路發現為例，經典 Dijkstra演算法的複雜性為0(mnlogn)，其中n是圖中的節點數，m是邊數。隨著圖規模的增長，上述操作的代價急劇上升。此外，這一演算法複雜性基於單機內存環境。考慮到單機內存無法滿足大圖數據處理需求，大圖數據操作還需要考慮磁碟訪問代價和分散式環境中網路訪問代價。
第二，大圖操作需求靈活，提供簡潔、高效、表達能力強的查詢語言面臨困難。隨著大圖數據應用的深化，大圖數據之上的操作需求日益複雜。大圖數據操作不僅僅局限於類似檢索某個點的所有關聯邊這樣簡單的查詢，而且還包括更加複雜的、側重於全局的查詢和分析，如圖中最短路發現查詢、最小支撐樹構建查詢、子圖模式匹配等操作。考慮到大圖數據操作的靈活性，很難抽取公共部分進行優化或者簡化表達。此外，圖數據操作通常需要循環迭代，這對方便、易用的圖查詢語言的設計有很大的影響。
第三，大圖數據複雜性的特點使得很難直接應用並行計算模型解決大圖數據操作。圖數據規模龐大使得並行分布策略不可避免。同時，由於圖數據內部關聯靈活、複雜，圖數據操作很可能需要全局的圖數據信息。即使實現圖數據的分塊和並行操作，不同分塊之間依然存在大量的訪問，無法簡單直接實施並行操作。
3. 大圖數據管理中的主要研究問題
面對大圖數據管理的挑戰，很多研究機構從不同的角度展開研究工作，包括大圖數據管理的體系結構、大圖數據的組織、大圖數據管理的查詢設計、大圖數據查詢執行和優化等問題。
3.1 大圖數據管理的體系結構
在大圖數據管理中，不同的底層體系結構、底層系統軟體、硬體都會對大圖數據管理產生影響。
分散式大圖數據管理是大圖數據管理的主流結構。由於大圖數據的規模龐大、節點信息豐富、計算代價高，利用多機的計算資源和存儲資源管理大圖是大圖數據管理的趨勢。在分散式大圖數據管理中，目前應用比較廣泛的是基於 Mapreduce和基於BSP計算模型的大圖數據管理。基於 Mapreduce框架實現大圖數據管理是可行的技術路線。 Mapreduce框架是目前通用大數據的並行處理框架，大圖數據的查詢可以通過 Mapreduce框架實現，具有良好的可擴展性和大數據分析的高吞吐量。但是，由於 Mapreduce框架處理大圖數據導致過多的磁碟讀寫操作，基於 Mapreduce框架的大圖數據管理效率不高。
基於BSP計算模型的大圖數據管理方案具有較好的可擴展性和較高的效率。為了克服 Mapreduce管理大圖導致的各類問題， Google借鑒BSP計算模型的思路，設計了Pregel框架。 Pregel框架將圖數據存儲在分散式環境中不同計算節點的內存中，支持以點為中心的計算模式，通過內存隨機訪問直接修改節點的狀態，避免磁碟讀寫的/O代價。Google的 Pregel系統已經用於Web級別的大圖節點重要性排序等操作，展示出較強的可擴展性。 Pregel在 Apache社區的開源版本Giraph在 Facebook也得到重要應用，在社區發現、子圖聚類等操作上取得良好效果。
單機大圖數據處理是一種重要的技術路線。隨著CPU和內存技術的發展，使得單機有資源支持海量大圖的處理。單機環境中無需考慮分散式大圖數據管理中引入的網路代價，其演算法設計實現簡單，調試安裝代價相對低廉。為了提高大圖數據處理的可擴展性，而單機內存有限，單機計算環境中使用外存不可避免，單機大圖數據處理框架的一個關鍵問題就是需要降低外存隨機掃描對大圖數據操作的影響。目前單機大圖數據計算框架，如GraphChi、 XStream等，處理常用的測試圖數據(如 Twitter數據)，能夠取得和分散式大圖數據計算框架可比較的性能。
基於關係資料庫管理大圖數據是另一種可選的技術方案。關係資料庫在聯機事務處理領域取得巨大成功，成為企業信息基礎設施中不可或缺的組成部分，有巨大的市場份額。圖數據管理和關係數據管理也有很多相通之處，如都需要數據存儲、數據緩存、索引、查詢優化、並發控制等。基於關係資料庫能夠快速實現超過內存的大圖數據的管理，如索引、更新、並發操作等。關係資料庫管理圖數據面臨的問題是關係資料庫擅長一次處理一個集合，而圖數據操作考慮優化策略，往往採用一次一個節點的操作方式，直接利用關係資料庫管理大圖數據效率不高。
充分利用新硬體的特性是提高圖數據管理系統性能的有效手段。CPU中 Cache是影響計算性能的重要因素。在圖數據組織和操作過程中考慮Cache的特寺性，提升CPU的Cache命中率，能夠在全內存環境中進一步提高系統性能。圖形處理器GPU帶有大量的並行計算模塊，通過設計合適的圖數據分塊和並行方法，結合CPU和GPU提高大圖數據管理的效率。相對於帶有機械設備的硬碟，採用電子定址的快閃記憶體更加適合支持帶有大量隨機訪問的圖數據操作。在基於快閃記憶體的圖數據管理中，需要考慮快閃記憶體寫入代價昂貴的約束。
3.2查詢語言設計
圖數據表示方式靈活，查詢分析形式多樣。圖數據查詢不僅僅包括對特定子圖數據的獲取，而且包括圖數據的轉換。由於查詢方式多樣，目前沒有一種廣為接受、易於表達、便於優化支持高效執行的查詢語言。我們分析圖數據管理中可能的查詢語言方式。
提供圖數據基本操作API是目前大圖數據管理系統的一種查詢方式。目前的圖資料庫管理系統，如Neo4j，提供了基本的圖操作APl，如圖數據存儲、遍歷、最短路查詢等操作。用戶在其應用程序中僅僅需要調用這些AP，系統負責這些調用的執行和優化。然而由於圖的操作方式靈活，利用有限的API操作很難支持不同領域的圖操作需求。例如，Neo4j無法直接實現 Page Rank的迭代計算。
根據現有圖數據管理框架的介面要求，編寫圖數據不同查詢腳本是目前圖數據查詢和分析的主流方式。系統不提供相對高層的圖操作API，而是提供相對底層的編程介面。如Mapreduce框架介面、以點(邊)為中心的計算介面等。用戶根據查詢流程，編寫符合介面的查詢腳本。這種方式足夠靈活，能夠支持複雜的圖查詢操作。但是，這種方式需要用戶掌握腳本語言，負責腳本的編寫、調試、優化等，用戶應用開發負擔重。
提供描述性圖查詢是介於圖操作API和圖框架介面的一種方式。類似於關係代數，代數將不同類型的圖操作公共部分抽取出來，形成圖數據操作體系。用戶通過相對高層的描述性查詢表達圖操作，系統負責將這些查詢轉換到底層框架中。這種方式能夠屏蔽不同的底層平台的實現細節，減少用戶應用系統實現的代價。然而，由於圖操作本身的複雜性，即使採用描述性查詢，描述性查詢自身也很複雜，例如，描述性圖查詢中需要有遞歸或者迭代機制，還需要選擇、賦值等操作。
圖的關鍵字查詢是圖數據查詢的一種有前景的查詢方式。圖數據具有靈活的結構特性，用戶通過結構信息表達查詢繁瑣。而現實中圖數據是帶有其他屬性信息的。用戶可以採用關鍵字描述圖查詢目標，圖查詢反饋包含這些關鍵字的特定子圖，圖的結構信息用於查詢結果的排序。採用這種方式無需用戶了解複雜的圖結構，極大減輕用戶圖查詢的代價，但是不支持圖數據的抽取和轉換。
面向特定領域的圖查詢也是一種有效的圖數據查詢方式。特定領域的需求實際上是圖數據查詢的一種約束和限制。比較典型的領域相關查詢語言是知識圖譜領域中的SPAROL。 SPARQL採用類SQL查詢的形式表達查詢模式，查詢結果為與查詢模式匹配的數據子圖。 SPARQL採用類SQL的形式，能夠降低用戶的學習成本，提高用戶的接受度。
3.3 大圖數據組織
大圖數據管理需要根據所在的計算環境，合理組織數據，提高數據處理的效率。在分散式環境中，大圖數據需要劃分到不同的計算節點中進行保存和處理。圖數據劃分需要考慮不同圖劃分之間的消息通信、計算節點的負載平衡等因素。最原始的圖劃分方法採用隨機節點分塊方法，根據Hash函數將圖節點劃分到不同的分區塊中，或者採用節點ID區間的方式進行劃分。由於不同子圖之間的邊意味著消息通信量，可以採用目前綜合性能優異的 Metis圖劃分方法，獲得降低子圖間通信量的圖劃分方法。由於同一數據節點在計算節點中出現並且僅出現一次，這種劃分策略又稱為點劃分策略。
針對度數分布符合冪律分布的圖數據，可以採用邊劃分的策略。即選擇度數較大的數據節點進行切分，建立這一個數據節點在不同的計算節點中的副本，分散存儲相關聯的數據邊，利用副本之間少量的消息量，降低點劃分形成的子圖間消息數量，減少採用點劃分導致的計算負載不均衡的問題，提高整體運行效率。
現有系統還採用了以邊為中心的計算模式。通常來講，圖中邊的數量遠大於點的數量，而邊的信息在圖數據操作中往往是無需改變的，點上附加的數據值是需要頻繁改變的。以邊為中心的思想將節點信息和邊信息進行分離，將邊的信息置於外存，節點信息盡量置於內存，通過順序掃描邊，改變內存中節點的數值。由於處理腳本主要是改變節點的數據值，這種方式本質上也是一種以節點為中心的計算。
在單機外存環境中，圖數據劃分內部還需要進一步組織，減少外存隨機掃描對查詢效率的影響。例如，按照邊某一端點的ID實現圖數據的順序劃分，而在同一個劃分內部，按照另一端點的DD進行了排序。這種組織方式能夠在某一個圖劃分載入到內存時，通過順序掃描特定的劃分片段可以獲取這一圖劃分相關邊信息，減少外存隨機訪問的影響。
3.4 大圖數據查詢分析的執行和優化
目前分散式大圖數據操作執行方式分為同步執行方式和非同步執行方式。在同步執行式中，同一個計算任務由多個超步組成。在每個超步中，節點接收到其他節點發送的消息，根據用戶腳本處理消息，向其他節點發送消息。每個超步間通過柵欄保持同步，超步結束需要等待所有的參與計算節點結束。同步執行方式的優勢為編程易於調試，系統穩定性高，可擴展性高。
與同步方式對應的執行方式為非同步執行方式。其特點是執行過程中沒有全局統一的同步概念。主要思路為數據節點在任何時刻，都可以進行計算。非同步的方式優勢在於能夠快速收斂，執行效率較高。但是，非同步執行方式無法保證執行過程中的確定性。即同一任務多次執行，最終結果可能都不一樣。這一特點在某些數據操作中影響計算有效性，並使得演算法在分散式環境中難以調試。
減少分散式環境中通信量是大圖數據操作的一種優化策略。傳統以節點為中心的計算模式中，不同數據節點之間通過消息或者共享內存進行通信。如果能夠感知到同一計算節點的其他數據節點，則可以通過效率較高的局部內存訪問替代昂貴的網路訪問。良好的圖劃分方法是實現這一優化的基礎。
負載平衡是分散式查詢執行過程中需要考慮的問題。分散式環境中同步執行查詢的代價取決於最慢的計算節點。不同類型的圖數據查詢產生不同的負載分布。根據計算節點的實時負載，遷移數據節點，實現負載的動態平衡，能夠查詢的運行時間。在數據節點的動態遷移過程中，需要考慮數據節點在分散式環境中的重定位問題。
查詢腳本層面的優化是大圖查詢優化的有效手段。圖數據操作通常涉及循環迭代而在分散式系統中每次循環都有額外代價，如BSP模型中超步的同步代價、 Mapreduce框架中圖數據的掃描和傳輸等。此外，某些循環在分散式環境中活躍節點過少，循環帶來的相對收益差。減少分散式環境中的循環次數是圖數據查詢重要的優化策略。
4. 國外研究現狀
面對大圖數據帶來的技術挑戰，國外高校、研究機構展開大圖數據的研究工作，設計並實現了大圖數據管理系統。我們以典型系統為代表，分析國外大圖數據管理相關的研究進展。
4.1 大圖數據分散式管理框架
Pregel： Pregel是Google在2010年發表針對大圖數據的分散式計算框架，是目前大圖數據管理領域最有影響力的研究成果之一。針對 Mapreduce框架管理大圖缺乏迭代支持、隨機數據修改代價昂貴等問題， Pregel框架做了創新和優化。 Pregel將不同數據節點進行分割，分別載入到不同的計算節點中。圖數據查詢整體遵循BSP計算模型，每個圖查詢由多個超步加以完成。每個超步中，圖數據節點計算採用以節點為中心的編程模型。 Pregel框架在 google得到廣泛應用，支持Web級別的大圖數據節點重要性排序等基本操作。
Giraph： Giraph 是 Apache所支持的，它是一個在 Hadoop之上運行的 Pregel的開源系統。 Giraph 中實現了BSP的計算模型，支持用戶以點為中心的腳本編程。相對於其他分散式圖查詢系統， Giraph 有一個顯著特點，即 Giraph 本身是一個無 Reducer的 Mapreduce任務，圖數據查詢處理易於和 Hadoop環境進行集成。 Giraph 在 Facebook有重要的應用，支持社區發現、節點重要性排序等操作。
Trinity系統： 微軟研究院設計了Trinity系統。該系統能夠同時支持低延遲的在線查和高吞吐量的離線分析。為了避免外存隨機掃描的影響， Trinity將圖數據保存在內存雲中，並且設計了複雜的內存機制來管理邊長數據。 Trinity在上層引入了查詢語言TQL表達圖數據的查詢。
Graphlab 和 PowerGraph： Graphlab是一個支持非同步執行方式、利用共享內存的大圖數據管理框架。為了提高非同步執行中的數據一致性， Graphlab引入了數據節點訪問的鎖機制。針對自然圖中高度數節點帶來的負載偏斜， Graphlab的後續版本 PowerGraph引入了邊劃分的策略，建立高度數節點的副本，劃分關聯邊到不同的計算節點，使得每個算節點上擁有均衡數量的邊，從而提高查詢執行效率。
4.2 大圖數據單機管理框架
GraphChi和 XStream： Graphchi是單機圖數據查詢框架。單機環境處理大圖不可避免需要外存的支持，而大量隨機訪問外存數據會產生嚴重的性能問題。 Graphchi將圖數據按照節點ID區間進行劃分，保存入邊信息，每個分區的出邊信息在其他分區中順序存儲，這樣利用外存的順序訪問替代隨機方法，提升單機外存環境中以點為中心的計算框架的性能。 Xstream採用以邊為中心的存儲方式，不需要對邊表進行排序，也不需要索引，同時通過順序存取提高緩存的命中率。
4.3 基於關係資料庫的大圖管理框架
Vertexica： 其是MIT開發的基於關係資料庫(列式存儲)的圖數據管理框架，其特點是基於資料庫系統存儲圖數據，其上提供了以點為中心的計算模式，支持用戶通過編寫腳本管理圖數據;還提供了一種查詢語言 GRAPHiQL，支持用戶表達關係操作和圖數據操作。
4.4大圖數據高層查詢語言
SociaLite： SociaLite是斯坦福大學開發的一種基於Datalog的大規模圖數據查詢系統。SociaLite擴展Datalog支持嵌套底層數據，支持遞歸實現聚集操作，允許用戶自定義執行次序等。Sosocialite可以方便表達可達性查詢、最短路查詢、Pagerank、三角形計算等圖查詢。用戶提交的 Socialite查詢能夠自動轉換到底層執行計劃，並實現優化。
4.5 部分大圖數據管理框架特性
5. 國內研究現狀
下面我們從大圖數據管理框架、大圖數據操作演算法、大圖數據應用三個層面討論國內在大圖數據管理方面的進展。
5.1大圖數據管理框架
BC-BSP： BC-BSP是東北大學和中國移動合作開發的，基於BSP模型的大圖數據布式並行選代計算的平台。BC-BsP系統支持基於虛擬桶的均衡哈希劃分、基於邊聚簇特性的圖劃分動態調整策略，提供了以分區(子圖)為中心和以(頂)點為中心的兩種計算模式和編程介面，提高了數據處理的靈活性和適應性。與目前的開源框架Hama以及Giraph相比，BC-BSP具有良好的可擴展性。
MoCGraph： MoCGraph 是北京大學開發的基於消息流式處理的可擴展大圖查詢框架，在BSP環境中能夠以數據流的方式處理大圖計算中的消息數據，減少中間結果對框架內存的壓力。同時利用流式計算減少針對外存的隨機訪問操作。
PSgL： PSgL是北京大學開發的子圖並行列舉框架，支持在圖數據中枚舉所有與模式圖同構的子圖。其利用分治思想，基於圖遍歷操作迭代枚舉結果，設計了多種分發策略保證計算節點間的負載均衡，提出了三種獨立機制來縮小中間結果規模，支持索引查詢、圖結構分析等重要應用。
VENUS： VENUS是華為研究人員所研製的單機大圖數據管理框架。VENUS針對GraphChi框架存在的問題進行了優化，分別存儲支持更新節點信息和只讀邊信息，通過順序掃描減少邊數據對內存中的佔用，通過將節點數據儘可能放入內存，減少訪問節點數據對隨機掃描的影響。
GraphHP： GraphHP 是西北工業大學開發的圖數據管理框架，結合圖查詢執行中的同步模式和非同步模式。 Graphhp中數據節點分為邊界節點和局部節點。在同步環節，邊界節點之間進行消息通訊，而局部節點的計算通過非同步操作完成。通過兩階段的超步模式加快了系統收斂速度。
Graph Memory： Graph Memory是東北大學開發的圖數據存儲和查詢優化系統，結合集群環境下的異構計算資源(如眾核、多處理器、多處理節點等)以及內存訪問特性，提供適合大圖數據的並行處理框架、分析任務調度策略，以及系統負載平衡演算法;採用基於世系的數據容錯技術和基於熱備進程的任務恢復技術，來提升整個系統的可靠性和可用性。
5.2 大圖數據查詢和分析
GStore 和 GAnswer： GStore是北京大學開發的利用子圖匹配技術面向海量RDF數據的SPARQL檢索引擎。gStore將RDF數據存儲為圖數據，利用圖模式匹配操作支持圖SPARQL查詢，引入結構編碼減少模式匹配過程中的搜索空間。gAnswer引入了RDF數據的自然語言查詢方式，避免了用戶編寫複雜的結構查詢，利用子圖匹配，同時獲取自然語言查詢答案和短語消岐。
Laft-Suite：Laft-Suite是清華大學研發麵向社交網路分析系統，深入解決了社區結構分析、重要節點及潛在重要節點發現、社交鏈接產生方向腿短、推斷以及社交網路演化預測等問題，提供了一系列有效的解決方案，不僅支持傳統的社交網靜態結構分析，而且能展現社交網路的生成過程和演化規律。
5.3 大圖數據應用系統
學術空間( ScholarSpace)： 學術空間是人民大學開發的，以學者為中心的個人學術息空間。支持各領域基於作者名的學術信息查詢，自動生成包括發表文獻列表、發表數量園線圖、合作作者列表/圖形化展示及知名學者圖片、新聞的個人學術成就總頁面。還供了了面向各學科領域的文獻發表數量機構排名統計功能和各期刊收錄文獻單位和作者的Top20排名統計功能，方便用戶更直觀地了解本領域的學術研究現狀。同時系統按月提供所收錄刊物的文獻導讀輯錄，方便學者瀏覽本領域文獻。系統通過自主研發的Web數據抽取和數據集成方法構建了語義豐富的關聯資料庫，目前具有近200萬論文實體，100多萬作者實體。系統藉助RDF通過三元組形式對關聯數據進行描述，結構與大圖數據十分類似。學術空間 ScholarSpace 採用北京大學 gStore對RDF數據進行存儲，包括1000萬條三元組、60萬節點，其查詢引擎通過編碼等方式對圖的節點和邊進行組織，並通過子圖匹配演算法實現圖上的高效查詢，具有良好的性能和可擴展性，能夠在集群上進行實現，取得了良好的應用效果。
學者網：學者網是華南師範大學開發的，面向學者的社交網路，目前用戶及學術數據記錄已超過億條，形成了複雜的圖數據模型。基本存儲模式採用關係資料庫與分散式存儲混合方式;對需要頻繁讀取的數據，實現高效的緩存查詢和更新技術;對於需要進行大規模處理的數據，採用離線計算的方式實現;在進行論文搜索、學者關係和學術社區挖掘等推薦系統，採用了 Hadoop分散式框架對數據進行處理。
中國娛樂圈明星關係網： 這是我在做學校大作業時候，自己做的一個使用圖資料庫的應用，其中資料庫使用單機版的Neo4j，節點數量僅僅3000內，覆蓋了國內的大多數明星。使用了資料庫的最短路等演算法，可以驗證6度空間理論。查詢語言採用了Neo4j自主發明的查詢語言cypher。
6. 國內外研究進展比較
面對大圖數據管理的迫切需求，從工業界到學術界都開展了圖數據管理的研究工作，圖數據管理成為國內外的研究熱點。國內的研究人員逐漸從大圖數據演算法研究，擴展到框架實現以及系統應用。我們從大圖數據管理的框架層面和演算法層面比較國內外的研究進展。
在框架層面，國外研究機構所提出的 Pregel、 Powergraph、 Graphchi等框架在系統成熟度、系統應用、原創性方面，要優於國內高校和科研院所所提到的框架。 Pregel在Google已經成功支持Web級別大圖數據操作， Powergraph提供了多種圖數據分析挖掘演算法， Graphchi在單機上取得集群可比較的性能，上述框架全部開源。國內各個高校和研究機構也在框架層面做了大量的工作，但是更多側重於現有框架在某些方面的改進，包括消息處理機制、任務調度機制、圖數據分割機制、查詢優化機制等，期待更多原創性系統性、實用性的成果出現。
在圖數據分析演算法層面，國內研究結構針對最短路發現、社區發現、 SimRank計算、模式匹配、信息推薦等熱點問題，提出了多種圖數據分析和挖掘方法，在方法的可擴展性、方法的效率，方法的資源消耗等方面，達到和國外同行所提出的方法相當的水平。
圖數據研究的最大推動力是應用的發展。國內社交網路平台數據(如微信)，購物網路平台數據(如淘寶)等發展迅猛，產生了大量的圖數據，也帶來了現實的挑戰。阿里、華為、騰訊、百度等國內巨頭已經開始了大圖數據管理關鍵技術的研究和應用。這些基於真實場景和需求的研究更有生命力，將提高國內大圖數據管理的研究水平。
7. 總結
隨著應用的逐步深化，圖數據管理的研究也將繼續發展。我們將圖數據管理的發展 趨勢歸納為以下幾點。
兼顧在線查詢和離線分析的大圖數據管理系統：不同類型的計算任務具有不同的特點，在線應用要求實時性高、響應及時，而離線處理任務更關注任務吞吐量、並發能力以及資源的合理利用性。目前所提出的圖數據管理的框架，包括 Pregel、 GraphLab、GraphChi等，更多側重於圖數據的分析，強調圖數據分析的吞吐量，查詢的實時響應不是目前框架的重點。兼顧查詢效率和吞吐量的大圖數據管理系統將結合兩種處理方式的優點，屏蔽具體的計算模型，根據用戶提交的查詢和數據量自動選擇合適的處理方式。
支持豐富屬性的大圖數據管理框架：目前的大圖數據處理框架，更多側重於大圖數據結構的分析，而現實世界中的大圖數據往往帶有屬性信息。大圖數據實際上包含結構和內容兩類數據。大圖數據之上僅考慮結構特性的查詢應用場景較窄。充分借鑒其他研究領域，如信息檢索領域、數據挖掘領域的研究進展，實現結構和內容相結合的大圖數據查詢和分析，為應用提供更有效的大圖數據管理服務。
大圖數據管理中的事務：隨著大圖數據應用的不斷深入，多個用戶可能同時於操作大圖數據，同時大圖數據是保存在不同的數據中心中，如何支持多個用戶並發訪問大圖數據，保證數據一致性是大圖數據後續需要解決的問題。某些最新的工作已經開始探討分散式大圖計算環境中錯誤恢復等操作，後續還有廣闊研究空間。
參考
由於前些年以及後些年的《CCF中國計算機科學技術發展報告》都有電子版，並且大家都可以下載，唯獨這年的電子報告無從下載。恰好當年我以學生嘉賓參加CNCC2015，有幸獲贈一本《CCF2014-2015中國計算機科學技術發展報告》，並有圖領獎 Michael stonebraker的親筆簽名。於是就利用OCR進行了翻譯，並人工進行了校驗，並添加了部分內容。
推薦閱讀：