Finding Global Optimum for Truth Discovery: Entropy Based Geometric Variance
Finding Global Optimum for Truth Discovery: Entropy Based Geometric Variance
复制标题
DOI：
10.4230/lipics.socg.2016.34
复制
发表时间：
2016-06
期刊：
影响因子：
--
通讯作者：
Hu Ding;Jing Gao;Jinhui Xu
中科院分区：
文献类型：
--
作者：
Hu Ding;Jing Gao;Jinhui Xu
真相发现是数据挖掘、数据库、大数据等数据分析相关领域出现的一个重要问题。它关注的是从许多不可靠的来源获得的数据集中找到最值得信赖的信息。由于其重要性，近年来人们对该问题进行了广泛的研究，并提出了许多技术。然而，所有这些都是启发式的，没有任何质量保证。在本文中，我们将该问题表述为一个高维几何优化问题，称为基于熵的几何方差。依靠一些新的几何技术（如对数划分和修正单纯形引理），我们进一步发现了这个问题的新见解。我们首次证明了可以在保证解质量的情况下解决真值发现问题。特别是，我们证明了在一些合理的假设下，在近线性时间内实现(1+eps)-近似是可能的。我们期望我们的算法对其他与数据相关的应用有用。
Truth Discovery is an important problem arising in data analytics related fields such as data mining, database, and big data. It concerns about finding the most trustworthy information from a dataset acquired from a number of unreliable sources. Due to its importance, the problem has been extensively studied in recent years and a number techniques have already been proposed. However, all of them are of heuristic nature and do not have any quality guarantee. In this paper, we formulate the problem as a high dimensional geometric optimization problem, called Entropy based Geometric Variance. Relying on a number of novel geometric techniques (such as Log-Partition and Modified Simplex Lemma), we further discover new insights to this problem. We show, for the first time, that the truth discovery problem can be solved with guaranteed quality of solution. Particularly, we show that it is possible to achieve a (1+eps)-approximation within nearly linear time under some reasonable assumptions. We expect that our algorithm will be useful for other data related applications.