缺失數(shù)據(jù)查詢處理技術(shù)研究.pdf

1、隨著計算機、互聯(lián)網(wǎng)、通信以及定位技術(shù)的快速發(fā)展，數(shù)據(jù)呈爆炸式增長。這些數(shù)據(jù)在形態(tài)上具有海量、高維、多源、異構(gòu)、不確定/不完整等特征，使得當(dāng)前相關(guān)技術(shù)很難支撐人們進行復(fù)雜而多樣的智能處理需求。缺失數(shù)據(jù)具有不確定/不完整特征，并廣泛存在于科學(xué)研究和社會生活的各個領(lǐng)域，如通信、交通和經(jīng)濟等領(lǐng)域。
　　查詢是計算機科學(xué)的基本問題，存在于目前幾乎所有的計算機應(yīng)用領(lǐng)域。如何高效、智能地查詢數(shù)據(jù)，挖掘有價值的信息，服務(wù)于社會，已成為當(dāng)今信息技術(shù)

2、的重大挑戰(zhàn)。然而，現(xiàn)有的查詢處理技術(shù)大多只關(guān)注完整數(shù)據(jù)。由于缺失數(shù)據(jù)的性質(zhì)與完整數(shù)據(jù)的性質(zhì)存在很大差異，因而缺失數(shù)據(jù)查詢不能（直接）有效地采用傳統(tǒng)的完整數(shù)據(jù)查詢處理方法。為此，本文對缺失數(shù)據(jù)查詢處理技術(shù)進行了深入研究，主要包括:
　　1)不完整數(shù)據(jù)查詢:相似查詢在地理信息系統(tǒng)和多媒體檢索等方面有著廣闊的應(yīng)用前景?，F(xiàn)有大多的相似查詢處理方法只針對完整數(shù)據(jù)，但在許多的實際應(yīng)用中，數(shù)據(jù)集中的對象可能存在缺失信息（如數(shù)據(jù)對象的某些屬性值缺

3、失等）;這些對象之間的鄰近關(guān)系就不能用傳統(tǒng)的相似度計算方式衡量，而需要尋找適用于缺失數(shù)據(jù)對象的新穎的鄰近關(guān)系度量方式。本文開發(fā)了兩種有效的不完整數(shù)據(jù)索引方法，并提出了精確和近似的查詢算法，以支持不完整數(shù)據(jù)k最近鄰查詢問題。此外，偏好查詢在決策支持、個性化服務(wù)、以及推薦系統(tǒng)等方面具有重要的應(yīng)用價值。例如，在電影推薦系統(tǒng)中，針對含有缺失信息的電影評分?jǐn)?shù)據(jù)集，系統(tǒng)可以利用Top-k支配查詢選出前k個觀眾評分最好的電影以推薦給電影愛好者。本文提

4、出了面向不完整數(shù)據(jù)Top-k支配查詢的skyband剪枝、上界值剪枝、位圖索引技術(shù)以及壓縮技術(shù)，并設(shè)計了多種有效的查詢算法，以支持不完整數(shù)據(jù)Top-k支配查詢問題。同時，本文分析了位圖索引壓縮技術(shù)對查詢效率和索引空間成本的影響，并進一步探討了查詢效率和索引空間成本的權(quán)衡問題。
　　2)不確定圖查詢:盡管已有許多專家學(xué)者致力于不確定圖查詢處理技術(shù)研究，并取得了大量可喜的研究成果，但距離滿足不斷出現(xiàn)的、復(fù)雜而多樣的查詢需求還有一定的差

5、距，仍待進一步深入研究。例如，不確定圖反k最近鄰查詢在資源優(yōu)化配置、本質(zhì)蛋白質(zhì)識別等場景具有重大的應(yīng)用前景。然而，尚未有學(xué)者對不確定圖反k最近鄰查詢進行研究。所以，本文探討了不確定圖反k最近鄰查詢問題。本文引入了圖規(guī)模剪枝、等價圖剪枝和概率界剪枝以縮小圖規(guī)模、減少可能圖數(shù)量和縮小候選數(shù)據(jù)節(jié)點數(shù)量。本文除了提出精確算法來處理不確定圖反k最近鄰查詢，還給出了一種新穎的抽樣算法。該算法使用了圖規(guī)模剪枝和自適應(yīng)分層抽樣方法。該抽樣方法被證明是無

6、偏的且其方差不比隨機抽樣方法差。與已有算法相比，本文所提出的精確算法效率平均提高了五個數(shù)量級;而且，抽樣算法比精確算法效率至少提高了三個數(shù)量級。
　　3)概率查詢質(zhì)量優(yōu)化:在許多的實際應(yīng)用中，數(shù)據(jù)帶有不確定性，使得基于這些不確定數(shù)據(jù)的查詢（即概率查詢）往往返回一組不確定的查詢結(jié)果。換句話說，概率查詢返回的結(jié)果包含大量噪聲，這使得查詢質(zhì)量下降。為此，本文提出一種新穎的概率查詢質(zhì)量優(yōu)化框架，旨在給定的預(yù)算內(nèi)選擇出一組最影響查詢質(zhì)量的不

7、確定數(shù)據(jù)對象去清洗，以最大化查詢質(zhì)量。本文結(jié)合一個新開發(fā)的ASI結(jié)構(gòu)加速查詢質(zhì)量計算，并利用兩個有效的剪枝策略提出分支界限法、貪心算法和抽樣算法以支持?jǐn)?shù)據(jù)對象選擇問題。ASI結(jié)構(gòu)被證實比未使用該結(jié)構(gòu)的質(zhì)量計算算法性能提升了兩到三個數(shù)量級。
　　4)缺失數(shù)據(jù)查詢處理系統(tǒng):基于上述的研究成果，本文開發(fā)了一個基于不完整數(shù)據(jù)偏好查詢的餐館推薦系統(tǒng)。該系統(tǒng)考慮了餐廳的不完整評級信息，并在PostgreSQL數(shù)據(jù)庫中集成了不完整數(shù)據(jù)skyli