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

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

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

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

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

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

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

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