基于半度量路網(wǎng)的高效查詢算法.pdf

1、空間數(shù)據(jù)庫(kù)已成為數(shù)據(jù)庫(kù)領(lǐng)域中的熱點(diǎn)研究方向，路網(wǎng)作為空間數(shù)據(jù)庫(kù)領(lǐng)域中重要的一部分，目前在各個(gè)地圖服務(wù)、商用在線導(dǎo)航系統(tǒng)以及基于位置的查詢應(yīng)用軟件中有著廣泛的應(yīng)用，路網(wǎng)中的查詢得到了越來(lái)越廣泛的關(guān)注。由于路網(wǎng)具有道路數(shù)量多、密度大、交叉頻繁、路況復(fù)雜等特性，如何在路網(wǎng)中高效的查詢至關(guān)重要。
　　路網(wǎng)中利用網(wǎng)絡(luò)距離作為距離的度量方式，廣泛存在不滿足三角不等式關(guān)系的情況，稱(chēng)這樣的路網(wǎng)為半度量路網(wǎng)。由于半度量路網(wǎng)不滿足三角不等式關(guān)系，常見(jiàn)

2、的度量空間中的索引結(jié)構(gòu)無(wú)法有效工作，目前已提出的預(yù)計(jì)算的方法存在查詢速度慢、計(jì)算代價(jià)慢的問(wèn)題，如何在半度量路網(wǎng)中高效的查詢是本文的研究重點(diǎn)和難點(diǎn)。
　　為了解決半度量路網(wǎng)中的查詢速度慢、計(jì)算代價(jià)大的問(wèn)題，本文提出了半度量路網(wǎng)中的高效查詢方法。首先，由于直接在半度量路網(wǎng)中查詢代價(jià)大，本文提出了兩種方法將半度量路網(wǎng)轉(zhuǎn)化為度量路網(wǎng)來(lái)降低查詢代價(jià)。一種方法為隨機(jī)刪除邊算法將半度量路網(wǎng)轉(zhuǎn)化為度量路網(wǎng)，該方法簡(jiǎn)單，容易實(shí)現(xiàn)，但轉(zhuǎn)化過(guò)程中信息損

3、失比較大。為了進(jìn)一步降低查詢代價(jià)，以最小化的信息損失將半度量路網(wǎng)轉(zhuǎn)化為度量路網(wǎng)，這是一個(gè)NP-hard問(wèn)題，因此本文提出了另一種啟發(fā)式的排序刪除邊算法以近似最小化的信息損失完成度量化。其次，提出了QM-樹(shù)索引結(jié)構(gòu)，在查詢中利用三角不等式關(guān)系剪枝不可能包含查詢結(jié)果的子樹(shù)，有效的減少了查詢時(shí)間。最后，本文提出了半度量路網(wǎng)中的范圍查詢方法以及K近鄰查詢方法。這兩種查詢方法都包括查詢和驗(yàn)證兩部分，查詢部分利用三角不等式關(guān)系來(lái)剪枝不可能為查詢結(jié)果