Speaker: Amin Karbasi,Yale Institute of Network Science, Yale University
Title: From Small-World Networks to User-Driven Content Search
In this talk, I will describe a new way of navigating through a database of similar objects using comparisons. In short, at each step, the database presents two objects to the user, who then selects among the pair the object closest to the target that she has in mind. This process continues until, based on the usera s answers, the database can uniquely identify the target she has in mind. This kind of interactive navigation (also known as exploratory search) and its variants have numerous real-life applications in content-based image/multimedia retrieval.
I will argue that the above problem is strongly related to the small-world network design: given a graph embedded in a metric space, how should one augment this graph by adding edges in order to minimize the expected cost of greedy forwarding. I will first show that the small-world network design problem is NP-hard. Given this negative result, I propose a novel mechanism for small-world design and provide an upper bound on its performance. This mechanism has a natural equivalent in the context of content search through comparisons, and I establish both (order optimum) upper and lower bounds for its performance. These bounds are intuitively appealing as they provide performance guarantees in terms of the bias of the distribution of targets, captured by the entropy, as well as the topology of their embedding, captured by the doubling dimension.
For additional information contact: Peter Marbach