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

作者：张旭; 何向南; 金澈清; 周傲英

来源：Z201110011, 2011, (10): 1871-1878.

• 生物网络
• 社会网络
• 不确定图
• k最近邻查询
• 可能世界 biological network
• social network
• uncertain graph
• k-nearest neighbors
• possible worlds

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

• 出版日期2011
• 单位华东师范大学