conference2022ICORE 2026 Australasian BCORE 2023 Australasian B
Hop-Constrained s-t Simple Path Enumeration In Large Uncertain Graphs
Xia Li, Kongzhang Hao, Zhengyi Yang, Xin Cao, Wenjie Zhang
RAIDS Lab Authors
Details
Year
2022
Publisher
Springer
Rankings
ICORE 2026 Australasian B · CORE 2023 Australasian B
Research Area
Scalable Data Systems
Tags
Resources
Abstract
Uncertain graphs are graphs where each edge is assigned with a probability of existence. In this paper, we study the problem of hop-constrained s-t simple path enumeration in large uncertain graphs. To the best of our knowledge, we are the first to study this problem in the literature. Specifically, we propose a light-weight index to prune candidate paths by adopting the concept of probability-constrained distance. An efficient enumeration algorithm is designed based on the index structure. Experiment results on real-world datasets show that our proposed methods significantly outperform the baseline methods by up to 6 times.
Author Affiliations
Xia Li
University of New South Wales
Kongzhang Hao
University of New South Wales
Zhengyi Yang
University of New South Wales
Xin Cao
University of New South Wales
Wenjie Zhang
University of New South Wales
BibTeX
@inproceedings{li2022hop2,
title = {Hop-Constrained s-t Simple Path Enumeration in Large Uncertain Graphs},
author = {Li, Xia and Hao, Kongzhang and Yang, Zhengyi and Cao, Xin and Zhang, Wenjie},
editor = {Hua, Wen and Wang, Hua and Li, Lei},
booktitle = {Databases Theory and Applications},
year = {2022},
publisher = {Springer International Publishing},
address = {Cham},
pages = {115--127},
isbn = {978-3-031-15512-3}
}