THESIS
2023
1 online resource (xiv, 151 pages) : illustrations (some color)
Abstract
The task of efficiently and effectively extracting tuples from databases that align with user
preference is a critical challenge in the domain of multi-criteria decision-making. Traditional
operators, such as the top-k query and the k nearest neighbors query, propose
solutions by modeling user preference as functions, called utility functions, and thereafter
identifying the k tuples with the highest or lowest function scores. However, these traditional
operators encounter practical limitations when applied to real-world scenarios. The
crux is that user preference is typically nuanced, multi-criteria, and sometimes not fully
recognized by users themselves. Therefore, users may have difficulties articulating their
preference in an explicit manner, which is a prerequisite for utility funct...[
Read more ]
The task of efficiently and effectively extracting tuples from databases that align with user
preference is a critical challenge in the domain of multi-criteria decision-making. Traditional
operators, such as the top-k query and the k nearest neighbors query, propose
solutions by modeling user preference as functions, called utility functions, and thereafter
identifying the k tuples with the highest or lowest function scores. However, these traditional
operators encounter practical limitations when applied to real-world scenarios. The
crux is that user preference is typically nuanced, multi-criteria, and sometimes not fully
recognized by users themselves. Therefore, users may have difficulties articulating their
preference in an explicit manner, which is a prerequisite for utility function modeling.
This predicament prompts the exploration and development of interactive operators.
In this thesis, we study how to enhance the traditional operators 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: totally ordered attributes,
preference-based attributes, and categorical attributes. Each type is associated with unique
characteristics. The totally ordered attributes, such as the price of a laptop, have numerical
values with inherent orders that are universally recognized. The preference-based
attributes, such as the monitor size of a laptop, also possess numerical values, yet user
preference on their values varies widely, lacking universally agreed orders. Lastly, the
categorical attributes, such as 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 operators.
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
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 totally ordered and preference-based attributes. We propose
an algorithm that asks an asymptotically optimal number of questions in cases where
each tuple is described by one totally ordered attribute and one preference-based attribute.
Furthermore, in scenarios where tuples are described by an arbitrary number of both attributes,
we present two algorithms with verifiable performance guarantee. Our third
work focuses on tuples that are described by totally ordered and categorical attributes.
We propose an algorithm that asks an asymptotically optimal number of questions when
each tuple is exclusively described by categorical attributes. Moreover, in scenarios where
tuples are characterized by both totally ordered and categorical attributes, we introduce
an algorithm with provable performance guarantee. Compared to current state-of-the-art
operators, three of our work achieves a significant breakthrough in reducing the number
of questions asked to users during the interaction process.
Post a Comment