Efficient sampling methods for shortest path query over uncertain graphs

Yurong Cheng, Ye Yuan, Guoren Wang, Baiyou Qiao, Zhiqiong Wang

科研成果: 书/报告/会议事项章节会议稿件同行评审

7 引用 (Scopus)

摘要

Graph has become a widely used structure to model data. Unfortunately, data are inherently with uncertainty because of the occurrence of noise and incompleteness in data collection. This is why uncertain graphs catch much attention of researchers. However, the uncertain graph models in existing works assume all edges in a graph are independent of each other, which dose not really make sense in real applications. Thus, we propose a new model for uncertain graphs considering the correlation among edges sharing the same vertex. Moreover, in this paper, we mainly solve the shortest path query, which is a funduemental but important query on graphs, using our new model. As the problem of calculating shortest path probability over correlated uncertain graphs is #P-hard, we propose different kinds of sampling methods to efficiently compute an approximate answer. The error is very small in our algorithm, which is proved and further verified in our experiments.

源语言英语
主期刊名Database Systems for Advanced Applications - 19th International Conference, DASFAA 2014, Proceedings
出版商Springer Verlag
124-140
页数17
版本PART 2
ISBN(印刷版)9783319058122
DOI
出版状态已出版 - 2014
已对外发布
活动19th International Conference on Database Systems for Advanced Applications, DASFAA 2014 - Bali, 印度尼西亚
期限: 21 4月 201424 4月 2014

出版系列

姓名Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
编号PART 2
8422 LNCS
ISSN(印刷版)0302-9743
ISSN(电子版)1611-3349

会议

会议19th International Conference on Database Systems for Advanced Applications, DASFAA 2014
国家/地区印度尼西亚
Bali
时期21/04/1424/04/14

指纹

探究 'Efficient sampling methods for shortest path query over uncertain graphs' 的科研主题。它们共同构成独一无二的指纹。

引用此

Cheng, Y., Yuan, Y., Wang, G., Qiao, B., & Wang, Z. (2014). Efficient sampling methods for shortest path query over uncertain graphs. 在 Database Systems for Advanced Applications - 19th International Conference, DASFAA 2014, Proceedings (PART 2 编辑, 页码 124-140). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 卷 8422 LNCS, 号码 PART 2). Springer Verlag. https://doi.org/10.1007/978-3-319-05813-9_9