US5696964A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multimedia database retrieval system which maintains a posterior probability distribution that each item in the database is a target of a search
Assignee: NEC Corp
•
Filing: 1996-04-16
•
Granted: 1997-12-09
•
Expires: 2016-04-16
Abstract
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.
Inventors
- 👤 Ingemar J. Cox
- 👤 Matthew L. Miller
- 👤 Stephen M. Omohundro
- 👤 Peter N. Yianilos
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 18:38
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/40; G06F16/50; G06F16/58; G06F16/583; G06F16/5838; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99935; Y10S707/99941; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
105 words
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.
Claim 2
Dependent Claim
105 words
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.
Claim 3
Dependent Claim
18 words
The method according to claim 1 wherein said generating step generates a list of N most probable items.
Claim 4
Dependent Claim
32 words
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.
Claim 5
Dependent Claim
76 words
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.
Claim 6
Dependent Claim
65 words
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.
Claim 7
Dependent Claim
32 words
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.
Claim 8
Dependent Claim
35 words
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.
Claim 9
Dependent Claim
36 words
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.
Claim 10
Dependent Claim
55 words
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.
Claim 11
Dependent Claim
25 words
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.
Claim 12
Dependent Claim
26 words
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.
Claim 13
Dependent Claim
61 words
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.
Claim 14
Dependent Claim
47 words
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.
Claim 15
Dependent Claim
26 words
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.
Claim 16
Dependent Claim
14 words
The method according to claim 1 wherein the database is a database of images.
Claim 17
Dependent Claim
14 words
The method according to claim 1 wherein the database is a database of sounds.
Claim 18
Dependent Claim
15 words
The method according to claim 1 wherein the database is a database of video clips.
Claim 19
Dependent Claim
15 words
The method according to claim 1 wherein the database is a database of 2d shapes.
Claim 20
Dependent Claim
15 words
The method according to claim 1 wherein the database is a database of 3d shapes.
Claim 21
Dependent Claim
14 words
The method according to claim 1 wherein the database is a database of text.
Claim 22
Dependent Claim
68 words
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.
Claim 23
Dependent Claim
68 words
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.
References Cited (Backward Citations)
US5579471A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-12-08 | 2001-06-09 | 2001-12-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-12-08 | 2005-06-09 | 2005-12-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-12-08 | 2009-06-09 | 2009-12-09 | $7700.00 | Window Closed / Lapsed |