@inproceedings{2277e51407ac4cd19c76f805ee653ed0,
title = "Human-powered data cleaning for probabilistic reachability queries on uncertain graphs",
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.",
keywords = "Crowdsourcing, Reachability query, Uncertain Graph",
author = "Xin Lin and Yun PENG and Jianliang XU and CHOI, {Koon Kau}",
note = "Funding Information: This work was supported by HK-RGC grants 12244916, 12200114, 12201315. Xin Lin{\textquoteright}s work was also supported by NSFC (No. 61773167, 61572193) and NSF of Shanghai (No. 17ZR1444900). Yun Peng{\textquoteright}s work was supported by NSFC (No. 61502258, 71402083) and NSF of Shandong (No. ZR2014FQ007, ZR2015FM020).; 34th IEEE International Conference on Data Engineering, ICDE 2018 ; Conference date: 16-04-2018 Through 19-04-2018",
year = "2018",
month = oct,
day = "24",
doi = "10.1109/ICDE.2018.00235",
language = "English",
series = "Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018",
publisher = "IEEE",
pages = "1755--1756",
booktitle = "Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018",
address = "United States",
}