MaxFirst for MaxBRkNN
MaxFirst for MaxBRkNN
复制标题
DOI：
10.1109/icde.2011.5767892
复制
发表时间：
2011-04
期刊：
影响因子：
--
通讯作者：
Zenan Zhou;Wei Wu;Xiaohui Li;M. Lee;W. Hsu
中科院分区：
文献类型：
--
作者：
Zenan Zhou;Wei Wu;Xiaohui Li;M. Lee;W. Hsu
MaxBRNN问题找到一个区域，使得在该区域内建立新的服务站点将通过邻近度来保证最大数量的客户。这个问题假设每个客户只使用他/她最近的服务站点提供的服务。然而，在现实中，客户倾向于去他/她最近的服务站点。为了解决这个问题，MaxBRNN可以扩展到MaxBRkNN问题，该问题找到一个最佳区域，使得在该区域中设置服务站点可以保证将该站点视为其k个最近服务位置之一的最大数量的客户。我们进一步概括了MaxBRkNN问题以反映真实的场景，其中客户可能对不同的服务站点有不同的偏好，同时服务站点可能更喜欢目标客户。在本文中，我们提出了一个有效的解决方案，称为MaxFirst来解决这个广义MaxBRkNN问题。该算法的工作原理是将空间划分为象限，并仅在可能包含最佳区域的象限中进行搜索。在空间划分过程中，我们计算一个象限的BRkNN的大小的上界和下界，并使用这些边界来修剪没有希望的象限。实验结果表明，MaxFirst算法比现有算法快2~3个数量级。
The MaxBRNN problem finds a region such that setting up a new service site within this region would guarantee the maximum number of customers by proximity. This problem assumes that each customer only uses the service provided by his/her nearest service site. However, in reality, a customer tends to go to his/her k nearest service sites. To handle this, MaxBRNN can be extended to the MaxBRkNN problem which finds an optimal region such that setting up a service site in this region guarantees the maximum number of customers who would consider the site as one of their k nearest service locations. We further generalize the MaxBRkNN problem to reflect the real world scenario where customers may have different preferences for different service sites, and at the same time, service sites may have preferred targeted customers. In this paper, we present an efficient solution called MaxFirst to solve this generalized MaxBRkNN problem. The algorithm works by partitioning the space into quadrants and searches only in those quadrants that potentially contain an optimal region. During the space partitioning, we compute the upper and lower bounds of the size of a quadrant's BRkNN, and use these bounds to prune the unpromising quadrants. Experiment results show that MaxFirst can be two to three orders of magnitude faster than the state-of-the-art algorithm.