不确定图数据库中高效查询处理  

Efficient Query Processing on Uncertain Graph Databases

作　　者：张硕[1] 高宏[1] 李建中[1] 邹兆年[1] 

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《计算机学报》2009年第10期2066-2079,共14页Chinese Journal of Computers

基　　金：国家"九七三"重点基础研究发展规划项目基金(2006CB303000);国家自然科学基金重点项目(60533110);国家自然科学基金(60773063);国家自然科学基金委与香港研究资助局联合科研基金(60831160525)资助

摘　　要：近年来,在多种领域中产生的大量数据都可以自然地建模为图结构,比如蛋白质交互网络、社会网络等.测量手段的不准确性以及数据本身的性质导致不确定性在很多图数据中普遍存在.文中研究不确定图数据库中的高效查询处理方法.首先给出一种数据模型来表示图的不确定性.鉴于对用户提交的查询图通常会产生大量匹配结果,高效得到概率最大的k个匹配常常更具有现实意义.因此文中形式化提出概率top-k子图匹配查询的问题.为了解决提出的查询问题,以附带概率信息的邻居子图为基础,设计了一种有效的索引结构.另外,提出一种高效的基于索引的查询处理方法.该查询处理方法的核心是一个基于搜索树的匹配算法,其中运用了一种概率剪枝技术来提高性能.实验结果表明,所提出方法具有良好的效率和可扩展性.In recent years, lots of data in various domains have been naturally modeled by graphs, e.g. protein interaction networks, social networks, etc. Uncertainty is inherent in many of these graphs due to the imprecise characteristics of equipments or the nature of data. This pa- per addresses efficient query processing on uncertain graph databases. A data model is proposed for representing uncertainties in graphs, and a new formulation for probabilistic top-k subgraph matching query is presented. An effective index structure based on neighborhood suhgraphs with probabilistic information in uncertain graphs in databases is devised. In addition, based on indexes, an effieient search-tree based algorithm with probabilistic pruning techniques is proposed to search large uncertain graphs. Experimental results show that the proposed algorithms are efficient and scalable.

关 键 词：不确定性 不确定图 top—k查询 查询处理 图索引 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]