Source: http://www.google.com/patents/US8015162?ie=ISO-8859-1
Timestamp: 2014-07-30 19:21:37
Document Index: 339735777

Matched Legal Cases: ['art 134', 'Application No. 2', 'Application No. 200780036634', 'Application No. 200680038100', 'Application No. 200780036634', 'Application No. 06801549']

Patent US8015162 - Detecting duplicate and near-duplicate files - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign in<nobr>Advanced Patent Search</nobr>PatentsNear-duplicate documents may be identified by processing an accepted set of documents to determine a first set of near-duplicate documents using a first technique, and processing the first set to determine a second set of near-duplicate documents using a second technique. The first technique might be...http://www.google.com/patents/US8015162?utm_source=gb-gplus-sharePatent US8015162 - Detecting duplicate and near-duplicate filesAdvanced Patent SearchPublication numberUS8015162 B2Publication typeGrantApplication numberUS 11/499,260Publication dateSep 6, 2011Filing dateAug 4, 2006Priority dateAug 4, 2006Also published asCA2660202A1, CA2660202C, CN101523343A, CN101523343B, CN102982053A, EP2054797A2, EP2054797A4, US20080044016, US20120290597, WO2008019133A2, WO2008019133A3, WO2008019133A9Publication number11499260, 499260, US 8015162 B2, US 8015162B2, US-B2-8015162, US8015162 B2, US8015162B2InventorsMonika H. HenzingerOriginal AssigneeGoogle Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (35), Non-Patent Citations (37), Referenced by (6), Classifications (7), Legal Events (4) External Links: USPTO, USPTO Assignment, EspacenetDetecting duplicate and near-duplicate filesUS 8015162 B2Abstract Near-duplicate documents may be identified by processing an accepted set of documents to determine a first set of near-duplicate documents using a first technique, and processing the first set to determine a second set of near-duplicate documents using a second technique. The first technique might be token order dependent, and the second technique might be order independent. The first technique might be token frequency independent, and the second technique might be frequency dependent. The first technique might determine whether two documents are near-duplicates using representations based on a subset of the words or tokens of the documents, and the second technique might determine whether two documents are near-duplicates using representations based on all of the words or tokens of the documents. The first technique might use set intersection to determine whether or not documents are near-duplicates, and the second technique might use random projections to determine whether or not documents are near-duplicates.
Recall that the Web may include the same documents duplicated in different forms or at different places on the Web. For example, as introduced in �1.2.1 above, documents may be �mirrored� at different sites on the Web, documents may have a number of different formats so that users can render or download the content in a form that they prefer, documents may have a different versions with different information prepended or appended, some documents may have been generated from others using consistent word replacement, and some documents may aggregate or incorporate documents available from another source on the Web. It would be desirable to eliminate such duplicates or near-duplicates. Besides eliminating duplicate or near-duplicate documents to meet user expectations and wishes, eliminating duplicate or near-duplicate documents is desirable to search engine hosting entities to (i) reduce storage requirements (e.g., for the index and data structures derived from the index), and (ii) reduce the time and/or computational resources needed to process indexes, queries, etc.
 S ⁡ ( d ) ⋂ S ⁡ ( d ′ )   S ⁡ ( d ) ⋃ S ⁡ ( d ′ )  is a good measure for the similarity of d and d′.
The Charikar algorithm is now described. Let b be a constant. Each token is projected into b-dimensional space by randomly choosing b entries from {−1, 1 }. The resulting b-dimensional vector may be referred to as a �token vector�. The same tokens, whether occurring on the same page or on different pages, will have the same b-dimensional representation (i.e., the same �token vector�). For each page, a representative b-dimensional vector (which may be referred to as an �initial page vector�) is created by adding the projections of all the tokens in the page's token sequence (i.e., adding all of the page's �token vectors�). The final vector for the page (which may be referred to as a �final page vector�) is created by setting every positive entry in the vector to 1 and every non-positive entry to 0. The generates a random b-dimensional projection (i.e., a final page vector) for each page. The final page vectors have the property that the cosine similarity of two pages is proportional to the number of bits in which the two corresponding projections agree. That is, similarity in the Charikar algorithm (referred to as �C-similarity�) of two Web pages is the number of bits their projections agree on. Two pages are near-duplicates in the Charikar algorithm (or are C-similar) if the number of agreeing bits in their projections is above a fixed threshold t.
�2. SUMMARY OF THE INVENTION Some embodiments consistent with the present invention might detect near-duplicate documents by (a) accepting a set of documents, (b) processing the set of documents to determine a first set of near-duplicate documents using a first document similarity technique, and (c) processing the first set of near duplicate documents to determine a second set of near-duplicate documents using a second document similarity technique.
�3. BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a block diagram of an environment in which at least some aspects of the present invention may be used.
�4. DETAILED DESCRIPTION The present invention may involve novel methods, apparatus, message formats, and/or data structures for determining whether or not documents are similar. The following description is presented to enable one skilled in the art to make and use the invention, and is provided in the context of particular applications and their requirements. Thus, the following description of embodiments consistent with the present invention provides illustration and description, but is not intended to be exhaustive or to limit the present invention to the precise form disclosed. Various modifications to the disclosed embodiments will be apparent to those skilled in the art, and the general principles set forth below may be applied to other embodiments and applications. For example, although a series of acts may be described with reference to a flow diagram, the order of acts may differ in other implementations when the performance of one act is not dependent on the completion of another act. Further, non-dependent acts may be performed in parallel. No element, act or instruction used in the description should be construed as critical or essential to the present invention unless explicitly described as such. Also, as used herein, the article �a� is intended to include one or more items. Where only one item is intended, the term �one� or similar language is used. In the following, �information� may refer to the actual information, or a pointer to, or a location of, such information. Thus, the present invention is not intended to be limited to the embodiments shown and the inventor regards her invention to include any patentable subject matter described.
Regarding the query processing part 134′, the searching operations 230 may be run by a Web server and may use a lexicon 232, together with the inverted index 226 and the PageRanks 228, to generate query results in response to a query. The query results may be based on a combination of (i) information derived from PageRanks 228 and (ii) information derived from how closely a particular document matches the terms contained in the query (also referred to as the information retrieval (or �IR�) component). Having described exemplary environments in which the present invention may be used, exemplary embodiments consistent with the present invention are now described in �4.2 below.
Still referring to block 320, in some embodiments consistent with the present invention, the first document similarity technique might include (i) fingerprinting every sub-sequence of k tokens to generate (n−k+1) shingles, (ii) fingerprinting each shingle with m different fingerprinting functions fi for 1≦i≦m to generate (n−k+1) values for each of the m fingerprinting functions fi, (iii) determining, for each i, the smallest value to create an m-dimensional vector of minvalues, (iv) reducing the m-dimensional vector of minvalues to an m′-dimensional vector of supershingles by fingerprinting non-overlapping sequences of minvalues, and (v) concluding that two documents are near-duplicates if and only if their supershingle vectors agree in at least two supershingles (or, alternatively, if the two documents agree in at least one megashingle). The first document similarity technique might be any of the techniques described in the Broder paper introduced in �1.2.3 above or described in the Fetterly papers (D. Fetterly, M. Manasse, and M. Najork, �On the Evolution of Clusters of Near-Duplicate Web Pages,� 1st Latin American Web Congress, pp. 37-45 (November 2003); and D. Fetterly, M. Manasse, and M. Najork, �Detecting Phrase-Level Duplication on the World Wide Web,� 28th Annual International ACM SIGIR Conference (August 2005), both incorporated herein by reference). In such embodiments, the parameter m might be set to 84, the parameter l might be set to 14, the parameter m′ might be set to 6 and the parameter k might be set to any value from 5 to 10 (e.g., 8). Some embodiments consistent with the present invention might use the following parameter values: m=84; =14; m′=6; and k=some value from 5 to 10. Some embodiments consistent with the present invention might omit the wrapping of the shingling �window� from the end of the document, in which case (n−k+1) shingles are generated. If, on the other hand, the shingling window can wrap around from the end of the document to its beginning, n shingles are generated.
�4.3 CONCLUSIONS As can be appreciated from the foregoing, improved near-duplicate detection techniques are disclosed. These near-duplicate detection techniques performed well, particularly when analyzing Web pages from the same Website. These techniques did so without sacrificing much in the number of returned correct pairs.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5465299Nov 29, 1993Nov 7, 1995Hitachi, Ltd.Electronic document processing system and method of forming digital signatureUS5745900Aug 9, 1996Apr 28, 1998Digital Equipment CorporationMethod for indexing duplicate database records using a full-record fingerprintUS5778395Oct 23, 1995Jul 7, 1998Stac, Inc.System for backing up files from disk volumes on multiple nodes of a computer networkUS5850490Nov 17, 1995Dec 15, 1998Xerox CorporationAnalyzing an image of a document using alternative positionings of a class of segmentsUS5909677Jun 18, 1996Jun 1, 1999Digital Equipment CorporationMethod for determining the resemblance of documentsUS6052693Jul 2, 1996Apr 18, 2000Harlequin Group PlcSystem for assembling large databases through information extracted from text sourcesUS6088707Oct 6, 1997Jul 11, 2000International Business Machines CorporationComputer system and method of displaying update status of linked hypertext documentsUS6119124 *Mar 26, 1998Sep 12, 2000Digital Equipment CorporationMethod for clustering closely resembling data objectsUS6134532Nov 14, 1997Oct 17, 2000Aptex Software, Inc.System and method for optimal adaptive matching of users to most relevant entity and information in real-timeUS6230155Nov 23, 1998May 8, 2001Altavista CompanyMethod for determining the resemining the resemblance of documentsUS6240409Jul 31, 1998May 29, 2001The Regents Of The University Of CaliforniaMethod and apparatus for detecting and summarizing document similarity within large document setsUS6263348Jul 1, 1998Jul 17, 2001Serena Software International, Inc.Method and apparatus for identifying the existence of differences between two filesUS6285999Jan 9, 1998Sep 4, 2001The Board Of Trustees Of The Leland Stanford Junior UniversityMethod for node ranking in a linked databaseUS6349296Aug 21, 2000Feb 19, 2002Altavista CompanyMethod for clustering closely resembling data objectsUS6360215Nov 3, 1998Mar 19, 2002Inktomi CorporationMethod and apparatus for retrieving documents based on information other than document contentUS6363377Dec 22, 1998Mar 26, 2002Sarnoff CorporationSearch data processorUS6381601Dec 22, 1999Apr 30, 2002Hitachi, Ltd.Grouping and duplicate removal method in a databaseUS6505160May 2, 2000Jan 7, 2003Digimarc CorporationConnected audio and other media objectsUS6658423Jan 24, 2001Dec 2, 2003Google, Inc.Detecting duplicate and near-duplicate filesUS6665661Sep 29, 2000Dec 16, 2003Battelle Memorial InstituteSystem and method for use in text analysis of documents and recordsUS6850252Oct 5, 2000Feb 1, 2005Steven M. HoffbergIntelligent electronic appliance system and methodUS6871200 *Jul 11, 2002Mar 22, 2005Forensic Eye Ltd.Registration and monitoring systemUS6873982Jul 16, 1999Mar 29, 2005International Business Machines CorporationOrdering of database search results based on user feedbackUS6912505Mar 29, 2001Jun 28, 2005Amazon.Com, Inc.Use of product viewing histories of users to identify related productsUS6978419Nov 15, 2000Dec 20, 2005Justsystem CorporationMethod and apparatus for efficient identification of duplicate and near-duplicate documents and text spans using high-discriminability text fragmentsUS7366718Jun 27, 2003Apr 29, 2008Google, Inc.Detecting duplicate and near-duplicate filesUS7472121 *Dec 15, 2005Dec 30, 2008International Business Machines CorporationDocument comparison using multiple similarity measuresUS7739314Aug 15, 2005Jun 15, 2010Google Inc.Scalable user clustering based on set similarityUS20030061233Sep 21, 2001Mar 27, 2003Manasse Mark S.System and method for determining likely identity in a biometric databaseUS20040139072Jan 13, 2003Jul 15, 2004Broder Andrei Z.System and method for locating similar records in a databaseUS20040210575 *Apr 18, 2003Oct 21, 2004Bean Douglas M.Systems and methods for eliminating duplicate documentsUS20050165800 *Jan 26, 2004Jul 28, 2005Fontoura Marcus F.Method, system, and program for handling redirects in a search engineUS20060101060Sep 7, 2005May 11, 2006Kai LiSimilarity search system with compact data structuresUS20070038659Aug 15, 2005Feb 15, 2007Google, Inc.Scalable user clustering based on set similarityUS20080162478Mar 15, 2008Jul 3, 2008William PughDetecting duplicate and near-duplicate files* Cited by examinerNon-Patent CitationsReference1A. Broder et al., "Min-Wise Independent Permutations, Journal of Computer Systems and Sciences," vol. 60(3), pp. 630-659 (2000) (special issue for STOC '98), preliminary version in Proceedings of the 30th Annual ACM Symposium on Theory of Computing (1998).2Andoni et al., "Locality-sensitive hashing using stable distributions," Nearest Neighbor Methods in Learning and Vision: Theory and Practice, Darrell et al. (eds.), MIT Press, Cambridge, MA, in preparation, Chapter 4, pp. 55-67, 2006.3Andrei Z. Broder, "On the resemblance and containment of documents," Proc. of Compression and Complexity of Sequences 1997, pp. 21-29 (IEEE Computer Society), pp. 1-9.4Andrei Z. Broder, "Some applications of Rabin's fingerprinting method," R. Capocelli, A. DeSantis, U. Vaccaro, Eds; Sequences II: Methods in Communications, Security, and Computer Science, pp. 143-152 (Springer-Verlag, 1993).5Andrei Z. Broder, Steven C. Glassman, Mark S. Manasse, Geoffrey Swieg, "Syntactic Clustering of the Web," Proc. 6th Int'l. World Wide Web Conf., pp. 391-404 (Apr. 1997) and SRC Technical Note 1997-015 (Jul. 25, 1997), http://gatekeeper.dec.com/pub/DEC/SRC/technical-notes/SRC-1997-105-html/, Nov. 27, 2000, pp. 1-14.6Brin, S. et al, "The Anatomy of a Large-Scale Hypertextual Search Engine", Seventh International World Wide Web Conference, Apr. 14-18, 1998, Brisbane, Australia, 20 pgs.7Canadian Office Action for Application No. 2,660,202, dated Dec. 1, 2009, 3 pages.8Charikar et al., "Incremental Clustering and Dynamic Information Retrieval," STOC '97, 1997, El Paso, TX, pp. 626-635.9 *Charikar, Moses, "Similarity Estimation Techniques from Rounding Algorithms", 2002, pp. 380-388, obtained from ACM.10Chinese Office Action for Application No. 200780036634.0, dated May 18, 2010, 12 pgs.11Chinese Office Action issued for Application No. 200680038100.7, mailed Oct. 8, 2010, 9 pgs.12Chinese Office Action issued for Application No. 200780036634.0, mailed Nov. 30, 2010, 5 pgs.13Cohen, "Size-Estimation Framework with Applications to Transitive Closure and Reachability," J. Comput. System Sci., 1997, 55(3), pp. 441-453.14E. Cohen et al., "Finding Interesting Associations Without Support Pruning," 16th International Conference on Data Engineering (ICDE), 2000.15European Search Report in Application No. 06801549.4, mailed Dec. 8, 2010, 10 pages. 10 pgs.16Fetterly et al., "On the Evolution of Clusters of Near-Duplicate Web Pages", 9 pages, 2003.17Fetterly, M., et al., "Detecting Phrase-Level Duplication on the World Wide Web", 28th Annual International ACM SIGIR Conference, Aug. 2005, 8 pgs.18Haveliwala et al., "Scalable Techniques for Clustering the Web," Proceedings of WebDB, 2000, 6 pages.19Heintze, N., "Scalable Document Fingerprinting", Proc. of the 2nd USENIX Workshop on Electronic Commerce, Nov. 1996, 10 pgs.20Hoad, Timothy C. et al., "Methods for Identifying Versioned and Plagiarised Documents", RMIT University, School of Computer Science and Information Technology, 18 pages, 2003.21Indyk and Motwani, "Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality," Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998, 20 pages.22International Preliminary Report on Patentability for Application No. PCT/US2006/031868, mailed Apr. 30, 2009, 10 pages.23International Search Report and Written Opinion for Application No. PCT/US2006/031868, mailed Jul. 2, 2008, 14 pages.24Jeffrey Dean et al., "MapReduce: Simplified Data Processing on Large Clusters," OSDI, 2004.25M. Datar et al., "Locality-Sensitive Hashing Scheme Based on p-Stable Distributions," SCG'04, Jun. 9-11, 2004.26Manber, U., "Finding similar files in a large file system", Proc. of the USENIX Winter 1994 Technical Conference, Jan. 1994, 11 pgs.27Min Fang, Narayanan Shivakumar, Hector Garcia-Molina, Rajeev Motwanti, Jeffrey D. Ullman, "Computing Iceberg Queries Efficiently," Proc. 24th Int'l Conf. on Very Large Databases, pp. 299-310 (1998).28Papadimitriou et al., "Latent Semantic Indexing: A Probabilistic Analysis," PODS '98, (preliminary version) JCSS, special edition (full version), Nov. 14, 1997, 21 pages.29PCT/ISA/210, "International Search Report" for PCT/US07/17487, mailed Sep. 22, 2008 (2 pgs.)30PCT/ISA/220, "Notification of Transmittal of the International Search Report and the Written Opinion of the International Searching Authority, or the Declaration" for PCT/US07/17487, mailed Sep. 22, 2008 (1 pg.)31PCT/ISA/237, "Written Opinion of the International Searching Authority" for PCT/US07/17487, mailed Sep. 22, 2008 (9 pgs.)32Rabin, M., "Fingerprinting by random polynomials", Report TR-15-81, Center for Research in Computing Technology, Harvard University, 1981, 14 pgs.33Schwab and Kobsa, "Adaptivity through Unobtrusive Learning," 2002, 16(3), pp. 5-9.34Sergey Brin, James Davis, Hector Garcia-Molina, "Copy Detection Mechanisms for Digital Documents," Proc. of ACM SIGMOD Annual Conf. (San Jose, 1995), http://www-db.stanford.edu/~sergey/copy.html on Nov. 27, 2000, pp. 1-21.35Sergey Brin, James Davis, Hector Garcia-Molina, "Copy Detection Mechanisms for Digital Documents," Proc. of ACM SIGMOD Annual Conf. (San Jose, 1995), http://www-db.stanford.edu/�sergey/copy.html on Nov. 27, 2000, pp. 1-21.36Xiao et al., "Measuring Similarity of Interests for Clustering Web-Users," ADC, 2001, pp. 107-114.37Xie and Phoha, "Web User Clustering from Access Log Using Belief Function," K-CAP '01, Oct. 22-23, 2001, Victoria, British Columbia, Canada, pp. 202-208.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS8131751Dec 3, 2008Mar 6, 2012Google Inc.Algorithms for selecting subsequencesUS8594239 *Feb 21, 2011Nov 26, 2013Microsoft CorporationEstimating document similarity using bit-stringsUS20100198864 *Jul 2, 2008Aug 5, 2010Equivio Ltd.Method for organizing large numbers of documentsUS20120213313 *Feb 21, 2011Aug 23, 2012Microsoft CorporationEstimating document similarity using bit-stringsUS20120290678 *May 12, 2011Nov 15, 2012International Business Machines CorporationDynamic, user-driven service catalogUS20130018906 *Jul 11, 2011Jan 17, 2013Aol Inc.Systems and Methods for Providing a Spam Database and Identifying Spam Communications* Cited by examinerClassifications U.S. Classification707/692, 726/32, 707/749International ClassificationG06F7/02Cooperative ClassificationG06F17/2211, G06F17/3089European ClassificationG06F17/30W7Legal EventsDateCodeEventDescriptionApr 3, 2012CCCertificate of correctionJan 31, 2012CCCertificate of correctionNov 4, 2010ASAssignmentOwner name: GOOGLE INC., CALIFORNIAEffective date: 20060914Free format text: CORRECTIVE ASSIGNMENT TO CORRECT THE ASSIGNEE NAME FROM GOOGLE, INC. TO GOOGLE INC. PREVIOUSLY RECORDED ON REEL 018391 FRAME 0199. ASSIGNOR(S) HEREBY CONFIRMS THE CORRECT ASSIGNEE NAME IS GOOGLE INC;ASSIGNOR:HENZINGER, MONIKA H.;REEL/FRAME:025317/0163Oct 11, 2006ASAssignmentOwner name: GOOGLE, INC., CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:HENZINGER, MONIKA H.;REEL/FRAME:018391/0199Effective date: 20060914RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google