發(fā)布時間：2018-02-12 23:44

  本文關鍵詞： 可達查詢 大規(guī)模圖 動態(tài)圖 哈夫曼編碼 標簽索引　出處：《電子學報》2017年02期 　論文類型：期刊論文

【摘要】：隨著社交網(wǎng)絡分析、生物信息網(wǎng)絡分析等新必應用的涌現(xiàn)和計算機技術的飛速發(fā)展,圖的規(guī)模迅速增長,并且頻繁更新,使得對大規(guī)模動態(tài)圖數(shù)據(jù)的處理需求愈加迫切.現(xiàn)有的面向大規(guī)模動態(tài)圖的可達查詢研究成果較少,尚存在索引壓縮困難以及圖結(jié)構(gòu)待優(yōu)化等問題.本文提出了一種支持大規(guī)模動態(tài)圖的基于改進哈夫曼編碼的可達查詢處理方法(Huffman-based Label Reachability,HuffLR).該方法首先對預處理圖進行結(jié)構(gòu)上的兩次壓縮,得到雙壓縮圖;其次,基于雙壓縮圖提出一種前綴label索引,該索引能夠有效表達節(jié)點問的可達關系;最后,提出雙壓縮圖的演進和可達查詢處理及優(yōu)化算法,主要包括邊的插入與刪除、節(jié)點的插入與刪除.實驗表明,本文提出的基于改進哈夫曼編碼的大規(guī)模動態(tài)圖可達查詢處理方法具有良好的可行性和有效性.
[Abstract]:With the emergence of new applications such as social network analysis, biological information network analysis, and the rapid development of computer technology, the scale of maps has grown rapidly and updated frequently. It makes the processing of large-scale dynamic graph data more urgent. There are still some problems in index compression and graph structure optimization. In this paper, an improved Huffman-based Label rehabilitation algorithm based on improved Huffman-based Label rehabilitation is proposed to support large-scale dynamic graphs. Two compressions on the structure, Secondly, a prefix label index based on the double compression graph is proposed, which can effectively express the reachability relationship between nodes. Finally, the evolution and reachability query processing and optimization algorithm of the double compression graph are proposed. The experiments show that the proposed method based on improved Huffman coding is feasible and effective for large scale dynamic graph reachable query processing.
【作者單位】： 遼寧大學信息學院;
【基金】：國家自然科學基金(No.61472169,No.61502215,No.61572119,No.61303016,No.61472069,No.11547235) 遼寧省教育廳優(yōu)秀人才項目(No.LR201017);遼寧省教育廳科學研究一般項目(No.L2015193) 遼寧省博士科研啟動基金(No.201501127) 遼寧大學青年科研基金(No.LDQN201438)
【分類號】：O157.5

【相似文獻】

相關期刊論文 前8條

1 田端財;殷曉麗;;基于哈夫曼編碼的圖像壓縮技術研究[J];科技資訊;2009年08期

2 鹿璐;;哈夫曼編碼器軟硬件系統(tǒng)的設計與實現(xiàn)[J];黑龍江科技信息;2009年29期

3 張全伙，于洪斌，林榆;優(yōu)化哈夫曼編碼數(shù)據(jù)壓縮技術及程序?qū)崿F(xiàn)[J];華僑大學學報(自然科學版);1995年03期

4 劉曉鋒;吳亞娟;;哈夫曼編碼的一種基于樹型模式匹配的改進型算法[J];西華師范大學學報(自然科學版);2006年01期

5 孫巖賓;;基于哈夫曼編碼在Symbian平臺下對文件壓縮解壓的研究[J];科技資訊;2011年30期

6 王防修;;LZW碼的改進算法[J];武漢工業(yè)學院學報;2009年02期

7 王杰,劉誼;GIS中幾種壓縮編碼方法[J];礦山測量;2004年04期

8 ;[J];;年期

相關碩士學位論文 前3條

1 許彬彬;密碼分析中矩陣的存儲與計算[D];國防科學技術大學;2013年

2 李菁菁;MP3軟件解碼器的研究與實現(xiàn)[D];大連海事大學;2006年

3 蔡英;嵌入式Linux下MP3播放器的研究與實現(xiàn)[D];昆明理工大學;2007年

，

本文編號：1506837