Mining Approximate Acyclic Schemes from Relations
Mining Approximate Acyclic Schemes from Relations
复制标题
DOI：
10.1145/3318464.3380573
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Batya Kenig;Pranay Mundra;G. Prasad;Babak Salimi;Dan Suciu
中科院分区：
文献类型：
--
作者：
Batya Kenig;Pranay Mundra;G. Prasad;Babak Salimi;Dan Suciu
非循环模式在数据库和机器学习中有许多应用，例如改进的设计，更有效的存储以及查询和机器学习算法的性能提高。多值依赖（MVD）是非循环模式的构建块。从数据中发现MVD和非循环模式比其他形式的数据依赖性（如函数依赖性）更具挑战性，因为这些依赖性不适用于数据子集，并且因为它们对数据中的噪声非常敏感;例如，单个错误或丢失的元组可能会使模式无效。在本文中，我们提出了Maimon，一个系统发现近似的非循环计划和MVDs的数据。我们给出了一个原则性的近似定义，通过使用信息论的概念，然后描述了Maimon的两个组成部分：挖掘近似MVD，然后从近似MVD重建非循环计划。我们在20个真实世界的数据集上对Maimon进行了实验评估，并表明它可以扩展到100万行和30列。
Acyclic schemes have numerous applications in databases and in machine learning, such as improved design, more efficient storage, and increased performance for queries and machine learning algorithms. Multivalued dependencies (MVDs) are the building blocks of acyclic schemes. The discovery from data of both MVDs and acyclic schemes is more challenging than other forms of data dependencies, such as Functional Dependencies, because these dependencies do not hold on subsets of data, and because they are very sensitive to noise in the data; for example a single wrong or missing tuple may invalidate the schema. In this paper we present Maimon, a system for discovering approximate acyclic schemes and MVDs from data. We give a principled definition of approximation, by using notions from information theory, then describe the two components of Maimon: mining for approximate MVDs, then reconstructing acyclic schemes from approximate MVDs. We conduct an experimental evaluation of Maimon on 20 real-world datasets, and show that it can scale up to 1M rows, and up to 30 columns.