Source: http://www.google.com/patents/US7580921?dq=4182933
Timestamp: 2016-09-26 05:54:43
Document Index: 258949923

Matched Legal Cases: ['Application No. 200510085373', 'Application No. 200510085370', 'Application No. 200510085371', 'Application No. 200510085372', 'Application No. 2005203237', 'Application No. 2005203238', 'Application No. 2005203239', 'Application No. 2005203240']

Patent US7580921 - Phrase identification in an information retrieval system - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsAn information retrieval system uses phrases to index, retrieve, organize and describe documents. Phrases are identified that predict the presence of other phrases in documents. Documents are the indexed according to their included phrases. Related phrases and phrase extensions are also identified. Phrases...http://www.google.com/patents/US7580921?utm_source=gb-gplus-sharePatent US7580921 - Phrase identification in an information retrieval systemAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS7580921 B2Publication typeGrantApplication numberUS 10/900,021Publication dateAug 25, 2009Filing dateJul 26, 2004Priority dateJul 26, 2004Fee statusPaidAlso published asCA2513850A1, CA2513850C, CN1728142A, CN1728142B, DE602005026609D1, EP1622053A1, EP1622053B1, US7603345, US8078629, US20060018551, US20060294155, US20110131223Publication number10900021, 900021, US 7580921 B2, US 7580921B2, US-B2-7580921, US7580921 B2, US7580921B2InventorsAnna Lynn PattersonOriginal AssigneeGoogle Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (109), Non-Patent Citations (47), Referenced by (55), Classifications (11), Legal Events (4) External Links: USPTO, USPTO Assignment, EspacenetPhrase identification in an information retrieval system
US 7580921 B2Abstract
1. A computer implemented method for identifying phrases in a document collection, the method comprising:
collecting possible phrases from documents in the document collection;
classifying individual possible phrases as either a good phrase or a bad phrase according to a frequency of occurrence of the individual possible phrase;
determining, for a pair of good phrases gj and gk in the document collection, an information gain of gk with respect to gj as a function of an actual co-occurrence rate of gj and gk and an expected co-occurrence rate of gj and gk in the document collection;
selectively retaining as valid phrases those good phrases that, predict the occurrence of at least one other good phrase in the document collection, where a good phrase gj predicts the occurrence of another good phrase gk in the document collection when the determined information gain of gk in the presence of gj exceeds a first predetermined threshold;
identifying, for a plurality of selectively retained valid phrases gx, a phrase gy as a related phrase of gx where the information gain of gy in the presence of gx exceeds a second predetermined threshold that is more restrictive than the first predetermined threshold; and
storing the valid phrases and identified related phrases on a computer-readable storage medium.
2. The method of claim 1, wherein collecting possible phrases comprises:
traversing the words of a document with a multiword phrase window, and selecting as candidate phrases all sequences of words in the window that begin with a first word in the window.
3. The method of claim 2, wherein the phrase window includes at least 4 words.
4. The method of claim 1, wherein collecting possible phrases comprises:
maintaining for each possible phrase and each good phrase a frequency count of a number of documents containing the phrase;
maintaining for each possible phrase and each good phrase a frequency count of a number of instances of the phrase; and
maintaining for each possible phrases and each good phrase a frequency count of a number of distinguished instances of the phrase.
5. The method of claim 4, wherein a distinguished instance of a phrase comprises a phrase distinguished from neighboring content in the document by grammatical or format markers.
6. The method of claim 1, wherein classifying each possible phrase as either a good phrase or a bad phrase comprises:
classifying a possible phrase as a good phrase where the possible phrase appears in a minimum number of documents, and appears a minimum number of instances in the document collection.
7. The method of claim 1, wherein classifying each possible phrase as either a good phrase or a bad phrase comprises:
classifying a possible phrase as a good phrase where the possible phrase appears in a minimum number of distinguished instances in the document collection.
8. The method of claim 1, wherein the first predetermined threshold is 1.
9. The method of claim 1, wherein the information gain of gj with respect to gk is:
A(j,k) is an actual co-occurrence rate of gj and gk; and
E(j,k) is an expected co-occurrence rate gj and gk.
10. The method of claim 9, wherein good phrases gj and gk co-occur in a document when gj and gk are within a predetermined number of words of each other.
11. The method of claim 1, wherein retaining good phrases that predict the occurrence of at least one other good phrase in the document collection comprises:
removing a good phrase having an information gain with respect to a plurality of other good phrases less than a predetermined threshold.
removing incomplete phrases from the good phrases.
13. The method of claim 12, wherein an incomplete phrase is a phrase that only predicts its phrase extensions, and wherein a phrase extension of a phrase is a super-sequence of the phrase that begins with the phrase.
maintaining for each incomplete phrase at least one phrase extension of the incomplete phrase; and
responsive to a phrase in a search query being an incomplete phrase, including in the search query at least one phrase extension of the incomplete search phrase.
15. The method of claim 1, wherein the second predetermined threshold is about 100.
for each phrase gx, identifying a cluster comprising the phrase and at least one related phrase gy.
for each phrase gx, identifying a set R including a plurality of related phrases;
determining for each pair of related phrases in set R an information gain of the pair of related phrases; and
identifying as a cluster of related phrases of gx, phrase gx, and each related phrase in set R that has non-zero information gain with respect to each other phrase in set R.
assigning each cluster a unique cluster number as a function of the related phrases included in the cluster.
assigning to the cluster a name comprising the related phrase having a highest information gain of the related phrases in the cluster.
for a phrase gj, storing a bit vector in which each bit position corresponds to a valid phrase, and the bit corresponding to the bit position indicates whether the valid phrase is a related phrase of gj.
21. A computer program product, for identifying phrases in a document collection, comprising computer operable instructions stored on a computer-readable storage medium and configured to control a processor to perform the operation of:
classifying individual possible phrases as either a good phrase or a bad phrase according to a frequency of occurrence of the possible phrase;
selectively retaining as valid phrases those good phrases that predict the occurrence of at least one other good phrase in the document collection, where a good phrase gj predicts the occurrence of another good phrase gk in the document collection when the determined information gain of gk in the presence of gj exceeds a first predetermined threshold;
storing the selectively retained good phrases on a computer-readable storage medium.
22. The computer program product of claim 21, wherein the information gain of gj with respect to gk is defined as I(j,k)=A(j,k)/E(j,k), where A(j,k) is an actual co-occurrence rate of gj and gk, and E(j,k) is an expected co-occurrence rate of gj and gk.
23. A computer implemented method for indexing documents in a document collection, the method comprising:
classifying each possible phrase as either a good phrase or a bad phrase according to a frequency of occurrence of the possible phrase;
storing as valid phrases, on a computer-readable storage medium, only good phrases that predict the occurrence of at least one other good phrase in the document collection where a good phrase gj predicts the occurrence of another good phrase gk in the document collection when the determined information gain of gk in the presence of gj exceeds a first predetermined threshold;
indexing documents in the document collection with respect to the valid phrases and the related phrases.
24. The method of claim 23, wherein the information gain of gk with respect to gj is defined as I(j,k)=A(j,k)/E(j,k), where A(j,k) is an actual co-occurrence rate of gj and gk, and E(j,k) is an expected co-occurrence rate of gj and gk.
25. The method of claim 23, wherein collecting possible phrases comprises:
maintaining for each possible phrases and each good phrase a frequency count of a number of distinguished instances of the phrase, a distinguished instance of the phrase comprising the phrase distinguished from neighboring content in the document by grammatical or format markers. Description
“Phrase-Based Indexing in an Information Retrieval System,” application Ser. No. 10/900,055, filed on Jul. 26, 2004; “Phrase-Based Searching in an Information Retrieval System,”application Ser. No. 10/900,041, filed on Jul. 26, 2004; “Phrase-Based Personalization of Searches in an Information Retrieval System,” application Ser. No. 10/900,039, filed on Jul. 26, 2004; “Automatic Taxonomy Generation in Search Results Using Phrases,” application Ser. No. 10/900,259, filed on Jul. 26, 2004; “Phrase-Based Generation of Document Descriptions,” application Ser. No. 10/900,075, filed on Jul. 26, 2004; and “Phrase-Based Detection of Duplicate Documents in an Information Retrieval System,” application Ser. No. 10/900,012, filed on Jul. 26, 2004, all of which are co-owned, and incorporated by reference herein. FIELD OF THE INVENTION
The problem here is that conventional systems index documents based on individual terms, than on concepts. Concepts are often expressed in phrases, such as “Australian Shepherd,” “President of the United States,” or “Sundance Film Festival”. At best, some prior systems will index documents with respect to a predetermined and very limited set of ‘known’ phrases, which are typically selected by a human operator. Indexing of phrases is typically avoided because of the perceived computational and memory requirements to identify all possible phrases of say three, four, or five or more words. For example, on the assumption that any five words could constitute a phrase, and a large corpus would have at least 200,000 unique terms, there would approximately 3.2�1026 possible phrases, clearly more than any existing system could store in memory or otherwise programmatically manipulate. A further problem is that phrases continually enter and leave the lexicon in terms of their usage, much more frequently than new individual words are invented. New phrases are always being generated, from sources such technology, arts, world events, and law. Other phrases will decline in usage over time.
In addition the various lists, a co-occurrence matrix 212 (G) for the good phrases is maintained. The matrix G has a dimension of m�m, where m is the number of good phrases. Each entry G(j,k) in the matrix represents a pair of good phrases (gj, gk). The co-occurrence matrix 212 logically (though not necessarily physically) maintains three separate counts for each pair (gj,gk) of good phrases with respect to a secondary window 304 that is centered at the current word i, and extends +/−h words. In one embodiment, such as illustrated in FIG. 3, the secondary window 304 is 30 words. The co-occurrence matrix 212 thus maintains:
C(j,k): Conjunctive Interesting count: the number of times that both gj and phrase gk appear as distinguished text in a secondary window. The use of the conjunctive interesting count is particularly beneficial to avoid the circumstance where a phrase (e.g.,a copyright notice) appears frequently in sidebars, footers, or headers, and thus is not actually predictive of other text.
It should be noted that the good phrase list 208 will naturally include individual words as phrases, in addition to multi-word phrases, as described above. This is because each the first word in the phrase window 302 is always a candidate phrase, and the appropriate instance counts will be accumulated. Thus, the indexing system 110 can automatically index both individual words (i.e., phrases with a single word) and multiple word phrases. The good phrase list 208 win also be considerably shorter than the theoretical maximum based on all possible combinations of m phrases. In typical embodiment, the good phrase list 208 will include about 6.5�105 phrases. A list of bad phrases is not necessary to store, as the system need only keep track of possible and good phrases.
First, recall that the co-occurrence matrix 212 contains good phrases gj, each of which predicts at least one other good phrase gk with an information gain greater than the information gain threshold. To identify 400 related phrases then, for each pair of good phrases (gj,gk) the information gain is compared with a Related Phrase threshold, e.g., 100. That is, gj and gk are related phrases where:
Accordingly, any entry (gj,gk) that is less the Related Phrase threshold is zeroed out, indicating that the phrases gj, gk are not related. Any remaining entries in the co-occurrence matrix 212 now indicate all related phrases.
The columns gk in each row gj of the co-occurrence matrix 212 are then sorted by the information gain values I(gj,gk), so that the related phrase gk with the highest information gain is listed first. This sorting thus identifies for a given phrase gj, which other phrases are most likely related in terms of information gain.
For each related phrase m in Rj, the indexing system 110 determines if each of the other related phrases in R is also related to gj. Thus, if I(gk,gl) is also non-zero, then gj, gk, and gl are part of a cluster. This cluster test is repeated for each pair (gl, gm) in R.
For example, assume the good phrase “Bill Clinton” is related to the phrases “President”, “Monica Lewinsky”, because the information gain of each of these phrases with respect to “Bill Clinton” exceeds the Related Phrase threshold. Further assume that the phrase “Monica Lewinsky” is related to the phrase “purse designer”. These phrases then form the set R. To determine the clusters, the indexing system 110 evaluates the information gain of each of these phrases to the others by determining their corresponding information gains. Thus, the indexing system 110 determines the information gain I(“President”,“Monica Lewinsky”), I(“President”, “purse designer”), and so forth, for all pairs in R. In this example, “Bill Clinton,” “President”, and “Monica Lewinsky” form a one cluster, “Bill Clinton,” and “President” form a second cluster, and “Monica Lewinsky” and “purse designer” form a third cluster, and “Monica Lewinsky”, “Bill Clinton,” and “purse designer” form a fourth cluster. This is because while “Bill Clinton” does not predict “purse designer” with sufficient information gain, “Monica Lewinsky” does predict both of these phrases.
For each good phrase gi (example g1 “President” and g4 “President of ATT”) post the document identifier (e.g.,the URL) to the posting list for the good phrase gi in the index 150. This update identifies that the good phrase gi appears in this specific document.
In one embodiment, the related phrase information is a related phase bit vector. This bit vector may be characterized as a “bi-bit” vector, in that for each related phrase gk there are two bit positions, gk−1, gk−2. The first bit position stores a flag indicating whether the related phrase gk is present in the document d (i e.,the count for gk in document d is greater than 0). The second bit position stores a flag that indicates whether a related phrase gl of gk is also present in document d. The related phrases gl of a related phrase gk of a phrase gj are herein called the “secondary related phrases of gj” The counts and bit positions correspond to the canonical order of the phrases in R (sorted in order of decreasing information gain). This sort order has the effect of making the related phrase gk that is most highly predicted by gj associated with the most significant bit of the related phrase bit vector, and the related phrase gl that is least predicted by gj associated with the least significant bit.
Given each query phrase Q, there will be some number N of related phrases Qr to the query phrase, as identified during the phrase identification process. As described above, the related query phrases Qr are ordered according to their information gain from the query phrase Q. These related phrases are then assigned points, started with N points for the first related phrase Qr1 (i.e., the related phrase Qr with the highest information gain from Q), then N-1 points for the next related phrase Qr2, then N-2 points for Qr3, and so on, so that the last related phrase QrN is assigned 1 point.
In large corpuses such as the Internet, it is quite common for there to be multiple instances of the same document, or portions of a document in many different locations. For example, a given news article produced by a news bureau such as the Associated Press, may be replicated in a dozen or more websites of individual newspapers. Including all of these duplicate documents in response to a search query only burdens the user with redundant information, and does not usefully respond to the query. Thus, the presentation system 130 provides a further capability 704 to identify documents that are likely to be duplicates or near duplicates of each other; and only include one of these in the search results. Consequently, the user receives a much more diversified and robust set of results, and does not have to waste time reviewing documents that are duplicates of each other. The presentation system 130 provides the functionality as follows.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5321833Aug 29, 1990Jun 14, 1994Gte Laboratories IncorporatedAdaptive ranking system for information retrievalUS5523946May 5, 1995Jun 4, 1996Xerox CorporationCompact encoding of multi-lingual translation dictionariesUS5696962May 8, 1996Dec 9, 1997Xerox CorporationMethod for computerized information retrieval using shallow linguistic analysisUS5724571Jul 7, 1995Mar 3, 1998Sun Microsystems, Inc.Method and apparatus for generating query responses in a computer-based document retrieval systemUS5754939Oct 31, 1995May 19, 1998Herz; Frederick S. M.System for generation of user profiles for a system for customized electronic identification of desirable objectsUS5771378Jun 7, 1995Jun 23, 1998Reed Elsevier, Inc.Associative text search and retrieval system having a table indicating word position in phrasesUS5826261May 10, 1996Oct 20, 1998Spencer; GrahamSystem and method for querying multiple, distributed databases by selective sharing of local relative significance information for terms related to the queryUS5835087Oct 31, 1995Nov 10, 1998Herz; Frederick S. M.System for generation of object profiles for a system for customized electronic identification of desirable objectsUS5915249Jun 14, 1996Jun 22, 1999Excite, Inc.System and method for accelerated query evaluation of very large full-text databasesUS5920854Aug 14, 1996Jul 6, 1999Infoseek CorporationReal-time document collection search engine with phrase indexingUS5956722Sep 23, 1997Sep 21, 1999At&T Corp.Method for effective indexing of partially dynamic documentsUS5960383Feb 25, 1997Sep 28, 1999Digital Equipment CorporationExtraction of key sections from texts using automatic indexing techniquesUS6070158Nov 13, 1997May 30, 2000Infoseek CorporationReal-time document collection search engine with phrase indexingUS6085186Sep 19, 1997Jul 4, 2000Netbot, Inc.Method and system using information written in a wrapper description language to execute query on a networkUS6098034Mar 18, 1996Aug 1, 2000Expert Ease Development, Ltd.Method for standardizing phrasing in a documentUS6178419Jul 18, 1997Jan 23, 2001British Telecommunications PlcData access systemUS6185550Jun 13, 1997Feb 6, 2001Sun Microsystems, Inc.Method and apparatus for classifying documents within a class hierarchy creating term vector, term file and relevance rankingUS6185558Mar 10, 1998Feb 6, 2001Amazon.Com, Inc.Identifying the items most relevant to a current query based on items selected in connection with similar queriesUS6298344Mar 26, 1999Oct 2, 2001Matsushita Electric Industrial Co., Ltd.Document searching apparatusUS6349316Apr 8, 1999Feb 19, 2002Microsoft CorporationDocument summarizer for word processorsUS6363377Dec 22, 1998Mar 26, 2002Sarnoff CorporationSearch data processorUS6366933Oct 27, 1995Apr 2, 2002At&T Corp.Method and apparatus for tracking and viewing changes on the webUS6415283Oct 13, 1998Jul 2, 2002Orack CorporationMethods and apparatus for determining focal points of clusters in a tree structureUS6470307Jun 23, 1997Oct 22, 2002National Research Council Of CanadaMethod and apparatus for automatically identifying keywords within a documentUS6499030Mar 30, 2000Dec 24, 2002Fujitsu LimitedApparatus and method for information retrieval, and storage medium storing program thereforUS6542888Nov 26, 1997Apr 1, 2003International Business Machines CorporationContent filtering for electronic documents generated in multiple foreign languagesUS6549895Jul 5, 2000Apr 15, 2003International Business Machines CorporationMethod and apparatus for analyzing data retrieval using index scanningUS6571240Feb 2, 2000May 27, 2003Chi Fai HoInformation processing for searching categorizing information in a document based on a categorization hierarchy and extracted phrasesUS6594658Dec 12, 2000Jul 15, 2003Sun Microsystems, Inc.Method and apparatus for generating query responses in a computer-based document retrieval systemUS6596030Feb 15, 2002Jul 22, 2003At&T Corp.Identifying changes in on-line data repositoriesUS6684183Dec 6, 1999Jan 27, 2004Comverse Ltd.Generic natural language service creation environmentUS6691106May 23, 2000Feb 10, 2004Intel CorporationProfile driven instant web portalUS6741981 *Mar 2, 2001May 25, 2004The United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration (Nasa)System, method and apparatus for conducting a phrase searchUS6741982Dec 19, 2001May 25, 2004Cognos IncorporatedSystem and method for retrieving data from a database systemUS6741984Feb 23, 2001May 25, 2004General Electric CompanyMethod, system and storage medium for arranging a databaseUS6772150Mar 22, 2000Aug 3, 2004Amazon.Com, Inc.Search query refinement using related search phrasesUS6778980Sep 27, 2001Aug 17, 2004Drugstore.ComTechniques for improved searching of electronically stored informationUS6820237Jan 21, 2000Nov 16, 2004Amikanow! CorporationApparatus and method for context-based highlighting of an electronic documentUS6823333Mar 2, 2001Nov 23, 2004The United States Of America As Represented By The Administrator Of The National Aeronautics And Space AdministrationSystem, method and apparatus for conducting a keyterm searchUS6832224Apr 1, 2002Dec 14, 2004Tacit Software, Inc.Method and apparatus for assigning a confidence level to a term within a user knowledge profileUS6839682 *Oct 3, 2000Jan 4, 2005Fair Isaac CorporationPredictive modeling of consumer financial behavior using supervised segmentation and nearest-neighbor matchingUS6859800Apr 26, 2000Feb 22, 2005Global Information Research And Technologies LlcSystem for fulfilling an information needUS6862710Mar 22, 2000Mar 1, 2005Insightful CorporationInternet navigation using soft hyperlinksUS6886010Aug 22, 2003Apr 26, 2005The United States Of America As Represented By The Secretary Of The NavyMethod for data and text mining and literature-based discoveryUS6910003Jul 10, 2000Jun 21, 2005Discern Communications, Inc.System, method and article of manufacture for concept based information searchingUS6978274 *Aug 31, 2001Dec 20, 2005Attenex CorporationSystem and method for dynamically evaluating latent concepts in unstructured documentsUS6981040Jun 20, 2000Dec 27, 2005Utopy, Inc.Automatic, personalized online information and product servicesUS6983345Aug 20, 2001Jan 3, 2006Ser Solutions, Inc.Associative memoryUS7028026May 28, 2002Apr 11, 2006Ask Jeeves, Inc.Relevancy-based database retrieval and display techniquesUS7051023 *Nov 12, 2003May 23, 2006Yahoo! Inc.Systems and methods for generating concept units from search queriesUS7051024Feb 11, 2002May 23, 2006Microsoft CorporationDocument summarizer for word processorsUS7058589Dec 17, 1999Jun 6, 2006Iex CorporationMethod and system for employee work schedulingUS7085771 *May 17, 2002Aug 1, 2006Verity, IncSystem and method for automatically discovering a hierarchy of concepts from a corpus of documentsUS7089236Oct 13, 1999Aug 8, 2006Search 123.Com, Inc.Search engine interfaceUS7139756Jan 22, 2002Nov 21, 2006International Business Machines CorporationSystem and method for detecting duplicate and similar documentsUS7149748May 6, 2003Dec 12, 2006Sap AgExpanded inverted indexUS7158983Sep 23, 2002Jan 2, 2007Battelle Memorial InstituteText analysis techniqueUS7171619Jul 5, 2001Jan 30, 2007Sun Microsystems, Inc.Methods and apparatus for accessing document contentUS7194483Mar 19, 2003Mar 20, 2007Intelligenxia, Inc.Method, system, and computer program product for concept-based multi-dimensional analysis of unstructured informationUS7200802Jun 13, 2003Apr 3, 2007Hewlett-Packard Development Company, L.P.Evaluating distinctiveness of documentUS7206389Jan 7, 2004Apr 17, 2007Nuance Communications, Inc.Method and apparatus for generating a speech-recognition-based call-routing systemUS7240064Nov 10, 2003Jul 3, 2007Overture Services, Inc.Search engine with hierarchically stored indicesUS7243092Aug 29, 2002Jul 10, 2007Sap AgTaxonomy generation for electronic documentsUS7254580Sep 30, 2003Aug 7, 2007Google Inc.System and method for selectively searching partitions of a databaseUS7426507Jul 26, 2004Sep 16, 2008Google, Inc.Automatic taxonomy generation in search results using phrasesUS20010000356 *Dec 12, 2000Apr 19, 2001Woods William A.Method and apparatus for generating query responses in a computer-based document retrieval systemUS20010021938Apr 8, 1999Sep 13, 2001Ronald A. FeinDocument summarizer for word processorsUS20020042707Jun 18, 2001Apr 11, 2002Gang ZhaoGrammar-packaged parsingUS20020042793Aug 10, 2001Apr 11, 2002Jun-Hyeog ChoiMethod of order-ranking document clusters using entropy data and bayesian self-organizing feature mapsUS20020046018May 11, 2001Apr 18, 2002Daniel MarcuDiscourse parsing and summarizationUS20020052901Aug 31, 2001May 2, 2002Guo Zhi LiAutomatic correlation method for generating summaries for text documentsUS20020065857Aug 3, 2001May 30, 2002Zbigniew MichalewiczSystem and method for analysis and clustering of documents for search engineUS20020078090Jun 29, 2001Jun 20, 2002Hwang Chung HeeOntological concept-based, user-centric text summarizationUS20020091671Nov 20, 2001Jul 11, 2002Andreas ProkophMethod and system for data retrieval in large collections of dataUS20020138467May 22, 2002Sep 26, 2002Guy JacobsonMethod for effective indexing of partially dynamic documentsUS20020143524Sep 13, 2001Oct 3, 2002Lingomotors, Inc.Method and resulting system for integrating a query reformation module onto an information retrieval systemUS20020147578Sep 13, 2001Oct 10, 2002Lingomotors, Inc.Method and system for query reformulation for searching of informationUS20020174113Jan 3, 2002Nov 21, 2002Homare KanieDocument retrieval method /device and storage medium storing document retrieval programUS20030037041Oct 1, 2002Feb 20, 2003Pinpoint IncorporatedSystem for automatic determination of customized prices and promotionsUS20030051214Aug 6, 2002Mar 13, 2003Ricoh Company, Ltd.Techniques for annotating portions of a document relevant to concepts of interestUS20030069877Dec 5, 2001Apr 10, 2003Xerox CorporationSystem for automatically generating queriesUS20030078913Mar 2, 2001Apr 24, 2003Mcgreevy Michael W.System, method and apparatus for conducting a keyterm searchUS20030144995Jan 25, 2002Jul 31, 2003International Business MachinesCompressing index files in information retrievalUS20030195877Mar 31, 2003Oct 16, 2003Ford James L.Search query processing to provide category-ranked presentation of search resultsUS20040006736Jun 13, 2003Jan 8, 2004Takahiko KawataniEvaluating distinctiveness of documentUS20040034633Mar 14, 2003Feb 19, 2004Rickard John TerrellData search system and method using mutual subsethood measuresUS20040052433Sep 18, 2002Mar 18, 2004Henry Steven G.Information research initiated from a scanned image mediaUS20040064438Aug 22, 2003Apr 1, 2004Kostoff Ronald N.Method for data and text mining and literature-based discoveryUS20040068396 *Sep 22, 2003Apr 8, 2004Takahiko KawataniMethod of vector analysis for a documentUS20040133560Jan 7, 2003Jul 8, 2004Simske Steven J.Methods and systems for organizing electronic documentsUS20040158580Dec 19, 2001Aug 12, 2004David CarmelLossy index compressionUS20040186824Mar 17, 2003Sep 23, 2004Kemal DelicStoring and/or retrieving a document within a knowledge base or document repositoryUS20040186827Apr 25, 2003Sep 23, 2004Anick Peter G.Systems and methods for interactive search query refinementUS20040260692Jun 18, 2003Dec 23, 2004Brill Eric D.Utilizing information redundancy to improve text searchesUS20050043940Aug 20, 2004Feb 24, 2005Marvin ElderPreparing a data source for a natural language queryUS20050060651May 5, 2003Mar 17, 2005Anderson Roy EdwardElectronic document indexing system and methodUS20050071328Sep 30, 2003Mar 31, 2005Lawrence Stephen R.Personalization of web searchUS20050154723Dec 28, 2004Jul 14, 2005Ping LiangAdvanced search, file system, and intelligent assistant agentUS20050165778Dec 22, 2004Jul 28, 2005Microsoft CorporationAdaptive Web crawling using a statistical modelUS20050216564Aug 24, 2004Sep 29, 2005Myers Gregory KMethod and apparatus for analysis of electronic communications containing imageryUS20050256848May 13, 2004Nov 17, 2005International Business Machines CorporationSystem and method for user rank searchUS20050278620Jun 15, 2005Dec 15, 2005TekelecMethods, systems, and computer program products for content-based screening of messaging service messagesUS20060020571Jul 26, 2004Jan 26, 2006Patterson Anna LPhrase-based generation of document descriptionsUS20060020607Jul 26, 2004Jan 26, 2006Patterson Anna LPhrase-based indexing in an information retrieval systemUS20060031195Jul 26, 2004Feb 9, 2006Patterson Anna LPhrase-based searching in an information retrieval systemUS20060106792Jan 25, 2005May 18, 2006Patterson Anna LMultiple index based information retrieval systemUS20060143174Jan 24, 2006Jun 29, 2006Verizon Laboratories Inc.Hypervideo: information retrieval using time-related multimediaUS20060143714Feb 21, 2006Jun 29, 2006Pkware, Inc.System and method for manipulating and managing computer archive filesUS20060294155Jun 28, 2006Dec 28, 2006Patterson Anna LDetecting spam documents in a phrase based information retrieval system* Cited by examinerNon-Patent CitationsReference1 *Ahonen-Myka H. et al., "Finding Co-occuring Text Phrases by Combining Sequence and Frequent Set Discovery", Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence on Text Mining: Foundations Techniques and Applications (Jul. 31, 1999-Aug. 6, 1999), pp. 1-9, Stockholm, Sweden. (Provided by Applicant).2Ahonen-Myka H. et al., "Finding Co-occurring Text Phrases By Combining Sequence and Frequent Set Discovery", Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence on Text Mining: Foundations Techniques and Applications (Jul. 31, 1999-Aug. 6, 1999), pp. 1-9. Stockholm, Sweden.3Caropreso, M. et al., "Statistical Phrases in Automated Text Categorization," Internet Publication-Technical Report, May 26, 2000, pp. 1-18.4Chang, C.T.K. et al., "Performance and Implications of Semantic Indexing in a Distributed Environment", Proceedings of the Eighth International Conference on Information Knowledge Management, (1999) pp. 391-398. New York, NY.5 *Chen et al., "Automatic Thesaurus Generation for an Electronic Community System", Journal of the American Society for Information Science, 1995, pp. 175-193 (provided by Applicant).6Chen, H. et al., "Automatic Construction of Networks of Concepts Characterizing Document Databases", IEEE Transactions on Systems, Man and Cybernetics. Part B: Cybernetics, Sep. 5, 1992, pp. 75-88, vol. 22, No. 5. IEEE Service Center, USA.7Chen, H. et al., "Automatic Thesaurus Generation for an Electric Community System", Journal of the American Society for Information, Apr. 1, 1995, pp. 175-193, vol. 46, No. 3. Washington, USA.8Cheung, F. et al., "An Efficient Algorithm for Incremental Update of Concept Spaces", University of Hong Kong Technical Report (Sep. 2002).9English translation of First Office Action from the State Intellectual Property Office for Chinese Patent Application No. 200510085373.4, dated Mar. 2008.10English translation with First Office Action from the State Intellectual Property Office for Chinese Patent Application No. 200510085370.0, dated Apr., 2008.11English translation with First Office Action from the State Intellectual Property Office for Chinese Patent Application No. 200510085371.5, dated Apr. 2008.12English translation with First Office Action from the State Intellectual Property Office for Chinese Patent Application No. 200510085372.X, dated Mar. 2008.13European Search Report, EP05254644.7-2201, Oct. 21, 2005.14European Search Report, EP05254645.4-2201, Sep. 21, 2005, 12 pages.15European Search Report, EP05254646.2-2201, Oct. 11, 2005.16European Search Report, EP05254647.0-2201, Oct. 4, 2005.17Examiner's First Report on Australian Patent Application No. 2005203237, Sep. 11, 2007, 2 Pages.18Examiner's First Report on Australian Patent Application No. 2005203238, Sep. 10, 2007, 2 Pages.19Examiner's First Report on Australian Patent Application No. 2005203239, Sep. 13, 2007, 2 Pages.20Examiner's First Report on Australian Patent Application No. 2005203240, Sep. 13, 2007, 2 Pages.21Garner, Harold et al., "Gene Alert - A Sequence Search Results Keyword Parser," IEEE Engineering in Medicine and Biology Magazine, vol. 17 (Mar-Apr 1998), 119-122.22Gedeon, T.D. et al., "Hierarchical Co-Occurrence Relations", Systems, Man, and Cybernetics, IEEE International Conference in San Diego, CA, Oct. 11, 1998-Oct. 14, 1998, pp. 2750-2755, vol. 3. New York, USA.23House, D., "Save Web Time with WebSumm", [online] Jul. 1997 [Retrieved on May 7, 2005], Retrieved from the Internet: <URL: http://www.mitre.org/news/the-edge/july-97/first.html>.24Jing, Y. et al., "An Association Thesaurus for Information Retrieval", Proceedings of RIAO-94, Fourth International Conference on Intelligent Multimedia Information Retrieval Systems and Management, (Oct. 11, 1994-Oct. 13, 1994). New York, NY.25 *Jones et al., "Interactive Document Summarisation Using Automatically Extracted Keyphrases", Proceedings of the 35th Annual Hawaii International Conference on System Sciences, 2002, pp. 1-10 (provided by Applicant).26Jones, S. et al., "Interactive Document Summarisation Using Automatically Extracted Key Phrases", Proceedings of the 35th Annual Hawaii International Conference, Jan. 7, 2001-Jan. 10, 2001, pp. 1287-1296. Piscataway, New Jersey, USA.27Jones, S. et al., "Topic-Based Browsing Within a Digital Library Using Keyphrases," Proceedings of the Fourth ACM conference on Digital Libraries, Aug. 11 - 14, 1999, Berkeley, CA: ACM Press, (1999), 114-121.28Kando, N., "Text Structure Analysis as a Tool to Make Retrieved Document Usable", Proceedings of the 4th International Workshop On Information Retrieval With Asian Languages, Nov. 11, 1999, [online] [Retrieved on Oct. 5, 2005] Retrieved from the Internet: <URL: http://research.nii.ac.jp/[kando/>.29Leroy, G. et al., "Meeting Medical Terminology Needs-The Ontology-Enhanced Medical Concept Mapper", IEEE Transactions on Information Technology in Biomedicine, Dec. 2001, pp. 261-270, vol. 5, No. 4. USA.30Lin, C-S. et al., "An Automatic Indexing and Neural Network Approach to Concept Retrieval and Classification of Multilingual (Chinese-English) Documents", IEEE Transaction on Systems, Man and Cybernetics. Part B Cybernetics, vol. 26, No. 1 (Feb. 1, 1996), pp. 75-88. USA.31Mandala, R. et al., "Association for Computing Machinery: 'Combining Multiple Evidence From Different Types of Thesaurus for Query Expansion'", Proceedings of SIGIR'99 22nd International Conference on Research and Development in Information Retrieval, Aug. 1999, pp. 191-197. New York, NY, USA.32Nguyen, Hung V., et al., "Mining 'Hidden Phrase' Definitions from the Web", Proceedings of the Fifth Asian-Pacific Web Conference (Apr. 23, 2002-Apr. 25, 2002), Xian, China.33PCT International Search Report and Written Opinion, PCT/US06/02709, Jun. 25, 2007, 9 pages.34Pretschner, A. et al., "Ontology Based Personalized Search", Tools with Artificial Intelligence, Proceedings of the 11th IEEE International Conference, Nov. 9, 1999-Nov. 11, 1999, pp. 391-398, IEEE Computational Intelligence Society, Chicago, IL, USA.35Related U.S. Appl. No. 10/900,012 filed Jul. 26, 2004 (Patterson, A.L.).36Related U.S. Appl. No. 10/900,039 filed Jul. 26, 2004 (Patterson, A.L.).37Related U.S. Appl. No. 11/043,438 filed Jan. 25, 2005 (Patterson, A.L.).38Related U.S. Appl. No. 11/851,962 filed Sep. 7, 2007 (Patterson, A.L.).39 *Schutze et al., "A Cooccurrence-based Theraurus and Two Applications to Information Retrieval", Information Processing & Management, vol. 33, No. 3, pp. 307-318, 1997. (Previously Provided).40Schutze, H. et al., "A Cooccurence-Based Thesaurus and Two Applications to Information Retrieval", Information Processing & Management, May 1997, pp. 885-902, vol. 33, No. 3. Elsevier, Barking, Great Britain.41 *Schutze, H. et al., "A Cooccurrence-Based Thesaurus and Two Applications to Information Retrieval", Information Processing & Management, 1997, pp. 307-318. (Provided by Applicant).42Srinivasan, P., "Optimal Document-Indexing Vocabulary for Medline", Information Processing & Management, Sep. 1996, vol. 32, No. 5. Elsevier, Barking, Great Britain.43U.S. Appl. No. 10/900,012 Notice of Allowance mailed Sep. 12, 2008.44U.S. Appl. No. 10/900,055 Notice of Allowance mailed Dec. 12, 2007.45U.S. Appl. No. 10/900,075 Notice of Allowance mailed Aug. 22, 2008.46U.S. Appl.No. 10/900,259 Notice of Allowance mailed Jan. 23, 2008.47Yun, Bo-Hyun et al., "Semantic-Based Information Retrieval for Content Management and Security", Computational Intelligence Blackwell Publishers USA, vol. 19, No. 2 (May 2, 2003), pp. 87-110. USA.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS7693813Apr 6, 2010Google Inc.Index server architecture using tiered and sharded phrase posting listsUS7702614Mar 30, 2007Apr 20, 2010Google Inc.Index updating using segment swappingUS7711679Jul 26, 2004May 4, 2010Google Inc.Phrase-based detection of duplicate documents in an information retrieval systemUS7925655Mar 30, 2007Apr 12, 2011Google Inc.Query scheduling using hierarchical tiers of index serversUS7966309Jan 17, 2007Jun 21, 2011Google Inc.Providing relevance-ordered categories of informationUS7966321Jan 17, 2007Jun 21, 2011Google Inc.Presentation of local resultsUS7970768 *Jun 28, 2011Microsoft CorporationContent data indexing with content associationsUS7987189Aug 20, 2007Jul 26, 2011Microsoft CorporationContent data indexing and result rankingUS8005822Aug 23, 2011Google Inc.Location in search queriesUS8078629Oct 13, 2009Dec 13, 2011Google Inc.Detecting spam documents in a phrase based information retrieval systemUS8090723Mar 2, 2010Jan 3, 2012Google Inc.Index server architecture using tiered and sharded phrase posting listsUS8108412Mar 4, 2010Jan 31, 2012Google, Inc.Phrase-based detection of duplicate documents in an information retrieval systemUS8117223Sep 7, 2007Feb 14, 2012Google Inc.Integrating external related phrase information into a phrase-based indexing information retrieval systemUS8150859 *Feb 5, 2010Apr 3, 2012Microsoft CorporationSemantic table of contents for search resultsUS8161073Apr 17, 2012Holovisions, LLCContext-driven searchUS8166021Mar 30, 2007Apr 24, 2012Google Inc.Query phrasificationUS8166045Apr 24, 2012Google Inc.Phrase extraction using subphrase scoringUS8326842 *Dec 4, 2012Microsoft CorporationSemantic table of contents for search resultsUS8326858Jan 17, 2007Dec 4, 2012Google Inc.Synchronization of fixed and mobile dataUS8386239Jun 17, 2010Feb 26, 2013Holovisions LLCMulti-stage text morphingUS8402033Oct 14, 2011Mar 19, 2013Google Inc.Phrase extraction using subphrase scoringUS8489591Jun 2, 2011Jul 16, 2013Google Inc.Presentation of local resultsUS8489628Dec 1, 2011Jul 16, 2013Google Inc.Phrase-based detection of duplicate documents in an information retrieval systemUS8543381 *Jun 17, 2010Sep 24, 2013Holovisions LLCMorphing text by splicing end-compatible segmentsUS8560550Jul 20, 2009Oct 15, 2013Google, Inc.Multiple index based information retrieval systemUS8612427Mar 4, 2010Dec 17, 2013Google, Inc.Information retrieval system for archiving multiple document versionsUS8631027Jan 10, 2012Jan 14, 2014Google Inc.Integrated external related phrase information into a phrase-based indexing information retrieval systemUS8682901Dec 20, 2011Mar 25, 2014Google Inc.Index server architecture using tiered and sharded phrase posting listsUS8713078Aug 13, 2009Apr 29, 2014Samsung Electronics Co., Ltd.Method for building taxonomy of topics and categorizing videosUS8849835 *Nov 2, 2011Sep 30, 2014Google Inc.Reconciling dataUS8943067Mar 15, 2013Jan 27, 2015Google Inc.Index server architecture using tiered and sharded phrase posting listsUS8966407Jan 17, 2007Feb 24, 2015Google Inc.Expandable homepage modulesUS8996507Aug 22, 2011Mar 31, 2015Google Inc.Location in search queriesUS9015043Oct 1, 2010Apr 21, 2015Google Inc.Choosing recognized text from a background environmentUS9037573Jun 17, 2013May 19, 2015Google, Inc.Phase-based personalization of searches in an information retrieval systemUS9069750Jun 30, 2011Jun 30, 2015Abbyy Infopoisk LlcMethod and system for semantic searching of natural language textsUS9075864Dec 31, 2010Jul 7, 2015Abbyy Infopoisk LlcMethod and system for semantic searching using syntactic and semantic analysisUS9098489Jun 30, 2011Aug 4, 2015Abbyy Infopoisk LlcMethod and system for semantic searchingUS9189482Nov 8, 2012Nov 17, 2015Abbyy Infopoisk LlcSimilar document searchUS9223877Jan 7, 2015Dec 29, 2015Google Inc.Index server architecture using tiered and sharded phrase posting listsUS9262767 *Feb 14, 2012Feb 16, 2016Google Inc.Systems and methods for generating statistics from search engine query logsUS9355169Sep 13, 2012May 31, 2016Google Inc.Phrase extraction using subphrase scoringUS9361331Mar 13, 2013Jun 7, 2016Google Inc.Multiple index based information retrieval systemUS9384224Nov 18, 2013Jul 5, 2016Google Inc.Information retrieval system for archiving multiple document versionsUS20070282822 *Aug 20, 2007Dec 6, 2007Microsoft CorporationContent data indexing with content associationsUS20070282831 *Aug 20, 2007Dec 6, 2007Microsoft CorporationContent data indexing and result rankingUS20080172357 *Jan 17, 2007Jul 17, 2008Google Inc.Location in search queriesUS20080172362 *Jan 17, 2007Jul 17, 2008Google Inc.Providing Relevance-Ordered Categories of InformationUS20080172373 *Jan 17, 2007Jul 17, 2008Google Inc.Synchronization of Fixed and Mobile DataUS20090070312 *Sep 7, 2007Mar 12, 2009Google Inc.Integrating external related phrase information into a phrase-based indexing information retrieval systemUS20100030773 *Jul 20, 2009Feb 4, 2010Google Inc.Multiple index based information retrieval systemUS20110184726 *Jul 28, 2011Connor Robert AMorphing text by splicing end-compatible segmentsUS20110196875 *Feb 5, 2010Aug 11, 2011Microsoft CorporationSemantic table of contents for search resultsUS20110202521 *Aug 18, 2011Jason ColemanEnhanced database search features and methodsUS20120215765 *Aug 23, 2012Olcan SercinogluSystems and Methods for Generating Statistics from Search Engine Query Logs* Cited by examinerClassifications U.S. Classification707/3, 707/2, 707/1International ClassificationG06F, G06F17/30Cooperative ClassificationY10S707/99931, Y10S707/99932, Y10S707/99937, Y10S707/99933, G06F17/30616European ClassificationG06F17/30T1ELegal EventsDateCodeEventDescriptionDec 6, 2004ASAssignmentOwner name: GOOGLE, INC., CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:PATTERSON, ANNA LYNN;REEL/FRAME:015429/0451Effective date: 20041104Mar 23, 2010CCCertificate of correctionDec 21, 2010CCCertificate of correctionJan 30, 2013FPAYFee paymentYear of fee payment: 4RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services