Top-k中心度查詢算法研究
本文關(guān)鍵詞:Top-k中心度查詢算法研究
更多相關(guān)文章: 中心度 拓?fù)渑判?/b> 擴(kuò)展順序 廣度優(yōu)先遍歷
【摘要】:如何快速地找出中心度最高的k個(gè)點(diǎn)是有關(guān)圖模型研究的熱點(diǎn)問題之一,在現(xiàn)實(shí)生活中有著廣泛的應(yīng)用,比如超市選址、城市規(guī)劃、熱點(diǎn)新聞報(bào)道、數(shù)據(jù)挖掘以及病毒營(yíng)銷策略等。通過對(duì)現(xiàn)有方法進(jìn)行分析,發(fā)現(xiàn)現(xiàn)有方法的低效性主要是由于頂點(diǎn)處理順序的代價(jià)過高和處理頂點(diǎn)數(shù)量過多造成的。本文針對(duì)現(xiàn)有中心度計(jì)算方法效率低的問題展開研究,具體內(nèi)容如下。首先,針對(duì)頂點(diǎn)處理順序的代價(jià)過高提出一種基于拓?fù)渑判虻膖op-k中心度查詢算法。該算法采用拓?fù)漤樞蛱娲延蟹椒ǖ捻旤c(diǎn)處理順序,減少已有方法求解頂點(diǎn)處理順序所帶來的昂貴的時(shí)間代價(jià)。其優(yōu)點(diǎn)是簡(jiǎn)單、高效,但是應(yīng)用具有一定的局限性,對(duì)于結(jié)構(gòu)比較復(fù)雜的圖計(jì)算代價(jià)會(huì)很高。其次,針對(duì)處理頂點(diǎn)數(shù)量過多的問題,提出基于估算篩選的中心度查詢算法。該算法通過一次廣度優(yōu)先遍歷估算出每個(gè)點(diǎn)中心度的上界值,通過上界值的大小確定頂點(diǎn)的處理順序。在計(jì)算過程中,通過維護(hù)top-k中心度的真實(shí)值,可以有效地過濾掉無需計(jì)算中心度真實(shí)值的點(diǎn),使候選集需要計(jì)算真實(shí)中心度值的點(diǎn)變少,從而減少計(jì)算代價(jià),提高了算法性能。最后,在不同類型特征和規(guī)模大小的圖上進(jìn)行實(shí)驗(yàn)對(duì)比分析,從時(shí)間消耗、k值變化等方面對(duì)本文方法的高效性進(jìn)行了驗(yàn)證。
【關(guān)鍵詞】:中心度 拓?fù)渑判?/strong> 擴(kuò)展順序 廣度優(yōu)先遍歷
【學(xué)位授予單位】:燕山大學(xué)
【學(xué)位級(jí)別】:碩士
【學(xué)位授予年份】:2016
【分類號(hào)】:TP301.6
【目錄】:
- 摘要5-6
- Abstract6-9
- 第1章 緒論9-14
- 1.1 研究背景9-10
- 1.2 研究現(xiàn)狀10-12
- 1.3 研究?jī)?nèi)容12
- 1.4 本文結(jié)構(gòu)12-14
- 第2章 基礎(chǔ)知識(shí)概述14-22
- 2.1 基本概念14-15
- 2.2 問題定義15-16
- 2.3 基本算法16-20
- 2.3.1 拓?fù)渑判蛩惴?/span>16-18
- 2.3.2 求top-k問題的堆排序算法18-20
- 2.4 本章小結(jié)20-22
- 第3章 基于拓?fù)渑判虻闹行亩炔樵兯惴?/span>22-32
- 3.1 問題分析22-27
- 3.2 基于拓?fù)渑判虻乃惴ㄋ枷?/span>27-28
- 3.3 基于拓?fù)渑判蚍ǖ牟樵冞^程28-30
- 3.4 算法分析30-31
- 3.5 本章小結(jié)31-32
- 第4章 基于估算篩選的中心度查詢算法32-44
- 4.1 問題分析32-33
- 4.2 基于估算篩選的算法思想33-34
- 4.3 基于估算篩選法的查詢過程34-41
- 4.4 算法分析41-42
- 4.5 本章小結(jié)42-44
- 第5章 實(shí)驗(yàn)44-54
- 5.1 實(shí)驗(yàn)環(huán)境44
- 5.2 數(shù)據(jù)集和評(píng)價(jià)標(biāo)準(zhǔn)44-45
- 5.3 性能比較與分析45-52
- 5.3.1 不同類型的圖45-48
- 5.3.2 查詢時(shí)間的消耗48-50
- 5.3.3 k值的選取50-52
- 5.4 本章小結(jié)52-54
- 結(jié)論54-55
- 參考文獻(xiàn)55-59
- 攻讀碩士學(xué)位期間承擔(dān)的科研任務(wù)與主要成果59-60
- 致謝60
【相似文獻(xiàn)】
中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條
1 張麗紅;;查詢算法的優(yōu)化設(shè)計(jì)[J];職大學(xué)報(bào);2009年02期
2 陳富強(qiáng);奚建清;;商覆蓋立方體中下掘與上卷操作的查詢算法設(shè)計(jì)[J];信息技術(shù);2011年04期
3 李英女,鄭國(guó)雄;鐵路客運(yùn)信息查詢算法[J];鐵路計(jì)算機(jī)應(yīng)用;2000年02期
4 徐紅波;郝忠孝;;一種基于Z曲線近似k-最近對(duì)查詢算法[J];計(jì)算機(jī)研究與發(fā)展;2008年02期
5 劉平;陳旭燦;李思昆;;嵌入式空間數(shù)據(jù)庫(kù)綜合查詢算法[J];計(jì)算機(jī)工程;2008年17期
6 趙智慧;;基于對(duì)象方向方位的連續(xù)方向查詢算法[J];齊齊哈爾大學(xué)學(xué)報(bào)(自然科學(xué)版);2010年04期
7 徐紅波;韓啟龍;潘海為;;空間數(shù)據(jù)庫(kù)最優(yōu)位置查詢算法研究[J];計(jì)算機(jī)工程與應(yīng)用;2011年18期
8 杜左強(qiáng);基于對(duì)象的空間數(shù)據(jù)庫(kù)的方位查詢算法[J];信息技術(shù);2004年07期
9 徐紅波;郝忠孝;;一種采用Z曲線高維空間范圍查詢算法[J];小型微型計(jì)算機(jī)系統(tǒng);2009年10期
10 高靜波,李新友,唐澤圣,周曉輝;半動(dòng)態(tài)矩形交查詢算法[J];軟件學(xué)報(bào);1997年08期
中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前10條
1 洪潤(rùn)秋;金文;陳鋼;王能斌;;迭代查詢子查詢算法的研究[A];第十一屆全國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集[C];1993年
2 常珂;劉辰;楊正球;;基于樹狀結(jié)構(gòu)的查詢算法的設(shè)計(jì)與實(shí)現(xiàn)[A];中國(guó)通信學(xué)會(huì)第六屆學(xué)術(shù)年會(huì)論文集(中)[C];2009年
3 孫煥良;劉江秀;許景科;;基于楔的時(shí)間序列流雙向封裝過濾查詢算法[A];第二十五屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集(二)[C];2008年
4 李江波;周強(qiáng);陳祖舜;;漢語(yǔ)詞典快速查詢算法研究[A];第二屆全國(guó)學(xué)生計(jì)算語(yǔ)言學(xué)研討會(huì)論文集[C];2004年
5 董科;王國(guó)仁;寧博;毛克明;趙相國(guó);;基于壓縮葉子流的XML Twig查詢[A];第二十三屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集(研究報(bào)告篇)[C];2006年
6 劉旭輝;馮建華;洪親;;一種支持更新的圖可達(dá)性查詢算法[A];第二十四屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集(技術(shù)報(bào)告篇)[C];2007年
7 劉怡;郝云飛;;一種有效的復(fù)調(diào)音樂查詢算法[A];第三屆和諧人機(jī)環(huán)境聯(lián)合學(xué)術(shù)會(huì)議(HHME2007)論文集[C];2007年
8 黃海;侯穎;朱圣平;;一種多維向量并行查詢算法[A];2010年全國(guó)開放式分布與并行計(jì)算機(jī)學(xué)術(shù)會(huì)議論文集[C];2010年
9 徐忠華;張剡;陳玲;柏文陽(yáng);;基于星型模型的輪廓連接查詢算法[A];第26屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集(A輯)[C];2009年
10 陳冬霞;吉根林;武志峰;;一種基于簽名的XML查詢算法[A];第二十一屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集(技術(shù)報(bào)告篇)[C];2004年
中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前7條
1 徐紅波;基于空間填充曲線高維空間查詢算法研究[D];哈爾濱理工大學(xué);2010年
2 劉潤(rùn)濤;基于序的空間數(shù)據(jù)索引及查詢算法研究[D];哈爾濱理工大學(xué);2009年
3 季長(zhǎng)清;云計(jì)算環(huán)境下的大規(guī)模空間近鄰查詢算法研究[D];大連海事大學(xué);2014年
4 鄒磊;圖數(shù)據(jù)庫(kù)中的子圖查詢算法研究[D];華中科技大學(xué);2009年
5 謝鯤;布魯姆過濾器查詢算法及其應(yīng)用研究[D];湖南大學(xué);2007年
6 劉艷;基于主存的高維空間連接及查詢算法研究[D];哈爾濱理工大學(xué);2011年
7 田小梅;多布魯姆過濾器查詢算法及其應(yīng)用研究[D];湖南大學(xué);2013年
中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條
1 黃海龍;大規(guī)模圖的圖查詢算法研究[D];燕山大學(xué);2015年
2 李青;分布式計(jì)算環(huán)境下海量RDF數(shù)據(jù)的skyline查詢研究[D];鄭州大學(xué);2015年
3 鄧育;空間近似關(guān)鍵字反遠(yuǎn)鄰查詢方法研究[D];安徽工業(yè)大學(xué);2015年
4 于世龍;信息物理融合系統(tǒng)資源索引與查詢技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2013年
5 郭巖;實(shí)時(shí)數(shù)據(jù)流相似性查詢算法的研究[D];華北電力大學(xué);2015年
6 鐘麗娟;時(shí)間序列數(shù)據(jù)相似性與聚合top-k查詢算法研究與應(yīng)用[D];浙江大學(xué);2016年
7 李海莉;面向高速骨干網(wǎng)的網(wǎng)絡(luò)流量測(cè)量關(guān)鍵技術(shù)研究[D];解放軍信息工程大學(xué);2014年
8 孟凡帥;基于HDFS的時(shí)空數(shù)據(jù)共享與查詢隱私保護(hù)的研究與實(shí)現(xiàn)[D];東北大學(xué);2014年
9 劉增蘭;同構(gòu)發(fā)布/訂閱系統(tǒng)的系統(tǒng)最優(yōu)化與并行查詢算法的研究與實(shí)現(xiàn)[D];東北大學(xué);2014年
10 葉向東;面向web規(guī)模RDF數(shù)據(jù)查詢算法的研究與實(shí)現(xiàn)[D];東北大學(xué);2014年
,本文編號(hào):698041
本文鏈接:http://sikaile.net/guanlilunwen/yingxiaoguanlilunwen/698041.html