面向不确定图的k最近邻查询

Processing k-Nearest Neighbors Query over Uncertain Graphs

生物网络、社会网络、交际网络等复杂的网络被广泛的研究,由于数据抽出时引入的噪声和错误使这些数据具有不确定性,因此可以对这些应用使用不确定图模型建模,k最近邻查询问题是查询一个图上的距离某个特定点最近的k个邻居节点的问题,它是不确定图上的一个基础问题.设计了一个解决不确定图上最近邻问题的框架,首先定义了一种新颖的不确定图上的k最近邻查询,然后提出了针对该查询的一般处理算法,同时对该算法进行了优化,使算法效率得到极大提高.理论分析和实验结果表明提出的算法能够高效地处理不确定图上的k最近邻查询.

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.