Efficiently identifying images, videos, songs or documents most relevant to the user using binary search trees on attributes for guiding relevance feedback

A computer program product embodied in a computer readable storage medium for efficiently identifying images, videos, audio files or documents relevant to a user using attribute binary trees for guiding relevance feedback, the computer program product comprising the programming instructions for:

• constructing a binary search tree for each relative attribute of interest in a pool of database images, videos, audio files or documents;
• setting a current pivot exemplar for each binary tree as corresponding to a database image, video, audio file or document with a median relative attribute value among all remaining database items in a subtree;
• predicting an information gain that would result from asking a user how a user's target image, video, audio file or document compares to each pivot exemplar of a plurality of pivot exemplars, wherein said comparison is made in terms of an attribute associated with that pivot's binary tree;
• providing a pivot exemplar deemed most informative from among said plurality of pivot exemplars to a user to provide a comparison between said attribute in said user's target image, video, audio file or document and in said current pivot exemplar;
• and
• receiving comparative attribute feedback from said user regarding whether a degree of said attribute in said user's target image, video, audio file or document is more, less or equal with said attribute displayed in said provided pivot exemplar.

A system, comprising:

• a memory unit for storing a computer program for efficiently identifying images, videos, audio files or documents relevant to a user using attribute binary trees for guiding relevance feedback;
• and
• a processor coupled to said memory unit, wherein said processor, responsive to said computer program, comprises:
• circuitry for constructing a binary search tree for each relative attribute of interest in a pool of database images, videos, audio files or documents;
• circuitry for setting a current pivot exemplar for each binary tree as corresponding to a database image, video, audio file or document with a median relative attribute value among all remaining database items in a subtree;
• circuitry for predicting an information gain that would result from asking a user how a user's target image, video, audio file or document compares to each pivot exemplar of a plurality of pivot exemplars, wherein said comparison is made in terms of an attribute associated with that pivot's binary tree;
• circuitry for providing a pivot exemplar deemed most informative from among said plurality of pivot exemplars to a user to provide a comparison between said attribute in said user's target image, video, audio file or document and in said current pivot exemplar;
• and
• circuitry for receiving comparative attribute feedback from said user regarding whether a degree of said attribute in said user's target image, video, audio file or document is more, less or equal with said attribute displayed in said provided pivot exemplar.