Methods and apparatus for providing search results in response to an ambiguous search query

• US 7,136,854 B2
• Filed: 12/26/2000
• Issued: 11/14/2006
• Est. Priority Date: 07/06/2000
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Bauer, John Abraham, Ghemawat, Sanjay, Brin, Sergey, Smith, Benjamin Thomas
• Primary Examiner(s): Gaffin, Jeffrey
• Assistant Examiner(s): Mahmoudi, Hassan
• Application Number:
  US09/748,431
• Publication Number:
  US 20020133481A1
• Time in Patent Office: 2,149 Days
• Field of Search: 707/3, 707/6, 707/10, 707/104.1, 707/2, 707/4, 704/257, 345/864, 715/810
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2452 Query translation
• CPC Class Codes: G06F 16/3332 Query translation
• CPC Class Codes: G06F 16/972 Access to data in other repository systems, e.g. legacy data or dynamic Web page generation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Methods and apparatus consistent with the invention allow a user to submit an ambiguous search query and to receive relevant search results. In one embodiment, a sequence of numbers received from a user of a standard telephone keypad is translated into a set of potentially corresponding alphanumeric sequences. These potentially corresponding alphanumeric sequences are provided as an input to a conventional search engine, using a boolean “OR” expression, and the search results are presented to the user. The search engine effectively limits search results to those in which the user was likely interested.

Claims

1. A method of providing search results in response to an ambiguous search query, the ambiguous search query including a sequence of ambiguous information components, the method comprising:

receiving a sequence of ambiguous information components from a user;

obtaining mapping information that maps the ambiguous information components to less ambiguous information components;

using the mapping information and a lexicon, the lexicon comprising less ambiguous information components that have been previously processed by a search engine as search queries, to convert the sequence of ambiguous information components into at least two corresponding sequences of less ambiguous information components;

providing the at least two sequences of less ambiguous information, each of the sequences effectively being joined by a logical “

OR”

operation request, as an input to the search engine;

obtaining search results from the search engine; and

presenting the search results to the user.

2. The method of claim 1, wherein the mapping information is based on the configuration of a standard telephone keypad.

3. The method of claim 1, wherein the ambiguous information components comprise numbers and the less ambiguous information components comprise letters.

4. The method of claim 1, wherein each of the ambiguous information components comprise a single press of a key and the less ambiguous information comprises letters that correspond to the key.

5. The method of claim 1, wherein the ambiguous information components comprise phonemes.

6. The method of claim 5, wherein the less ambiguous information components comprise alphanumeric information.

7. The method of claim 1, wherein the ambiguous information components comprise visual information.

8. The method of claim 1, wherein the act of using further comprises using a dictionary to help convert the sequence of ambiguous information components into one or more corresponding sequences of less ambiguous information components.

9. The method of claim 1 wherein the act of using the mapping information and the lexicon to convert the sequence of ambiguous information components into one or more corresponding sequences of less ambiguous information components includes using the mapping information to directly translate the sequence of ambiguous information components into one or more corresponding sequences of less ambiguous information components.

10. The method of claim 1 wherein the ambiguous information components are more ambiguous than the less ambiguous information components due to a limited capability of a user input device.

11. The method of claim 1 further comprising looking up search results using an index including entries, at least one entry including a sequence of less ambiguous information components mapped to a set of one or more items.

12. A method of providing search results to a user in response to an ambiguous search query, comprising:

receiving at least two number words constituting a number phrase;

converting each number word into one or more letter words, based on mapping information, in combination with a lexicon, to generate a plurality of letter phrases, each of the letter phrases corresponding to the number phrase, wherein the lexicon is a list of letter phrases that previously have been processed by the search engine as search queries;

forming a search query to a search engine wherein the search query includes at least one of the letter phrases;

obtaining search results from the search engine in response to the search query; and

providing the search results to a user,

wherein the search results include references to Web page documents.

13. The method of claim 12, wherein the providing step comprises providing at least two of the letter phrases, each of the letter phrases being effectively joined by a logical “

OR”

operation request, as a search query to a search engine.

14. The method of claim 12, wherein the mapping information is based on a standard telephone keypad.

15. The method of claim 12 wherein the search results provided to the user have been ranked such that search results corresponding to documents that include an exact match of at least one of the letter phrases are provided higher than search results corresponding to documents that do not include an exact match of any of the letter phrases.

16. The method of claim 12 wherein the search results exclude search results corresponding to documents that do not include an exact match of any of the letter phrases.

17. A method of providing search results in response to an ambiguous search query, the ambiguous search query including a sequence of ambiguous information components, the method comprising:

receiving a sequence of ambiguous information components from a user;

obtaining mapping information that maps the ambiguous information components to less ambiguous information components;

using the mapping information to translate the sequence of ambiguous information components into a plurality of corresponding sequences of less ambiguous information components;

determining a subset of the plurality of sequences of less ambiguous information components by comparing the plurality of sequences of less ambiguous information components with terms used in past search queries, stored in a search query log, that previously have been processed by the search engine;

providing the subset of sequences of less ambiguous information components as an input to a search engine;

obtaining search results from the search engine; and

presenting the search results to the user.

18. The method of claim 17, wherein the act of determining comprises using statistical information about the co-occurrence of the less ambiguous information components within the sequence.

19. A method of providing search results in response to an ambiguous search query, comprising:

receiving a sequence of information components from a user, each information component corresponding to a key press;

obtaining mapping information that maps each of the key press information components to a plurality of other information components, each corresponding to the same key press;

using the mapping information, in combination with a lexicon, to determine, from the sequence of key press information components, other sequences of information components by converting each key press information component to each of the other information components that correspond to the key press component, wherein the lexicon is a list of other sequences of information components that previously have been processed by a search engine as search queries;

providing one or more of the received sequence and the other sequences as a search query input to the a search engine;

obtaining search results from the search engine; and

presenting the search results to the user,

wherein the search results include references to Web page documents.

20. The method of claim 19, wherein the mapping information is based on the configuration of a standard telephone keypad.

21. The method of claim 20, wherein the received information components comprise numbers and the other information components comprise letters.

22. The method of claim 20, wherein both the received and other information components comprise letters.

23. The method of claim 19, wherein the act of providing comprises providing at least two sequences to the search engine using a logical “

OR”

operations.

24. A method of providing search results in response to an ambiguous search query, the ambiguous search query including a sequence of ambiguous information components, the method comprising:

receiving a sequence of ambiguous information components from a user associated with a language;

obtaining mapping information that maps the ambiguous information components to less ambiguous information components;

using the mapping information, in combination with a lexicon, to convert the sequence of ambiguous information components into one or more corresponding sequences of less ambiguous information components, wherein the lexicon is a list of sequences of less ambiguous information components that previously have been processed by a search engine as search queries;

providing one or more of the sequences of less ambiguous information as an input to a search engine;

obtaining search results from a search engine;

reordering the obtained search results using the language of the user; and

presenting the reordered search results to the user, wherein the search results include references to Web page documents.

25. A computer-readable medium consisting of one or more memory devices and/or storage devices storing one or more instructions for providing search results in response to an ambiguous search query, the ambiguous search query including a sequence of ambiguous information components, the instructions comprising:

receiving a sequence of ambiguous information components from a user;

obtaining mapping information that maps the ambiguous information components to less ambiguous information components;

using the mapping information, in combination with a lexicon, to convert translate the sequence of ambiguous information components into at least two corresponding sequences of less ambiguous information components, wherein the lexicon is a list of sequences of less ambiguous information components that previously have been processed by a search engine as search queries;

providing the at least two sequences of less ambiguous information, each of the sequences effectively being joined by a logical “

OR”

operation request, as an input to the a search engine;

obtaining search results from the search engine; and

presenting the search results to the user.

26. An apparatus for providing search results in response to an ambiguous search query, the ambiguous search query including a sequence of ambiguous information components, comprising:

at least one memory having program instructions; and

at least one processor configured to execute the program instructions to perform the operations of;

receiving a sequence of ambiguous information components from a user;

obtaining mapping information that maps the ambiguous information components to less ambiguous information components;

using the mapping information, in combination with a lexicon, to convert the sequence of ambiguous information components into at least two corresponding sequences of less ambiguous information components, wherein the lexicon is a list of sequences of less ambiguous information components that previously have been processed by a search engine as search queries;

providing the at least two sequences of less ambiguous information, each of the sequences effectively being joined by a logical “

OR”

operation request, as an input to the a search engine;

obtaining search results from the search engine; and

presenting the search results to the user.

27. An apparatus for providing search results in response to an ambiguous search query, the ambiguous search query including a sequence of ambiguous information components, comprising:

means for receiving a sequence of ambiguous information components from a user;

means for obtaining mapping information that maps the ambiguous information components to less ambiguous information components;

means for using the mapping information, in combination with a lexicon, to convert the sequence of ambiguous information components into at least two corresponding sequences of less ambiguous information components, wherein the lexicon is a list of sequences of less ambiguous information components that previously have been processed by a search engine as search queries;

means for providing the at least two sequences of less ambiguous information, each of the sequences effectively being joined by a logical “

OR”

operation request, as an input to the a search engine;

means for obtaining search results from the search engine; and

means for presenting the search results to the user.