We study approximate algorithms for placing a set of documents into M distributed Web servers in this paper. We define the load of a server to be the summation of loads induced by all documents stored. The size of a server is defined in a similar manner. We propose five algorithms. Algorithm 1 balances the loads and sizes of the servers by limiting the loads to k/sub l/ and the sizes to k/sub s/ times their optimal values, where 1/k/sub l/-1 + 1/k/sub n/-1. This result improves the bounds on load and size of servers in (L.C. Chen et al., 2001). Algorithm 2 further reduces the load bound on each server by using partial document replication, and algorithm 3 by sorting. Algorithm 4 employs both partial replication and sorting. Last, without using sorting and replication, we give algorithm 5 for the dynamic placement at the cost of a factor Q(log M) in the time-complexity.
展开▼
机译：本文研究了将一组文档放入M个分布式Web服务器的近似算法。我们将服务器的负载定义为所有存储的文档引起的负载总和。服务器的大小以类似的方式定义。我们提出了五种算法。算法1通过将负载限制为k / sub l /，并将大小限制为k / sub s /乘以其最佳值，从而平衡服务器的负载和大小，其中1 / k / sub l / -1 + 1 / k / sub n / -1。这个结果改善了（L.C. Chen et al。，2001）中服务器的负载和大小的界限。算法2通过使用部分文档复制进一步减少了每个服务器上的负载，算法3通过排序来减少了。算法4同时使用了部分复制和排序。最后，在不使用排序和复制的情况下，我们以时间复杂度中的因子Q（log M）为代价，给出了动态放置的算法5。
展开▼
