基于圖數(shù)據(jù)的關(guān)鍵字覆蓋集合問題研究.pdf

1、集合覆蓋問題是圖數(shù)據(jù)管理中的熱點問題之一，可以應(yīng)用到現(xiàn)實生活中的很多領(lǐng)域，包括網(wǎng)絡(luò)安全、資源分配、電路設(shè)計、運輸車輛等等。具有影響力的關(guān)鍵字的覆蓋集合技術(shù)可以用來查詢社交網(wǎng)絡(luò)中的特殊用戶，也可以用于互聯(lián)網(wǎng)中消息的發(fā)布等。本文從以下幾個方面對基于圖數(shù)據(jù)的關(guān)鍵字集合覆蓋處理方法進行研究，具體研究內(nèi)容如下。
　　首先，通過對現(xiàn)有算法進行分析，發(fā)現(xiàn)現(xiàn)有的算法中存在的一些不足，要么低效、要么結(jié)果的準(zhǔn)確性不能保證，針對現(xiàn)有問題，提出一種基于離

2、線索引的PICS-IN算法，該算法采用了建立離線索引的方法，對于給定的需要覆蓋的屬性集合中的每個屬性，在節(jié)點集合中找到能夠包含這些屬性的關(guān)鍵字，并建立屬性的倒排索引，避免了每次查找能夠覆蓋這些屬性的節(jié)點時，都要遍歷數(shù)據(jù)集中的節(jié)點集合的不足。其優(yōu)點體現(xiàn)在通過建立屬性和關(guān)鍵字的離線索引，減少了查找符合條件的關(guān)鍵字的時間，也保證了結(jié)果的準(zhǔn)確性。
　　其次，為了使本文提出的算法更高效，提出了高效的過濾劃分組的剪枝策略，并設(shè)計了相應(yīng)的PS-