|
|||||
|
|
| 选择-验证-过滤:一种迭代的子图包含查询处理机制 | |
| 引用本文： | 吕建华,张柏礼,姜杉,陆宁云,王菲菲.选择-验证-过滤:一种迭代的子图包含查询处理机制[J].计算机研究与发展,2012,49(10):2221-2228. |
| 作者姓名： | 吕建华 张柏礼 姜杉 陆宁云 王菲菲 |
| 作者单位： | 1. 东南大学计算机科学与工程学院 南京210096;计算机网络和信息集成教育部重点实验室(东南大学) 南京210096 2. 东南大学计算机科学与工程学院 南京210096 3. 南京航空航天大学自动化学院 南京210016 |
| 基金项目： | 国家自然科学基金项目，江苏省自然科学基金项目 |
| 摘 要： | 近年来,图模型广泛应用于生物信息、计算化学、语义网等领域.目前,"过滤-验证"机制被广泛用于子图包含查询,即首先根据图数据的特征构造索引,然后根据索引产生候选集,最后对候选集中的每一个图进行子图同构验证.在这类算法中,"过滤"阶段是关注的重点,力争过滤掉更多的数据;而"验证"阶段则只是单纯地进行候选图子图同构检测,并没有进一步优化查询性能的可能.因此,提出了一种新的子图包含查询的迭代处理机制:"选择-验证-过滤",可利用从子图同构验证过程中得到的信息,结合数据库中图数据之间的相关关系,进行迭代查询处理.该机制首先选择数据库中的图与查询图进行同构验证,然后根据本次验证得到的信息,结合图数据之间的子图映射关系,进行迭代查询处理.一旦子图同构验证成功则可直接获得查询结果,而若验证不成功,则可以缩小下次迭代的查询搜索空间.为提高验证成功概率,提出了一种基于搜索空间预测的图选择策略.大量实验表明,该算法具有较"过滤-验证"机制更高的查询处理性能. |
| 关 键 词： | 图数据 子图包含查询 选择-验证-过滤 迭代算法 搜索空间优化 |
Selection-Verification-Filtering: An Iterative Subgraph Containment Query Processing Strategy |
|
| Lu Jianhua , Zhang Baili , Jiang Shan , Lu Ningyun , Wang Feifei.Selection-Verification-Filtering: An Iterative Subgraph Containment Query Processing Strategy[J].Journal of Computer Research and Development,2012,49(10):2221-2228. | |
| Authors: | Lu Jianhua Zhang Baili Jiang Shan Lu Ningyun Wang Feifei |
| Affiliation: | 1 ( College of Computer Science and Engineering , Southeast University , Nanjing210096 ) 2 ( Key Laboratory of Computer Network and Information Integration ( Southeast University ), Ministry of Education , Nanjing210096 ) 3 ( College of Automation Engineering , Nanjing University of Aeronautics and Astronautics , Nanjing210016 ) |
| Abstract: | |
| Keywords: | |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |