Skip to Main content Skip to Navigation
Conference papers

Scalable Evaluation of k-NN Queries on Large Uncertain Graphs

Abstract : Large graphs are prevalent in social networks, traffic networks, and biology. These graphs are often inexact. For example, in a friendship network, an edge between two nodes u and v indicates that users u and v have a close relationship. This edge may only exist with a probability. To model such information, the uncertain graph model has been proposed, in which each edge e is augmented with a probability that indicates the chance e exists. Given a node q in an uncertain graph G, we study the k-NN query of q, which looks for k nodes in G whose distances from q are the shortest. The k-NN query can be used in friend-search, data mining, and pattern-recognition. Despite the importance of this query, it has not been well studied. In this paper, we develop a tree-based structure called the U-tree. Given a k-NN query, the U-tree produces a compact representation of G, based on which the query can be executed efficiently. Our results on real and synthetic datasets show that our algorithm can scale to large graphs, and is 75% faster than state-of-the-art solutions.
Complete list of metadata

Cited literature [43 references]  Display  Hide  Download
Contributor : Silviu Maniu Connect in order to contact the contributor
Submitted on : Friday, December 14, 2018 - 2:43:42 PM
Last modification on : Friday, July 9, 2021 - 4:35:30 AM
Long-term archiving on: : Friday, March 15, 2019 - 3:11:23 PM


Publisher files allowed on an open archive



Xiaodong Li, Reynold Cheng, Yixiang Fang, Jiafeng Hu, Silviu Maniu. Scalable Evaluation of k-NN Queries on Large Uncertain Graphs. 21st International Conference on Extending Database Technology (EDBT), Mar 2018, Vienna, Austria. ⟨10.5441/002/edbt.2018.17⟩. ⟨hal-01955609⟩



Record views


Files downloads