选择-验证-过滤:一种迭代的子图包含查询处理机制
近年来，图模型广泛应用于生物信息、计算化学、语义网等领域。目前，“过滤-验证”机制被广泛用于子图包含查询，即首先根据图数据的特征构造索引，然后根据索引产生候选集，最后对候选集中的每一个图进行子图同构验证。在这类算法中，“过滤”阶段是关注的重点，力争过滤掉更多的数据；而“验证”阶段则只是单纯地进行候选图子图同构检测，并没有进一步优化查询性能的可能。因此，提出了一种新的子图包含查询的迭代处理机制：“选择-验证-过滤”，可利用从子图同构验证过程中得到的信息，结合数据库中图数据之间的相关关系，进行迭代查询处理。该机制首先选择数据库中的图与查询图进行同构验证，然后根据本次验证得到的信息，结合图数据之间的子图映射关系，进行迭代查询处理。一旦子图同构验证成功则可直接获得查询结果，而若验证不成功，则可以缩小下次迭代的查询搜索空间。为提高验证成功概率，提出了一种基于搜索空间预测的图选择策略。大量实验表明，该算法具有较“过滤-验证”机制更高的查询处理性能。
图数据 查询处理 迭代算法 搜索空间
Lu Jianhua 吕建华 Zhang Baili 张柏礼 Jiang Shan 姜杉 Lu Ningyun 陆宁云 Wang Feifei 王菲菲
College of Computer Science and Engineering, Southeast University, Nanjing 210096;Key Laboratory of 东南大学计算机科学与工程学院 南京 210096;计算机网络和信息集成教育部重点实验室(东南大学) 南京 210096 College of Computer Science and Engineering, Southeast University, Nanjing 210096 东南大学计算机科学与工程学院 南京 210096 College of Automation Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 21001 南京航空航天大学自动化学院 南京 210016
国内会议
合肥
中文
2221-2228
2012-10-01（万方平台首次上网日期，不代表论文的发表时间）