【摘要】：隨著科學(xué)技術(shù)的飛速發(fā)展以及計(jì)算機(jī)的普及,產(chǎn)生了海量的數(shù)據(jù)。在網(wǎng)絡(luò)、數(shù)學(xué)、生物、化學(xué)等領(lǐng)域,數(shù)據(jù)起著至關(guān)重要的作用。圖是一種通用且具有廣泛研究?jī)r(jià)值的數(shù)據(jù)結(jié)構(gòu),作為一種最直觀的表達(dá)方式,越來越多的應(yīng)用依賴于圖數(shù)據(jù)進(jìn)行表示。圖數(shù)據(jù)的應(yīng)用變得越來越廣泛,其規(guī)模迅速增大,同時(shí)數(shù)據(jù)也變得更加多樣化和復(fù)雜化,如何從海量的圖數(shù)據(jù)中挖掘有效的信息成為研究的核心問題。近年來,我們可以發(fā)現(xiàn)在圖數(shù)據(jù)庫(kù)中存在噪音以及錯(cuò)誤的圖越來越多,因此學(xué)術(shù)界愈加關(guān)注如何在圖數(shù)據(jù)庫(kù)中進(jìn)行相似性搜索,從而得到隱藏的信息。圖相似性搜索對(duì)于深入研究圖數(shù)據(jù)庫(kù)起著強(qiáng)烈的推進(jìn)作用。圖編輯距離是一種用來確定圖相似性最有效的措施,在模式識(shí)別、計(jì)算機(jī)視覺、生物信息等領(lǐng)域有著非常廣泛的應(yīng)用。圖編輯距離作為一種度量?jī)蓚�(gè)圖之間相似性的有效方法,是不精確圖匹配的基礎(chǔ)。不精確的圖匹配已經(jīng)成為模式分析領(lǐng)域的重要研究焦點(diǎn)之一,在現(xiàn)實(shí)生活中無處不在。當(dāng)前已經(jīng)驗(yàn)證了圖編輯距離計(jì)算是一個(gè)NP問題,在通常情況下,圖編輯距離計(jì)算在多項(xiàng)式時(shí)間內(nèi)無法解決,計(jì)算起來十分復(fù)雜,浪費(fèi)了大量的時(shí)間,效率低下,所以如何避免過多的圖編輯距離計(jì)算成為了亟待解決的問題。為此,學(xué)術(shù)界提出了計(jì)算圖編輯距離邊界的算法,以此來提高計(jì)算效率。圖編輯距離邊界算法雖然可以減少計(jì)算量,提高效率,但仍有優(yōu)化的空間。本文的主要內(nèi)容如下:(1)簡(jiǎn)單介紹了幾種與圖編輯距離相關(guān)的算法及各自存在的優(yōu)缺點(diǎn)。(2)結(jié)合現(xiàn)有的圖編輯距離邊界過濾算法,提出了兩種新的方法,分別針對(duì)兩種不同的情況,對(duì)圖編輯距離邊界過濾算法進(jìn)行優(yōu)化,從而進(jìn)一步減少計(jì)算所消耗的時(shí)間。(3)建立概率索引圖,利用概率索引圖找到更好的中介圖,進(jìn)而提出快速收斂方法來解決圖相似性問題,進(jìn)一步減少不必要的圖編輯距離計(jì)算,達(dá)到提高效率的目的。(4)最后驗(yàn)證本文提出的方法,通過在真實(shí)數(shù)據(jù)集與人工數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)研究,從各個(gè)方面綜合分析新方法。結(jié)果表明,這些方法具有良好的性能,同時(shí)通過實(shí)驗(yàn)結(jié)果也證實(shí)了使用我們提出的新方法來進(jìn)行圖相似性搜索的有效性和可行性。
[Abstract]:With the rapid development of science and technology and the popularization of computer, massive data are produced. Data play an important role in the fields of network, mathematics, biology, chemistry and so on. As a kind of intuitionistic expression, graph is a kind of universal data structure with extensive research value. More and more applications depend on graph data for representation. The application of graph data becomes more and more extensive, its scale increases rapidly, at the same time, the data becomes more diversified and more complicated. How to mine the effective information from the massive graph data becomes the core problem of the research. In recent years, we can find that there are more and more noise and errors in the graph database, so the academic circles pay more attention to how to search the similarity in the graph database to get hidden information. Graph similarity search plays an important role in the further study of graph database. Graph editing distance is the most effective measure to determine the similarity of graphs. It is widely used in pattern recognition, computer vision, biological information and other fields. As an effective method to measure the similarity between two graphs, graph editing distance is the basis of inexact graph matching. Imprecise graph matching has become an important research focus in the field of pattern analysis and is ubiquitous in real life. At present, it has been proved that the calculation of graph edit distance is a NP problem. In general, the calculation of graph edit distance can not be solved in polynomial time. The calculation is very complicated, and it wastes a lot of time and is inefficient. Therefore, how to avoid too much graph editing distance calculation has become an urgent problem. In order to improve the computational efficiency, an algorithm for calculating the distance boundary of graph editing is proposed in this paper. Although graph editing distance boundary algorithm can reduce computation cost and improve efficiency, there is still room for optimization. The main contents of this paper are as follows: (1) several algorithms related to graph editing distance and their advantages and disadvantages are briefly introduced. (2) two new methods are proposed in combination with the existing edge filtering algorithms for graph editing distance. For two different cases, the edge filtering algorithm of graph editing distance is optimized to further reduce the computation time. (3) the probabilistic index graph is built and the better intermediary graph is found by using probabilistic index graph. Furthermore, a fast convergence method is proposed to solve the problem of graph similarity, further reduce the calculation of unnecessary graph editing distance, and achieve the purpose of improving efficiency. (4) finally, the method proposed in this paper is verified. Through the experimental research on real data set and artificial data set, the new method is analyzed synthetically from all aspects. The results show that these methods have good performance, and the effectiveness and feasibility of using the new method to search the similarity of graphs are also verified by the experimental results.
【學(xué)位授予單位】：遼寧大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：O157.5

【參考文獻(xiàn)】

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

1 胡敏;程天梅;王曉華;;融合全局和局部特征的人臉識(shí)別[J];電子測(cè)量與儀器學(xué)報(bào);2013年09期

2 曹斌;尹建偉;陳慧蕊;;基于Levenshtein距離的流程檢索方法[J];計(jì)算機(jī)集成制造系統(tǒng);2012年08期

3 劉華清;陳振東;涂剛;;數(shù)據(jù)庫(kù)索引與優(yōu)化[J];現(xiàn)代計(jì)算機(jī)(專業(yè)版);2012年18期

4 李路;周良;丁秋林;;基于貝葉斯網(wǎng)絡(luò)的草圖符號(hào)識(shí)別研究[J];計(jì)算機(jī)科學(xué);2011年06期

5 袁堯;張玉成;董雯霞;鄭如松;楊育波;石晶林;;基于二分圖匹配的多業(yè)務(wù)流網(wǎng)絡(luò)選擇機(jī)制[J];軟件學(xué)報(bào);2010年06期

6 肖冰;李潔;高新波;;一種度量圖像相似性和計(jì)算圖編輯距離的新方法[J];電子學(xué)報(bào);2009年10期

7 師軍,曹菡;啟發(fā)式搜索問題研究[J];微型機(jī)與應(yīng)用;2004年10期

，

本文編號(hào)：2400669