Efficient processing of k-regret minimization queries with theoretical guarantees

DOI10.1016/J.INS.2021.11.080arXiv2103.11630OpenAlexW3217026425MaRDI QIDQ6154451FDOQ6154451

Authors:

Publication date: 15 February 2024

Published in: Information Sciences (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2103.11630

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

zbMATH Keywords

curvatureregret minimizationskyline querysubmodularity ratio

Mathematics Subject Classification ID

Computer science (68-XX) Operations research, mathematical programming (90-XX)

Cites Work

• Submodular functions and optimization.
• Title not available (Why is that?)
• An analysis of approximations for maximizing submodular set functions—I
• Fast algorithms for maximizing submodular functions
• Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
• Title not available (Why is that?)
• Efficient Algorithms for k-Regret Minimizing Sets
• Recurrent neural variational model for follower-based influence maximization
• \(k\)-regret minimizing set: efficient algorithms and hardness
• \(k\)-regret queries using multiplicative utility functions
• Faster approximation algorithm for the \(k\)-regret minimizing set and related problems

Cited In (2)

• Diversity and freshness-aware regret minimizing set queries
• Towards strong regret minimization sets: balancing freshness and diversity in data selection

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)