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

【摘要】：可達(dá)查詢作為圖查詢中一類基本查詢,在眾多領(lǐng)域得到廣泛應(yīng)用.研究發(fā)現(xiàn),圖規(guī)模的不斷增長導(dǎo)致傳統(tǒng)單機(jī)環(huán)境下的查詢算法已無法滿足大規(guī)模圖的查詢需求.為此,提出一種折疊樹編碼索引的大規(guī)模圖可達(dá)查詢方法,該方法由離線預(yù)處理和在線查詢兩階段構(gòu)成.預(yù)處理階段,提出一種折疊樹編碼索引方法 FTCI,該方法建立了基于B+樹的標(biāo)記機(jī)制對分割子圖進(jìn)行標(biāo)記,并通過標(biāo)記子圖上的折疊樹創(chuàng)建及相應(yīng)類哈夫曼編碼,良好地保存了子圖內(nèi)部及子圖間的可達(dá)信息;在線查詢階段,采用分布式技術(shù),設(shè)計(jì)了基于FTCI的可達(dá)查詢方法,根據(jù)查詢節(jié)點(diǎn)隸屬子圖情況,給出子圖內(nèi)、子圖間查詢策略.實(shí)驗(yàn)證明提出的方法在保證高效查詢的同時(shí)降低了索引的存儲開銷,提高了可達(dá)查詢的處理效率.
[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.
【作者單位】： 遼寧大學(xué)信息學(xué)院;
【基金】：國家自然科學(xué)基金項(xiàng)目(61472169,61502215)資助 遼寧省教育廳一般項(xiàng)目(L2015193)資助 遼寧省博士科研啟動(dòng)基金項(xiàng)目(201501127)資助 遼寧大學(xué)青年科研基金項(xiàng)目(LDQN201438)資助
【分類號】：O157.5

【相似文獻(xiàn)】

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

1 王防修;;LZW碼的改進(jìn)算法[J];武漢工業(yè)學(xué)院學(xué)報(bào);2009年02期

，

本文編號：1835304