论文标题
在添加剂不平等下的近似总查询
Approximate Aggregate Queries Under Additive Inequalities
论文作者
论文摘要
我们考虑评估某些类型的功能汇总查询的问题，这些查询是对添加剂不平等的关系。这种汇总查询（通常在许多应用中，尤其是在学习应用中）自然/通常出现。我们对此类问题的计算复杂性进行了相对完整的分类。我们首先表明问题是NP-HARD，即使是一个添加剂不平等的情况。因此，我们转向近似查询。我们的主要结果是一种有效的算法，用于近似，任意相对误差，许多自然聚合查询具有一个添加剂不等式。我们提供可以使用此算法有效解决的自然查询示例。相比之下，我们表明，存在两个添加剂不等式的情况是完全不同的，它表明它是NP-HARD评估简单的聚合查询，具有两个添加剂不平等，并具有任何有界的相对误差。
We consider the problem of evaluating certain types of functional aggregation queries on relational data subject to additive inequalities. Such aggregation queries, with a smallish number of additive inequalities, arise naturally/commonly in many applications, particularly in learning applications. We give a relatively complete categorization of the computational complexity of such problems. We first show that the problem is NP-hard, even in the case of one additive inequality. Thus we turn to approximating the query. Our main result is an efficient algorithm for approximating, with arbitrarily small relative error, many natural aggregation queries with one additive inequality. We give examples of natural queries that can be efficiently solved using this algorithm. In contrast, we show that the situation with two additive inequalities is quite different, by showing that it is NP-hard to evaluate simple aggregation queries, with two additive inequalities, with any bounded relative error.
