基于動態(tài)矩形遍歷搜索的K-NN查詢算法.pdf

1、隨著移動計算、無線通信以及定位技術(shù)的快速發(fā)展,大量的應(yīng)用領(lǐng)域,如交通、商貿(mào)、物流、氣象、軍事等,積累了巨大的空間數(shù)據(jù)。人們迫切需要對這些數(shù)據(jù)進(jìn)行各種查詢分析以便發(fā)現(xiàn)其隱藏的知識或做出正確的決策。
　　本文首先分析了利用傳統(tǒng)的樹索引和網(wǎng)格索引進(jìn)行K-NN查詢的優(yōu)缺點,基于樹索引的K-NN算法,采用測量距離和剪枝策略提高查詢效率,在繼續(xù)查找下一近鄰時,往往需要大量的距離計算以便排除不必要的查找區(qū)域,在數(shù)據(jù)量龐大的情況下,頻繁的計算距離

2、所花費的時間代價很大,算法查詢效率急劇下降,基于網(wǎng)格索引的K-NN查詢算法,通過計算被查詢對象與其周圍八個網(wǎng)格中的對象距離,獲取近鄰對象,并一層層向外擴(kuò)大查詢范圍,查詢范圍不靈活,會出現(xiàn)空網(wǎng)格單元使得近鄰對象的查詢次序與實際排序順序不一致,致使搜索緩慢,存儲利用率低。
　　本文提出了基于動態(tài)矩形遍歷搜索的K-NN查詢算法,采用聚類方法將空間數(shù)據(jù)對象聚類到被查詢對象所在的水平和豎直方向,選擇大小合適的矩形動態(tài)進(jìn)行移動以獲取下次進(jìn)行查

3、詢的范圍,采用動態(tài)矩形進(jìn)行遍歷搜索K-NN對象,由于將數(shù)據(jù)對象進(jìn)行聚類,使得每類中數(shù)據(jù)對象間距變小,動態(tài)矩形在每個方向的查詢區(qū)域不為空,節(jié)省了存儲空間,采用要查找的K-NN對象數(shù)目來選取動態(tài)矩形的大小,排除了人為性,查找范圍具有很大隨機(jī)性,由實際數(shù)據(jù)對象的空間分布決定,動態(tài)矩形大小更為合理,同時有效排除了當(dāng)前不必要查詢的區(qū)域,在四個方向上是循環(huán)進(jìn)行查找,每次遍歷過程中,動態(tài)矩形只在一個方向進(jìn)行一次數(shù)據(jù)對象范圍劃分,查找完后,便轉(zhuǎn)向下一個

4、方向進(jìn)行避免了某方向長期被占用,由于下一個查找方向是上次遍歷過程中下一個具有最小近鄰距離的方向,所查找的近鄰對象之間的順序趨于最終結(jié)果排序順序,只需進(jìn)行少量對象間的調(diào)整即可,提高了查詢效率。
　　論文在采用 Java開發(fā)技術(shù)實現(xiàn)了對基于動態(tài)矩形遍歷搜索的 K-NN查詢算法方法的仿真測試。然后依照空間數(shù)據(jù)庫中有關(guān)索引算法性能評價的準(zhǔn)則,運用隨機(jī)所產(chǎn)生的空間數(shù)據(jù)對象集進(jìn)行測試,實現(xiàn)了對基于動態(tài)矩形遍歷搜索的K-NN查詢算法,樹索引和網(wǎng)