分布式检索中索引数据分布模型与求解方法

Model and solving methods for index data distribution on internet

针对互联网中索引数据分布的优化问题,建立了在搜索代理服务器存储容量和总费用约束条件下数据优化分布问题的数学模型,并阐明此问题为一个NP问题。提出了两种多项式时间的启发式近似优化算法,并通过模拟实验对算法性能进行评价,实验结果表明,这两种算法可以有效地降低数据访问成本。

The problem of optimally distributing index data objects on Intemet is studied. A mathematic model was built for the problem to find a set of proxies from candidates set and to replicate objects at them. The aim is that the total access cost is minimized, subject to the constraints of the storage capacity of the proxies and the total fees charged for the proxies. This optimization problem is proved as NP-complete. Two heuristic algorithms were proposed and evaluated by simulation. The simulation results show that these two heuristics could significantly reduce the access cost.