Adaptive Content Search Through Comparisons

Details Adaptive Content Search Through Comparisons Adaptive Content Search Through Comparisons

2011-07-15

arxiv.org/abs/1107.3059v1

Computer Science

Learning

34 pages, 4 figures, Submitted to the Journal of Machine Learning Research (JMLR)

Scientific paper

We study the problem of navigating through a database of similar objects using comparisons. This problem is known to be strongly related to the small-world network design problem. However, contrary to prior work, which focuses on cases where objects in the database are equally popular, we consider here the case where the demand for objects may be heterogeneous. We show that, under heterogeneous demand, the small-world network design problem is NP-hard. Given the above negative result, we propose a novel mechanism for small-world design and provide an upper bound on its performance under heterogeneous demand. The above mechanism has a natural equivalent in the context of content search through comparisons, and we establish both an upper bound and a lower bound for the performance of this mechanism. These bounds are intuitively appealing, as they depend on the entropy of the demand as well as its doubling constant, a quantity capturing the topology of the set of target objects. Finally, based on these results, we propose an adaptive learning algorithm for content search that meets the performance guarantees achieved by the above mechanisms.

Affiliated with

Also associated with

No associations

Rating

Adaptive Content Search Through Comparisons does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Adaptive Content Search Through Comparisons, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive Content Search Through Comparisons will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-226337