High-dimensional Regret Minimization DOI: XXXXXXX.XXXXXXX Conference: 2026 ACM SIGMOD/PODS Conference; May 31–June 05; Bengaluru, India ISBN: 978-1-4503-XXXX-X/2018/06
Junyu Liao, Ashwin Lall, Mitsunori Ogihara, Raymond Chi-Wing Wong · 2025
Read High-dimensional Regret Minimization DOI: XXXXXXX.XXXXXXX Conference: 2026 ACM SIGMOD/PODS Conference; May 31–June 05; Bengaluru, India ISBN: 978-1-4503-XXXX-X/2018/06 by Junyu Liao, Ashwin Lall, Mitsunori Ogihara, Raymond Chi-Wing Wong (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-24078.txt.
Introduction
Junyu Liao, Ashwin Lall, Mitsunori Ogihara, and Raymond Wong work on interactive queries. Such a query learns what a user wants. It shows small sets of options. The user picks a favorite. The query then gradually homes in on the best recommendation.
The catch is scale. Housing and financial datasets can carry hundreds of attributes. Older methods slow down badly at that size. Others pester the user through a thousand rounds or more. The team's framework, FHDR, avoids both failures. It answers in under a hundredth of a second. It needs fewer than thirty rounds of feedback. Experiments compared it with the best known algorithms. FHDR won by at least ten times on running time. On interaction counts, the margin was far larger. The authors call it a new state of the art.
Catalog record
| CREATOR | Junyu Liao, Ashwin Lall, Mitsunori Ogihara, Raymond Chi-Wing Wong |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 80 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-24078
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
High-dimensional Regret Minimization DOI: XXXXXXX.XXXXXXX Conference: 2026 ACM SIGMOD/PODS Conference; May 31–June 05; Bengaluru, India ISBN: 978-1-4503-XXXX-X/2018/06 Junyu Liao, Ashwin Lall, Mitsunori Ogihara, Raymond Chi-Wing Wong Abstract . Multi-criteria decision making in large databases is very important in real world applications. Recently, an interactive query has been studied extensively in the database literature with the advantage of both the top- k k query (with limited output size) and the skyline query (which does not require users to explicitly specify their preference function). This approach iteratively asks the user to select the one preferred within a set of options. Based on rounds of feedback, the query learns the implicit preference and returns the most favorable as a recommendation. However, many modern applications in areas like housing or financial product markets feature datasets with hundreds of attributes. Existing interactive algorithms either fail to scale or require excessive user interactions (often exceeding 1000 1000 rounds). Motivated by this, we propose FHDR ( F ast H igh- D imensional R eduction), a novel framework that takes less than 0.01 s 0.01s with fewer than 30 30 rounds of interaction. It is considered a breakthrough in the field of interactive queries since most, if not all, existing studies are not scalable to high-dimensional datasets. Extensive experiments demonstrate that FHDR outperforms the best-known algorithms by at least an order of magnitude in execution time and up to several orders of magnitude in terms of the number of interactions required, establishing a new state of the art for scalable interactive regret minimization. 1. Introduction Multi-criteria decision making in a large database containing a number of tuples/options is very important in real world applications. A common approach to facilitating user decision-making in databases is to model user preference as a utility function ( 7 ; 31 ; 32 ) , which assigns each tuple a numerical score. Knowledge of this function—either explicit or implicit—enables systems to reduce user effort in identifying preferred tuples. Two major paradigms built on this assumption are (1) the top- k query ( 16 ; 36 ; 42 ; 23 ; 24 ) and (2) the skyline query ( 5 ; 6 ; 25 ; 29 ; 35 ) . (1) In a top- k query, the user explicitly provides a utility function and an integer k , and the system returns the k highest-scoring tuples. While conceptually straightforward, this approach is impractical when the user cannot specify precise weights in the utility function—especially in high-dimensional data, where hundreds of attributes make this specification infeasible. (2) The skyline query, by contrast, assumes only that the utility function is component-wise monotonic: if one tuple is no worse than another in every attribute, its utility is at least as high. The system thus returns all skyline points, i.e., tuples not dominated by any other. Although this avoids requiring an explicit utility function, its major drawback is the output size—the number of skyline tuples increases rapidly with dimensionality. This is because with more dimensions, the probability of a tuple being dominated in all dimensions becomes smaller. Consequently, without explicit knowledge of the utility function, skyline systems may still overwhelm the user with an unmanageable number of results. Recently, the k -regret query ( 1 ; 2 ; 32 ; 37 ; 49 ) has emerged as a promising solution to the limitations of top- k and skyline queries. The method selects k representative tuples such that, for any possible user preference, the best tuple in the returned set closely approximates the global optimum in the database. The difference between these two utilities is measured by the regret ratio (defined in Section 3 ), and the objective is to minimize its maximum value across all utility functions. A lower maximum regret ratio indicates that users experience less regret when choosing from the returned set rather than from the entire database. All the aforementioned frameworks operate in a single round, presenting all candidate tuples to the user at once. This naturally raises the question: can multiple rounds of interaction further reduce regret or output size? To address this, interactive regret minimization frameworks ( 31 ; 50 ) have been proposed, where the system iteratively presents a few candidate tuples per round, learns the user’s implicit utility function from their choices, and progressively refines subsequent recommendations. Most previous studies have focused on databases with only a small number of attributes, typically in the range of 2\sim 10 . The user is required to specify the attributes they are interested in prior, which is often difficult. In this paper, we take a step further into a high-dimensional setting , where each item may be described by more than a hundred attributes, without having the user to make that prior decision. These scenarios are increasingly common in modern applications, like housing markets (price, size, location, age, etc.) and financial products (interest rate, risk level, liquidity, historical performance, etc.). In these domains, the dimensionality poses significant challenges: computational costs grow exponentially, theoretical guarantees become weaker, and traditional algorithms often fail to provide meaningful representative subsets. These challenges highlight the urgent need for novel algorithms that can handle high-dimensional data both effectively and efficiently. We want algorithms that satisfy the following requirements: • Quality. The algorithm should produce recommendations of consistently high quality. In particular, the number of returned options should remain small and manageable, while the regret ratio of the result set should be minimized. Ideally, the algorithm should be capable of identifying the user’s favorite option from the entire database. • Efficiency. The algorithm must execute within a reasonable time. For high-dimensional datasets with potentially millions of tuples, excessive computation time renders the solution impractical for real-world applications. • Usability. The interaction process should require minimal effort for the user. This means relying only on simple, intuitive questions and keeping the number of interactions small, so that the system remains practical and user-friendly even when dimensionality grows. These requirements are essential for high-dimensional regret minimization, since the returned set is not useful without high quality, the method cannot scale without efficiency, and the approach is unlikely to be adopted in practice without usability. Our work is motivated by a key observation that, in practice, users rarely value all attributes equally. Instead, they typically focus on a much smaller subset of attributes. For instance, when purchasing a house, a property may be described by hundreds of attributes such as floor area, age, nearby amenities, and energy efficiency. Yet most buyers base their decisions primarily on a few key factors (e.g., price, size, and location) while treating the rest as secondary. This behavioral pattern has been widely documented across fields such as cognitive psychology ( 14 ; 17 ; 26 ; 15 ) and conjoint analysis ( 46 ; 40 ; 44 ; 12 ) , as well as supported by our own survey, all indicating that human decision-making generally depends on a limited number of salient attributes rather than the full feature set. In psychology, the “Take-The-Best” heuristic ( 14 ; 17 ) shows that people often make accurate decisions using only a few key attributes. The rule ranks attributes by importance and bases the choice on the first few that distinguish