INTERACTIVE SEARCH WITH DIFFERENT TYPES OF ATTRIBUTES

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "INTERACTIVE SEARCH WITH DIFFERENT TYPES OF ATTRIBUTES"

By

Mr. Weicheng WANG


Abstract:

The task of efficiently and effectively extracting tuples from databases that
align with user preferences is a critical challenge in the domain of
multi-criteria decision-making. Traditional approaches, such as the top-k query
and the k nearest neighbors query, propose solutions by modeling user
preferences as functions, called utility functions, and thereafter identifying
the k tuples with the highest or lowest function scores. However, these
traditional approaches encounter practical limitations when applied to
real-world scenarios. The crux is that user preferences are typically nuanced,
multi-criteria, and sometimes even unconscious or not fully recognized by the
users themselves. Therefore, users may have difficulties articulating their
preferences in an explicit manner, which is a critical prerequisite for utility
function modeling.

This predicament prompts the exploration and development of interactive
methodologies. In this thesis, we study how to enhance the traditional
approaches with the help of user interaction. Specifically, we engage a user by
posing a series of questions. Each question consists of two tuples and asks the
user to indicate which one s/he prefers. Based on the user feedback, the user's
utility function is learned implicitly, and the tuples with the highest or
lowest function scores w.r.t. the learned utility function are returned.

We classify the attributes of tuples into three distinct types: universally
totally ordered attributes, preference-based ordered attributes, and nominal
attributes. Each type is associated with unique characteristics. The
universally totally ordered attributes, such as the price of a laptop, have
numerical values with inherent orders that are universally recognized. The
preference-based ordered attributes, such as the monitor size of a laptop, also
possess numerical values, yet user preferences on their values vary widely,
lacking universally agreed orders. Lastly, the nominal attributes, like the
color of a laptop, involve categorical values without any inherent universal
orders. This attribute classification forms the foundation of our step-by-step
enhancements to traditional approaches.

In our work, we focus on different types of attributes sequentially, while
upholding a consistent primary objective - to identify tuples that are of
interest to users by asking users as few questions as possible. Our first work
centers around tuples solely described by universally totally ordered
attributes. We propose an algorithm that asks an asymptotically optimal number
of questions in situations where each tuple is described by two attributes. For
scenarios where each tuple is described by multiple attributes, we propose two
algorithms, both backed with provable performance guarantee. Our second work
takes into account tuples that are described by both universally totally
ordered and preference-based ordered attributes. We propose an algorithm that
asks an asymptotically optimal number of questions in cases where each tuple is
described by one universally totally ordered attribute and one preference-based
ordered attribute. Furthermore, in scenarios where tuples are described by an
arbitrary number of attributes, we present two algorithms with verifiable
performance guarantee. Our third work focuses on tuples that are described by
universally totally ordered and nominal attributes. We propose an algorithm
that asks an asymptotically optimal number of questions when each tuple is
exclusively described by nominal attributes. Moreover, in scenarios where
tuples are characterized by both universally totally ordered and nominal
attributes, we introduce an algorithm with a proven performance guarantee.
Compared to current state-of-the-art methods, our work achieves a significant
breakthrough in reducing the number of questions asked to users during the
interaction process.


Date:                   Wednesday, 16 August 2023

Time:                   10:00am - 12:00noon

Venue:                  Room 5501
                        Lifts 25/26

Chairman:               Prof. Yik Man CHIANG (MATH)

Committee Members:      Prof. Raymond WONG (Supervisor)
                        Prof. Yangqiu SONG
                        Prof. Ke YI
                        Prof. Jiachuan YANG (CIVL)
                        Prof. Gautam DAS (University of Texas)


**** ALL are Welcome ****