首頁 > 期刊 > 自然科學與工程技術 > 信息科技 > 電子信息科學綜合 > 計算機科學與探索 > 基于Voronoi劃分的位置數據KNN查詢處理方法 【正文】
摘要:K最近鄰(KNN)查詢是空間數據查詢研究的重要內容。目前的KNN查詢方法在處理大規模的位置數據時,存在著更新和查找失衡的問題,導致查詢效率較低。因此,提出基于Voronoi劃分的位置數據KNN查詢處理方法。首先,創建了一個二級空間索引結構VRI,包含VHash和VR樹兩部分。一級索引結構VHash表示Voronoi圖的直鄰;二級索引結構VR樹,按照各Voronoi單元所在的最小矩形區域的重疊面積,自下而上地生成對應的R樹。其次,基于VRI索引結構提出了位置數據的KNN查詢算法及動態維護算法,在KNN查詢方法中,采用VR樹進行定位,VHash查找K近鄰,能夠有效地對查詢點定位,查找速度快。再次,針對數據更新的情況,索引結構也能夠及時更新,在更新的時間段內,對于位置數據隨時間變化的KNN查詢,提出了利用記錄表進行有效查詢的方法。最后,實驗表明,提出的基于Voronoi劃分的空間索引結構和其對應的KNN查詢算法均具有較好的性能和適應性。
注:因版權方要求,不能公開全文,如需全文,請咨詢雜志社