PROJECT TITLE :

Human-Powered Data Cleaning for Probabilistic Reachability Queries on Uncertain Graphs - 2017

ABSTRACT:

Unsure graph models are widely utilized in real-world applications such as knowledge graphs and social networks. To capture the uncertainty, each edge in an uncertain graph is related to an existential probability that signifies the chance of the existence of the sting. One notable issue of querying unsure graphs is that the results are sometimes uninformative as a result of of the edge uncertainty. In this paper, we have a tendency to take into account probabilistic reachability queries, which are one among the fundamental classes of graph queries. To form the results more informative, we tend to adopt a crowdsourcing-based approach to clean the unsure edges. However, considering the time and monetary cost of crowdsourcing, it is a downside to efficiently choose a restricted set of edges for cleaning that maximizes the standard improvement. We prove that the edge selection problem is #P-laborious. In light-weight of the hardness of the problem, we propose a series of edge choice algorithms, followed by a range of optimization techniques and pruning heuristics for reducing the computation time. Our experimental results demonstrate that our proposed techniques outperform a random choice by up to twenty seven times in terms of the result quality improvement and also the brute-force answer by up to 60 times in terms of the elapsed time.