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

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

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

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

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