Multimedia database retrieval system which maintains a posterior probability distribution that each item in the database is a target of a search

• US 5,696,964 A
• Filed: 04/16/1996
• Issued: 12/09/1997
• Est. Priority Date: 04/16/1996
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Research Institute, Inc. (NEC Corporation)
• Inventors: Omohundro, Stephen M., Miller, Matthew L., Cox, Ingemar J., Yianilos, Peter N.
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US08/634,313
• Time in Patent Office: 602 Days
• Field of Search: 395/601, 395/602, 395/603, 395/604, 395/605, 395/615, 395/326, 395/968
• US Class Current: 1/1
• 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/5838 using colour
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A queryless, multimedia database search method incorporating a Bayesian inference engine that refines its answer with each user response. The set of user responses includes of a series of displays and user actions, and is defined by a relatively simple user interface.

Claims

1. An interactive method for finding items in a database, said method comprising the steps of:

generating a list of N items according to a procedure based upon a probability distribution over the items in the database;

displaying said list of N items to a user;

capturing a user response to the displayed items through an interactive user-interface, wherein said response expresses a relation between the displayed items and an item being searched for;

recomputing the probability distribution over items in the database according to the user response; and

repeating the above steps until the item being searched for is one of the N items displayed.

2. The method according to claim 1 wherein said generating step generates a list of N most probable items.

3. The method according to claim 1 wherein said generating step generates the lists of N items such that any mutual information between the user response and the item searched for is maximized.

4. The method according to claim 3 in which the list of N items to be displayed is chosen by:

(i) placing the highest probability item on the list;

(ii) using a subset of the items in the database, finding an item which when added to the list results in a combination having the highest estimated mutual information;

(iii) adding the item to the list; and

repeating the above steps (ii)-(iii) until the list contains N items.

5. The method according to claim 3 wherein the method of estimating mutual information comprises the steps of:

initializing, in decreasing order of probability, a complete list of possible targets;

choosing from the list a set of sample targets having equally spaced probabilities; and

computing the mutual information between the sample targets and the user response where each of the sample targets has equal prior probability.

6. The method according to claim 1 wherein said capturing step further includes the user responding to displayed items by identifying the items that are most similar to the item being searched for.

7. The method according to claim 1 wherein said capturing step further includes the user responding to the displayed items by indicating a degree of similarity between the displayed items and the item being searched for.

8. The method according to claim 1 wherein said capturing step further includes the user responding to displayed items by indicating aspects or components of the displayed items that are similar to the item being searched for.

9. The method according to claim 1 wherein said recomputing step includes computing a new probability distribution over items in the database from the user response according to Bayes'"'"' rule and an algorithmic model of the user wherein said algorithmic model computes a probability distribution over response, conditioned on items displayed and items being searched for.

10. The method according to claim 9 wherein:

the algorithmic model of the user employs a set of precomputed features of the items in the database.

11. The method according to claim 9 wherein:

the algorithmic model of the user employs a set of manually entered features of the items in the database.

12. The method according to claim 9 wherein:

the algorithmic model of the user assigns an independent probability of the user identifying each displayed item as closest to the item being searched for, and computes the probability of any given combination of indications as the product of the probabilities of the indicated items times the product of one minus the non-indicated items.

13. The method according to claim 12 wherein:

the probability of each displayed item being identified as closest to the item being searched for is computed as the product of the probabilities that the user will consider that displayed item to be closer than the other displayed items.

14. The method according to claim 10, wherein the database is a database of images and one of the precomputed features is a histogram of basic colors.

15. The method according to claim 1 wherein the database is a database of images.

16. The method according to claim 1 wherein the database is a database of sounds.

17. The method according to claim 1 wherein the database is a database of video clips.

18. The method according to claim 1 wherein the database is a database of 2d shapes.

19. The method according to claim 1 wherein the database is a database of 3d shapes.

20. The method according to claim 1 wherein the database is a database of text.

21. An interactive method for measuring the effectiveness of a database search, said method comprising the steps of:

generating a target object for which to be searched;

displaying said target object and a set of candidate objects to a user;

measuring the search effectiveness by evaluating one or more metrics of difficulty user has in finding the target; and

repeating the above steps while averaging the measures of difficulty.