In this paper, we investigate the hybrid regret min-imization (HRM) query, a new method to extract representative tuples from databases. The HRM query combines the two types of regret minimization queries in the literature, namely maximum regret minimization (MRM) and average regret minimization (ARM) queries, aiming to select a size-k subset of tuples from a database to simultaneously minimize the maximum and average regret ratios. We show the NP-hardness of the HRM problem and propose an asymptotic algorithmic (AA) framework with several optimization techniques and a multiplicative weights update (MWU) algorithm to process HRM queries efficiently with theoretical guarantees. Finally, we demonstrate that our proposed algorithms achieve better performance for HRM queries than existing methods specific to MRM and ARM queries through extensive experiments on real-world and synthetic datasets.

Regret minimization queries are important methods to extract representative tuples from databases. They have been extensively investigated in the last decade due to wide applications in multi-criteria decision making. For a given database$D$and a class$\mathcal {F}$of utility functions (e.g., all nonnegative linear functions), two typical regret minimization queries considered in existing studies are maximum regret minimization (MRM) and average regret minimization (ARM) queries, whereby a subset of$k$tuples is selected from$D$to minimize the maximum or average of regret ratios among all utility functions in$\mathcal {F}$, respectively. However, due to the different properties of maximum and average regret ratios, the result of one query cannot fulfill the requirement of the other. To the best of our knowledge, there has not yet been any attempt to combine both queries. In this paper, we first introduce the hybrid regret minimization (HRM) query, which simultaneously minimizes the maximum and average regret ratios. We show that finding the optimal result for an HRM query is NP-hard, but it is possible to exploit submodularity for approximate HRM query processing. We propose an efficient asymptotic approximation algorithm based on submodular maximization to process HRM queries and several optimization techniques, such as memoization, lazy evaluation, and stochastic subsampling, to improve query efficiency. Furthermore, we consider extending a multiplicative weights update (MWU) algorithm for multi-objective submodular maximization to provide higher-quality results for HRM queries. Finally, we demonstrate that our proposed algorithms achieve better performance for HRM queries than existing methods specific to MRM and ARM queries through extensive experiments on real-world and synthetic datasets. Meanwhile, our proposed algorithms are efficient and scalable to large datasets.

Finding a small set of representative tuples from a large database is an important functionality for supporting multi-criteria decision making. Top-$k$queries and skyline queries are two widely studied queries to fulfill this task. However, both of them have some limitations: a top-$k$query requires the user to provide her utility functions for finding the$k$tuples with the highest scores as the result; a skyline query does not need any user-specified utility function but cannot control the result size. To overcome their drawbacks, the$k$-regret minimization query was proposed and received much attention recently, since it does not require any user-specified utility function and returns a fixed-size result set. Specifically, it selects a set$R$of tuples with a pre-defined size$r$from a database$D$such that themaximum$k$-regret ratio, which captures how well the top-ranked tuple in$R$represents the top-$k$tuples in$D$for any possible utility function, is minimized. Although there have been many methods for$k$-regret minimization query processing, most of them are designed for static databases without tuple insertions and deletions. The only known algorithm to process continuous$k$-regret minimization queries (C$k$RMQ) in dynamic databases suffers from suboptimal approximation and high time complexity. In this paper, we propose a novel dynamic coreset-based approach, calledDynCore, for C$k$RMQ processing. It achieves the same (asymptotically optimal) upper bound on the maximum$k$-regret ratio as the best-known static algorithm. Meanwhile, its time complexity is sublinear to the database size, which is significantly lower than that of the existing dynamic algorithm. The efficiency and effectiveness ofDynCoreis confirmed by experimental results on real-world and synthetic datasets.

Finding a happiness maximizing set (HMS) from a database, i.e., selecting a small subset of tuples that preserves the best score with respect to any nonnegative linear utility function, is an important problem in multi-criteria decision-making. When an HMS is extracted from a set of individuals to assist data-driven algorithmic decisions such as hiring and admission, it is crucial to ensure that the HMS can fairly represent different groups of candidates without bias and discrimination. However, although the HMS problem was extensively studied in the database community, existing algorithms do not take group fairness into account and may provide solutions that under-represent some groups. In this paper, we propose and investigate a fair variant of HMS (FairHMS) that not only maximizes the minimum happiness ratio but also guarantees that the number of tuples chosen from each group falls within predefined lower and upper bounds. Similar to the vanilla HMS problem, we show that FairHMS is NP-hard in three and higher dimensions. Therefore, we first propose an exact interval cover-based algorithm called IntCov for FairHMS on two-dimensional databases. Then, we propose a bicriteria approximation algorithm called BiGreedy for FairHMS on multi-dimensional databases by transforming it into a submodular maximization problem under a matroid constraint. We also design an adaptive sampling strategy to improve the practical efficiency of BiGreedy. Extensive experiments on real-world and synthetic datasets confirm the efficacy and efficiency of our proposal.

Beyond top-k and skyline queries, in the last decade regret minimization queries have played an important role in the database community to solve multi-criteria decision making problems. To reduce the user's regret, interaction is proved to be an efficient way to turn the user's regret ratio to 0, i.e. identifying the user's ideal point from the large dataset. However, existing interactive regret minimization framework needs more rounds of user's interaction to identify her/his ideal point. To reduce the number of interaction rounds, we propose a system, called IDEAL, IDE ntifying the user's ideAL tuple via sorting in the database. In our system, we use the National Basketball Association (NBA) dataset to show our interactive framework via sorting mechanism, which can make the regret minimization query quickly converge to the user's ideal data point from initial displayed several points with few rounds of the user's interaction.

Video summarization which potentially fast browses a large amount of emerging video data as well as saves storage cost has attracted tremendous attentions in machine learning and information retrieval. Among existing efforts, determinantal point processes (DPPs) designed for selecting a subset of video frames to represent the whole video have shown great success in video summarization. However, existing methods have shown poor performance to generate fixed-size output summaries for video data, especially when video frames arrive in streaming manner. In this paper, we provide an efficient approach k-seqLS which summarizes streaming video data with a fixed-size k in vein of DPPs. Our k-seqLS approach can fully exploit the sequential nature of video frames by setting a time window and the frames outside the window have no influence on current video frame. Since the log-style of the DPP probability for each subset of frames is a non-monotone submodular function, local search as well as greedy techniques with cardinality constraints are adopted to make k-seqLS fixed-sized, efficient and with theoretical guarantee. Our experiments show that our proposed k-seqLS exhibits higher performance while maintaining practical running time.

Regret-based queries are a complement of top-k and skyline queries when users cannot specify accurate utility functions while must output a controllable size of the query results. Various regret-based queries are proposed in last decade for multi-criteria decision making. The k-regret minimizing set (k-RMS) query which returns r points from the dataset and minimizes the maximum k-regret ratio has been extensively studied. However, existing state-of-art algorithms to find k-regret minimizing sets are very time-consuming and unapplicable. In this paper, we propose a faster algorithm SAMPGREED for k-RMS queries by utilizing the monotonicity of the regret ratio function with sampling techniques. We provide the theoretical analysis of our SAMPGREED algorithm and experiments on synthetic and real datasets verify our proposed algorithm is superior to existing state-of-art approaches.

The k-coverage query is an ideal solution for representative queries with almost known nice characteristics, such as stability, scale-invariance, traversal efficiency and so on. In this paper, we formally define deletion-robust k-coverage queries on data streams. Further, we design a robust-seiving algorithm with a chain structure to robustly answer k-coverage queries when certain amount of data points are deleted. Finally, experiments on synthetic and real datasets verify the effectiveness and efficiency of our proposed method.

Skyline queries are usually associated with user preferences which are dependent on his/her current contexts. For most contexts are from sensing devices, uncertainty is along with the contexts. In this paper, asymptotic-efficient skyline query processing algorithms over uncertain contexts are proposed. First possible world semantics model is utilized to model uncertain contexts as well as uncertain contextual preferences. Since exact skyline algorithm is a #P-hard problem, two heuristic skyline algorithms LHSA, CHSA are proposed to reduce the number of possible worlds not contributing to final skyline query results. To improve the efficiency of skyline query processing under user specified precision, two Monte Carlo Sampling based approximation algorithms 2PMA, S2PMA are proposed. Finally, extensive experimental results show that LHSA and CHSA algorithms can reduce the number of possible worlds to a large extent and the proposed 2PMA and S2PMA algorithms perform more efficiently than heuristic algorithms while S2PMA algorithm is prior to 2PMA with smaller absolute errors.