基于部分匹配方式的可扩展P2P搜索算法

理想的P2P(Peer-to-Peer)搜索算法应该同时具有信息检索水平的查询质量和有效的搜索性能。然而,现有的搜索算法都不能同时较好地满足这两点。基于这两个目标,该文提出一种基于层次聚类的分布层层次聚类(DHC)搜索算法。该算法中首先利用向量空间模型将文件内容表示成向量的形式,然后经过层次聚类操作得到一棵关于全网所有文件向量的层次树,层次树信息分布式地存储于整个网络中,以层次树为路由线索,路由深度不会超过树的高度。初步仿真试验表明,该算法的查全率在80%以上,并具有对数量级的搜索与更新代价。

Scalable routing algorithm for partial matches in P2P systems

The ideal routing algorithm in a P2P system should not only provide the IR algorithms' effectiveness, but also guarantee the router's scalability. This paper describes the distributed hierarchical clustering that meets both objectives. The algorithm is based on a state-of-the-art document ranking algorithm and the vector-space model, through which the files in a P2P network are denoted as vectors. The file content vectors are used to cluster a given content to produce a content clustering tree using a hierarchical clustering algorithm. The vectors are stored in a fully distributed manner. The path length of the routings in the cluster tree will be no longer than the tree depth. Simulations show that, with distributed hierarchical clustering, search recalls are more than eighty percent successful with lookup and join/departure costs both scaling logarithmically with the number of physical nodes.