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

• US 20070061321A1
• Filed: 09/27/2005
• Published: 03/15/2007
• Est. Priority Date: 08/26/2005
• Status: Active Grant

• Current Assignee: Veveo, Inc. (Adeia Inc.)
• Original Assignee: Veveo, Inc. (Adeia Inc.)
• Inventors: Aravamudan, Murali, Rajasekharan, Ajit, Barve, Rakesh, Venkataraman, Sashikumar, Garg, Pankaj, Rajanala, Pranav
• Granted Patent: US 7,788,266 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 method of processing a search query entered by a user of a device having a text input interface with overloaded keys, said search query being directed at identifying an item from a set of items, each of said items having one or more associated descriptors, said method comprising:

(a) receiving from the user an ambiguous search query directed at identifying a desired item, said search query comprising a prefix substring of each of at least two words relating to said desired item;

(b) dynamically identifying a group of one or more items from said set of items having one or more descriptors matching said search query as said user enters each character of said search query; and

(c) outputting identification of said one or more items of said group identified in (b) to be displayed on the device operated by said user.

2. The method of claim 1 further comprising ordering said one or more items of said group identified in (b) in accordance with one or more given criteria.

3. The method of claim 2 wherein said one or more given criteria include one or more of:

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

4. The method of claim 1 wherein said overloaded keys each represent a number and at least two alphabetic characters, and wherein said method further comprises indexing said items by performing a many-to-many mapping of said descriptors associated with said items to numeric strings corresponding to various search query prefix substrings.

5. The method of claim 1 wherein said step (b) is performed using a trie data structure or a term intersection process or a combination thereof.

6. The method of claim 1 wherein the user presses one of said overloaded keys once to generate each character of said search query.

7. The method of claim 1 wherein said search query comprises words in an ordered format.

8. The method of claim 1 wherein said search query comprises words in an unordered format.

9. The method of claim 1 wherein said search query comprises words separated by a word separator.

10. The method of claim 1 wherein said search query is processed by a server system remote from said user.

11. The method of claim 1 wherein said search query is processed by said device operated by said user.

12. The method of claim 1 further comprising determining said descriptors prior to receiving said reduced text search query from the user.

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

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

15. The method of claim 1 wherein said device is a cell phone, a PDA or a remote control device for a television.

16. A system for processing a search query entered by a user of a device having a text input interface with overloaded keys, said search query being directed at identifying an item from a set of items, each of said items having one or more associated descriptors, said system comprising:

a memory for storing identification of said set of items and associated descriptors; and

a processor for (a) receiving a user input of an ambiguous search query directed at identifying a desired item, said search query comprising a prefix substring of each of at least two words relating to said desired item;

(b) dynamically identifying a group of one or more items from said set of items having one or more descriptors matching said search query as said user enters each character of said search query; and

(c) outputting identification of said one or more items of said group to be displayed on the device operated by said user.

17. The system of claim 16 wherein said processor orders said one or more items of said group in accordance with one or more given criteria.

18. The system of claim 17 wherein said one or more given criteria include one or more of:

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

19. The system of claim 16 wherein said overloaded keys of said device each represent a number and at least two alphabetic characters, and wherein said processor indexes said items by performing a many-to-many mapping of said descriptors associated with said items to numeric strings corresponding to various search query prefix substrings.

20. The system of claim 16 wherein said processor identifies said group using a trie data structure or a term intersection process or a combination thereof.

21. The system of claim 16 wherein the user presses one of said overloaded keys once to generate each character of said search query.

22. The system of claim 16 wherein said search query comprises words in an ordered format.

23. The system of claim 16 wherein said search query comprises words in an unordered format.

24. The system of claim 16 wherein said search query comprises words separated by a word separator.

25. The system of claim 16 wherein said processor and memory are part of a server system remote from said user.

26. The system of claim 16 wherein said processor and memory are part of said device operated by said user.

27. The system of claim 16 wherein said descriptors are determined prior to said processor receiving said reduced text search query from the user.

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

29. The method of claim 16 wherein said items comprise products or services sought by said user.

30. The system of claim 16 wherein said device is a cell phone, a PDA or a remote control device for a television.

31. A system for processing search queries entered by users of devices having a text input interface with overloaded keys, said search queries being directed at identifying an item from a set of items, each of said items having one or more associated descriptors, said system comprising:

a server;

a plurality of devices operated by users, said devices each having a text input interface with overloaded keys, said devices each transmitting to the server an ambiguous search query directed at identifying a desired item, each said search query comprising a prefix substring of each of at least two words relating to said desired item;

a network for transmitting data between said server and said devices; and

a database for storing identification of said set of items and associated descriptors;

wherein for each search query received from a device, said server dynamically identifies a group of one or more items from a set of items having one or more descriptors matching said search query as said user enters each character of said search query, and transmits identification of said one or more items of said identified group to the device to be displayed to said user.

32. The system of claim 31 wherein said server orders said one or more items of said group in accordance with one or more given criteria.

33. The system of claim 32 wherein said one or more given criteria include one or more of:

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

34. The system of claim 31 wherein said overloaded keys of said devices each represent a number and at least two alphabetic characters, and wherein said server indexes said items by performing a many-to-many mapping of said descriptors associated with said items to numeric strings corresponding to various search query prefix substrings.

35. The system of claim 31 wherein said server identifies said group using a trie data structure or a term intersection process or a combination thereof.

36. The system of claim 31 wherein for each device, the user presses one of said overloaded keys once to generate each character of said search query.

37. The system of claim 31 wherein each said search query comprises words in an ordered format.

38. The system of claim 31 wherein each said search query comprises words in an unordered format.

39. The system of claim 31 wherein each said search query comprises words separated by a word separator.

40. The system of claim 31 wherein said descriptors are determined prior to said server receiving said reduced text search query from the user.

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

42. The method of claim 31 wherein said items comprise products or services sought by said users.

43. The system of claim 31 wherein said devices include cell phones, PDAs or television remote control devices.