Fast Interactive Search with a Scale-Free Comparison Oracle
Daniyar Chumbalov Lars Klein Lucas Maystre Matthias Grossglauser
A comparison-based search algorithm lets a user find a target item $t$ in a
database by answering queries of the form, ``Which of items $i$ and $j$ is
closer to $t$?'' Instead of formulating an explicit query (such as one or
several keywords), the user navigates towards the target via a sequence of such
(typically noisy) queries.
  We propose a scale-free probabilistic oracle model called $\gamma$-CKL for
such similarity triplets $(i,j;t)$, which generalizes the CKL triplet model
proposed in the literature. The generalization affords independent control over
the discriminating power of the oracle and the dimension of the feature space
containing the items.
  We develop a search algorithm with provably exponential rate of convergence
under the $\gamma$-CKL oracle, thanks to a backtracking strategy that deals
with the unavoidable errors in updating the belief region around the target.
  We evaluate the performance of the algorithm both over the posited oracle and
over several real-world triplet datasets. We also report on a comprehensive
user study, where human subjects navigate a database of face portraits.