TY - GEN
T1 - Faster algorithm for truth discovery via range cover
AU - Huang, Ziyun
AU - Ding, Hu
AU - Xu, Jinhui
N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - Truth discovery is a key problem in data analytics which has received a great deal of attention in recent years. In this problem, we seek to obtain trustworthy information from data aggregated from multiple (possibly) unreliable sources. Most of the existing approaches for this problem are of heuristic nature and do not provide any quality guarantee. Very recently, the first quality-guaranteed algorithm has been discovered. However, the running time of the algorithm depends on the spread ratio of the input points and is fully polynomial only when the spread ratio is relatively small. This could severely restrict the applicability of the algorithm. To resolve this issue, we propose in this paper a new algorithm which yields a (1 + ε)-approximation in near quadratic time for any dataset with constant probability. Our algorithm relies on a data structure called range cover, which is interesting in its own right. The data structure provides a general approach for solving some high dimensional optimization problems by breaking them down into a small number of parametrized cases.
AB - Truth discovery is a key problem in data analytics which has received a great deal of attention in recent years. In this problem, we seek to obtain trustworthy information from data aggregated from multiple (possibly) unreliable sources. Most of the existing approaches for this problem are of heuristic nature and do not provide any quality guarantee. Very recently, the first quality-guaranteed algorithm has been discovered. However, the running time of the algorithm depends on the spread ratio of the input points and is fully polynomial only when the spread ratio is relatively small. This could severely restrict the applicability of the algorithm. To resolve this issue, we propose in this paper a new algorithm which yields a (1 + ε)-approximation in near quadratic time for any dataset with constant probability. Our algorithm relies on a data structure called range cover, which is interesting in its own right. The data structure provides a general approach for solving some high dimensional optimization problems by breaking them down into a small number of parametrized cases.
UR - http://www.scopus.com/inward/record.url?scp=85025157359&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85025157359&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-62127-2_39
DO - 10.1007/978-3-319-62127-2_39
M3 - Conference contribution
AN - SCOPUS:85025157359
SN - 9783319621265
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 461
EP - 472
BT - Algorithms and Data Structures - 15th International Symposium, WADS 2017, Proceedings
A2 - Ellen, Faith
A2 - Kolokolova, Antonina
A2 - Sack, Jorg-Rudiger
PB - Springer Verlag
T2 - 15th International Symposium on Algorithms and Data Structures, WADS 2017
Y2 - 31 July 2017 through 2 August 2017
ER -