TY - GEN
T1 - Finding global optimum for truth discovery
T2 - 32nd International Symposium on Computational Geometry, SoCG 2016
AU - Ding, Hu
AU - Gao, Jing
AU - Xu, Jinhui
N1 - Publisher Copyright:
© Hu Ding, Jing Gao, and Jinhui Xu.
PY - 2016/6/1
Y1 - 2016/6/1
N2 - 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 + ∈)-approximation within nearly linear time under some reasonable assumptions. We expect that our algorithm will be useful for other data related applications.
AB - 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 + ∈)-approximation within nearly linear time under some reasonable assumptions. We expect that our algorithm will be useful for other data related applications.
KW - Data mining
KW - Entropy
KW - Geometric optimization
KW - High dimension
UR - https://www.scopus.com/pages/publications/84976904257
U2 - 10.4230/LIPIcs.SoCG.2016.34
DO - 10.4230/LIPIcs.SoCG.2016.34
M3 - Conference contribution
AN - SCOPUS:84976904257
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 34.1-34.16
BT - 32nd International Symposium on Computational Geometry, SoCG 2016
A2 - Fekete, Sandor
A2 - Lubiw, Anna
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 14 June 2016 through 17 June 2016
ER -