Method and system for incremental search with reduced text entry where the relevance of results is a dynamically computed function of user input search string character count

• US 8,122,034 B2
• Filed: 10/07/2005
• Issued: 02/21/2012
• Est. Priority Date: 06/30/2005
• Status: Active Grant

• Current Assignee: Veveo, Inc. (Adeia Inc.)
• Original Assignee: Veveo, Inc. (Adeia Inc.)
• Inventors: Aravamudan, Murali, Barve, Rakesh D., Venkataraman, Sashikumar, Rajasekharan, Ajit
• Primary Examiner(s): Boccio, Vincent
• Assistant Examiner(s): Wong, Huen
• Application Number:
  US11/246,432
• Publication Number:
  US 20070005563A1
• Time in Patent Office: 2,328 Days
• Field of Search: 707/1, 707/3, 707/5, 707/6, 707/7, 707/706, 707/748, 707/752, 709/230, 709/231, 715/816, 725/39
• US Class Current: 707/752
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/739 in form of a video summary, e.g. the video summary being a video sequence, a composite still image or having synthesized frames
• CPC Class Codes: G06F 16/7867 using information manually generated, e.g. tags, keywords, comments, title and artist information, manually generated time, location and usage information, user ratings
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: H04N 21/4828 for searching program descriptors retrieval of video data G06F16/739

Abstract

A method and system are provided for processing a search request received from a user operating a text input device. The search request is directed at identifying a desired item from a set of items. Each of the items of the set of items has one or more associated terms. The method includes receiving a query input from a user directed at identifying the desired item. The query input comprises one or more characters input by the user on the text input device. As each character of the query input is received from the user, a group of items having one or more terms matching the characters received thus far of the query input is dynamically identified. The items in this group of items are ordered based on relevance values of the terms matching the characters and on the number of characters of the query input used in identifying the group of items. Identification of the group of items as ordered is transmitted to the user to be displayed on a device operated by the user.

Claims

1. A method of processing a search request received from a user operating a hand-held text input device, the search request directed at identifying a desired item from a set of items, each of the items having one or more associated terms, the method comprising:

providing the set of items, the items having assigned popularity values to indicate a relative measure of a likelihood that the item is desired by the user;

for each item, associating a set of terms to describe the item and assigning a relevance value for each term based on a relevance of the term in identifying the item, the terms associated with the items being organized into searchable subspace categories, each subspace category having a relevance bias value;

receiving text on the hand-held text input device entered by the user, the text having one or more text characters of one or more prefixes for terms the user is using to identify a desired item;

in response to receiving a text character, performing a first incremental find to compare the one or more user-entered prefixes with the terms associated with the items and to retrieve the relevance values for the one or more user-entered prefixes matching terms associated with the items;

determining a first ranking order of items found in the first incremental find based at least in part on the retrieved relevance values and the assigned popularity values of the items found in the first incremental find;

ordering and presenting one or more items to the user found in the first incremental find based on the first ranking order;

in response to receiving at least one subsequent text character, performing a second incremental find to compare the one or more user-entered prefixes, including the at least one subsequent text character and any preceding text characters, with the terms associated with the items and to retrieve the relevance values for said one or more user-entered prefixes matching terms associated with the items;

determining a count of the number of characters of text received from the user;

adjusting the relevance value assigned to at least one of the terms associated with one or more of the items retrieved in response to the one or more user-entered prefixes, wherein the adjusting of the relevance value is based on the count of the number of text characters received from the user;

determining a second ranking order of the items found in the second incremental find based at least in part on the adjusted relevance values and the assigned popularity values of the items found in the second incremental find; and

ordering and presenting one or more items to the user based on the second ranking order so that the relative order of the items found in both the first and second incremental finds is adjusted as characters are entered;

wherein at least one of determining the first ranking order and determining the second ranking order is further based on the relevance bias values of the subspace categories.

2. The method of claim 1, wherein the relevance bias values are based on the count of the number of text characters received from the user.

3. The method of claim 1, wherein the subspace categories include a personalized history category containing terms associated with items identified from previous incremental finds conducted by the user.

4. The method of claim 1, wherein the ordering and presenting of one or more items is limited to items having associated terms of one or more selected subspace categories.

5. The method of claim 4, wherein the one or more selected subspace categories are selected based on the count of the number of text characters received from the user.

6. The method of claim 1, wherein the ordered and presented one or more items are presented on a display device, the display device having display space allocated according to the subspace categories.

7. The method of claim 1, wherein the hand-held text input device includes a set of overloaded keys generating an ambiguous text input.

8. The method of claim 7, wherein the hand-held text input device is a phone, a mobile computing device, or a remote control device for a television.

9. The method of claim 1, wherein the ordered and presented one or more items are presented on a display constrained device.

10. The method of claim 9, wherein the display device is a phone, a mobile computing device, or a non-intrusive interface display area of a television.

11. The method of claim 1, wherein the assigned popularity values of one or more items of the set of items is based on a relative measure of popular opinion of the item.

12. The method of claim 1, wherein the assigned popularity values of one or more items of the set of items is based on a temporal relevance of the items or a location relevance of the items.

13. The method of claim 1, wherein at least one of determining the first ranking order and determining the second ranking order is further based on the number of prefixes of the received text.

14. The method of claim 1, wherein a portion of the set of items resides on a computer remote from the user.

15. The method of claim 1, wherein a computer remote from the user performs at least one of the steps of receiving text entered by the user, performing the first incremental find, determining the first ranking order, performing the second incremental find, determining the count of the number of characters of text received, adjusting the relevance values of the terms associated with the items, and determining the second ranking order.

16. A system for processing a search request received from a user operating a hand-held text input device, the search request directed at identifying a desired item from a set of items, each of the items having one or more associated terms, the system comprising:

a first memory for storing at least a first portion of the set of items, the items having assigned popularity values to indicate a relative measure of a likelihood that the item is desired by the user, and each item being associated with a set of terms to describe the item, each term being assigned a relevance value based on a relevance of an informational content of the term in identifying the item, the terms associated with the items being organized into searchable subspace categories, each subspace category having a relevance bias value;

a device input for receiving text entered by the user on a hand-held text input device, the text having two or more text characters of one or more prefixes for terms the user is using to identify a desired item, the two or more text characters including a first text portion and a second text portion, the second text portion being received subsequent to the first text portion;

a processor for performing a first incremental find in response to receiving the first text portion and for ordering one or more items found in the first incremental find based on a first ranking order, the first incremental find comparing the one or more user-entered prefixes with the terms associated with the items and retrieving the relevance values for the one or more user-entered prefixes matching terms associated with the items, the first ranking order of the one or more items found in the first incremental find being based on the assigned popularity values of the items and being based on the retrieved relevance values for the one or more user-entered prefixes matching terms associated with the items, so that relatively more popular and more relevant items appear earlier in the order for user selection or activation, the processor also for performing a second incremental find in response to receiving the second text portion and for ordering one or more items found in the second incremental find based on a second ranking order, the second incremental find comparing the one or more user-entered prefixes with the terms associated with the items and retrieving the relevance values for the one or more user-entered prefixes matching terms associated with the items, the second ranking order of the one or more items found in the second incremental find being based on the assigned popularity values of the items and being based on adjusted relevance values for the one or more user-entered prefixes matching terms associated with the items, the relevance values of the terms associated with the items being adjusted in response to the count of the number of text characters received from the user, the order of at least a portion of the one or more items being changed based on the adjusted relevance values of the terms, and at least one of the first ranking order and the second ranking order being further based on the relevance bias values of the subspace categories; and

a device output for presenting at least one of the first and the second ordered one or more items to the user.

17. The system of claim 16, wherein the relevance bias values are based on the count of the number of text characters received from the user.

18. The system of claim 16, wherein the subspace categories include a personalized history category containing terms associated with items identified from previous incremental finds conducted by the user.

19. The system of claim 16, wherein the incremental find is limited to items having associated descriptive terms of one or more selected subspace categories.

20. The system of claim 19, wherein the one or more selected subspace categories are selected based on the count of the number of text characters received from the user.

21. The system of claim 16, further comprising a display device for presenting the at least one of the first and the second ordered one or more items, the display device having display space allocated according to the subspace categories.

22. The system of claim 16, wherein the text entered by the user on the hand-held text input device includes a set of overloaded keys generating an ambiguous text input.

23. The system of claim 22, wherein the hand-held text input device is a phone, a mobile computing device, or a remote control device for a television.

24. The system of claim 16, further comprising a display constrained device for presenting the at least one of the first and the second ordered one or more items.

25. The system of claim 24, wherein the display device is a phone, a mobile computing device, or a non-intrusive interface display area of a television.

26. The system of claim 16, wherein the assigned popularity value of one or more items of the set of items is based on a relative measure of popular opinion of the item.

27. The system of claim 16, wherein the assigned popularity value of one or more items of the set of items is based on a temporal relevance of the item or a location relevance of the item.

28. The system of claim 16, wherein at least one of the first ranking order and the second ranking order of the one or more items is further based on a count of the number of prefixes of the received text.

29. The system of claim 16, further comprising a second memory on a computer remote from the user for storing at least a second portion of the set of items.

30. The system of claim 16, wherein the processor is disposed in a computer remote from the user.