Source: http://www.google.com/patents/US7809695?dq=6948823
Timestamp: 2015-01-27 19:43:15
Document Index: 688635290

Matched Legal Cases: ['art 200', 'art 200', 'art 210', 'art 210', 'art 250', 'art 250', 'art 250', 'art 210', 'Application No. 200580035487']

Patent US7809695 - Information retrieval systems with duplicate document detection and ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsMany companies provide online search facilities that enable users to conduct computerized searches for documents. Unfortunately, these searches frequently provide results that include duplicate documents�that is, documents that are completely or substantially identical to each other. This problem is...http://www.google.com/patents/US7809695?utm_source=gb-gplus-sharePatent US7809695 - Information retrieval systems with duplicate document detection and presentation functionsAdvanced Patent SearchPublication numberUS7809695 B2Publication typeGrantApplication numberUS 11/122,577Publication dateOct 5, 2010Filing dateMay 5, 2005Priority dateAug 23, 2004Fee statusPaidAlso published asCA2578157A1, CN101076800A, CN101076800B, EP1805661A1, US20060041597, WO2006023941A1Publication number11122577, 122577, US 7809695 B2, US 7809695B2, US-B2-7809695, US7809695 B2, US7809695B2InventorsJack G. Conrad, Joanne R. S. Claussen, Jie LinOriginal AssigneeThomson Reuters Global ResourcesExport CitationBiBTeX, EndNote, RefManPatent Citations (20), Non-Patent Citations (58), Referenced by (6), Classifications (8), Legal Events (4) External Links: USPTO, USPTO Assignment, EspacenetInformation retrieval systems with duplicate document detection and presentation functionsUS 7809695 B2Abstract Many companies provide online search facilities that enable users to conduct computerized searches for documents. Unfortunately, these searches frequently provide results that include duplicate documents�that is, documents that are completely or substantially identical to each other. This problem is particularly vexing when searching news stories, for example. Moreover, the duplicate documents are intermixed in the search results, leaving users to manually manage the complexities of identifying and/or filtering them. Accordingly, the present inventors devised systems, methods, and software that facilitate the identification and/or grouping of duplicate documents in search results. One exemplary system includes a signature generation module which generates document signatures based on length, temporal, and/or content components; a real-time duplicate detection module which uses the document signatures to identify �exact� or �fuzzy� duplicate documents; and a user-interface or presentation module which controls how duplicate documents are presented or suppressed in search results.
RELATED APPLICATIONS This application claims priority to U.S. Provisional Application 60/603,762 which was filed on Aug. 23, 2004, and to U.S. Provisional Application 60/623,975, which was filed on Nov. 1, 2004. Both these applications are incorporated herein by reference.
COPYRIGHT NOTICE AND PERMISSION A portion of this patent document contains material subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyrights whatsoever. The following notice applies to this document: Copyright�2004, West Services, Inc.
TECHNICAL FIELD Various embodiments of the present invention concern information-retrieval systems, such as those that provide news documents or other related content.
BACKGROUND Companies, such as Thomson Legal & Regulatory, Inc. of St. Paul, Minn. (doing business as Thomson West), collect and store a vast spectrum of documents, including news, from all over the world, for online access in a system of databases and research tools, known as the Westlaw� system. The Westlaw system empowers users to search over 100 million documents.
SUMMARY To address this and other needs, the present inventors devised systems, methods, and software that facilitate the identification and/or grouping of duplicate documents in search results. One exemplary system includes three major components: 1) a signature generation module which generates document signatures based on length, temporal, and/or content components; 2) a duplicate detection module which uses the document signatures to identify �exact� or �fuzzy� duplicate documents; and 3) a user-interface (or presentation) module which allows users to control how duplicate documents are presented in their search results. For instance, users can select whether to exclude duplicates from their search results or to group duplicates together in the results presentation. In some embodiments, the identification and grouping ultimately streamline the process of users interpreting and accessing search results that contain duplicate documents.
Exemplary Definitions The description includes many terms with meanings derived from their usage in the art or from their use within the context of the description. However, as a further aid, the following exemplary definitions are presented.
Exemplary Information Retrieval System FIG. 1 shows an exemplary online information-retrieval system 100. System 100 includes one or more databases 110, one or more servers 120, and one or more access devices 130.
Exemplary Methods of Operation FIG. 2 shows a flow chart 200 of one or more exemplary methods of operating a system, such as system 100. Flow chart 200 includes blocks 210-270, which, like other blocks in this description, are arranged and described in a serial sequence in the exemplary embodiment. However, some embodiments execute two or more blocks in parallel using multiple processors or processor-like devices or a single processor organized as two or more virtual machines or sub processors. Some embodiments also alter the process sequence or provide different functional partitions to achieve analogous results. For example, some embodiments may alter the client-server allocation of functions, such that functions shown and described on the server side are implemented in whole or in part on the client side, and vice versa. Moreover, still other embodiments implement the blocks as two or more interconnected hardware modules with related control and data signals communicated between and through the modules. Thus, the exemplary process flow (in FIG. 2 and elsewhere in this description) applies to software, hardware, and firmware implementations.
Exact Signature Generation More particularly, flow chart 210A, which yields a signature having a length scalar and a fingerprint (for example, a hash value), includes process blocks 211A-216A. The process begins at block 211A which entails determining one or more document length features or values. To this end, the exemplary embodiment determines a length scalar, which is defined as the document length in tokens, excluding newspaper, title, author and other header information.
Fuzzy Signature Generation Flow chart 210B�which shows generation of a document signature data structure (or characteristic feature set) based on document temporal, length, and content components�includes process blocks 211B-215B.
Exact Duplicate Detection In flow chart 250A, the exemplary method begins at block 251A, which entails selecting two or more documents of the search results for comparison. In the exemplary embodiment, this entails retrieving document signature data structures for each document in the search results based on their document identifiers and defining a number of document pairs for real-time duplicate detection or comparison. Defining the document pairs entails selecting a primary document and pairing the primary document (or more precisely its document signature) with each of the other documents in the search results, then selecting a second primary document and pairing it with all other documents with which it has not already been paired. Similarly, each document can be selected as a primary document and paired with all other documents with which it has not already been paired, ultimately defining a complete set of unique document pairings for comparison. (In some embodiments, the primary documents are selected in order of their relevance ranking within the search results. Also, some embodiments restrict application of the duplicate detection process to documents that exceed a certain relevance threshold or that have a certain minimum ranking.) Execution then advances to block 252A.
Fuzzy Duplicate Detection Flow chart 250B depicts an alternative detection process, which generally entails a real-time multilevel processing of the signature data structures for the documents identified in the search results. (Some embodiments may perform duplicate detection prior to, rather than in response to a user query.) Flow chart 250B includes process blocks 251B-255B.
Exemplary Options-Control Interface FIG. 8 shows an exemplary options-control interface 800, which functions as a portion of interface 138 in FIG. 1 and allows users to set values for preferences in subscriber database 123, such as those related to duplicate processing and/or presentation. In the exemplary embodiment, interface 800 includes an identify-duplicates control feature 810, duplicate-inclusion-or-exclusion control features 820, primary-duplicate-selection features 830, and a save-command feature 840.
Use of Temporal and Length Bins Some embodiments integrate the temporal and length comparison of blocks 252B and 253B (in FIG. 2) by defining sets or bins of potentially duplicate documents. For example, some embodiments retrieve a set of corresponding signature data structures as defined in flow chart 210B from signature database 124 and sort them in reverse chronological order based on their respective temporal components.
CONCLUSION In furtherance of the art, the present inventors have not only recognized a need to effectively address how information-retrieval systems handle the existence of duplicate documents in their document collections, but also presented herein systems, methods, and software that facilitate the identification and/or grouping of duplicate documents in search results, in accordance with user preferences. This identification and grouping ultimately streamline the process of users accessing and reviewing search results that contain duplicate documents.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5488725 *Mar 30, 1993Jan 30, 1996West Publishing CompanySystem of document representation retrieval by successive iterated probability samplingUS5826260 *Dec 11, 1995Oct 20, 1998International Business Machines CorporationInformation retrieval system and method for displaying and ordering information based on query element contributionUS5913208 *Jul 9, 1996Jun 15, 1999International Business Machines CorporationIdentifying duplicate documents from search results without comparing document contentUS6138113 *Aug 10, 1998Oct 24, 2000Altavista CompanyMethod for identifying near duplicate pages in a hyperlinked databaseUS6654739Jan 31, 2000Nov 25, 2003International Business Machines CorporationLightweight document clusteringUS6658423 *Jan 24, 2001Dec 2, 2003Google, Inc.Detecting duplicate and near-duplicate filesUS6757675 *Feb 12, 2003Jun 29, 2004The Regents Of The University Of CaliforniaMethod and apparatus for indexing document content and content comparison with World Wide Web search serviceUS6785669 *Mar 8, 2000Aug 31, 2004International Business Machines CorporationMethods and apparatus for flexible indexing of text for use in similarity searchesUS6978419 *Nov 15, 2000Dec 20, 2005Justsystem CorporationMethod and apparatus for efficient identification of duplicate and near-duplicate documents and text spans using high-discriminability text fragmentsUS7013310 *Jan 3, 2002Mar 14, 2006Cashedge, Inc.Method and apparatus for retrieving and processing dataUS7139756 *Jan 22, 2002Nov 21, 2006International Business Machines CorporationSystem and method for detecting duplicate and similar documentsUS7264274 *Jun 22, 2005Sep 4, 2007Delphi Technologies, Inc.Tuneable energy absorbing mounting structure for steering columnUS20020161788 *Mar 19, 2001Oct 31, 2002Mcdonald David T.System and method for efficiently processing messages stored in multiple message storesUS20020174101 *Jul 9, 2001Nov 21, 2002Fernley Helen Elaine PenelopeDocument retrieval systemUS20030172063Mar 7, 2002Sep 11, 2003Koninklijke Philips Electronics N.V.Method and apparatus for providing search results in response to an information search requestUS20040093323 *Nov 7, 2002May 13, 2004Mark BluhmElectronic document repository management and access systemUS20050060643 *Aug 12, 2004Mar 17, 2005Miavia, Inc.Document similarity detection and classification systemEP0513652A2May 6, 1992Nov 19, 1992Siemens AktiengesellschaftMethod for modelling similarity function using neural networkWO2003075181A2Feb 19, 2003Sep 12, 2003Koninkl Philips Electronics NvA method and apparatus for providing search results in response to an information search requestWO2006023941A1Aug 23, 2005Mar 2, 2006West Services IncDuplicate document detection and presentation functions* Cited by examinerNon-Patent CitationsReference1"Australian Application Serial No. 2005277039, Examiner Report mailed Jun. 5, 2008", 2 pgs.2"European Application Serial No. 05792821.0, Office Action mailed Apr. 21, 2009", 5 pgs.3"International Application Serial No. PCT/US2005/030024, International Preliminary Report on Patentability mailed Nov. 13, 2006", 8 pgs.4"International Application Serial No. PCT/US2005/030024, International Search Report and Written Opinion mailed Dec. 16, 2005", 12 pgs.5"International Search Report for corresponding PCT Application No. PCT/US2005/030024", (Dec. 16, 2005),4 pgs.6"New Zealand Application Serial No. 553567, Examiner Report Mailed Nov. 13, 2008", 1 pgs.7"Secure Hash Standard", Federal Information Processing Standards Publication 180-1, U.S. Department of Commerce/National Institute of Standards and Technology, (Apr. 17, 1995), 18 pgs/.8Brin, S., et al., "Copy Detection Mechanisms for Digital Documents", Proceedings of the Special Interest Group on Management of Data (SIGMOD '95), (May, 1995), 398-409.9Brin, S., et al., "The Anatomy of a Large-Scale Hypertextual Web Search Engine" Proceedings of the Seventh International World Wide Web Conference (WWW7 '98), (Apr. 1998), 107-117.10Broder, A. Z., et al., "Syntactic Clustering of the Web", Proceedings of the Sixth International World Wide Web Conference (WWW6 '97), (Apr. 1997), 1157-1166.11Burgin, R., "Variations in Relevance Judgments and the Evaluation of Retrieval Performance", Information Processing and Management, 26(5), (1992), 619-627.12Callan, J., et al., "Query-Based Sampling of Text", ACM Transactions on Information Systems (TOIS), 19(2), (Apr. 2001), 97-130.13Carletta, J., "Assessing Agreement on Classification Tasks: The Kappa Statistic", Computational Linguistics, 22(2), (1996), 249-254.14Chinese Application No. 200580035487.6, Office Action Mailed Jan. 9, 2009, 15 pgs.15Chinese Application Serial No. 200580035487.6, Office Action Mailed Aug. 21, 2009, 6 pgs.16Chowdhury, A., et al., "Collection Statistics for Fast Duplicate Document Detection", ACM Transactions on Information Systems (TOIS), 20(2), (Apr. 2002), 171-191.17Cleverdon, C. D., "The Effect of Variations in Relevance Assessments in Comparative Experimental Tests of Index Languages", Technical Report, Cranfield Library Report No. 3, Cranfield Institute of Technology, Cranfield, UK, (Oct. 1970), 53 pgs.18Conrad, J. G., et al., "Constructing a Text Corpus for Inexact Duplicate Detection", SIGIR '04, Jul. 25-29, 2004; Sheffield, South Yorkshire, UK, (Jul. 2004), 2 pgs.19Conrad, J. G., et al., "Managing D�j� Vu: Collection Building for the Identification of Non-Identical Duplicate Documents", CIKM '04, Nov. 8-13, 2004; Washington, DC,(Nov. 2004),9 pgs/.20Conrad, J. G., et al., "Online Duplicate Document Detection: Signature Reliability in a Dynamic Retrieval Environment", Proceedings of the 12th International Conference on Information and Knowledge Management (CIKM'03), (Nov. 2003), 443-452.21Cooper, J. W., et al., "Detecting Similar Documents Using Salient Terms", Proceedings of the 11th International Conference on Information and Knowledge Management (CIKM '02), (Nov. 2002), 245-251.22Cormack, G. V., et al., "Efficient Construction of Large Test Collections", Proceedings of the 21st International Conference on Research and Development in Information Retrieval (SIGIR '98), (Aug. 1998), 282-289.23Frieder, O. , et al., "On Scalable Information Retrieval Systems", Computer society, Proceedings of the Second IEEE International Symposium on Network Computing and Application (NCA'03), (Apr. 16, 2003), 241-245.24Frieder, O., et al., "Efficiency Considerations for Scalable Information Retrieval Servers", Journal of Digital Information, 1(5), (Jan. 2000), 1-26.25Harter, S. P., "Variations in Relevance Assessments and the Measurement of Retrieval Effectiveness", Journal of the American Society for Information Science, 47(1), (1996), 37-49.26Hawking, D., et al., "Overview of TREC-8 Web Track", The Eighth Text Retrieval Conference (TREC 8), (Feb. 2000), 131-148.27Heintze, N., et al., "Scalable Document Fingerprinting (Extended Abstract)", Proceedings of the Second USENIX Electronic Commerce Workshop, (Nov. 1996), 191-200.28Hersh, W., et al., "OHSUMED: An Interactive Retrieval Evaluation and New Large Test Collection for Research", Proceedings of the 17th International Conference on Research and Development in Information Retrieval (SIGIR '94), (Jul. 1994), 192-201.29Hoppenbrouwers, J., et al., "Invading the Fortress: How to Besiege Reinforced Information Bunkers", IEEE Proceedings, Advances in Digital Libraries, (May 22, 2000), 27-35.30Japanese Application Serial No. 2007-530061, Office Action Mailed Oct. 23, 2009, 8 pgs.31Jones, K. S., et al., "Information Retrieval Test Collections", Journal of Documentation, 32(1), (Mar. 1976), 59-75.32Jones, K. S., et al., "Report on the Need for and Provision of an 'Ideal' Information Retrieval Test Collection", British Library Research and Development Report 5266, Computer Laboratory, University of Cambridge, (1975), 1-42.33Jones, K. S., et al., "Report on the Need for and Provision of an �Ideal� Information Retrieval Test Collection", British Library Research and Development Report 5266, Computer Laboratory, University of Cambridge, (1975), 1-42.34Manber, U., "Finding Similar Files in a Large File System", USENIX Winter 1994 Technical Conference Proceedings (USENIX '94), (Jan. 1994), 1-10.35Marcu, D., "The Automatic Construction of Large-Scale Corpora for Summarization Research", Proceedings of the 22nd International Conference on Research and Development in Information Retrieval (SIGIR '99), (Aug. 1999), 137-144.36Miller, C. , et al., "Detecting Duplicates: A Researcher's Dream Come True", Online, 14(4), (Jul. 1990), 27-34.37Mishra, R. K., et al., "KhojYantra: An Integrated MetaSearch Engine with Classification, Clustering and Ranking", Database Engineering and Applications, Symposium 2000, (Sep. 18, 2000), 122-131.38Mitchell, T. M., "Contents", Machine Learning, WCB/ McGraw-Hill, (1997), 9 pgs.39Moroney, M. J., Facts from Figures, Harmondsworth [Eng.] ; Baltimore : Penguin Books, 3rd Edition, (1956), 334-370.40Park, S. T., et al., "Analysis of Lexical Signatures for Fnding Lost or Related Documents", Proceedings of the 25th International Conference on Research and Development in Information Retrieval (SIGIR '02), (Aug. 2002), 11-18.41Phelps, T. A., et al., "Robust Hyperlinks: Cheap, Everywhere, Now", Proceedings of the 8th International Conference on Digital Documents and Electronic Publishing (DDEP '00), (Sep. 2000), 28-43.42Press, W. H., et al., Numerical Recipes in C: The Art of Scientific Computing, Cambridge University Press, New York, NY, 2nd Edition, (1992), 504-510.43Rose, T., et al., "The Reuters Corpus vol. 1-From Yesterday's News to Tomorrow's Language Resources", Proceedings of the 3rd International Conference on Language Resources and Evaluation (LREC '02), (May 2002), 7 pgs.44Rose, T., et al., "The Reuters Corpus vol. 1�From Yesterday's News to Tomorrow's Language Resources", Proceedings of the 3rd International Conference on Language Resources and Evaluation (LREC '02), (May 2002), 7 pgs.45Sanderson, M., "Duplicate Detection in the Reuters Collection", Technical Report (TR-1997-5), (1997), 1-11.46Saracevic, T., "Users Lost: Reflections on the Past, Present, Future, and Limits of Information Science", Proceedings of the 20th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR '97), (Jul. 1997), 1-2.47Sheridan, P., et al., "Building a Large Multilingual Test Collection From Comparable News Documents", Workshop on Cross-Lingual Information Retrieval (SIGIR '97), (Aug. 1996), 56-65.48Shrivakumar, N. , et al., "Finding Near-Replicas of Documents on the Web", Proceedings of Workshop on Web Databases (WebDB '98), (Mar. 1998), 204-212.49Siegel, S., et al., Nonparametric Statistics for the Behavioral Sciences, McGraw Hill, Boston, MA, (1988), 284-289.50Soboroff, Ian , et al., "Building a Filtering Test Collection for TREC 2002", Proceedings of the 26th International Conference on Research and Development in Information Retrieval (SIGIR '03), (Jul.-Aug. 2003), 243-250.51Tenopir, C., et al., "Target & Freestyle: Dialog and Mead Join the Relevance Rank", Online, 18(3), (1994), 31-47.52Thompson, P. , et al., "TREC-3 Ad Hoc Experiments Using the WIN System", Proceedings of TREC-3, (1995), 211-217.53Tonella, P., et al., "Using Keyword Extraction for Web Site Clustering", Computer Society, Proceedings of the Ffifth IEEE International Workshop on Web Site Evolution (WSE'03), (Sep. 22, 2003), 41-48.54Turtle, H. , et al., "Natural Language vs. Boolean Query Evaluation: A Comparison of Retrieval Performance", Proceedings of the 17th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR '94), (Jul. 1994), 212-221.55Turtle, H. R., "Inference Networks for Document Retrieval", PhD Thesis, Computer and Information Science Department, University of Massachusetts,(Oct. 1991), 214 pgs.56Voorhees, E. M., "Overview of the Sixth Text REtrieval Conference (TREC-6).", Information Processing and Management, 36(1), (Jan. 2000), 3-35.57Voorhees, E. M., "Variations in Relevance Judgments and the Measurement of Retrieval Effectiveness", Information Processing and Management, 36(5), (Sep. 2000), 697-716.58Zhang, Yi , et al., "Novelty and Redundancy Detection in Adaptive Filtering", Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR '02), (Aug. 2002), 81-88.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS8185504 *Jul 10, 2008May 22, 2012Canon Kabushiki KaishaImage processing apparatus and image processing methodUS8250072 *Mar 4, 2010Aug 21, 2012Dmitri AsonovDetecting real word typosUS8301637 *Jul 25, 2008Oct 30, 2012Seiko Epson CorporationFile search system, file search device and file search methodUS20090019074 *Jul 10, 2008Jan 15, 2009Canon Kabushiki KaishaImage processing apparatus and image processing methodUS20100228729 *Mar 4, 2010Sep 9, 2010Dmitri AsonovDetecting Real Word TyposUS20110015921 *Jul 19, 2010Jan 20, 2011Minerva Advisory Services, LlcSystem and method for using lingual hierarchy, connotation and weight of authority* Cited by examinerClassifications U.S. Classification707/692, 707/729, 707/730International ClassificationG06F7/00Cooperative ClassificationG06F17/30864, G06F17/3061European ClassificationG06F17/30T, G06F17/30W1Legal EventsDateCodeEventDescriptionMar 26, 2014FPAYFee paymentYear of fee payment: 4Oct 6, 2008ASAssignmentOwner name: THOMSON REUTERS GLOBAL RESOURCES, SWITZERLANDFree format text: CHANGE OF NAME;ASSIGNOR:THOMSON GLOBAL RESOURCES;REEL/FRAME:021630/0917Effective date: 20080603Feb 8, 2007ASAssignmentOwner name: THOMSON GLOBAL RESOURCES, SWITZERLANDFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:WEST SERVICES INC;REEL/FRAME:018878/0682Effective date: 20061009May 5, 2005ASAssignmentOwner name: WEST SERVICES, INC., MINNESOTAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:CONRAD, JACK G.;CLAUSSEN, JOANNE R.S.;LIN, JIE;REEL/FRAME:016540/0747Effective date: 20050504RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services