选择-验证-过滤:一种迭代的子图包含查询处理机制

摘要：

近年来,图模型广泛应用于生物信息、计算化学、语义网等领域.目前,“过滤-验证”机制被广泛用于子图包含查询,即首先根据图数据的特征构造索引,然后根据索引产生候选集,最后对候选集中的每一个图进行子图同构验证.在这类算法中,“过滤”阶段是关注的重点,力争过滤掉更多的数据;而“验证”阶段则只是单纯地进行候选图子图同构检测,并没有进一步优化查询性能的可能.因此,提出了一种新的子图包含查询的迭代处理机制:“选择-验证-过滤”,可利用从子图同构验证过程中得到的信息,结合数据库中图数据之间的相关关系,进行迭代查询处理.该机制首先选择数据库中的图与查询图进行同构验证,然后根据本次验证得到的信息,结合图数据之间的子图映射关系,进行迭代查询处理.一旦子图同构验证成功则可直接获得查询结果,而若验证不成功,则可以缩小下次迭代的查询搜索空间.为提高验证成功概率,提出了一种基于搜索空间预测的图选择策略.大量实验表明,该算法具有较“过滤-验证”机制更高的查询处理性能.

关键词：图数据、子图包含查询、选择-验证-过滤、迭代算法、搜索空间优化

所属期刊栏目：49

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金项目61073059,61034005;江苏省自然科学基金项目BK2010409

在线出版日期：2012-12-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：2221-2228