Advanced Search
    Zhang Xu, He Xiangnan, Jin Cheqing, and Zhou Aoying. Processing k-Nearest Neighbors Query over Uncertain Graphs[J]. Journal of Computer Research and Development, 2011, 48(10): 1871-1878.
    Citation: Zhang Xu, He Xiangnan, Jin Cheqing, and Zhou Aoying. Processing k-Nearest Neighbors Query over Uncertain Graphs[J]. Journal of Computer Research and Development, 2011, 48(10): 1871-1878.

    Processing k-Nearest Neighbors Query over Uncertain Graphs

    • Complex networks, such as biological networks, social networks, and communication networks, have been widely studied,and the data extracted from those applications is inherently uncertain due to noise, incompleteness and inaccuracy,so these applications can be modeled as uncertain graphs. The k-nearest neighbors (kNN) is a fundamental query for uncertain graphs, which is to compute the k nearest nodes to some specific node in a graph. In this paper, we design a framework for processing kNN query in uncertain graphs. We firstly propose a new kNN query over uncertain graphs, following which a novel algorithm is proposed to solve the kNN query. Then we optimize this algorithm which greatly improves the efficiency of the kNN query. Theoretical analysis and experimental results show that the proposed algorithm can efficiently retrieve the answer of a kNN query for an uncertain graph.
    • loading

    Catalog

      Turn off MathJax
      Article Contents

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return