《不确定图数据库中高效查询处理》.pdf

第32卷第10期 计 算 机 学 报 V01．32No．10 CHINESE COMPUTERS Oct．2009 2009年10月 JOURNALOF 不确定图数据库中高效查询处理 张 硕 高 宏 李建中 邹兆年 (哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001) 摘要近年来，在多种领域中产生的大量数据都可以自然地建模为图结构，比如蛋白质交互网络、社会网络等． 测量手段的不准确性以及数据本身的性质导致不确定性在很多图数据中普遍存在．文中研究不确定图数据库中的 高效查询处理方法．首先给出一种数据模型来表示图的不确定性．鉴于对用户提交的查询图通常会产生大量匹配 结果，高效得到概率最大的k个匹配常常更具有现实意义．因此文中形式化提出概率top—k子图匹配查询的问题． 为了解决提出的查询问题，以附带概率信息的邻居子图为基础，设计了一种有效的索引结构．另外，提出一种高效 的基于索引的查询处理方法．该查询处理方法的核心是一个基于搜索树的匹配算法，其中运用了一种概率剪枝技 术来提高性能．实验结果表明，所提出方法具有良好的效率和可扩展性． 关键词 不确定性；不确定图；top-k查询；查询处理；图索引 中图法分类号TP311 DOI号：10．3724／SP．J．1016．2009．02066 Efficient onUncertainDatabases Processing Graph Query ZHANGShuoGAO LI ZOUZhao—-Nian HongJian——Zhong HarbinInstitute (School Scienceand ofTechnology，Harbin150001) ofComputer Technology， AbstractInrecent ofdatainvariousdomainshavebeen modeled years，10ts naturally by interactionnetworks，social isinherentin graphs，e．g．protein networks，etc．Uncertaintymany duetothe characteristicsof orthenatureofdata．This ofthese equipments graphs imprecise pa— addressesefficient onuncertaindatabases．Adatamodelis per queryprocessing graph proposed in a newformulationfor for uncertainties probabilistictop—k representing graphs，and