基于概率圖的概率反向近鄰查詢研究.pdf

1、空間數(shù)據(jù)查詢處理技術(shù)是數(shù)據(jù)管理的關(guān)鍵技術(shù),一直受到學(xué)術(shù)界和工業(yè)界的大量關(guān)注。作為空間數(shù)據(jù)的一類重要查詢,反向最近鄰查詢(RNN)及其變種在決策支持、資源分配等重要領(lǐng)域擁有廣泛的應(yīng)用場(chǎng)景。
　　 已有的反向最近鄰查詢工作主要集中于基于歐氏空間或確定圖模型的RNN查詢,而并沒有關(guān)注概率圖模型的RNN查詢。然而,在許多現(xiàn)實(shí)應(yīng)用場(chǎng)景中,由于設(shè)備誤差、道路擁堵狀況、網(wǎng)絡(luò)延時(shí)等因素造成圖模型中的數(shù)據(jù)具有不確定性。通常,這些場(chǎng)景可以采用邊權(quán)重

2、不確定的概率圖進(jìn)行建模。本文主要研究基于概率圖的概率反向近鄰查詢(PRNN):給定一個(gè)查詢點(diǎn)q和一個(gè)概率閾值τ,PRNN查詢返回以查詢點(diǎn)作為概率最近鄰(PNN)的所有數(shù)據(jù)點(diǎn)。實(shí)現(xiàn)基于概率圖的概率反向近鄰查詢具有極大的技術(shù)挑戰(zhàn),其原因在于(1)概率圖模型中的距離度量方式不同于歐式空間以及確定圖模型中的距離度量方式;(2)不同于確定圖模型,概率圖中的路徑不滿足最優(yōu)子結(jié)構(gòu)。
　　 本文首先形式化定義了PRNN查詢?；诨炯糁Σ呗?本