摘要
图的不确定性普遍存在,研究不确定图的高效查询处理具有重要意义.文中提出了不确定图上一种新型查询——近邻查询.给定一个查询标签集R和距离约束σ,在不确定图G上进行近邻查询是要找到标签集包含R并且任意两个顶点间距离不超过σ的匹配顶点集.为解决该问题,文中首先提出了"可靠期望距离",然后基于可靠期望距离建立了高效的近邻关系图索引,将不确定图上的近邻查询等价地转化为近邻关系图上的团查询问题,最后使用树搜索算法解决近邻关系图上的团查询问题.理论分析和实验结果表明文中提出的算法能够高效地完成不确定图上的top-k近邻查询.
The uncertainty of graph data is widely existed in practice,researching on efficient query processing algorithms on uncertain graphs has significant meanings.This paper propose a new kind of query on uncertain graphs——proximity query.Given a query label set R and a distance constrain σ,executing proximity query on an uncertain graph G is to find some vertex subsets of G that whose label set contains R and for any two vertices in it,the distance between them can not exceed σ.To solve this issue,first,we propose a distance measure function named ＂Reliable Expectation Distance＂,and then design an efficient proximity relations graphs index and the proximity query on uncertain graphs is equally converted to the clique finding on proximity relations graphs.Finally,we propose a tree-based searching algorithm to finish the query processing.Theoretical and experimental results show that the proposed algorithm can efficiently retrieve the top-k proximity query results.
出处
《计算机学报》
EI
CSCD
北大核心
2011年第10期1885-1896,共12页
Chinese Journal of Computers
基金
国家自然科学基金项目(61173023)
中央高校基本科研业务费专项资金(HIT.NSRIF.201180)资助
关键词
不确定图
近邻查询
可靠期望距离
近邻关系图
uncertain graph
proximity query
reliable expectation distance
proximity relations graphs
