不確定數(shù)據(jù)的世系管理和相似性查詢.pdf

1、不確定性數(shù)據(jù)在很多應(yīng)用中廣泛出現(xiàn),例如經(jīng)濟(jì)、軍事、物流、金融、電信等,其表現(xiàn)形式多種多樣,包括關(guān)系型數(shù)據(jù)、半結(jié)構(gòu)化數(shù)據(jù)、圖數(shù)據(jù)、流數(shù)據(jù)、移動(dòng)對(duì)象數(shù)據(jù)以及無結(jié)構(gòu)化的Web數(shù)據(jù)等。目前,根據(jù)應(yīng)用的特點(diǎn)與數(shù)據(jù)形式的多樣性,已經(jīng)出現(xiàn)了多種不確定數(shù)據(jù)模型,這些模型的核心思想都源自可能世界模型。該模型從一個(gè)不確定的數(shù)據(jù)源演化出諸多確定性的可能世界實(shí)例,所有實(shí)例的概率之和等于1。盡管可以針對(duì)各個(gè)實(shí)例單獨(dú)進(jìn)行查詢處理,合并中間結(jié)果并獲取最終結(jié)果,但是可

2、能世界實(shí)例的數(shù)量遠(yuǎn)大于不確定數(shù)據(jù)庫(kù)的規(guī)模,從而導(dǎo)致可能世界模型在實(shí)踐應(yīng)用中并不可行。因此必須采用排序、剪枝等啟發(fā)式技術(shù)進(jìn)行優(yōu)化處理以提高查詢處理效率。
　　針對(duì)不確定數(shù)據(jù)管理的挑戰(zhàn),本文主要考察不確定數(shù)據(jù)查詢處理的優(yōu)化。主要工作分為兩部分:不確定數(shù)據(jù)世系管理和相似性查詢。具體的,針對(duì)數(shù)據(jù)的不確定性,研究如何通過不確定數(shù)據(jù)的世系追蹤數(shù)據(jù)不確定性的來源和大小,以及對(duì)不確定性集合數(shù)據(jù)進(jìn)行相似度評(píng)價(jià),最后提出了不確定數(shù)據(jù)流上ER-topk

3、查詢的精確算法。本文的主要貢獻(xiàn)如下:
　　·首先研究了如何利用數(shù)據(jù)世系追蹤數(shù)據(jù)不確定性的來源和大小?；赑HP-tree數(shù)據(jù)結(jié)構(gòu),近似描述不確定數(shù)據(jù)的How世系,避免了追蹤數(shù)據(jù)演化的中間結(jié)果,同時(shí)也避免了運(yùn)用可能世界模型對(duì)不確定性數(shù)據(jù)進(jìn)行建模;基于PHP-tree,可以追蹤目標(biāo)數(shù)據(jù)的不確定性來源,以及對(duì)目標(biāo)數(shù)據(jù)的不確定性大小進(jìn)行評(píng)價(jià)。
　　·針對(duì)不確定集合,定義了不確定性集合的期望相似度算子,提出了不確定集合期望相似度的精確

4、和近似算法。具體的,運(yùn)用動(dòng)態(tài)規(guī)劃方法在多項(xiàng)式時(shí)間內(nèi)給出不確定集合期望相似度的精確算法,而不必?cái)U(kuò)展可能世界實(shí)例;考慮到精確算法需要耗費(fèi)大量的時(shí)間和空間,為克服可擴(kuò)展性差的缺點(diǎn),我們運(yùn)用Monte-Carlo方法在線性時(shí)間內(nèi)近似計(jì)算不確定集合的期望相似度。
　　·考慮到不確定集合相似度的多樣性,又評(píng)價(jià)了不確定性集合的概率閾值相似度。給出了不確定集合的概率閾值相似度算子的定義,以及精確和近似算法。運(yùn)用動(dòng)態(tài)規(guī)劃方法在多項(xiàng)式時(shí)間內(nèi)給出不確定

5、集合概率閾值相似度的精確計(jì)算過程;同時(shí)考慮到概率閾值相似度的計(jì)算結(jié)果是一個(gè)概率值,當(dāng)用戶給定相似度的閾值,利用尾概率不等式提出了一個(gè)線性時(shí)間內(nèi)的剪枝規(guī)則,大大加快了精確解的計(jì)算過程;考慮到?jīng)]有被剪枝的不確定集合的精確算法需要耗費(fèi)大量的時(shí)間和空間,我們運(yùn)用Monte-Carlo方法近似計(jì)算不確定集合的概率閾值相似度。
　　·基于界標(biāo)模型提出了不確定數(shù)據(jù)流響應(yīng)ER-topk查詢的精確算法,該方案將所有不斷到來的元組分成兩組,一組包含E