圖的可達(dá)性查詢處理是生物信息領(lǐng)域的熱點(diǎn)問題之一,用于測(cè)定蛋白質(zhì)交互網(wǎng)絡(luò)中任意兩個(gè)蛋白質(zhì)分子間是否存在交互作用.針對(duì)已有在可達(dá)查詢比例增大時(shí)在線搜索算法效率下降明顯及性能不穩(wěn)定的問題,提出優(yōu)化的OPT-R算法.首先,提出最優(yōu)生成樹的概念,使得采用最優(yōu)生成樹的OPT-R算法可以在常量時(shí)間回答更多的可達(dá)查詢;同時(shí)提出基于棧的互逆拓?fù)漤樞?使得OPT-R可以在常量時(shí)間回答更多的不可達(dá)查詢.作者還提出相應(yīng)的最優(yōu)生成樹及互逆拓?fù)漤樞蛏伤惴?并通過實(shí)驗(yàn)對(duì)基于20個(gè)不同規(guī)模的真實(shí)數(shù)據(jù)集從不同角度對(duì)算法的高效性進(jìn)行了驗(yàn)證.

【文章頁數(shù)】：14 頁

【文章目錄】：
1 引言
2 背景知識(shí)和相關(guān)工作
    2.1 背景知識(shí)
    2.2 相關(guān)工作分析
        2.2.1 標(biāo)簽法
        2.2.2 在線搜索法
3 基本思想
    3.1 最優(yōu)生成樹及其性質(zhì)
    3.2 基于棧的互逆拓?fù)漤樞?br>4 算法描述
    4.1 索引構(gòu)建
        4.1.1 求解互逆ST-order
        4.1.2 構(gòu)建最優(yōu)生成樹區(qū)間
        4.1.3 算法分析
    4.2 查詢處理
5 實(shí)驗(yàn)
    5.1 實(shí)驗(yàn)環(huán)境
    5.2 數(shù)據(jù)集
    5.3 性能比較及分析
        5.3.1 查詢時(shí)間
        5.3.2 索引構(gòu)建時(shí)間及索引大小
6 結(jié)論
Background



本文編號(hào)：3826217