《大規模圖數據管理中結構相似度查詢處理技術研究》是依託中國人民解放軍國防科技大學，由趙翔擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：大規模圖數據管理中結構相似度查詢處理技術研究
- 項目類別：青年科學基金項目
- 項目負責人：趙翔
- 依託單位：中國人民解放軍國防科技大學
中文摘要,結題摘要,
中文摘要
圖作為一種通用的數據結構可表示複雜的結構和語義，現實世界中與圖相關的套用幾乎無所不在，如交通網路和社交關係等。真實世界中實體規模的擴張導致相應圖規模激增，大規模圖數據對其管理與分析技術提出了巨大挑戰。本項目研究大規模圖數據管理中結構相似度查詢處理技術，旨在提出高效的結構查詢解決方案，滿足當前處理大規模圖數據需要。擬開展以下研究：1、在結構相似度度量方面，提出統一的分類框架，輔助用戶篩選滿足套用需求的度量；2、針對多屬性異構信息網路，構造實用合理的結構相似度度量；採用可擴展分散式計算平台處理大規模圖數據，基於現有圖劃分最佳化策略，設計高效的結構相似度查詢算法和索引支持，提高系統查詢回響性能；3、考慮動態演進圖，提出有效的圖劃分管理機制，支持圖結構的持續更新，並滿足通信代價最小化和負載均衡的目標；4、基於嚴格理論分析的基礎上，在真實大規模圖數據上開展廣泛實驗論證所提技術的高效性和可擴展性。
結題摘要
圖作為一種通用的數據結構可表示複雜的結構和語義，現實世界中與圖相關的套用幾乎無所不在，如交通網路和社交關係等。真實世界中實體規模的擴張導致相應圖規模激增，大規模圖數據對其管理與分析技術提出了巨大挑戰。本項目研究大規模圖數據管理中結構相似度查詢處理技術，旨在提出高效的結構查詢解決方案，滿足當前處理大規模圖數據需要。 在項目的支持下，開展了以下計畫書中規定的研究：1、統一的結構相似度度量分類框架及算法支持；2、面向大規模多屬性異構圖的結構相似度查詢方法；3、適應動態演進網路圖的結構相似度查詢方法；4、基於真實數據的對比驗證和技術有效性評估。除此之外，還根據研究需要考察了：5、面向大規模單幅圖的頻繁子圖挖掘算法；6、分散式子圖挖掘中的通信開銷與調度最佳化技術。 通過科研攻關，取得了一系列重要科研成果：1、在圖結構相似度檢索問題上，採用無固定尺寸、不相互重疊的子結構作為索引，提出了一種基於圖劃分的解決方案；2、在大規模單圖上的頻繁子圖發現問題上，利用分散式大圖處理框架Pregel，設計了一種高效可擴展的頻繁模式挖掘算法；3、在節點相似度匹配問題上，基於SimRank提出了一種增量算法，用於高效的top-k點對的快速檢索；4、在大圖計算模型上，針對現有大數據計算模型對圖計算的不適配，改進了一種基於分離器和組合器的BSP大圖計算模型；5、針對動態圖模式匹配問題，設計了一種基於結構分解的動態模式匹配方法，通過動態維護匹配結果集實現高效求解。 至此，已達成了關於人才培養、國內外學術交流等方面預期目標，尤其是在1、高水平學術論文方面，在項目執行期間共發表學術論文29篇，SCI檢索6篇，並包括了VLDB Journal、SIGIR、IEEE TNNLS等國際高水平期刊和會議論文和《軟體學報》《計算機學報》等國內高水平期刊論文；2、智慧財產權保護方面，申請和受理國家發明專利18項，國防發明專利2項，其中2項已授權，其餘均已進入實質審查階段。
