本文選題：分布式 + 大規(guī)模圖　； 參考：《小型微型計算機系統(tǒng)》2017年09期

【摘要】：可達查詢作為圖查詢中一類基本查詢,在眾多領(lǐng)域得到廣泛應(yīng)用.研究發(fā)現(xiàn),圖規(guī)模的不斷增長導(dǎo)致傳統(tǒng)單機環(huán)境下的查詢算法已無法滿足大規(guī)模圖的查詢需求.為此,提出一種折疊樹編碼索引的大規(guī)模圖可達查詢方法,該方法由離線預(yù)處理和在線查詢兩階段構(gòu)成.預(yù)處理階段,提出一種折疊樹編碼索引方法 FTCI,該方法建立了基于B+樹的標記機制對分割子圖進行標記,并通過標記子圖上的折疊樹創(chuàng)建及相應(yīng)類哈夫曼編碼,良好地保存了子圖內(nèi)部及子圖間的可達信息;在線查詢階段,采用分布式技術(shù),設(shè)計了基于FTCI的可達查詢方法,根據(jù)查詢節(jié)點隸屬子圖情況,給出子圖內(nèi)、子圖間查詢策略.實驗證明提出的方法在保證高效查詢的同時降低了索引的存儲開銷,提高了可達查詢的處理效率.
[Abstract]:As a kind of basic query in graph query, reachable query is widely used in many fields. It is found that the traditional query algorithm in single machine environment can not meet the query demand of large scale graph due to the increasing of graph scale. For this reason, a large scale graph reachability query method based on folding tree coding index is proposed, which consists of two stages: off-line preprocessing and on-line query. In the preprocessing stage, a folding tree coding index method, FTCI, is proposed, which establishes a marking mechanism based on B-tree to mark the segmented subgraph, and creates the folding tree on the marker subgraph and the corresponding Huffman coding. The reachable information within and between subgraphs is well preserved, and in the online query stage, the reachability query method based on FTCI is designed by using distributed technology. According to the case of query node membership subgraph, the query strategy between subgraphs and subgraphs is given. Experiments show that the proposed method not only ensures efficient query, but also reduces the storage cost of index, and improves the processing efficiency of reachable query.
【作者單位】： 遼寧大學信息學院;
【基金】：國家自然科學基金項目(61472169,61502215)資助 遼寧省教育廳一般項目(L2015193)資助 遼寧省博士科研啟動基金項目(201501127)資助 遼寧大學青年科研基金項目(LDQN201438)資助
【分類號】：O157.5

【相似文獻】

相關(guān)期刊論文 前1條

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

，

本文編號：1835304