通过顺序依赖关系发现域顺序（CS D）---蔡秋纯

许多真实世界的数据都带有明确定义的域顺序；例如，字符串的字典顺序、整数的数字顺序和时间的时间顺序。我们的目标是发现我们还不知道的隐含域顺序；例如，农历中的月顺序是emph{Corner}emph{Apricot}emph{Peach}，等等。为此，我们通过顺序依赖（ODs）发现数据中的隐式域顺序来增强数据分析方法。我们首先识别出可处理的特殊情况，然后再进行最一般的情况，证明它是NP完全的。尽管如此，我们仍然可以用SAT解算器来处理一般情况。我们还提出了一个有趣度度量来对发现的隐域阶进行排序。最后，我们在一个属性格发现框架中实现我们的解决方案，并使用真实世界的数据集进行实验评估。

原文标题：Discovering Domain Orders through Order Dependencies

原文：Much real-world data come with explicitly defined domain orders; e.g., lexicographic order for strings, numeric for integers, and chronological for time. Our goal is to discover implicit domain orders that we do not already know; for instance, that the order of months in the Lunar calendar is emph{Corner} ≺ emph{Apricot} ≺ emph{Peach}, and so on. To do so, we enhance data profiling methods by discovering implicit domain orders in data through order dependencies (ODs). We first identify tractable special cases and then proceed towards the most general case, which we prove is NP-complete. Nevertheless, we show that the general case can be still handled by a SAT solver. We also propose an interestingness measure to rank the discovered implicit domain orders. Finally, we implement our solutions in an attribute-lattice discovery framework, and we perform an experimental evaluation using real-world datasets.

原文作者：Reza Karegar, Melicaalsadat Mirsafian, Parke Godfrey, Lukasz Golab, Mehdi Kargar, Divesh Srivastava, Jaroslaw Szlichta

原文地址：https://arxiv.org/abs/2005.14068