Kernelization for Big Data

本项目的主要研究目标是寻求一种严格的输入-输出高效预处理的数学理论。这一新理论将开发计算工具来设计强大的算法，用于对困难问题的非常大的实例进行预处理，从而非常高效地将这些实例压缩为具有保证大小的较小实例。我们的动机是当前具有压缩保证(内核化)的预处理例程无法处理不适合主内存的非常大的实例。该理论还试图严格解释使用无压缩保证算法(启发式)对超大实例进行预处理的实际成功，并将引入计算难解性的概念来解释启发式算法的局限性。该项目旨在设计预处理算法，利用先进处理器技术的全部能力和科学和工业中计算硬件的存储层次结构，高效地压缩大数据集。通过同时利用实例结构和硬件结构的新的多变量计算模型，我们将加深对可压缩性的数学起源的理解，并服务于构建更强大的算法来对海量数据集进行预处理。

The main research goal of this project is the quest for a rigorous mathematical theory of input-output efficient preprocessing. This new theory will develop the computational tools to design powerful algorithms for preprocessing very large instances of hard problems that very efficiently compress those instances to smaller ones with guaranteed size. Our motivation is the incapability of current preprocessing routines with compression guarantee (kernelizations) to handle very large instances that do not fit into main memory. The theory also seeks to rigorously explain the practical successes of preprocessing very large instances by algorithms without compression guarantee (heuristics), and will lead to a concept of computational intractability to explain the limitations of heuristics.The project aims to design preprocessing algorithms that harness the full capabilities of advanced processor technology and memory hierarchies of computing hardware in science and industry, to efficiently compress big data sets. With new multivariate computational models that utilize instance structure and hardware structure at the same time, we will deepen the understanding of the mathematical origins of compressibility and serve to build more powerful algorithms for preprocessing massive data sets.