Abstract:  With the development of Wi-Fi, RFID and other indoor positioning technology, more and more demands for indoor location-based service have emerged. Range queries and nearest neighbor queries specifically for indoor space have been proposed, while there are no studies on bichromatic reverse nearest neighbor (BRNN) queries. Thus, this paper proposes the interest point fusion graph (IPFG) model with the existence of interest points set. And this paper presents path pruning, floor pruning and cell pruning strategies, which are used to reduce the search space during BRNN query processing. On the basis of interest point fusion graph and pruning strategies, this paper proposes the query processing algorithm of indoor bichromatic reverse nearest neighbor (IBRNN) queries named Smart. By examining the graph elements of IPFG, Smart determines whether the moving objects associated with the graph element may belong to the result set. And extensive experimental analysis shows that Smart is effective and efficient.

Key words: indoor space, bichromatic reverse nearest neighbor queries, interest point fusion graph, query processing

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

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