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

A method, system and computer program product for efficiently identifying images, videos, audio files or documents relevant to a user using binary search trees in attribute space for guiding relevance feedback. A binary tree is constructed for each relative attribute of interest. A “pivot exemplar” (at a node of the binary tree) is set for each relative attribute's binary tree as corresponding to the database image, video, audio file or document with a median relative attribute value among that subtree's child examples. A pivot exemplar out of the available current pivot exemplars that has the highest expected information gain is selected to be provided to the user. Comparative attribute feedback is then received from the user regarding whether a degree of the attribute in the user's target image, video, audio file or document is more, less or equal with the attribute displayed in the selected pivot exemplar.