本文是一篇計算機碩士論文,本文研究了時態(tài)圖上的最短環(huán)計數(shù)問題,主要解決如何在給定時間區(qū)間內(nèi),快速、高效地查詢以給定頂點為核心的最短環(huán)長度及其計數(shù)。
3.時態(tài)圖上最短環(huán)計數(shù)在線查詢算法...............................19
3.1問題動機與分析.......................................19
3.2在線算法.............................21
4.基于SCPI索引的時態(tài)圖上最短環(huán)計數(shù)查詢算法...........................24
4.1問題分析.......................................24
4.2 SCPI索引..................................25
5.基于ATI索引的時態(tài)圖中最短環(huán)計數(shù)查詢算法.........................36
5.1問題分析.....................................................36
5.2 ATI索引............................................36
6.實驗結(jié)果與分析
6.1環(huán)境配置
本文所有實驗均在一臺搭載Intel Xeon Gold 5218R處理器的Linux服務器上完成。該服務器配備1TB內(nèi)存,操作系統(tǒng)為64位Ubuntu 20.04.6 LTS。所有算法均采用C++編程語言實現(xiàn),并使用g++編譯器進行編譯。

7.結(jié)論與展望
7.1研究結(jié)論
本文研究了時態(tài)圖上的最短環(huán)計數(shù)問題,主要解決如何在給定時間區(qū)間內(nèi),快速、高效地查詢以給定頂點為核心的最短環(huán)長度及其計數(shù)。本文工作的主要貢獻如下:
(1)結(jié)合時間窗口設定,明確定義了查詢輸入、結(jié)果要求及約束條件,提出了一種基于樸素BFS思想的在線查詢算法,該方法可以適用于任意時間區(qū)間與任意頂點的即時查詢場景。
(2)為了提升在線查詢算法的查詢性能,提出了基于索引的高效查詢算法的解決方案。此方案分為兩種索引支持的查詢框架——SCPI索引與ATI索引。SCPI索引維護了圖中每個頂點所有最短環(huán)長度及其計數(shù)發(fā)生的有效時間區(qū)間,查詢效率極高;而ATI索引只維護了圖中每個頂點無環(huán)狀態(tài)的有效時間區(qū)間,能夠有效剪枝無效路徑,從而減小了搜索空間,加速了最短環(huán)計數(shù)的查詢。相較在線查詢算法,SCPI索引適用于中小規(guī)模圖,查詢效率最好可快4個數(shù)量級;ATI索引在大規(guī)模數(shù)據(jù)集上表現(xiàn)優(yōu)越,查詢效率較在線方法提升了3個數(shù)量級。
(3)提出了一種針對ATI索引的優(yōu)化構(gòu)建算法,利用無環(huán)時間的單調(diào)性,采用局部更新策略維護無環(huán)時間信息,從而避免冗余計算,提高索引構(gòu)建效率。實驗結(jié)果表明,優(yōu)化算法能夠高效地完成ATI索引構(gòu)建,并且在大規(guī)模時態(tài)圖上的構(gòu)建效率相較于基礎構(gòu)建算法提升了3個數(shù)量級,顯著縮短了索引構(gòu)建時間。
參考文獻(略)
相關(guān)文章
UKthesis provides an online writing service for all types of academic writing. Check out some of them and don't hesitate to place your order.