Efficient processing of k-regret minimization queries with theoretical guarantees
From MaRDI portal
Publication:6154451
Abstract: Assisting end users to identify desired results from a large dataset is an important problem for multi-criteria decision making. To address this problem, top-k and skyline queries have been widely adopted, but they both have inherent drawbacks, i.e., the user either has to provide a specific utility function or faces many results. The k-regret minimization query is proposed, which integrates the merits of top-k and skyline queries. Due to the NP-hardness of the problem, the k-regret minimization query is time consuming and the greedy framework is widely adopted. However, formal theoretical analysis of the greedy approaches for the quality of the returned results is still lacking. In this paper, we first fill this gap by conducting a nontrivial theoretical analysis of the approximation ratio of the returned results. To speed up query processing, a sampling-based method, StocPreGreed,, is developed to reduce the evaluation cost. In addition, a theoretical analysis of the required sample size is conducted to bound the quality of the returned results. Finally, comprehensive experiments are conducted on both real and synthetic datasets to demonstrate the efficiency and effectiveness of the proposed methods.
Recommendations
- \(k\)-regret minimizing set: efficient algorithms and hardness
- Efficient Algorithms for k-Regret Minimizing Sets
- \(k\)-regret queries using multiplicative utility functions
- Faster approximation algorithm for the \(k\)-regret minimizing set and related problems
- Towards strong regret minimization sets: balancing freshness and diversity in data selection
Cites work
- scientific article; zbMATH DE number 3904328 (Why is no real title available?)
- scientific article; zbMATH DE number 3580314 (Why is no real title available?)
- An analysis of approximations for maximizing submodular set functions—I
- Efficient Algorithms for k-Regret Minimizing Sets
- Fast algorithms for maximizing submodular functions
- Faster approximation algorithm for the \(k\)-regret minimizing set and related problems
- Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
- Recurrent neural variational model for follower-based influence maximization
- Submodular functions and optimization.
- \(k\)-regret minimizing set: efficient algorithms and hardness
- \(k\)-regret queries using multiplicative utility functions
Cited in
(2)
This page was built for publication: Efficient processing of \(k\)-regret minimization queries with theoretical guarantees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6154451)
