一种面向不确定对象的可见k近邻查询算法.pdf

第33卷第10期 计 算 机 学 报 v01．33No．10 2010年10月 CHINESEJOURNALOFCOMPUTERS Oct．2010 一种面向不确定对象的可见k近邻查询算法 王艳秋’2’ 徐传飞 于 戈”矗’ 谷 峪”矗’ 陈 默” I’(东北大学信息科学与工程学院 沈阳 110819) 2’(医学影像计算教育部重点实验室(东北大学)沈阳 110819) 摘要真实世界中，常存在很多障碍物，影响空间对象到查询点的可见性及距离，可见k近邻查询查找距查询点 最近的女个可见对象，是时空查询领域的一类重要算法．由于度量设备误差以及通信开销的限制等因素，空间对象 位置不确定因素广泛存在．文中拟对不确定对象执行可见女近邻查询，提出了概率可见k近邻(PVkNN)查询，即查 找前k个成为查询点最近邻居概率最大的节点．为了高效地执行这一查询，文中提出了^一界限剪枝方法，基于可见 质心的紧缩过滤以及对不可见对象的剪枝策略，从宅间角度过滤掉不符合条件的对象．为避免对候选集合中每个 对象的概率都进行精确计算，从概率角度提出了根据概率上下限来对候选集合进行进一步的求精方法．采用近似 采样技术来获取可见区域的比例，实现|r对PVkNN的高效计算．采用真实和模拟数据集设计实验。充分验证了算 法的效率和精度． 关键词概率可见k近邻查询；不确定对象；空间剪枝；概率上下限求精 中图法分类号TP311DOI号：10．3724／SP．J．1016．2010．01943 UncertainData VisiblekNearest over NeighborQueries WANG XUChuan—Feil’YUGel’·2’ GUYul’-2’CHENM01’ Yan—Qiul’·2’ Scienceand 1 10819) ”(CollegeofInformation Engineering。NortheasternUniversit，，Shenyang Medical 110819) 2’(KeyLaboratoryof ImageComputing(NortheasternUniversity)，MinistryofEducation，Shenyang AbstractIn are obstacleswhichaffectthedistanceand manyspatialapplications，therephysical of the betweentwo visibleknearest isone visibility objects．The neighbor(VkNN)querysignifi— the withobstacles．Duetothemeasurementerrors，thelimitationof cant tosearch queries space in communicationsandso of locationisinherent database．This