時(shí)空道路網(wǎng)最近鄰查詢技術(shù).pdf

1、目前,在計(jì)算機(jī)領(lǐng)域出現(xiàn)了許多新的應(yīng)用,如定位服務(wù)等,這些新應(yīng)用的出現(xiàn),體現(xiàn)了無(wú)線網(wǎng)絡(luò)通訊等技術(shù)的發(fā)展。在時(shí)空數(shù)據(jù)庫(kù)中對(duì)于定位服務(wù)給予支持的一項(xiàng)重要查詢技術(shù)就是多類型最近鄰查詢。
　　 給定n種數(shù)據(jù)類型的數(shù)據(jù)集和一個(gè)查詢點(diǎn)q,時(shí)空道路網(wǎng)絡(luò)中的多類型最近鄰(MTNN)查詢就是要根據(jù)這個(gè)給定的查詢點(diǎn)q,找到一條最優(yōu)路徑,該路徑由n個(gè)數(shù)據(jù)結(jié)節(jié)組成,這n個(gè)結(jié)點(diǎn)分別屬于不同的數(shù)據(jù)類型。目前,大多數(shù)時(shí)空數(shù)據(jù)的查詢都是基于物體之間的歐氏距離的基

2、礎(chǔ)上的,如多類型最近鄰查詢。但現(xiàn)實(shí)情況是物體之間的距離受限于它所處的網(wǎng)絡(luò),像道路網(wǎng)、航空網(wǎng)、鐵路網(wǎng)等等?；诖?物體之間的距離的度量是其所處的網(wǎng)絡(luò)的網(wǎng)絡(luò)距離。
　　 本文在深入分析分層編碼視圖的基礎(chǔ)上,首先針對(duì)時(shí)空道路網(wǎng)絡(luò)中的多類型k最近鄰(MT-KNN)問(wèn)題,結(jié)合多類型最近鄰查詢及k最近鄰查詢的理論,提出了多類型k最近鄰查詢算法。通過(guò)對(duì)分層編碼視圖進(jìn)行擴(kuò)展,使其每個(gè)結(jié)點(diǎn)包含一個(gè)有k個(gè)數(shù)據(jù)項(xiàng)的局部路徑序列,建立了多路徑分層編碼路

3、徑視圖,并利用逐步擴(kuò)展局部路徑的方法,實(shí)現(xiàn)了多類型k最近鄰查詢；然后針對(duì)時(shí)空道路網(wǎng)絡(luò)中的時(shí)間受限的多類型-最近鄰(MT-TNN)問(wèn)題,結(jié)合多類型k最近鄰查詢的方法,提出了受時(shí)間窗限制的多類型最近鄰查詢算法。通過(guò)對(duì)分層編碼視圖進(jìn)行擴(kuò)展,使其每個(gè)結(jié)點(diǎn)包含一個(gè)時(shí)間序列TW,其中第i項(xiàng)表示在時(shí)間i在該點(diǎn)結(jié)束的局部路徑,建立了多路徑時(shí)間序列分層編碼路徑視圖,并仍利用逐步擴(kuò)展局部路徑的方法,實(shí)現(xiàn)了受時(shí)間窗限制的多類型最近鄰查詢。實(shí)驗(yàn)結(jié)果分析表明算法