1 Search Results for "Gao, Jing"

Document
DOI: 10.4230/LIPIcs.SoCG.2016.34
Finding Global Optimum for Truth Discovery: Entropy Based Geometric Variance

Authors: Hu Ding, Jing Gao, and Jinhui Xu

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
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.
Cite as

Hu Ding, Jing Gao, and Jinhui Xu. Finding Global Optimum for Truth Discovery: Entropy Based Geometric Variance. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{ding_et_al:LIPIcs.SoCG.2016.34,
  author =	{Ding, Hu and Gao, Jing and Xu, Jinhui},
  title =	{{Finding Global Optimum for Truth Discovery: Entropy Based Geometric Variance}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{34:1--34:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.34},
  URN =		{urn:nbn:de:0030-drops-59264},
  doi =		{10.4230/LIPIcs.SoCG.2016.34},
  annote =	{Keywords: geometric optimization, data mining, high dimension, entropy}
}
  • Refine by Author
  • 1 Ding, Hu
  • 1 Gao, Jing
  • 1 Xu, Jinhui

  • Refine by Classification

  • Refine by Keyword
  • 1 data mining
  • 1 entropy
  • 1 geometric optimization
  • 1 high dimension

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact