Visible to the public DURS: A Distributed Method for k-Nearest Neighbor Search on Uncertain Graphs

TitleDURS: A Distributed Method for k-Nearest Neighbor Search on Uncertain Graphs
Publication TypeConference Paper
Year of Publication2019
AuthorsLi, Xiaodong
Conference Name2019 20th IEEE International Conference on Mobile Data Management (MDM)
KeywordsBiology, Computer science, Correlation, distributed system, DURS, graph theory, Indexes, k-nearest neighbor, k-nearest neighbor queries, k-nearest neighbor search, Market research, Measurement, Metrics, nearest neighbor search, nearest neighbour methods, probability, pubcrawl, query processing, Scalability, scalable search, social networking (online), uncertain graphs
AbstractLarge 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.
Citation Keyli_durs_2019