Word deletion for searches

• US 7,865,495 B1
• Filed: 10/06/2005
• Issued: 01/04/2011
• Est. Priority Date: 10/06/2004
• Status: Active Grant

• Current Assignee: Connexity, Inc.
• Original Assignee: Shopzilla Incorporated
• Inventors: Dutton, Keith A., Roizen, Igor
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Smith; Brannon W
• Application Number:
  US11/245,602
• Time in Patent Office: 1,916 Days
• Field of Search: 707/3, 707/6, 707/999.003, 707/708, 707/765, 707/E17.063, 707/999.005
• US Class Current: 707/708
• CPC Class Codes: G06F 16/3346 using probabilistic model
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/971 Federated
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A searcher can be configured to improve search results through the use of intelligent word deletion. A search auto categorizer (SAC) operates on the original query and returns a list of leaf categories and a distribution of probabilities among the leaf categories. The original query is parsed into word pairs and each word pair is run through the search engine. The search results for each word pair are weighted by the leaf category probabilities. A word pair is selected from the results and one of the two words is deleted from the original query. The searcher can perform exhaustive deletion where multiple truncated queries are generated from the original query and the results list from one truncated query is returned as the results list. The searcher can build up a truncated query from the original query by iteratively appending a word selected from the original query to the truncated query.

Claims

1. In a computerized search system which queries are submitted by users who receive, in response, a list of documents selected from a corpus of documents wherein the list comprises documents deemed responsive to a user'"'"'s query, a method of preprocessing the query comprising:

obtaining a base query from a user, wherein the base query comprises a plurality of words;

determining a base distribution of nodes of a taxonomy that have non-zero probabilities of being relevant to the base query, wherein the taxonomy is a taxonomy of topics into which documents of the corpus of documents might be assigned;

modifying the base query to form a truncated query when it is determined that the base query will return no results, wherein modifying the base query to form the truncated query comprises;

identifying word pairs in the base query,

determining pair distributions for word pairs over the taxonomy,

selecting a desired word pair based in part on the pair distributions,

generating a first query by omitting from the base query a first word of the desired word pair,

generating a second query by omitting from the base query a second word from the desired word pair,

determining a first count of documents corresponding to the first query,

determining a second count of documents corresponding to the second query, and

determining at least one word to remove from the base query based on the first and second counts such that the truncated query comprises a portion of the base query from which the at least one word is removed;

running the truncated query against the corpus of documents to obtain a results list of one or more documents in the document corpus deemed responsive to the truncated query; and

outputting the results list as the list comprising documents deemed responsive to the user'"'"'s query.

2. The method of claim 1, wherein the list of documents comprises a plurality of references to documents.

3. The method of claim 1, wherein the corpus of documents comprises web pages and the list of documents comprises at least a list of URLs.

4. The method of claim 1, wherein using the pair distributions to determine the one or more removed word comprises:

selecting a word pair from the pairs of words in the base query based in part on the pair distributions weighted by the base distribution of nodes; and

selecting a word from the word pair for deletion from the base query.

5. In a computerized search system which queries are submitted by users who receive, in response, a list of documents selected from a corpus of documents wherein the list comprises documents deemed responsive to a user'"'"'s query, a method of preprocessing the query comprising:

obtaining a base query from a user input, wherein the base query comprises a plurality of words;

determining a base distribution of nodes of a taxonomy of the computerized search system having non-zero probabilities of being relevant to the base query;

forming a plurality of truncated queries each comprising a distinct pair of words from the plurality of words;

running the truncated queries at the base distribution of nodes to obtain a results list comprising a count of documents deemed responsive to each truncated query in one or more categories of the taxonomy;

selecting one of the truncated queries based on the count of the documents in its corresponding results list;

modifying the base query by removing from the base query a first word of the pair of words of the selected truncated query and running the modified base query to obtain a first results list;

modifying the base query by removing from the base query a second word of the pair of words of the selected truncated query and running the modified base query to obtain a second results list; and

outputting the first results list or the second results list as the list comprising documents deemed responsive to the user'"'"'s query based on an optimization policy of the computerized search system.