On Improving Robustness of Interactive Queries

PhD Thesis Proposal Defence


Title: "On Improving Robustness of Interactive Queries"

by

Mr. Qixu CHEN


Abstract:

The task of efficiently and effectively extracting interesting tuples from 
databases is a significant challenge in multi-criteria decision-making. Given a 
large dataset, it is both impractical and burdensome for users to manually 
search for tuples that match their interests. Traditional approaches, such as 
the top-$k$ query and the $k$ nearest neighbors query, propose solutions by 
modeling user preferences as a preference function and identifying the top 
tuples based on scores. However, these approaches often struggle in real-world 
applications, since users often find it difficult when attempting to articulate 
their preferences explicitly, which are typically nuanced and multi-criteria, 
sometimes even unconscious or not fully recognized by the users themselves.

Recent studies propose interactive queries, which suggest using user 
interactions to learn the user's preference, and return the points of interest 
based on the learnt preference. One popular type of interaction involves asking 
the user several rounds of questions, each requiring him/her to compare 2 
points for choosing a more preferred one. However, one crucial limitation in 
existing methods of this direction lies in their implicit assumption on user's 
reliability, ignoring that the user may provide unreliable feedback during 
interaction. We categorize the user's unreliability into two broad types of 
errors, namely random errors, where feedback may be incorrect with some 
probability, and persistent errors, where certain interactions consistently 
yield incorrect feedback.

In this thesis, we explore how to improve the robustness of interactive queries 
by addressing potential user errors. Specifically, in the first study, we 
tackle random errors and propose an algorithm that minimizes the number of 
questions needed when each tuple has two attributes. Moreover, for scenarios 
where each tuple is described by multiple attributes, we propose two 
algorithms, both with provable performance guarantees. In the second study, we 
develop techniques to handle both random and persistent errors, proposing two 
algorithms, one with asymptotically optimal round efficiency, and the other 
with a small number of rounds empirically. Compared to existing methods, our 
work greatly enhances the robustness of interactive queries against potential 
user errors.


Date:                   Monday, 7 October 2024

Time:                   4:00pm - 6:00pm

Venue:                  Room 5501
                        Lifts 25/26

Committee Members:      Prof. Raymond Wong (Supervisor)
                        Prof. Xiaofang Zhou (Chairperson)
                        Dr. Wilfred Ng
                        Prof. Dimitris Papadias