摘要：K最近鄰(KNN)查詢是空間數(shù)據(jù)查詢研究的重要內(nèi)容。目前的KNN查詢方法在處理大規(guī)模的位置數(shù)據(jù)時(shí),存在著更新和查找失衡的問(wèn)題,導(dǎo)致查詢效率較低。因此,提出基于Voronoi劃分的位置數(shù)據(jù)KNN查詢處理方法。首先,創(chuàng)建了一個(gè)二級(jí)空間索引結(jié)構(gòu)VRI,包含VHash和VR樹兩部分。一級(jí)索引結(jié)構(gòu)VHash表示Voronoi圖的直鄰;二級(jí)索引結(jié)構(gòu)VR樹,按照各Voronoi單元所在的最小矩形區(qū)域的重疊面積,自下而上地生成對(duì)應(yīng)的R樹。其次,基于VRI索引結(jié)構(gòu)提出了位置數(shù)據(jù)的KNN查詢算法及動(dòng)態(tài)維護(hù)算法,在KNN查詢方法中,采用VR樹進(jìn)行定位,VHash查找K近鄰,能夠有效地對(duì)查詢點(diǎn)定位,查找速度快。再次,針對(duì)數(shù)據(jù)更新的情況,索引結(jié)構(gòu)也能夠及時(shí)更新,在更新的時(shí)間段內(nèi),對(duì)于位置數(shù)據(jù)隨時(shí)間變化的KNN查詢,提出了利用記錄表進(jìn)行有效查詢的方法。最后,實(shí)驗(yàn)表明,提出的基于Voronoi劃分的空間索引結(jié)構(gòu)和其對(duì)應(yīng)的KNN查詢算法均具有較好的性能和適應(yīng)性。