一种处理图数据库中超图集合的查询方法  

An Approach for Processing Supergraph Set Query in Graph Database

作　　者：李兴东[1] 姜守旭[1] 张硕[1] 

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

出　　处：《计算机科学与探索》2010年第11期1005-1009,共5页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金No.60773068;60773063;国家自然科学基金重点项目No.60933001;国家重点基础研究计划(973)No.2006CB303000;国家高技术研究发展计划(863)No.2009AA01Z149;国家博士后基金No.20090450126;哈尔滨工业大学优秀青年教师培养计划No.HITQNJS.2009.052~~

摘　　要：针对图数据库中超图集合查询问题给出有效解决方案,算法采用过滤-验证框架机制,过滤器是基于特征的索引树。给出从数据库中快速提取特征的算法以及索引建立方法。将特征组织在一棵树中,使得过滤阶段两个特征的公共诱导子图只与查询图做一次子图同构测试。在验证阶段,将Ullman算法与极大团查找算法相结合进行子图同构检测。This paper proposes an approach for processing supergraph set query in graph database,filtering-verification schema is selected in the algorithm,the filter is an index tree based on features mined from databsae.Fast algorithm for extracting features from databases is provided,it also gives method for constructing index.Organizing features in a tree make that the common induced subgraph of two or more features can be isomorphicly mapped into query only once.In verification phase,Ullman algorithm together with finding maximum cliuqe algorithm processes subgraph isomorphism test.

关 键 词：超图集合查询 特征 索引 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]