Human-powered data cleaning for probabilistic reachability queries on uncertain graphs

Research output: Chapter in book/report/conference proceedingConference contributionpeer-review

1 Citation (Scopus)

Abstract

In this paper, we consider probabilistic reachability queries on uncertain graphs. To make the results more informative, we adopt a crowdsourcing-based approach to clean the uncertain edges. One important problem is how to efficiently select a limited set of edges for cleaning that maximizes the quality improvement. We prove that the edge selection problem is #P-hard. In light of the hardness of the problem, we propose a series of edge selection algorithms, followed by a number of optimization techniques and pruning heuristics for minimizing the computation time. Our experimental results demonstrate that our proposed techniques outperform a random selection by up to 27 times in terms of the result quality improvement and the brute-force solution by up to 60 times in terms of the elapsed time.

Original languageEnglish
Title of host publicationProceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1755-1756
Number of pages2
ISBN (Electronic)9781538655207
DOIs
Publication statusPublished - 24 Oct 2018
Event34th IEEE International Conference on Data Engineering, ICDE 2018 - Paris, France
Duration: 16 Apr 201819 Apr 2018

Publication series

NameProceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018

Conference

Conference34th IEEE International Conference on Data Engineering, ICDE 2018
Country/TerritoryFrance
CityParis
Period16/04/1819/04/18

Scopus Subject Areas

  • Information Systems
  • Information Systems and Management
  • Hardware and Architecture

User-Defined Keywords

  • Crowdsourcing
  • Reachability query
  • Uncertain Graph

Fingerprint

Dive into the research topics of 'Human-powered data cleaning for probabilistic reachability queries on uncertain graphs'. Together they form a unique fingerprint.

Cite this