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

Xin Lin; Yun PENG; Jianliang XU; Koon Kau Choi

doi:10.1109/ICDE.2018.00235

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

Xin Lin, Yun PENG, Jianliang XU, Koon Kau Choi

Department of Computer Science

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

2 Citations (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 language	English
Title of host publication	Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018
Publisher	IEEE
Pages	1755-1756
Number of pages	2
ISBN (Electronic)	9781538655207
DOIs	https://doi.org/10.1109/ICDE.2018.00235
Publication status	Published - 24 Oct 2018
Event	34th IEEE International Conference on Data Engineering, ICDE 2018 - Paris, France Duration: 16 Apr 2018 → 19 Apr 2018 https://ieeexplore.ieee.org/xpl/conhome/8476188/proceeding

Publication series

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

Conference

Conference	34th IEEE International Conference on Data Engineering, ICDE 2018
Country/Territory	France
City	Paris
Period	16/04/18 → 19/04/18
Internet address	https://ieeexplore.ieee.org/xpl/conhome/8476188/proceeding

Scopus Subject Areas

Information Systems
Information Systems and Management
Hardware and Architecture

User-Defined Keywords

Crowdsourcing
Reachability query
Uncertain Graph

Access to Document

10.1109/ICDE.2018.00235

Cite this

Lin, X., PENG, Y., XU, J., & Choi, K. K. (2018). Human-powered data cleaning for probabilistic reachability queries on uncertain graphs. In Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018 (pp. 1755-1756). Article 8509456 (Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018). IEEE. https://doi.org/10.1109/ICDE.2018.00235

@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",

url = "https://ieeexplore.ieee.org/xpl/conhome/8476188/proceeding",

}

Lin, X, PENG, Y, XU, J & Choi, KK 2018, Human-powered data cleaning for probabilistic reachability queries on uncertain graphs. in Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018., 8509456, Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018, IEEE, pp. 1755-1756, 34th IEEE International Conference on Data Engineering, ICDE 2018, Paris, France, 16/04/18. https://doi.org/10.1109/ICDE.2018.00235

Human-powered data cleaning for probabilistic reachability queries on uncertain graphs. / Lin, Xin; PENG, Yun; XU, Jianliang et al.
Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018. IEEE, 2018. p. 1755-1756 8509456 (Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

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

AU - Lin, Xin

AU - PENG, Yun

AU - XU, Jianliang

AU - Choi, Koon Kau

N1 - Funding Information: This work was supported by HK-RGC grants 12244916, 12200114, 12201315. Xin Lin’s work was also supported by NSFC (No. 61773167, 61572193) and NSF of Shanghai (No. 17ZR1444900). Yun Peng’s work was supported by NSFC (No. 61502258, 71402083) and NSF of Shandong (No. ZR2014FQ007, ZR2015FM020).

PY - 2018/10/24

Y1 - 2018/10/24

N2 - 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.

AB - 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.

KW - Crowdsourcing

KW - Reachability query

KW - Uncertain Graph

UR - http://www.scopus.com/inward/record.url?scp=85057121620&partnerID=8YFLogxK

U2 - 10.1109/ICDE.2018.00235

DO - 10.1109/ICDE.2018.00235

M3 - Conference proceeding

AN - SCOPUS:85057121620

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

SP - 1755

EP - 1756

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

PB - IEEE

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

Y2 - 16 April 2018 through 19 April 2018

ER -

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

Abstract

Publication series

Conference

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this