标题： 通过预处理生成多项式对数大小的输出来使大规模数据上的问题变得易处理 显示英文标题

标题： Making problems tractable on big data via preprocessing with polylog-size output

摘要： 为了在经过适当预处理后可以在大数据上实现可行的查询和预处理无帮助的查询之间提供二分法，Fan等人开发了$\sqcap$-可 tractability 理论。该理论为理解大数据背景下查询类的可 tractability 提供了正式的基础。在此基础上，本文引入了一个新的$\sqcap'$-可 tractability 概念。受一些用于处理大数据的技术启发，我们对预处理函数施加了限制，该限制使函数只能产生相对较小的数据库作为输出，最多为输入数据库的多项式对数大小。同时，我们对重新分解数据和查询时的冗余信息进行了限制。这些变化旨在使我们的理论更贴近实际。我们设定了两个复杂度类，分别表示自身为$\sqcap'$-可 tractable 的布尔查询类和可以变为$\sqcap'$-可 tractable 的查询类。基于我们复杂度类中的新分解方法，我们研究了两种归约，这两种归约的不同之处在于是否允许重新分解数据和查询部分。我们验证了归约的传递性和兼容性，并分析了复杂度类的完整问题和大小。我们得出结论，所有布尔查询的PTIME类都可以变为$\sqcap'$-可 tractable，类似于$\sqcap$-可 tractability 理论的情况。 带着一点惊讶，我们证明了所有$\sqcap'$-可处理查询的集合严格小于所有$\sqcap$-可处理查询的集合，因此所有$\sqcap'$-可处理查询的集合是 PTIME 查询集合的真子集。 以这种方式，我们在 PTIME 查询的复杂度类内部获得了一个新的复杂度类。 显示英文摘要

摘要： To provide a dichotomy between those queries that can be made feasible on big data after appropriate preprocessing and those for which preprocessing does not help, Fan et al. developed the $\sqcap$-tractability theory. This theory provides a formal foundation for understanding the tractability of query classes in the context of big data. Along this line, we introduce a novel notion of $\sqcap'$-tractability in this paper. Inspired by some technologies used to deal big data, we place a restriction on preprocessing function, which limits the function to produce a relatively small database as output, at most polylog-size of the input database. At the same time, we bound the redundancy information when re-factorizing data and queries for preprocessing. These changes aim to make our theory more closely linked to practice. We set two complexity classes to denote the classes of Boolean queries that are $\sqcap'$-tractable themselves and that can be made $\sqcap'$-tractable, respectively. Based on a new factorization in our complexity classes, we investigate two reductions, which differ from whether allowing re-factorizing data and query parts. We verify the transitive and compatible properties of the reductions and analysis the complete problems and sizes of the complexity classes. We conclude that all PTIME classes of Boolean queries can be made $\sqcap'$-tractable, similar to that of the $\sqcap$-tractability theory. With a little surprise, we prove that the set of all $\sqcap'$-tractable queries is strictly smaller than that of all $\sqcap$-tractable queries, and thus the set of $\sqcap'$-tractable queries is properly contained in that of PTIME queries. In this way, we attain a new complexity class inside the complexity class of PTIME queries.