移動(dòng)環(huán)境下增量組最近鄰居查詢方法研究.pdf

1、計(jì)算技術(shù)和無(wú)線通訊技術(shù)的發(fā)展與結(jié)合推動(dòng)了移動(dòng)計(jì)算技術(shù)的發(fā)展。在移動(dòng)環(huán)境下，用戶可以隨時(shí)隨地實(shí)現(xiàn)對(duì)信息的訪問(wèn)。由于用戶的移動(dòng)性，當(dāng)用戶從一個(gè)區(qū)域移動(dòng)到另一個(gè)區(qū)域時(shí)，需要將用戶位置相關(guān)信息動(dòng)態(tài)更新到數(shù)據(jù)庫(kù)，此時(shí)，用戶的與位置相關(guān)的請(qǐng)求結(jié)果也會(huì)動(dòng)態(tài)發(fā)生變化。由于查詢結(jié)果隨著時(shí)間動(dòng)態(tài)發(fā)生變化，此時(shí)采取有效的查詢處理方法來(lái)處理用戶請(qǐng)求必然是一個(gè)具有挑戰(zhàn)性的研究課題。
　　 組最近鄰居查詢定義為在一組對(duì)象中找到距離另一組對(duì)象距離和最小的對(duì)象

2、的集合。已有相關(guān)學(xué)者在靜態(tài)組最近鄰居查詢方面做了大量研究，然而針對(duì)動(dòng)態(tài)更新環(huán)境下的移動(dòng)對(duì)象組最近鄰居查詢還沒(méi)有有效的方法。
　　 采用每次更新時(shí)刻執(zhí)行一次查詢可以解決這一問(wèn)題，然而這不能充分利用上一次查詢的結(jié)果，所需代價(jià)很大。增量組最近鄰居查詢方法可以較好的解決這一問(wèn)題。通過(guò)交點(diǎn)鏈表的方式求出K+1組最近鄰居，當(dāng)下一次更新到來(lái)時(shí)，利用K+1組最近鄰居就能求出新的時(shí)刻的K組最近鄰居。結(jié)合組最近鄰居的特點(diǎn)，K+1組最近鄰居查詢改進(jìn)算