6,598,051

July 22, 2003

Web page connectivity server.

A connectivity server for a collecting, arranging and representing data defining the interconnection of pages on the World Wide Web (Web). A URL Database stores URLs and associates a fingerprint and CS_id with each URL. The URL Database interface is operable to translate between any two of a URL, a fingerprint, and a Host_id. A Host Database associates a Host_id with each distinct hostname in the URL Database. The Host Database interface is operable to accept a Host_id and return a number equal to the number of URLs on the respective host and to return the CS_ids of those URLs. A Link Database stores links between source URLs and destination URLs. The Link Database interface is operable to retrieve, for a given CS_id, the number of inlinks to and outlinks from the URL corresponding to the CS_id. In an embodiment characterized by a single processor, with access to all databases stored in RAM links and URL information may be retrieved sufficiently rapidly so that applications that touch every link, even multiple times, may execute in real time, in a few minutes or hours. Representative applications enabled by the connectivity server include static ranking of pages (eigenranks), query precomputation, mirror-site detection, and related-page identification.

Inventors:  Wiener; Janet L. (Palo Alto, CA); Stata; Raymond P. (Palo Alto, CA); Burrows; Michael (Palo Alto, CA) 
Assignee:  Altavista Company (Palo Alto, CA) 

6,526,440

February 25, 2003 

Ranking search results by reranking the results based on local inter-connectivity.

A search engine for searching a corpus improves the relevancy of the results by refining a standard relevancy score based on the interconnectivity of the initially returned set of documents. The search engine obtains an initial set of relevant documents by matching a user's search terms to an index of a corpus. A re-ranking component in the search engine then refines the initially returned document rankings so that documents that are frequently cited in the initial set of relevant documents are preferred over documents that are less frequently cited within the initial set.

Inventors:  Bharat; Krishna (Santa Clara, CA) 
Assignee:  Google, Inc. (Mountain View, CA) 

6,529,903

March 4, 2003 

Methods and apparatus for using a modified index to provide search results in response to an ambiguous search query.

A system allows a user to submit an ambiguous search query and to receive potentially disambiguated search results. In one implementation, a search engine's conventional alphanumeric index is translated into a second index that is ambiguated in the same manner as which the user's input is ambiguated. The user's ambiguous search query is compared to this ambiguated index, and the corresponding documents are provided to the user as search results.

Inventors:  Smith; Benjamin Thomas (Mountain View, CA); Brin; Sergey (Palo Alto, CA); Ghemawat; Sanjay (Mountain View, CA); Manning; Christopher D. (Palo Alto, CA) 
Assignee:  Google, Inc. (Mountain View, CA)

6,615,209

September 2, 2003 

Detecting query-specific duplicate documents.

An improved duplicate detection technique that uses query-relevant information to limit the portion(s) of documents to be compared for similarity is described. Before comparing two documents for similarity, the content of these documents may be condensed based on the query. In one embodiment, query-relevant information or text (also referred to as "snippets") is extracted from the documents and only the extracted snippets, rather than the entire documents, are compared for purposes of determining similarity.

Inventors:  Gomes; Benedict (Berkeley, CA); Smith; Benjamin Thomas (Mountain View, CA) 
Assignee:  Google, Inc. (Mountain View, CA) 

6,658,423

December 2, 2003 

6,564,208

May 13, 2003

Delivering non-default items in association with search results.

Techniques are provided for delivering search results pages to the users of a search engine, where one or more search result listings on the search results pages include items that are not included by default. The non-default items may take many forms, including but not limited to images, banners, controls, animations, and even Java applets. The non-default items may be designed to entice the search engine users to select the search result listing with which they are associated over possibly higher-ranked search result listings that contain only default items.

Inventors:  Littlefield; Andrew (San Mateo, CA); Hall; Matthew Charles Grogan (San Jose, CA); Palmer; Michael E. (San Francisco, CA); Toman; Troy Richardson (San Carlos, CA) 
Assignee:  Inktomi Corporation (Foster City, CA)

6,523,021

February 18, 2003 

Business directory search engine.

A system and method for efficiently searching directory listing information to obtain more relevant results is provided. In a computer system running a computing application, it is advantageous to provide search capabilities, in the form of a search engine, to operators to assist them in their effort of retrieving desired data. The search engine may cooperate with a data store having directory listing information to provide listings data to an operator. In an illustrative implementation, this search engine may be deployed on an Internet Web site that offers business listing information. The search system may comprise a user interface to enter search query information, a data store that houses a variety of directory listing information according to a predefined data taxonomy, and a means for displaying the search results. In operation, the search engine offers a variety of search options, such as, search by business name, by business categories levels, by geographic position of the user or the business, or a combination thereof. Depending on the search query entered, the search engine will perform either a bounded search (i.e. a search bounded to a specific geographic area), a proximity search (i.e. a search proximate to a computed centroid), or a combination of the two to find the most relevant directory listings. Using the inputted search qualifiers, the search engine polls the data store according to a predefined set of rules and instructions for the relevant directory listing information. These rules are directly related to the taxonomy of the data store.

Inventors:  Monberg; James C. (Seattle, WA); Mariani; Rico (Kirkland, WA); Staab; Sanford A. (Woodinville, WA) 
Assignee:  Microsoft Corporation (Redmond, WA) 

6,553,372

April 22, 2003

Natural language information retrieval system.

A natural language information retrieval (NLIR) system employing a hash table technique to reduce memory requirements and a proxy process module to improve processing speed on multi-processor platforms. The NLIR system includes a Dynamic Link Library (DLL) search engine annex that implements a number of improvements that allow the preexisting natural language processing (NLP) core code module to operate sufficiently fast in a limited-memory environment. The improvements relate to (1) reducing storage requirements, (2) increasing processing speed, (3) improved operation on multi-processor platforms, and (4) a trouble-shooting mechanism. The NLIR system includes three modes of operation. First, during index processing, the NLIR system prepares documents for NLP searching to create a group of searchable documents. Second, during question processing, the NLIR system receives a natural language question and, for each document in the group of searchable documents, computes a document score connoting the likelihood that the document includes an answer to the natural language question. Third, during debugging, the NLIR system receives trouble-shooting requests and returns diagnostic reports, such as a document trace report and a question trace report.

Inventors:  Brassell; Lenox H. (Seattle, WA); Miller; John W. (Kirkland, WA) 
Assignee:  Microsoft Corporation (Redmond, WA) 

6,556,983

April 29, 2003 

Methods and apparatus for finding semantic information, such as usage logs, similar to a query using a pattern lattice data space.

A pattern lattice data space as a framework for analyzing data, in which both schema-based and statistical analysis are accommodated, is defined. Ways to manage the size of the lattice structures in the pattern lattice data space are described. Utilities to classify or cluster, search (find similar data), or relate data using lattice fragments in the pattern lattice data space are also described. Superpattern cone or lattice generation function, which may be used by the classification and clustering functions, is also described. In addition, a subpattern cone or lattice generation process, which may be used by the search (find similar data) and data relating functions, is also described. Finally, a function to label, in readily understandable "pidgin", categories which classify information, is also described.

Inventors:  Altschuler; Steven (Redmond, WA); Ingerman; David V. (Princeton, NJ); Wu; Lani (Redmond, WA); Zhao; Lei (Bellevue, WA) 
Assignee:  Microsoft Corporation (Redmond, WA)

6,601,059

July 29, 2003 

Computerized searching tool with spellchecking.

A method for improving searching of a network receives a search query from a user without the query passing over the network. The query is then examined to determine if it includes misspelled words. After examining the query, the query is used to search the network. In some embodiments, the method also includes a step of providing a visual cue to the user to indicate that the search query includes a misspelled word. In further embodiments of the invention, the method also includes a step of providing lists of possible spellings for the misspelled words and allowing the user to select one of the possible spellings from the list. The method then replaces the misspelled word with the selected spelling to produce modified text. The modified text is then used to search the network.

Inventors:  Fries; Karen E. (Seattle, WA) 
Assignee:  Microsoft Corporation (Redmond, WA)

6,665,837

December 16, 2003

Method for identifying related pages in a hyperlinked database.

A method is described for identifying related pages among a plurality of pages in a linked database such as the World Wide Web. An initial page is selected from the plurality of pages. Pages linked to the initial page are represented as a graph in a memory. The pages represented in the graph are scored on content, and a set of pages is selected, the selected set of pages having scores greater than a first predetermined threshold. The selected set of pages is scored on connectivity, and a subset of the set of pages that have scores greater than a second predetermined threshold are selected as related pages. 

6,553,364

April 22, 2003

Information retrieval from hierarchical compound documents.

A search query is applied to documents in a document repository wherein the documents are organized into a hierarchy. A search engine searches the hierarchy to return documents which match a query term either directly or indirectly. A specific embodiment of the search engine organizes the query term into individual subterms and matches the subterms against documents, returning only those documents which indirectly match the entire search query term and directly match at least one of the query subterms.  

6,631,372

October 7, 2003

Search engine using sales and revenue to weight search results.

A search engine selects one or more search hits from among a plurality of hits, wherein a hit is a reference to a page or a site, based on a user interest, comprising an input module for accepting a query from a user, the query representing an interest of the user; a tracking module for tracking the user's navigation through the plurality of pages, including at least a destination purchase page, the destination purchase page being a page from which the user makes a purchase; a sales module which records associations between purchases and queries where the associations are provided, at least in part by an output of the tracking module; and a search module, which takes as its inputs at least a query and sales associations of that query provided by the sales module, and which outputs one or more search hits based on at least the query and the sales associations of that query. In some systems, instead of using sales data to alter the weights of the search results, merchant bidding is used to alter the weights of the search results, or a combination of the two is used.