计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2006年
z3期
490-497
,共8页
高云君%李春%陈根才%姜贤塔%陈岭%陈纯
高雲君%李春%陳根纔%薑賢塔%陳嶺%陳純
고운군%리춘%진근재%강현탑%진령%진순
查询处理%k最近邻居查询%移动对象轨迹%算法
查詢處理%k最近鄰居查詢%移動對象軌跡%算法
사순처리%k최근린거사순%이동대상궤적%산법
近10多年来,研究者们已经在k最近邻居(kNN)查询方面做了很多工作,但是对于移动对象轨迹的kNN查询处理却研究得很少.鉴于此,研究了在存储有历史移动对象轨迹信息的TB树结构上的kNN查询问题,并且提出了一种有效的基于最佳优先搜索范例的kNN(k≥1)查询算法,称为BFPkNN.BFPkNN是一种I/O最佳的算法,即它仅仅访问有可能包含最终结果的结点.同时,为了减少存储空间和CPU代价,又提出了若干有效的剪枝策略.大量的实验证明BFPkNN在效率和可扩展性上均大大胜过其他同类算法.
近10多年來,研究者們已經在k最近鄰居(kNN)查詢方麵做瞭很多工作,但是對于移動對象軌跡的kNN查詢處理卻研究得很少.鑒于此,研究瞭在存儲有歷史移動對象軌跡信息的TB樹結構上的kNN查詢問題,併且提齣瞭一種有效的基于最佳優先搜索範例的kNN(k≥1)查詢算法,稱為BFPkNN.BFPkNN是一種I/O最佳的算法,即它僅僅訪問有可能包含最終結果的結點.同時,為瞭減少存儲空間和CPU代價,又提齣瞭若榦有效的剪枝策略.大量的實驗證明BFPkNN在效率和可擴展性上均大大勝過其他同類算法.
근10다년래,연구자문이경재k최근린거(kNN)사순방면주료흔다공작,단시대우이동대상궤적적kNN사순처리각연구득흔소.감우차,연구료재존저유역사이동대상궤적신식적TB수결구상적kNN사순문제,병차제출료일충유효적기우최가우선수색범례적kNN(k≥1)사순산법,칭위BFPkNN.BFPkNN시일충I/O최가적산법,즉타부부방문유가능포함최종결과적결점.동시,위료감소존저공간화CPU대개,우제출료약간유효적전지책략.대량적실험증명BFPkNN재효솔화가확전성상균대대성과기타동류산법.