Content Search Through Comparisons
We study the problem of navigating through a database of similar objects using comparisons under heterogeneous demand, a prob- lem strongly related to small-world network design. 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 network design and provide an upper bound on its perfor- mance under heterogeneous demand. The above mechanism has a natural equivalent in the context of content search through comparisons, again under heterogeneous demand; we use this to establish both upper and lower bounds on content search through comparisons. 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, we propose an adaptive learning algorithm for content search that meets the performance guarantees achieved by the above mechanisms.