圖索引技術(shù)新方法.pdf

1、隨著結(jié)構(gòu)化數(shù)據(jù)在互聯(lián)網(wǎng)應(yīng)用中的大量出現(xiàn)，對復(fù)雜數(shù)據(jù)進(jìn)行圖建模在近年來越來越流行。圖索引問題在圖數(shù)據(jù)庫應(yīng)用中至關(guān)重要。本文主要研究了圖數(shù)據(jù)庫上的圖索引問題。
　　本文提出了MSTA索引方法及MSTA索引方法上的子圖查詢算法、超圖查詢算法、相似性查詢算法和相關(guān)性查詢算法。MSTA索引方法利用最小生成樹作為數(shù)據(jù)特征，將所有的最小生成樹依據(jù)邊序列的包含關(guān)系和最大公共子圖距離度量組織成MST樹索引結(jié)構(gòu)，高效的支持各種查詢算法。傳統(tǒng)索引方法的

2、索引大小和索引建立時間是MSTA索引方法的數(shù)十倍，甚至上百倍。MSTA索引方法上的查詢算法都是近似的，返回的結(jié)果是最好的部分結(jié)果。我們還分析了MSTA索引方法的原理和正確性。實驗結(jié)果輔證了該索引方法的高效索引性能及查詢性能。
　　本文提出了RQ索引方法及RQ索引方法上的相關(guān)性查詢算法。我們分析了相關(guān)性查詢算法的代價組成，從而得出代價影響的兩個結(jié)論；分析了已有索引方法在支持相關(guān)性查詢上的不足。RQ索引方法，利用四種不同維度選擇策略得