室内概率阈值反向最近邻查询  

Probabilistic Threshold Reverse Nearest Neighbor Queries for Indoor Moving Objects

作　　者：王丽[1] 秦小麟[1] 许建秋[1] 

机构地区：[1]南京航空航天大学计算机科学与技术学院,南京210016

出　　处：《计算机科学》2015年第1期201-205,214,共6页Computer Science

基　　金：国家自然科学基金项目(61373015;61300052);国家教育部高等学校博士学科点博导基金资助项目(20103218110017);中央高校基本科研业务费专项项目(NP2013307)资助

摘　　要：室内空间变得越发的庞大和复杂,随之产生了越来越多的室内空间查询需求。目前已有文献提出了针对室内空间环境的范围查询和最近邻查询,而作为常见的空间查询类型的反向最近邻查询,尚未有相关的研究。为此,提出了室内概率阈值反向最近邻查询和基于定位设备的设备可达图模型。在图模型基础上,提出了室内概率阈值反向最近邻查询处理算法,该算法由基于图模型的批量剪枝、基于室内距离的剪枝、基于概率的剪枝和概率计算4部分构成,通过剪枝策略修剪掉不可能出现在结果集中的对象,从而缩小了查询空间,提高了效率。Indoor spaces are becoming increasingly large and complex,and more and more demand for initiating indoor spatial queries has emerged.Range queries and nearest neighbor queries specifically for indoor space have been proposed,while there are no studies on reverse nearest neighbor queries.Thus,this paper presented the formal definition of probabilistic threshold reverse nearest neighbor query （IPRNN） for indoor moving objects and a device reachable graph model.The query processing algorithm of IPRNN was proposed based on the graph model.The algorithm consists of four parts：model pruning,indoor distance pruning,probability pruning and probability calculation.The objects that are not likely to appear in the result set are built out through pruning strategy,thereby significantly reducing the search space and improving efficiency.

关 键 词：室内空间 反向最近邻 设备可达图模型 查询处理 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]