This is an old revision of the document!
A New Model for an Interactive Browser In this work we consider the problem of searching in a database of objects . Contrary to traditional databases, users do not submit queries that are subsequently matched to objects. Instead, a search for a target object is conducted in several phases. In each phase, a user is presented with a list of database objects. The user selects from this list the object that is most similar to the target she wishes to find. A new list is then presented to the user, and the above process is repeated. When the target item is among the items presented to the user, she retrieves this item and the search terminates. The above problem and has several important real-life applications, for instance navigating through a database of pictures of humans, such as Flickr or Picasa, in which subjects are photographed under a variety of non-idealized conditions.
The use of interactive methods (i.e., that incorporate human feedback) for content search has a long history in literature. Arguably, the first oracle considered to model such methods is the so-called membership oracle, which allows the search mechanism to ask a user questions of the form “does the target belong to set A”. Branson et al. deploy such an interactive method for object classification and evaluate it on the Ani- mals with attributes database. A similar approach was used by Geman et al who formulated shape recognition as a coding problem and applied this approach to handwritten numerals and satellite images. Having access to a membership oracle however is a strong assumption, as humans may not necessarily be able to answer queries of the above type for any object set A. Moreover, the large number of possible sets makes the cost of designing optimal querying strategies over large datasets prohibitive.
One way to address the above constraints is through a graphical model.