The Indistinguishability Query

We propose the indistinguishability query for iden-tifying all of a user's near-optimal tuples. This query returns all the tuples that are at most a small fraction away from the optimal of the user's unknown utility function. This is motivated by the idea that users can have a hard time distinguishing very similar tuples and in fact even tuples that are slightly inferior in the identified criteria may have additional characteristics that make them more attractive to the user. In order to perform this query without knowledge of the user's utility function, we use a simple interactive framework that asks the user to perform a modest number of comparisons to narrow down their utility function. We show that the indistinguishability query cannot be approximated solely with real tuples in the database and thus our algorithms with provable bounds must present the user with artificial tuples. We also give heuristic algorithms that show the user only real tuples from the database. Since the user may make errors while performing comparisons, we generalize our algorithms to account for user error as well. Experiments on synthetic and real data sets show that the indistinguishability query can be performed accurately while asking the user to compare a small number of tuples.