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