| 一种面向不确定对象的可见k近邻查询算法 |
| |
| 引用本文： | 王艳秋,徐传飞,于戈,谷峪,陈默.一种面向不确定对象的可见k近邻查询算法[J].计算机学报,2010,33(10). |
| |
| 作者姓名： | 王艳秋 徐传飞 于戈 谷峪 陈默 |
| |
| 基金项目： | 国家自然科学基金，国家"八六三"高技术研究发展计划项目基金 |
| |
| 摘 要： | 真实世界中,常存在很多障碍物,影响空间对象到查询点的可见性及距离,可见k近邻查询查找距查询点最近的k个可见对象,是时空查询领域的一类重要算法.由于度量设备误差以及通信开销的限制等因素,空间对象位置不确定因素广泛存在.文中拟对不确定对象执行可见k近邻查询,提出了概率可见k近邻(PVkNN)查询,即查找前k个成为查询点最近邻居概率最大的节点.为了高效地执行这一查询,文中提出了k-界限剪枝方法,基于可见质心的紧缩过滤以及对不可见对象的剪枝策略,从空间角度过滤掉不符合条件的对象.为避免对候选集合中每个对象的概率都进行精确计算,从概率角度提出了根据概率上下限来对候选集合进行进一步的求精方法,采用近似采样技术来获取可见区域的比例,实现了对PVkNN的高效计算.采用真实和模拟数据集设计实验,充分验证了算法的效率和精度.
|
| 关 键 词： | 概率可见k近邻查询 不确定对象 空间剪枝 概率上下限求精 |
Visible k Nearest Neighbor Queries over Uncertain Data |
| |
| WANG Yan-Qiu,XU Chuan-Fei,YU Ge,GU Yu,CHEN Mo.Visible k Nearest Neighbor Queries over Uncertain Data[J].Chinese Journal of Computers,2010,33(10). |
| |
| Authors: | WANG Yan-Qiu XU Chuan-Fei YU Ge GU Yu CHEN Mo |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
|
