Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality

Min Xie, Raymond Chi-Wing Wong, Jian Li, Cheng Long, Ashwin Lall

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Citations (Scopus)

Abstract

Extracting interesting tuples from a large database is an important problem in multi-criteria decision making. Two representative queries were proposed in the literature: top-k queries and skyline queries. A top-k query requires users to specify their utility functions beforehand and then returns k tuples to the users. A skyline query does not require any utility function from users but it puts no control on the number of tuples returned to users. Recently, a k-regret query was proposed and received attention from the community because it does not require any utility function from users and the output size is controllable, and thus it avoids those deficiencies of top-k queries and skyline queries. Specifically, it returns k tuples that minimize a criterion called the maximum regret ratio.

In this paper, we present the lower bound of the maximum regret ratio for the k-regret query. Besides, we propose a novel algorithm, called SPHERE, whose upper bound on the maximum regret ratio is asymptotically optimal and restriction-free for any dimensionality, the best-known result in the literature. We conducted extensive experiments to show that SPHERE performs better than the state-of-the-art methods for the k-regret query.
Original languageEnglish
Title of host publicationProceedings of the 2018 ACM International Conference on Management of Data (SIGMOD)
PublisherAssociation for Computing Machinery (ACM)
Pages959-974
ISBN (Electronic)978-1-4503-4703-7
DOIs
Publication statusPublished - 27 May 2018
Event2018 International Conference on Management
of Data
- Houston, United States
Duration: 10 Jun 201815 Jun 2018

Conference

Conference2018 International Conference on Management
of Data
Abbreviated titleSIGMOD '18
CountryUnited States
CityHouston
Period10/06/201815/06/2018

Fingerprint Dive into the research topics of 'Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality'. Together they form a unique fingerprint.

Cite this