| Title | DURS: A Distributed Method for k-Nearest Neighbor Search on Uncertain Graphs |
| Publication Type | Conference Paper |
| Year of Publication | 2019 |
| Authors | Li, Xiaodong |
| Conference Name | 2019 20th IEEE International Conference on Mobile Data Management (MDM) |
| Keywords | Biology, 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 |
| Abstract | 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. |
| DOI | 10.1109/MDM.2019.00-23 |
| Citation Key | li_durs_2019 |
DURS: A Distributed Method for k-Nearest Neighbor Search on Uncertain Graphs