本文是一篇計(jì)算機(jī)碩士論文，本文研究了時(shí)態(tài)圖上的最短環(huán)計(jì)數(shù)問(wèn)題，主要解決如何在給定時(shí)間區(qū)間內(nèi)，快速、高效地查詢以給定頂點(diǎn)為核心的最短環(huán)長(zhǎng)度及其計(jì)數(shù)。

3.時(shí)態(tài)圖上最短環(huán)計(jì)數(shù)在線查詢算法...............................19

3.1問(wèn)題動(dòng)機(jī)與分析.......................................19

3.2在線算法.............................21

4.基于SCPI索引的時(shí)態(tài)圖上最短環(huán)計(jì)數(shù)查詢算法...........................24

4.1問(wèn)題分析.......................................24

4.2 SCPI索引..................................25

5.基于ATI索引的時(shí)態(tài)圖中最短環(huán)計(jì)數(shù)查詢算法.........................36

5.1問(wèn)題分析.....................................................36

5.2 ATI索引............................................36

6.實(shí)驗(yàn)結(jié)果與分析

6.1環(huán)境配置

本文所有實(shí)驗(yàn)均在一臺(tái)搭載Intel Xeon Gold 5218R處理器的Linux服務(wù)器上完成。該服務(wù)器配備1TB內(nèi)存，操作系統(tǒng)為64位Ubuntu 20.04.6 LTS。所有算法均采用C++編程語(yǔ)言實(shí)現(xiàn)，并使用g++編譯器進(jìn)行編譯。

7.結(jié)論與展望

7.1研究結(jié)論

本文研究了時(shí)態(tài)圖上的最短環(huán)計(jì)數(shù)問(wèn)題，主要解決如何在給定時(shí)間區(qū)間內(nèi)，快速、高效地查詢以給定頂點(diǎn)為核心的最短環(huán)長(zhǎng)度及其計(jì)數(shù)。本文工作的主要貢獻(xiàn)如下：

（1）結(jié)合時(shí)間窗口設(shè)定，明確定義了查詢輸入、結(jié)果要求及約束條件，提出了一種基于樸素BFS思想的在線查詢算法，該方法可以適用于任意時(shí)間區(qū)間與任意頂點(diǎn)的即時(shí)查詢場(chǎng)景。

（2）為了提升在線查詢算法的查詢性能，提出了基于索引的高效查詢算法的解決方案。此方案分為兩種索引支持的查詢框架——SCPI索引與ATI索引。SCPI索引維護(hù)了圖中每個(gè)頂點(diǎn)所有最短環(huán)長(zhǎng)度及其計(jì)數(shù)發(fā)生的有效時(shí)間區(qū)間，查詢效率極高；而ATI索引只維護(hù)了圖中每個(gè)頂點(diǎn)無(wú)環(huán)狀態(tài)的有效時(shí)間區(qū)間，能夠有效剪枝無(wú)效路徑，從而減小了搜索空間，加速了最短環(huán)計(jì)數(shù)的查詢。相較在線查詢算法，SCPI索引適用于中小規(guī)模圖，查詢效率最好可快4個(gè)數(shù)量級(jí)；ATI索引在大規(guī)模數(shù)據(jù)集上表現(xiàn)優(yōu)越，查詢效率較在線方法提升了3個(gè)數(shù)量級(jí)。

（3）提出了一種針對(duì)ATI索引的優(yōu)化構(gòu)建算法，利用無(wú)環(huán)時(shí)間的單調(diào)性，采用局部更新策略維護(hù)無(wú)環(huán)時(shí)間信息，從而避免冗余計(jì)算，提高索引構(gòu)建效率。實(shí)驗(yàn)結(jié)果表明，優(yōu)化算法能夠高效地完成ATI索引構(gòu)建，并且在大規(guī)模時(shí)態(tài)圖上的構(gòu)建效率相較于基礎(chǔ)構(gòu)建算法提升了3個(gè)數(shù)量級(jí)，顯著縮短了索引構(gòu)建時(shí)間。

參考文獻(xiàn)（略）