From Small-World Networks to Comparison-Based Search
From MaRDI portal
Publication:2977407
DOI10.1109/TIT.2015.2418284zbMATH Open1359.94959arXiv1107.3059OpenAlexW1974431111MaRDI QIDQ2977407FDOQ2977407
Laurent Massoulié, Stratis Ioannidis, Amin Karbasi
Publication date: 28 April 2017
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: The problem of content search through comparisons has recently received considerable attention. In short, a user searching for a target object navigates through a database in the following manner: the user is asked to select the object most similar to her target from a small list of objects. A new object list is then presented to the user based on her earlier selection. This process is repeated until the target is included in the list presented, at which point the search terminates. 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. They also illustrate interesting connections between comparison-based search to classic results from information theory. Finally, we propose an adaptive learning algorithm for content search that meets the performance guarantees achieved by the above mechanisms.
Full work available at URL: https://arxiv.org/abs/1107.3059
Small world graphs, complex networks (graph-theoretic aspects) (05C82) Applications of graph theory to circuits and networks (94C15)
Cited In (1)
This page was built for publication: From Small-World Networks to Comparison-Based Search
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2977407)
