Abstract
Finding a small representative subset of a database that minimizes user regret is a critical task for multi-criteria decision support. This paper proves that the $k$-regret minimizing set problem is NP-complete for dimensions $d \ge 3$. To address this hardness, we introduce two efficient approximation algorithms based on coresets and hitting sets. Experimental results demonstrate that these methods are orders of magnitude faster than existing techniques while maintaining high representation quality and scalability to large datasets.
Introduction
In modern database systems, helping users navigate multi-criteria datasets is a significant challenge. Traditional methods like Top-k ranking require users to specify exact utility weights, which is often impossible. Conversely, Skyline queries return all non-dominated points, but this set can become unmanageably large in high-dimensional spaces.
Regret Minimization offers a hybrid solution. It identifies a small subset $Q$ of a database $P$ such that for any possible linear utility function, the best item in $Q$ is "close enough" to the best item in $P$. This paper specifically investigates the $k$-regret minimizing set, where the utility of the best item in $Q$ is compared against the $k$-th best item in the entire dataset $P$.
Theoretical Complexity: The $d=3$ Boundary
A pivotal contribution of this work is the proof that finding a $k$-regret minimizing set is NP-complete for any dimension $d \ge 3$. While the problem is solvable in polynomial time for 2D datasets, the transition to 3D introduces geometric complexities that make exact solutions computationally intractable. This result justifies the necessity of approximation algorithms for practical applications.
Proposed Approximation Schemes
To overcome the NP-hardness, the authors propose two scalable approximation frameworks:
1. Coreset-based Approximation (RRS)
The authors link regret minimization to the concept of "directional width" in computational geometry. By utilizing $\epsilon$-kernel coresets, which approximate the extent of a point set in all directions, they demonstrate that an $\epsilon$-kernel of $P$ serves as a $(1, \epsilon)$-regret set. This approach is particularly valuable for dynamic databases, as coresets allow for efficient point insertions and deletions.
2. Hitting Set-based Approximation (HS)
By discretizing the space of possible user preferences into a "$\delta$-net" of directions, the problem is reformulated as a Hitting Set problem. A greedy algorithm is then employed to select points that "cover" the maximum number of preference directions with minimal regret. This method avoids the heavy computational cost of previous linear programming (LP) approaches.
Experimental Evaluation
The proposed algorithms were tested against the previous state-of-the-art (CTVW) using real-world datasets (NBA player stats, oceanographic data, image features) and synthetic benchmarks (AntiCor, Sphere).
- Performance: The Hitting Set (HS) algorithm demonstrated remarkable speed, outperforming CTVW by up to 480x on synthetic datasets.
- Scalability: On the ElNino dataset (~178k points), HS and RRS completed in seconds, whereas CTVW failed to finish after two days of computation.
- Quality: Despite the speedup, the approximation quality (size of the set vs. regret ratio) remained competitive with exact greedy methods.
Conclusion
This research establishes the fundamental hardness of $k$-regret minimization in dimensions $d \ge 3$ and provides the first truly scalable algorithms for the problem. While the "curse of dimensionality" remains a challenge for very high-dimensional data, the coreset and hitting set approaches offer a robust foundation for interactive multi-criteria decision support in large-scale databases.
Summary updated