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

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

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

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