Scalable evaluation of k-NN queries on large uncertain graphs

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.