MapReduce based location selection algorithm for utility maximization with capacity constraints
MapReduce based location selection algorithm for utility maximization with capacity constraints
复制标题
DOI：
10.1007/s00607-013-0382-5
复制
发表时间：
2014-01
期刊：
影响因子：
3.7
通讯作者：
Yu Sun;Jianzhong Qi;Rui Zhang;Yueguo Chen;Xiaoyong Du
中科院分区：
文献类型：
--
作者：
Yu Sun;Jianzhong Qi;Rui Zhang;Yueguo Chen;Xiaoyong Du
给定一组设施对象和一组客户对象，其中每个客户由她最近的设施提供服务，每个设施受服务能力的约束，我们研究如何找到所有地点，在这些地点上，如果建立了具有给定能力的新设施，则所服务的客户数量最大化(换句话说，设施的效用最大化)。这个问题本身就很难解决。现有的具有指数复杂度的算法是不可伸缩的，不能在大数据集上处理这个问题。因此，我们提出通过并行计算来解决这个问题，特别是使用MapReduce.我们提出了一种基于弧线的方法来将搜索空间划分为不相交的分区。对于负载均衡，我们提出了一种动态策略，将分区分配给Reducer，使估计的负载差异在阈值内。我们使用大容量的真实和合成数据集进行了广泛的实验。实验结果证明了该算法的有效性和可扩展性。
Given a set of facility objects and a set of client objects, where each client is served by her nearest facility and each facility is constrained by a service capacity, we study how to find all the locations on which if a new facility with a given capacity is established, the number of served clients is maximized (in other words, the utility of the facilities is maximized). This problem is intrinsically difficult. An existing algorithm with an exponential complexity is not scalable and cannot handle this problem on large data sets. Therefore, we propose to solve the problem through parallel computing, in particular using MapReduce. We propose an arc-based method to divide the search space into disjoint partitions. For load balancing, we propose a dynamic strategy to assign partitions to reducers so that the estimated load difference is within a threshold. We conduct extensive experiments using both real and synthetic data sets of large sizes. The results demonstrate the efficiency and scalability of the algorithm.