中文摘要：

真实世界中,常存在很多障碍物,影响空间对象到查询点的可见性及距离,可见k近邻查询查找距查询点最近的k个可见对象,是时空查询领域的一类重要算法.由于度量设备误差以及通信开销的限制等因素,空间对象位置不确定因素广泛存在.文中拟对不确定对象执行可见k近邻查询,提出了概率可见k近邻（PVkNN）查询,即查找前k个成为查询点最近邻居概率最大的节点.为了高效地执行这一查询,文中提出了k-界限剪枝方法,基于可见质心的紧缩过滤以及对不可见对象的剪枝策略,从空间角度过滤掉不符合条件的对象.为避免对候选集合中每个对象的概率都进行精确计算,从概率角度提出了根据概率上下限来对候选集合进行进一步的求精方法,采用近似采样技术来获取可见区域的比例,实现了对PVkNN的高效计算.采用真实和模拟数据集设计实验,充分验证了算法的效率和精度.

英文摘要：

In many spatial applications, there are physical obstacles which affect the distance and the visibility between two objects. The visible k nearest neighbor（VkNN） query is one of signifi- cant queries to search the space with obstacles. Due to the measurement errors, the limitation of communications and so on, uncertainty of object location is inherent in spatial database. This pa- per proposes a variant of the VkNN query which evaluates on uncertain data, namely probabilistic visible k nearest neighbor （PVkNN） query. A PVkNN query retrieves k objects visible to q with the maximum probability to be the nearest neighbor of the query point q. In order to improve the processing efficiency, this paper further proposes three spatial pruning methods and a probabilis- tic refinement method, proposes the k-bound pruning, visible center based pruning and the invisi- ble objects pruning methods. This paper also proposes a probabilistic refinement mechanism to avoid the integral computation for each object in the candidate set. Extensive experiments demonstrate the efficiency and the effectiveness of the proposed algorithms.