TY - GEN
T1 - DURS
T2 - 20th International Conference on Mobile Data Management, MDM 2019
AU - Li, Xiaodong
N1 - Publisher Copyright:
© 2019 IEEE.
PY - 2019/6
Y1 - 2019/6
N2 - Large graphs are increasingly prevalent in mobile networks, social networks, traffic networks and biological networks. These graphs are often uncertain, where edges are augmented with probabilities that indicates the chance to exist. Recently k-nearest neighbor search has been studied within the field of uncertain graphs, but the scalability and efficiency issues are not well solved. Moreover, solutions are implemented on a single machine and thus cannot fit large uncertain graphs. In this paper, we develop a framework, called DURS, to distribute k-nearest neighbor search into several machines and re-partition the uncertain graphs to balance the work loads and reduce the communication costs. Evaluation results show that DURS is essential to make the system scalable when answering k-nearest neighbor queries on uncertain graphs.
AB - Large graphs are increasingly prevalent in mobile networks, social networks, traffic networks and biological networks. These graphs are often uncertain, where edges are augmented with probabilities that indicates the chance to exist. Recently k-nearest neighbor search has been studied within the field of uncertain graphs, but the scalability and efficiency issues are not well solved. Moreover, solutions are implemented on a single machine and thus cannot fit large uncertain graphs. In this paper, we develop a framework, called DURS, to distribute k-nearest neighbor search into several machines and re-partition the uncertain graphs to balance the work loads and reduce the communication costs. Evaluation results show that DURS is essential to make the system scalable when answering k-nearest neighbor queries on uncertain graphs.
KW - Distributed system
KW - K-nearest neighbor
KW - Scalable search
KW - Uncertain graphs
UR - https://www.scopus.com/pages/publications/85071048583
U2 - 10.1109/MDM.2019.00-23
DO - 10.1109/MDM.2019.00-23
M3 - Conference contribution
AN - SCOPUS:85071048583
T3 - Proceedings - IEEE International Conference on Mobile Data Management
SP - 377
EP - 378
BT - Proceedings - 2019 20th International Conference on Mobile Data Management, MDM 2019
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 10 June 2019 through 13 June 2019
ER -