SEC一种在对等存储网络中的安全纠删码方案-PKU-北京大学.doc

一种基于LCS的相似网页检测算法 黄连恩, 王磊, 李晓明 报告编号 PKU_CS_NCIS_TR2007012 提交时间 2007-12-20 北京大学 信息科学技术学院 网络与信息系统研究所，100871 北京大学 网络与分布式系统实验室， 100871 一种基于LCS的相似网页检测算法? 黄连恩, 王磊, 李晓明 （北京大学 信息科学与技术学院， 100871） 摘要：网页的相似性检测长期以来是一个研究的热点，shingling和simhash被认为是当前最好的两个算法，然而它们存在着一定的不足：一方面，高的分数意味着高的相似概率，但并不必然意味着高的相似度；另一方面，哈希代码的长度和多样性之间的冲突决定了难以同时获得高的准确率和覆盖率。本文提出了一种新型的相似网页检测算法，同时具备高准确率与高覆盖率的优点。该算法采用基于LCS（longest common subsequence）的相似性度量方法，它可以更好地度量网页之间的相似度和包含关系，并获得高的准确度。同时，本文设计了一个包含了三个步骤的检测过程框架，以保证算法的效率。综合实验表明本文的算法同时获得了高准确率与高覆盖率并具有较好的效率。该算法成功应用于4.3亿文章型网页集合，将其分割为0.68亿个相似网页子集，整个过程使用6台Linux服务器仅花费了5天的时间。 关键词： 相似性检测; 消重; 最长公共子序列; 相似性度量 Achieving both High Precision and High Recall in Near-duplicate Detection Huang Lian’en, Wang Lei, Li Xiaoming Institute of Network Computing and Information Systems, Peking University Abstract: To Find near-duplicate documents, fingerprint-based paradigms such as shingling and simhash have been recognized as effective approaches and are considered the state-of-the-art. Nevertheless, we see two aspects of these approaches which may be improved. First, high score under these algorithms similarity measurement implies high probability of similarity between documents, which is different from high similarity of the documents. Second, there has to be a tradeoff between hash-code length and hash-code multiplicity in fingerprint paradigms, which makes it hard to maintain a satisfactory recall level while improving precision. In this paper we propose a new approache of near-duplicate detection for web pages, which has both merits of high precision and high recall. Technically, our approache is based on LCS (longest common subsequence) measurement, together with a 3-step framework, which is carefully designed to ensure high efficiency. A comprehensive experiment was conducted, which shows our method achieves both high precision and high recall. Also, the method has been successfully used to partition a set of 430 million web pages into 68 million subsets of similar pages.