道路網(wǎng)絡(luò)中的多對(duì)象最近鄰查詢研究.pdf

1、多對(duì)象最近鄰查詢(All Nearest Neighbors Query)[1]在地理信息系統(tǒng)、城市規(guī)劃和資源分配等領(lǐng)域有廣泛的實(shí)際應(yīng)用，也可作為模式識(shí)別和分類[2]、某些聚類算法或應(yīng)用的核心模塊[3，4，5]。道路網(wǎng)絡(luò)在實(shí)際生最近鄰查詢問題還沒得到很好的解決：一方面，針對(duì)歐氏空間的查詢處理算法不能直接適用于道路網(wǎng)絡(luò)環(huán)境：另一方面活中廣泛存在，但是至今為止，道路網(wǎng)絡(luò)環(huán)境中的多對(duì)象，通過重復(fù)調(diào)用道路網(wǎng)絡(luò)環(huán)境下的最近鄰查詢算法來進(jìn)行多對(duì)象最

2、近鄰查詢處理的計(jì)算代價(jià)較大。我們利用M樹[6]對(duì)道路網(wǎng)絡(luò)中的邊建立索引結(jié)構(gòu)，基于該索引，提出了一個(gè)新穎的多對(duì)象最近鄰查詢處理算法BANNS(Batched All Nearest NeighborsSearch)。 1、定義道路網(wǎng)絡(luò)中邊與邊之間的MaxD距離，其實(shí)際意義為：在道路網(wǎng)絡(luò)中，從一條邊的任意一個(gè)端點(diǎn)出發(fā)，到達(dá)另一條邊的某個(gè)端點(diǎn)所經(jīng)過的道路網(wǎng)絡(luò)距離一定不超過MaxD距離。 2、利用M樹[6]為道路網(wǎng)絡(luò)環(huán)境中的邊建

3、立索引結(jié)構(gòu)?；谠撍饕Y(jié)構(gòu)，我們提出了BANNS算法，采用了批處理的基本思想來處理道路網(wǎng)絡(luò)中的多對(duì)象最近鄰查詢。 3、為了給實(shí)際應(yīng)用提供更多的信息，我們對(duì)BANNS算法進(jìn)行了擴(kuò)展，使BAkNNS算法能查詢空間對(duì)象集合B中A集合元素的多個(gè)最近鄰。 4、分別使用人造道路網(wǎng)絡(luò)和真實(shí)道路網(wǎng)絡(luò)數(shù)據(jù)，驗(yàn)證了BANNS和BAkNNS算法的性能。實(shí)驗(yàn)結(jié)果顯示BANNS和BAkNNS性能穩(wěn)定、高效：當(dāng)空間對(duì)象集合A較大時(shí)，B.ANNS算法