Method and system for processing ambiguous, multi-term search queries

• US 7,788,266 B2
• Filed: 09/27/2005
• Issued: 08/31/2010
• Est. Priority Date: 08/26/2005
• Status: Active Grant

• Current Assignee: Veveo, Inc. (Adeia Inc.)
• Original Assignee: Veveo, Inc. (Adeia Inc.)
• Inventors: Garg, Pankaj, Rajanala, Pranav, Barve, Rakesh D., Aravamudan, Murali, Rajasekharan, Ajit, Venkataraman, Sashikumar
• Primary Examiner(s): Mofiz; Apu M
• Assistant Examiner(s): Nguyen; Cindy
• Application Number:
  US11/235,928
• Publication Number:
  US 20070061321A1
• Time in Patent Office: 1,799 Days
• Field of Search: 707 3- 5
• US Class Current: 707/748
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/84 Mapping; Conversion
• CPC Class Codes: G06F 16/9038 Presentation of query results
• CPC Class Codes: G06F 16/907 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 3/0484 for the control of specific functions or operations, e.g. selecting or manipulating an object, an image or a displayed text element, setting a parameter value or selecting a range

Abstract

In accordance with one or more embodiments of the invention, a method and system are provided of processing a search query entered by a user of a device having a text input interface with overloaded keys. The search query is directed at identifying an item from a set of items. Each of the items has one or more associated descriptors. The system receives from the user an ambiguous search query directed at identifying a desired item. The search query is a prefix substring of each of at least two words relating to the desired item. The system dynamically identifies a group of one or more items from the set of items having one or more descriptors matching the search query as the user enters each character of the search query. The system outputs identification of the one or more items of the identified group to be displayed on the device operated by the user.

Claims

1. A user-interface method for searching a relatively large set of content items in response to unresolved keystroke entry by a user from a keypad with overloaded keys in which a given key is in fixed association with a plurality of alphabetical and numerical symbols and the entry has relatively few keystrokes so that a subset of targeted content item results is quickly presented, the method comprising:

using an ordering criteria to rank and associate subsets of content items with corresponding strings of one or more unresolved keystrokes for overloaded keys so that the subsets of content items are directly mapped to the corresponding strings of unresolved keystrokes;

subsequent to ranking and associating the content items with strings of unresolved

keystrokes, receiving a first unresolved keystroke from a user, wherein one of the plurality of alphabetical and numerical symbols in fixed association with the first unresolved keystroke is a symbol the user is using to search for desired content items;

selecting and presenting the subset of content items that is associated with the first unresolved keystroke based on the direct mapping of unresolved keystrokes to the subsets of content items;

subsequent to receiving the first unresolved keystroke, receiving subsequent unresolved keystrokes from the user and forming a string of unresolved keystrokes including the first unresolved keystroke and the subsequent unresolved keystrokes in the order received;

an

selecting and presenting the subset of content items that is associated with the string of unresolved keystrokes received based on the direct mapping of unresolved keystrokes to the subsets of content items;

wherein at least one of selecting the subset of content items associated with the first unresolved keystroke and selecting the subset of content items associated with the string of unresolved keystrokes is performed using a data structure or a term intersection process or a combination thereof, the data structure including a first storage structure and a second storage structure, the first storage structure including a plurality of subsets of content items, each subset being associated with a corresponding string of unresolved keystrokes, wherein using the data structure to select a subset of content items includes returning the subset of content items of the first storage structure that is associated with the string of unresolved keystrokes entered by the user and retrieving additional content items from the second storage structure if the desired content items are not present in the first storage structure.

2. The method of claim 1 wherein said ordering criteria include one or more of:

temporal relevance, location relevance, popularity, personal preferences and character count.

3. The method of claim 1 wherein associating subsets of content items with corresponding strings of unresolved keystrokes comprises indexing said content items by performing a many-to-many mapping of descriptors associated with said content items to unresolved keystroke strings corresponding to various search query prefix substrings.

4. The method of claim 1 wherein the user presses one of said overloaded keys once to generate each character of said unresolved keystroke entry.

5. The method of claim 1 wherein said unresolved keystroke entry comprises words in an ordered format.

6. The method of claim 1 wherein said unresolved keystroke entry comprises words in an unordered format.

7. The method of claim 1 wherein said unresolved keystroke entry comprises words separated by a word separator.

8. The method of claim 1 wherein said unresolved keystroke entry is processed by a server system remote from said user.

9. The method of claim 1 wherein said unresolved keystroke entry is processed by said device operated by said user.

10. The method of claim 1 further comprising determining descriptors to describe the content items, wherein content items having similar descriptors are grouped into the same subsets of content items.

11. The method of claim 10 wherein said content items comprise television content items, and wherein each descriptor includes title, cast, director, description, or keyword information relating to a content item.

12. The method of claim 1 wherein said content items include a product or service sought by the user.

13. The method of claim 1 wherein the unresolved keystrokes are input by a user on one of a cell phone, a PDA or a remote control device for a television.

14. The method of claim 1, further comprising, from time-to-time, using the ordering criteria to update the subsets of content items associated with the corresponding strings of one or more unresolved keystrokes.

15. A system for searching a relatively large set of content items in response to unresolved keystroke entry by a user from a keypad with overloaded keys in which a given key is in fixed association with a plurality of alphabetical and numerical symbols and the entry has relatively few keystrokes so that a subset of targeted content item results is quickly presented, the system comprising:

a collection of subsets of content items associated with corresponding strings of one or more unresolved keystrokes for overloaded keys, the subsets of content items being ranked and associated with the content items based on an ordering criteria so that the subsets of content items are directly mapped to the corresponding strings of unresolved keystrokes; and

a computer memory comprising instructions for causing a computer system to;

receive a first unresolved keystroke from a user, wherein one of the plurality of alphabetical and numerical symbols in fixed association with the first unresolved keystroke is a symbol the user is using to search for desired content items select and present the subset of content items that is associated with the first unresolved keystroke based on the direct mapping of unresolved keystrokes to the subsets of content items;

subsequent to receiving the first unresolved keystroke, receive subsequent unresolved keystrokes from the user and form a string of unresolved keystrokes including the first unresolved keystroke and the subsequent unresolved keystrokes in the order received; and

select and present the subset of content items that is associated with the string of unresolved keystrokes received based on the direct mapping of unresolved keystrokes to the subsets of content items;

wherein at least one of selecting and presenting the subset of content items that is associated with the first unresolved keystroke and selecting and presenting the subset of content items that is associated with the string of unresolved keystrokes selects the subset of content items using a data structure or a term intersection process or a combination thereof, the data structure including a first storage structure and a second storage structure, the first storage structure including a plurality of subsets of content items, each subset being associated with a corresponding string of unresolved keystrokes, wherein using the data structure to select a subset of content items includes returning the subset of content items of the first storage structure that is associated with the string of unresolved keystrokes entered by the user and retrieving additional content items from the second storage structure if the desired content items are not present in the first storage structure.

16. The system of claim 15 wherein said ordering criteria include one or more of:

temporal relevance, location relevance, popularity, personal preferences and character count.

17. The system of claim 15 wherein the collection of subsets of content items associated with corresponding strings includes a many-to-many mapping of descriptors associated with said content items to unresolved keystroke strings corresponding to various search query prefix substrings.

18. The system of claim 15 wherein the user presses one of said overloaded keys once to generate each character of said unresolved keystroke entry.

19. The system of claim 15 wherein said unresolved keystroke entry comprises words in an ordered format.

20. The system of claim 15 wherein said unresolved keystroke entry comprises words in an unordered format.

21. The system of claim 15 wherein said unresolved keystroke entry comprises words separated by a word separator.

22. The system of claim 15 wherein at least one of receiving a first unresolved keystroke from the user, selecting and presenting the subset of content items that is associated with the first unresolved keystroke, receiving subsequent unresolved keystrokes from the user and forming a string of unresolved keystrokes, and selecting and presenting the subset of content items that is associated with the string of unresolved keystrokes occurs on a server system remote from said user.

23. The system of claim 15 wherein at least one of receiving a first unresolved keystroke from the user, selecting and presenting the subset of content items that is associated with the first unresolved keystroke, receiving subsequent unresolved keystrokes from the user and forming a string of unresolved keystrokes, and selecting and presenting the subset of content items that is associated with the string of unresolved keystrokes occurs on said device operated by said user.

24. The system of claim 15 wherein content items having similar descriptors are grouped into the same subsets of content items.

25. The system of claim 24 wherein said content items comprise television content items, and wherein each descriptor includes title, cast, director, description, or keyword information relating to a content item.

26. The system of claim 15 wherein said items comprise products or services sought by said user.

27. The system of claim 15 wherein the unresolved keystrokes are input by a user on one of a cell phone, a PDA or a remote control device for a television.

28. The system of claim 15, the computer memory further comprising instructions for causing the computer system to use the ordering criteria to update the subsets of content items associated with the corresponding strings of one or more unresolved keystrokes from time-to-time.

29. The system of claim 15, wherein at least a portion of the collection of subsets of content items associated with corresponding string of one or more unresolved keystrokes is on a server system remote from said user.

30. The system of claim 15, wherein at least a portion of the collection of subsets of content items associated with corresponding string of one or more unresolved keystrokes is on said device operated by said user.

31. The system of claim 15, wherein said content items comprise information about audio/video content.