张 豪，朱 睿，宋栿尧，方 鹏，夏秀峰

（沈阳航空航天大学计算机学院，沈阳 110136）

（∗通信作者电子邮箱13623212292@163.com）

0 引言

随着移动互联网技术的不断发展，基于位置的社交网络（Location-Based Social Network，LBSN）服务应用越来越广泛。许多学者研究了面向LBSN 的查询处理问题应对不同服务类型下的业务请求。

在众多查询处理问题中，面向反k近邻空间关键字（Reverse Spatial KeywordkNearest Neighbor，RSKkNN）［1］查询是一类重要问题，在市场分析、决策支持和交通信息等领域具有重要应用。具体地，在客户推荐系统中，该查询可以帮助商家根据客户偏好有针对性地利用短信等手段为客户推荐商品信息，从而增加营业收入。在交通信息管理领域，它可以通过分析乘客的用车偏好和位置信息，为乘客推荐车辆。

传统反k近邻查询可分为单色反k近邻查询（简称单色查询）和双色反k近邻查询（简称双色查询）。具体地，给定一组对象o和一个单色查询q，查询返回所有以q作为其k近邻的对象。与之不同，给定一组用户U、一组设施F和一个双色查询设施q，查询返回以设施q为k近邻的所有用户。反k近邻查询主要应用于推荐场景，其中单色反k近邻查询主要应用于同类型对象之间的推荐。例如，为某位用户推荐一些与他距离比较近的志趣相投的人。而双色反k近邻主要应用于两种不同类型对象之间的推荐，相较于单色反k近邻查询的应用更加广泛，比如推荐场景中更多的是为商场提供潜在的消费者，为司机提供潜在的乘客等，这些都是单色反k近邻查询无法做到的，所以本文重点研究双色反k近邻。……