本文是一篇計算機碩士論文，本文研究了時態(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)建時間。

參考文獻（略）