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

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

2、近鄰查詢處理的計算代價較大。我們利用M樹[6]對道路網(wǎng)絡(luò)中的邊建立索引結(jié)構(gòu)，基于該索引，提出了一個新穎的多對象最近鄰查詢處理算法BANNS(Batched All Nearest NeighborsSearch)。 1、定義道路網(wǎng)絡(luò)中邊與邊之間的MaxD距離，其實際意義為：在道路網(wǎng)絡(luò)中，從一條邊的任意一個端點出發(fā)，到達另一條邊的某個端點所經(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ò)中的多對象最近鄰查詢。 3、為了給實際應(yīng)用提供更多的信息，我們對BANNS算法進行了擴展，使BAkNNS算法能查詢空間對象集合B中A集合元素的多個最近鄰。 4、分別使用人造道路網(wǎng)絡(luò)和真實道路網(wǎng)絡(luò)數(shù)據(jù)，驗證了BANNS和BAkNNS算法的性能。實驗結(jié)果顯示BANNS和BAkNNS性能穩(wěn)定、高效：當(dāng)空間對象集合A較大時，B.ANNS算法