道路網絡中的多對象最近鄰查詢研究.pdf

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

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

3、立索引結構。基于該索引結構，我們提出了BANNS算法，采用了批處理的基本思想來處理道路網絡中的多對象最近鄰查詢。 3、為了給實際應用提供更多的信息，我們對BANNS算法進行了擴展，使BAkNNS算法能查詢空間對象集合B中A集合元素的多個最近鄰。 4、分別使用人造道路網絡和真實道路網絡數據，驗證了BANNS和BAkNNS算法的性能。實驗結果顯示BANNS和BAkNNS性能穩(wěn)定、高效：當空間對象集合A較大時，B.ANNS算法