室内双色数据集上的反向最近邻查询

来源：计算机科学与探索杂志2015年第3期北京时间：

作者：王丽，秦小麟，施常月

单位：南京航空航天大学 计算机科学与技术学院，南京 210016

摘要：随着Wi-Fi、RFID等室内定位技术的发展，产生了越来越多的基于室内空间的位置服务需求。目前已有文献提出了针对室内环境的范围查询和最近邻查询，而双色反向最近邻（bichromatic reverse nearest neighbor，BRNN）查询作为常见的空间查询类型，在室内空间中尚未有相关的研究。为此，提出了基于兴趣点集合的兴趣点融合图模型，并提出了基于路径、基于楼层和基于单元的3种剪枝策略，用于在查询处理时削减搜索空间。在兴趣点融合图和剪枝策略的基础上，提出了室内双色反向最近邻（indoor bichromatic reverse nearest neighbor，IBRNN）查询算法Smart。Smart算法通过对兴趣点融合图中的图元素的检查，从而判断与该图元素关联的移动对象是否有可能属于结果集。最后通过实验，对所提算法的有效性和高效性进行了验证。

关键词：室内空间,双色反向最近邻查询,兴趣点融合图,查询处理