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

第33 卷 第 10 期 计 算 机 学 报 V ol . 33 N o. 10 20 10 年10 月 CH IN ESE JO U RN A L O F CO M PU T ER S Oct . 2010 k 1) 2) 1) 1) 2) 1) 2) 1) 王艳秋 徐传飞 于 戈 谷 峪 陈 默 1) ( 东北大学信息科学与工程学院 沈阳 110819) 2) ( 医学影像计算教育部重点实验室( 东北大学) 沈阳 110819) 真实世界中 常存在很多障碍物 影响空间对象到查询点的可见性及距离 可见k 近邻查询查找距查询点 最近的k 个可见对象 是时空查询领域的一类重要算法. 由于度量设备误差以及通信开销的限制等因素 空间对象 位置不确定因素广泛存在. 文中拟对不确定对象执行可见k 近邻查询 提出了概率可见k 近邻( PV kN N ) 查询 即查 找前k 个成为查询点最近邻居概率最大的节点. 为了高效地执行这一查询 文中提出了k 界限剪枝方法 基于可见 质心的紧缩过滤以及对不可见对象的剪枝策略 从空间角度过滤掉不符合条件的对象. 为避免对候选集合中每个 对象的概率都进行精确计算 从概率角度提出了根据概率上下限来对候选集合进行进一步的求精方法 采用近似 采样技 来获取可见区域的比例 实现了对 PV kN N 的高效计算. 采用真实和模拟数据集设计实验 充分验证了算 法的效率和精度. 概率可见k 近邻查询; 不确定对象; 空间剪枝; 概率上下限求精 T P 311 DOI : 10. 37 24/ SP. J. 10 16 . 2010. 0 1943 Visible k Nearest Neighbor Queries over Uncertain Data WA N G Y anQ iu1) 2) XU ChuanF ei1) Y U Ge1) 2) GU Y u 1) 2) CH EN Mo1) 1) ( Colleg e of I nf ormation Sc ience and Eng ineering , N or theaster n Univ ersity , S heny ang 110819) 2) (K ey L aborator y of M edical Imag e Com uting (N or theaster n Univ er sity ) , M inistr y of E ducation, Sh enyang 110819) Abstract In m any sp at ial applicat ions t her e are phy sical o bstacles w hich af f ect the distance and the visibilit y bet w een t w o object s. T he v isible k nearest neighbor ( VkN N ) qu ery is one of sig nif i cant queries to search t he sp ace w ith obst acles. Du e to t he m easurement er rors t he limitat ion of com munic