不確定數(shù)據(jù)近鄰搜索算法的設(shè)計(jì)與實(shí)現(xiàn).pdf

1、數(shù)據(jù)的不確定性在許多領(lǐng)域中的具體應(yīng)用中普遍存在，不確定數(shù)據(jù)受到越來(lái)越多的關(guān)注。引起數(shù)據(jù)不確定性的原因多種多樣。原始數(shù)據(jù)不準(zhǔn)確或者使用粗粒度集合都會(huì)導(dǎo)致數(shù)據(jù)的不確定性，此外，出于隱私保護(hù)等特殊目的以及處理缺失值都可能成為數(shù)據(jù)不確定性的原因。如何管理好不確定性數(shù)據(jù)成為近年來(lái)數(shù)據(jù)庫(kù)領(lǐng)域中研究的熱點(diǎn)問(wèn)題。
　　不確定數(shù)據(jù)查詢是不確定數(shù)據(jù)管理的重要組成部分。本文研究不確定數(shù)據(jù)近鄰搜索算法，針對(duì)不確定數(shù)據(jù)如何進(jìn)行有效的近鄰查詢，在分析總結(jié)國(guó)內(nèi)

2、外相關(guān)研究的基礎(chǔ)上，提出了不確定數(shù)據(jù)上的組反k近鄰查詢和預(yù)測(cè)近鄰查詢的解決方案。
　　反k近鄰查詢?cè)诨谖恢玫姆?wù)中應(yīng)用廣泛，如智能導(dǎo)航、決策支持等。目前反k近鄰查詢大多針對(duì)單一查詢點(diǎn)進(jìn)行處理。本文把針對(duì)單一查詢點(diǎn)擴(kuò)展到了針對(duì)一組查詢點(diǎn)，提出了概率閾值組反k近鄰查詢算法PT-GRkNN。算法利用R*-tree索引結(jié)構(gòu)，使用過(guò)濾提純框架，逐步縮減查詢搜索空間，降低計(jì)算開(kāi)銷(xiāo)。實(shí)驗(yàn)表明，PT-GRkNN算法可以有效地過(guò)濾非結(jié)果集對(duì)象，提

3、高查詢結(jié)果的精確度。
　　時(shí)空數(shù)據(jù)上的預(yù)測(cè)近鄰查詢?cè)谠S多基于位置的服務(wù)中受到重視。由于像RFID、傳感器以及GPS等數(shù)據(jù)采集設(shè)備不夠精準(zhǔn)等原因的限制，數(shù)據(jù)只能在離散的時(shí)間點(diǎn)被采集。在這些離散的時(shí)間實(shí)例之間，被追蹤的移動(dòng)對(duì)象的位置是不確定的。本文利用過(guò)濾提純框架來(lái)解決不確定時(shí)空數(shù)據(jù)上的預(yù)測(cè)最近鄰查詢。在過(guò)濾階段，利用半馬爾科夫過(guò)程模型來(lái)描述對(duì)象在空間網(wǎng)格之間的移動(dòng)，過(guò)濾掉零概率成為查詢結(jié)果的對(duì)象。在提純階段使用馬爾科夫鏈模型來(lái)描述不