大规模流程模型库的高效检索算法

大规模流程模型库的高效检索算法 Efficient Retrieval of Large Process Model Repositories 1 2 first-author 黄华，男，博士生，副教授，主要从事软件工程和业务流程管理研究．E-mail:jdz_hh@qq.com 黄华，男，博士生，副教授，主要从事软件工程和业务流程管理研究．E-mail: jdz_hh@qq.com jdz_hh@qq.com 1 corresp 彭蓉, E-mail:rongpeng@whu.edu.cn 彭蓉, E-mail:rongpeng@whu.edu.cn rongpeng@whu.edu.cn 1 武汉大学 软件工程国家重点实验室/计算机学院，湖北 武汉 430072 武汉大学 软件工程国家重点实验室/计算机学院，湖北 武汉 430072 State Key Laboratory of Software Engineering/School of Computer, Wuhan University, Wuhan 430072, Hubei, China State Key Laboratory of Software Engineering/School of Computer, Wuhan University, Wuhan 430072, Hubei, China 景德镇陶瓷学院 信息工程学院，江西 景德镇 333001 景德镇陶瓷学院 信息工程学院，江西 景德镇 333001 School of Information Engineering, Jingdezhen Ceramic Institute, Jingdezhen 333001, Jiangxi, China School of Information Engineering, Jingdezhen Ceramic Institute, Jingdezhen 333001, Jiangxi, China 为了实现对大规模流程模型库的高效检索,本文提出一种基于两级索引(节点索引和边索引)的流程模型库检索（简称流程检索）算法.该算法通过节点索引过滤大规模流程模型库,得到候选模型集,由动态构建的边索引对候选模型集进行第二次过滤,应用子图同构算法对两次过滤后的候选模型进行验证.为进一步加速流程检索过程,将该算法与并行计算模式相结合,提出一种检索效率更高的多路并行检索算法.实验结果表明,本文提出的算法可以显著提高大规模流程模型库的检索效率. In order to achieve efficient retrieval of large process model repositories, this paper puts forward a new process retrieval algorithm based on two\|level index, in which the first level index (task index) is used to filter large process model repositories and the second level index (edge index) is used to filter candidate model set again, then the final candidate models are checked by a subgraph isomorphism algorithm. In addition, this paper also proposes a multi\|channel parallel retrieval algorithm to accelerate its execution. Experiments show that our algorithms can greatly improve the retrieval efficiency of large process model repositories. 业务流程管理 流程检索 两级索引 多路并行检索 business process management process retrieval two-level index multi-channel parallel retrieval 引言 1 伴随着流程管理技术的广泛应用,各企业的信息系统积累了大量的业务流程模型 [ 1 1 ] .例如,SAP(system applications and products) 参考模型库中就有600多个EPC(event-driven process chain)模型,中国海尔集团有3 000多个业务流程模型,而拥有20多个子公司的中国北车股份有限公司则具有多达200 000个业务流程模型.这些流程模型对企业的正常运营至关重要,就像企业核心数据一样必须进行管理与维护.其中,如何在大规模流程模型库中高效检索给定的流程模型就是挑战之一. 流程辅助建模的一个主要方法就是流程检索与推荐.流程检索可以有以下两方面的功能：一方面可以根据相似度合并现有流程,去除冗余,更好的管理流程库 [ 2 2 , 3 3 ] ;另一方面,可以帮助用户在现有相似流程模型基础上重新定制并建立相关的新流程.例如,业务流程建模师在创建其业务流程时,可根据其已输入的流程片段,检索企业的流程模型库,在已检索到的相似流程模型基础上,进行业务流程的创建与修改,这样可极大提高流程建模效率,降低建模的复杂度.然而,在流程模型数达到数十万规模的模型库中检索一个包含给定流程片段的流程模型并非易事.如果应用传统的流程检索技术(例如模型匹配算法)进行穷举查询,将耗费大量时间 [ 4 4 ] .因此,提高大规模流程模型库的检索效率将非常重要. 在流程模型的相似性计算与检索方面已有很多相关研究 [ 5 5 ~ 11 11 5~11 ] ，而在大规模流程模型库的高效检索方面研究相对较少.本文主要针对大规模流程模型库的检索效率问题进行研究,提出一种基于两级索引(节点索引和边索引)与并行计算相结合的流程模型库高效检索算法,该算法利用索引及并行计算技术,加速流程检索,以提高大规模流程模型库的检索效率. 相关研究 1 流程检索的核心是找到最为相似的流程并反馈给用户,所以当前有大量研究都是围绕着流程相似度计算进行的 [ 5 5 ] .例如,文献 [ 7 7 ] 提出了四种实现图匹配的方法,经实验证明,基于图匹配的结构相似度计算能够获得最好的检索质量;文献 [ 8 8 ] 提出了基于图结构的业务流程模型检索框架,该框架利用 BPMN-Q 语言匹配业务流程图和查询模型图的相似度,检索出相似的业务流程.以上工作都是通过改进流程相似度计算算法来提高流程检索的准确率和召回率,然而,由于这些算法是对流程模型库进行“硬”搜索(穷举查询),检索效率难以保证,所以并不适合大规模流程模型库的高效检索需求. 为此,一些研究者引入数据库管理中的索引技术，提出了基于索引的流程检索算法.例如,文献 [ 9 9 ] 提出了一种基于度量树的索引算法,这种索引结构主要利用对象特征值之间的距离来对检索空间进行划分,并利用图的编辑距离来计算流程模型之间的相似度,从而提高检索效率.文献 [ 10 10 ] 使用直接相邻变迁关系定义的TAR 来计算基于行为语义的流程相似度,并通过建立名为 TAR的索引结构来提高检索效率.文献 [ 12 12 ] 提出了一个基于特征网(FNet)的索引来加速流程检索的算法,实验显示该算法比当时已有的流程检索算法快了近两个数量级.此后文献 [ 4 4 ] 提出应用节点索引(Task Index)的两阶段流程检索算法.在该算法中,第一阶段为过滤阶段:通过节点索引进行模型的筛选;第二阶段为精化阶段:应用Ullman’s subgraph isomorphism 算法 [ 13 13 ] 对过滤后的候选模型集进行同构子图验证,实验表明该算法能有效提高大规模流程模型库的检索效率,其检索效率也优于文献 [ 14 14 ] 中的检索算法. 综上所述,通过为大规模流程模型库建立各类索引进行检索,可极大提高流程检索效率.但这些算法都是应用一级索引对模型库进行筛选,然后再应用复杂的验证算法,例如子图同构验证算法,对候选模型集进行精化.由于现有的候选模型集验证精化算法的时间复杂度一般都比较高,当通过某一类索引筛选出的候选模型集仍然很大时,这些算法的检索效率将大打折扣.例如,文献 [ 4 4 ] 中的两阶段流程检索算法是一个具有一定代表性的基于索引的流程检索算法,该算法在应用节点索引筛选出的候选模型集规模较小的情况下能有效提高大规模流程模型库的检索效率.然而,当流程模型库中存在大量具有相同或相似的任务节点时,经节点索引筛选出的候选模型集规模将仍然很大,由于对候选模型集的精化是应用Ullmann’s subgraph isomorphism 算法 [ 13 13 ] 进行同构子图验证,而在图检索中找出一个图的所有同构子图的计算复杂性是一个NP完全问题,因此,精化阶段将花费大量时间,其检索效率将无法被用户所接受. 鉴于此,我们拟引入两级索引技术,对文献 [ 4 4 ] 中提出的两阶段流程检索算法进行改进：在过滤后的候选模型集中动态构建边索引(edge index),应用边索引对候选模型集进行再次过滤(根据文献 [ 4 4 ] 中有关流程查询及覆盖的定义,若一流程模型覆盖当前目标查询模型,那么该流程模型图必须包含目标查询模型图的所有节点和节点间的边.因此,本文利用边索引去再次筛选候选模型集),以进一步缩小候选模型集规模,减少精化验证阶段的时间消耗,提高流程检索效率.此外,为适应更大规模的流程模型库检索,我们将改进后的两阶段流程检索算法与并行计算模式相结合,提出了一个在大规模流程模库中检索效率更高的多路并行检索算法.为了更好的理解本文提出的算法,下面我们将给出一些相关预备知识. 预备知识 1 模型定义 2 为了以统一的方式检索不同类型的流程模型,我们假定流程模型所用建模语言为YAWL,其他建模语言所构建的模型都可以直接或间接转化成YAWL模型 [ 15 15 ] . 我们对文献 [ 4 4 ] 中的简化版YAWL模型(YNet)进行改造得到本文所用的CNet模型的形式化定义. 定义1 (CNet ): CNet=( T,F,S,J,V, TV, R ,TR,LF)，其中: T ={Start}∪{End}∪{ t i |i =1,2,3,…,n }表示一个包括开始Start节点及结束End节点的任务节点集,其中 t i 是某一具体的任务节点; F (Start×( T ＼Start))∪(( T ＼Start)×( T ×End))∪(( T ∪End)×End)表示节点间的流向关系,是节点间的有向边集; S ={NONE,AND,XOR,OR}表示任务节点的分支行为集,节点的分支行为包括:无分支、与分支、异或分支、或分支; J ={NONE,AND,XOR,OR}表示任务节点的汇合行为集,节点的汇合行为包括:无汇合、与汇合、异或汇合、或汇合; V = { v i | i =1,2,3,…, n }表示被当前流程处理的相关数据变量集,其中 v i 是某一具体任务节点读写的数据变量; TV={( t i ,v j )| t i ∈T,v j ∈V,i =1,2,3,…,n,j=1,2,3,…,m }表示任务节点与被其读写的数据变量关联关系集; R={r i | i =1,2,3,…,n}表示流程执行所需的资源集,其中 r i 是某一具体资源,可以是一个角色,或一个人或一组人; TR= {( t i ,r j )| t i ∈T,r j ∈R,i =1,2,3,…,n,j=1,2,3,…,m} 表示任务节点与其执行所需资源的关联关系集; LF: T∪V∪R→L 表示一个标签映射函数, L 是一个标签集. 为了更好的理解CNet模型并用于描述文章2.2节中的索引构建过程,下面将给出利用我们开发的基于Web的工作流可视化建模工具( http://cbpm.pasp.cn http://cbpm.pasp.cn )所构建的4个CNet模型：CN1、CN2、CN3、CN4,如 图1 图1 所示.在 图1 图1 中省略了4个模型数据与资源方面的属性,只给出模型的控制流结构. 在本文中,从流程模型库(假设为 R )中检索与一个给定模型或流程片段(也即目标查询模型,假设为 q )相似的流程模型,实质上就是从流程模型库 R 中找到覆盖 q 的流程模型集(假设为 R q ).对于一个流程模型覆盖另一个流程模型及流程检索的形式化定义在文献 [ 4 4 ] 中有详细描述,本文将不再介绍.下面将给出本文所涉及的两类索引的构建方法. 索引构建 2 节点索引(task index) 3 本文的节点索引构建过程与文献 [ 4 4 ] 中节点索引构建过程相同,节点索引的存储结构也采用倒排索引表：(task,model list).其中task表示某一任务节点；model list表示包含该任务节点的模型编号列表.例如,在一个只有 图1 图1 中4个模型的流程集中,按照文献 [ 4 4 ] 中的方法抽取各模型的所有节点,并建立索引,所构建的节点索引如 表1 表1 所示. 在本文研究中,通过Apache Lucene( http://lucene.apache.org http://lucene.apache.org ) 事先对流程模型库中所有流程节点的索引进行批量构建是本文提出的大规模流程检索的前提条件,并且当增加与删除节点所引起的索引变化,也可通过Apache Lucene进行管理与维护. task model list A CN1,CN2,CN3,CN4 B CN1,CN2,CN3,CN4 C CN1 D CN1,CN2,CN4 E CN1,CN2 F CN3,CN4 G CN3,CN4 边索引(edge index) 3 在CNet中以一个节点到另一个邻接节点的有向边线代表流程结构图的一条边.例如,在 图1 图1 的CN1模型中就有边( A,B),(A,D),(B,C) 等.边索引也采用倒排索引结构存储：(edge,model list),其中edge表示边,model list表示包含该边的模型编号列表.仍以 图1 图1 中4个模型的流程集为例,我们为其构建的边索引如 表2 表2 所示. 在构建索引的过程中,建立节点索引的时间复杂度为 O(mn) ,其中 m 为流程模型库的模型个数, n 为模型中的平均节点数;建立边索引的时间复杂度为 O(uv) ,其中 u 为候选模型集的模型个数, v 为模型中的平均边数.经过筛选后, u $$\ll $$ m ,此时O(uv) $$\ll $$ O(mn).因此,本文仅在节点索引筛选后所得到的候选模型集中构造目标查询模型 q 的边索引.由于边索引是动态构建与销毁,所以不存在对边索引进行管理与维护的操作.经节点索引及边索引进行过滤后,将大大减少候选流程模型的数量.例如在一个只有 图1 图1 所示的4个模型的流程集中检索包含边( A,B ),( A,F )的目标查询流程模型 q 1 ,通过节点过滤,可知CN3,CN4能满足要求;但通过边索引过滤后,只有CN3满足检索要求,并且经子图同构验证后,CN3就是流程库中覆盖 q 1 的检索结果. edge model list (Start, A ) CN1,CN2,CN3,CN4 (A,B ) CN1,CN2,CN3,CN4 (A,D) CN1,CN2,CN4 (A,F ) CN3 (B,C ) CN1 (B,E ) CN2 (B,G ) CN3,CN4 ( C,E ) CN1 (D,E ) CN1,CN2 ( D,F ) CN4 (F,G ) CN3,CN4 (E ,End) CN1,CN2 (G ,End) CN3,CN4 算法设计 1 根据文中第二部分的讨论,文献 [ 4 4 ] 提出的两阶段流程检索算法是一个比较典型的基于索引的流程检索算法,该算法在大规模流程模型库中具有较高的检索效率,故作为本文比较的基准算法(假定为算法0).通过对该算法的分析与改进,我们提出了基于两级索引的流程检索算法及多路并行检索算法. 基于两级索引的流程检索算法 2 为了进一步减少基准方法中候选模型集的模型数量,我们利用数据库管理中的两级索引技术,在经过节点索引过滤后的候选模型集 R q 中动态创建目标查询模型 q 的所有边索引,通过边索引对候选模型集 R q 进行再次筛选，这样将得到规模更小的候选模型集.为了使我们提出的流程检索算法更符合实际,我们计算节点标签的语义相似度,并用子图同构算法对两次过滤后的最终候选模型集进行精化验证.改进后的算法如下: 输入： R //模型库 q //目标查询模型或流程片段 输出： R q //模型库R中覆盖q的模型子集 //过滤阶段 1 tasks =ExtractingTask( q ); 2 for each task in tasks do 3 { similar_tasks=GetSimilarTasks(task); 4 model_set=null; 5 for eachsimilar_task in similar_tasks do 6 {model_set = model_set + GetModellistBy TaskIndex (similar_task, R ); 7 } 8 add model_set to model_sets; 9 }//用task index进行第一次筛选 10 R q =GetIntersection(model_sets); 11 if | R q | > max_num_query_model then 12 { edges=ExtractingEdge( q ); 13 for each edge in edges do 14{ model_set=GetModellistByEdgeIndex (edge, R q ); 15 add model_set to model_sets′; 16}//用edge index进行第二次筛选 17 R e = GetIntersection(model_sets′); 18 R q = R e ; 19 } //精化阶段 20 for each r∈R q do 21 {if USGTest( q,r ) =false then //判断 r 是否是 q 的同构子图 22 { delete r from R q ; 23 } 24 } 25 return R q ; 在算法1中，第1~19行表示模型检索的过滤阶段，它包括两个部分：节点索引过滤(1~10行)及边索引过滤(11~19行).在节点索引过滤部分，第1行用于从查询模型 q 中抽取其所有节点，存于数组tasks中；第3行利用文献 [ 4 4 ] 给出的标签语义相似度计算公式，通过标签索引得到与当前节点标签的语义相似度大于给定的标签相似度阈值 θ 的节点,并存于similar_tasks数组中;第4~8行根据similar_tasks中的节点标签到从预先创建的节点索引表中得到查询模型 q 的所有相同或相似节点所对应用的模型,并存于集合model_sets中；第10行通过求model_sets的交集得到包含目标查询 q 所有节点的候选模型集 R q .在边索引过滤部分，第11行用于判断当前的候选模型集 R q 的数量是否超过给定的模型查询数阈值max_num_query_model(超过该值，所用查询响应时间将超过用户所能接受的等待时间)，如果超过该阈值，将对候选模型集 R q 进行第二次筛选；第12行用于抽取目标查询模型 q 所有边，存于数组edges中；第13~16行根据edges中的边从候选模型集 R q 中构建目标查询 q 的所有边索引,并得到每一边对应的模型存于集合model_sets′中； 第17行通过求model_sets′的交集得到包含目标查询 q 所有边的候选模型集 R e .此外，第20~24行表示模型检索的精化阶段,其中，第21行中的USGTest( q,r )用于验证 r 是否是 q 的同构子图，如果不是，执行第22行，将 r 从候选模型集 R q 中删除.函数USGTest的子图同构验证功能是应用Ullman’s subgraph isomorphism 算法 [ 13 13 ] 来实现的.在大规模流程模型库的检索中,当通过两级索引过滤后候选模型数量远小于只通过节点索引过滤后候选模型数量时，算法1与算法0相比，其检索效率将会显著提高. 多路并行检索算法 2 为了进一步提高算法1的检索效率,并将其推广应用到超大规模的流程模型库的检索中,我们将算法1与并行计算模式相结合,提出了多路并行检索算法. 多路并行检索算法实现的一个关键前提就是如何对大规模流程模型集进行合理的子集划分.假定有一个大规模流程模型集R,为了应用多路并行检索算法,需要将R划分成n个子集：R 1 ,R 2 ,…,R n .一个合理的子集划分原则将同时满足以下3点： ① R= R 1 ∪R 2 ∪…∪R n ② R i ∩R j =,i=1,2,…,n,j=1,2,…,n 且i≠j ③ |R i |≈|R j |,i=1,2,…,n,j=1,2,…,n 且i≠j 对于已合理划分为n个子集的大规模流程模型集R,我们发挥多核处理器的性能,应用多进程(multi-processing)并行计算方法,对于每一模型子集R i (i=1,2,…,n),启用一个进程(一个进程用一个CPU核心进行运算),将算法1的功能整体打包成一个函数QTLI( q,R i ),并将其作为进程运行中调用的方法,其具体算法如下: 在算法2中,第1行用于对大规模流程模型集R进行合理的划分,并将划分后的子集(或子集编号)存于集合数组RS中.本文中的模型数据用关系数据库进行存储,我们将通过创建视图的方法对流程模型数据集进行合理的子集划分.例如,将一有100 000个模型的流程集划分为10个子集,可根据流程模型编号(假定模型编号是从1开始依次递增)选取流程子集,将模型编号在1~10 000间的流程子集创建为视 图1 图1 ,模型编号在10 001~20 000间的流程子集创建为视 图2 图2 ,依次类推,共创建10个视图.这10个视图就是对当前流程集进行合理划分的10个子集;第2行是定义一个全局的检索结果集ResultList用于存储各检索进程的检索结果,ResultList的初始值为空;第3~6行是为每一流程子集创建一个进程(每一进程调用一个CPU核心),由该进程调用函数QTLI (q ,rs)对当前流程子集进行检索,其中函数QTLI (q ,rs)的实现过程与算法1基本类似,只是在返回检索结果 R q 之前加上以下几行代码： if | R q | > 0 then { lock(currentProcessing); add R q to ResultList; unlock(currentProcessing); } 以上代码用于将某一流程子集的非空检索结果集增加到全局检索结果集ResultList中． 对于算法2,将模型个数为m的流程模型集R合理划分为n个流程子集,则每一子集的个数约m/n.假定算法1在R中的查询时间复杂度为O(m) ,算法2用n个查询进程去并行检索R中的n个流程子集,在不考虑划分和合并时间的情况下,算法2的查询时间复杂度将约为O(m/n),则算法2与算法1间的加速比 speedup = O(m)/O(m/n)≈n.因此,在大规模流程模型库中进行流程检索,与算法1相比，算法2的检索效率将会显著提高. 输入： R//模型库 q //目标查询模型或流程片段 输出：R q //模型库R中覆盖q的模型子集 //子集划分与检索 1 RS=DivideSubSet( R ); 2 ResultList=;//定义一个全局检索结果集 3 for each rs in RS do 4 {Process=CreateOneProcess(QTLI( q ,rs)); 5 Process.Start(); 6 } //返回归总后的查询结果集 7 if AllProcessIsFinished()=true then 8 returnResultList; 实验验证 1 实验设计 2 为了对上述算法进行验证,我们开发了一个实验支撑平台( http://platform.pasp.cn http://platform.pasp.cn ).该平台已开发上线的功能包括:工作流可视化设计器( http://cbpm. pasp.cn http://cbpm. pasp.cn )、流程模型模拟生成工具、模型导入工具、实验结果图形化显示工具.其中,流程模型模拟生成工具通过应用WordNet数据库(MS SQL2005,400MB),随机生成流程各节点的标签.模型中控制流结构的生成规则来源于文献 [ 16 16 ] ,而对于节点分支行为及汇合行为,我们也采用随机方式进行赋值.为保证生成模型的正确性,流程模型模拟生成的过程中,我们对生成模型进行语法结构检测,以保证生成模型的结构正确性. 在实验中,我们利用流程模型模拟生成工具,随机生成6组大规模流程模型集,各组中的模型个数分别为：100 000、200 000、300 000、400 000、500 000、600 000,其任务节点的记录条数从2 321 568到13 944 907,节点间关联关系(边)的记录条数从3 207 539到19 265 511.另外,通过Apache Lucene为各组流程模型集批量生成其所有节点索引及标签索引,并存储在相应的索引表中. 通过流程模型模拟生成工具随机生成10个目标查询模型q 1 ~q 1 0 .为了比较算法0、算法1、算法2在同一标签相似度阈值(在我们的实验中θ=0.8)下检索效率方面的差异,在每组模型集中,对10个目标查询模型q 1 ~q 1 0 ,用算法0、算法1、算法2分别检索三次.其中,算法2在WEB服务器(具有多核处理器)的10个虚拟机上创建10个进程对每组模型集的10个合理划分子集 (10个数据库视图)进行10路并行检索,每次检索的结果及所耗时间和空间都实时写入到检索结果记录表中.最后,通过实验结果图形化显示工具实时查看实验结果,并对结果进行分析. 实验结果 2 真实数据 3 我们通过模型导入工具导入真实的流程模型数据,例如604个SAP参考模型 [ 17 17 ] ,进行实验验证.但由于其规模较小,我们只用作比较算法1与算法0在不同标签相似度阈值 θ 下查询效率的实验数据，如 图2 图2 所示，随标签相似度阈值 θ 增大，算法1将节省更多的查询时间；而在同一标签相似度阈值 θ 下比较算法0、算法1、算法2查询效率的实验中将采用模拟生成的大规模流程模型集进行实验验证. 模拟数据 3 根据文献 [ 4 4 ] 所述,我们从算法的执行代价:查询响应时间(query time)及查询内存占用量(storage size)来比较算法0、算法1、算法2的流程检索效率.由于是对多组模型集进行多次检索实验,且每次检索所需时间和空间的变化是相似的,因此,我们用每种算法对每组流程模型集的平均查询响应时间及平均查询内存占用量进行比较. 对每组大规模流程模型集,我们应用算法0、算法1、算法2进行了各10次的检索实验.从平均查询响应时间维度进行比较,得到如 图3 图3 所示的实验结果. 如 图3 图3 所示,算法1 (Task-Edge Index)及算法2 (Task-Edge Index for Parallel Query)的检索效率优于算法0 (Task Index),且随模型集规模的增大,其优势越发明显.如 图4 图4 所示,随着模型数量增多,算法0与算法1间的查询加速比也在增大.另外,在大规模流程模型库中,算法2的检索效率也明显优于算法1,并且随模型数量的增多,算法1与算法2的查询加速比也越来越大. 此外,对于算法0、算法1、算法2,从平均查询内存占用的量维度进行比较,得到如 图5 图5 所示的实验结果： 如 图5 图5 所示,算法1(task-edge index)和算法2(task-edge index for parallel query)的服务器内存占用量小于算法0 (Task Index),且随模型数量的增多,其优势越发明显.然而,算法2与算法1相比,其服务器内存占用量并没有节省,反而有所增多,因为服务器对多进程的创建和管理需要消耗内存空间. ① 算法1的平均查询响应时间/算法2的平均查询响应时间;②算法0的平均查询响应时间/算法1的平均查询响应时间 ① the average query time of Algorithm 1/the average query time of Algorithm 2; ② the average query time of Algorithm 0/the average query time of Algorithm 1 实验分析 2 为了更好的理解上述实验结果,我们对实验数据进行理论分析.每一种算法的查询响应时间及查询内存占用量的计算公式如下. ① 对于算法0,其查询响应时间: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458303&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458303&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458303&type=middle 而其查询内存占用量则由(2)式估算得到: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458304&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458304&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458304&type=middle ② 对于算法1,其查询响应时间： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458306&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458306&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458306&type=middle 其查询内存占用量可由(4)式估算得到： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458308&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458308&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458308&type=middle ③ 对于算法2,其查询响应时间: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458312&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458312&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458312&type=middle 其查询内存占用量由(6)式估算得到: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458315&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458315&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458315&type=middle 在上述 (1)~(6) 式中,T t 是查询请求及结果数据的网络传输时间,T I/O 是一个流程模型数据读写时间,T v 是单个模型的同构子图验证时间,T ti 是目标查询模型q的节点索引构建时间(从节点索引表检索出q的所有节点索引的时间),T ei 是在候选模型集中构建q的边索引时间,T c 是进程的创建与销毁时间,T i 表示进程i调用方法 QTLI 对模型子集i的查询时间,M I/O 是一个流程模型数据内存占用量(写入到内存进行同构子图的验证),M ti 是q的所有节点索引的内存占用量,M ei 是构建边索引的内存占用量,M t 是进程本身的内存占用量,M i 是进程i调用方法 QTLI 对模型子集i进行查询的内存占用量.另外,|R ti |是通过 Task Index 过滤后的候选集模型个数. 对于 (1)~(6) 式,有|R ti | $$\gg $$ |R ei |,(T I/O +T v ) $$\gg $$ T ti ,(T I/O +T v ) $$\gg $$ T ei ,T q 2 $$\gg $$ max ({T i |,i=1,2,3,…,n}),∑ni=1M i ≈M q 2 ,M I/O $$\gg $$ M ti ,M I/O $$\gg $$ M ei ,可得出：T 0 q > T 1 q > T 2 q ,M 0 q > M 2 q > M 1 q .也就意味着在同一标签相似度阈值下,与改进前的两阶段检索算法(算法0)相比,改进后的基于两级索引的两阶段检索算法(算法1)具有更高的检索效率,并且消耗的服务器内存更少；同时,多路并行检索算法的检索效率又高于基于两级索引的两阶段检索算法,但其消耗的服务器内存比算法1要多,这个实验结果正如 图3 图3 ~ 图5 图5 所示. 本文提出的基于两级索引的流程检索算法在节省内存空间的同时,能明显提高大规模流程模型库的检索效率;另外,将基于两级索引的流程检索算法与并行计算模式相结合而形成的多路并行检索算法,能大幅度提高大规模流程模型库的检索效率,更适合应用在超大规模流程模型库的高效检索中. 结论与展望 1 本文针对如何提高大规模流程模型库的检索效率问题,对一种典型的基于索引的流程检索算法,即文献 [ 4 4 ] 提出的两阶段流程检索算法进行分析和改进,提出了一种基于两级索引(节点索引和边索引)的流程检索算法,并且将该算法与并行计算模式相结合,提出了一种检索效率更高的多路并行检索算法.本文的主要贡献有如下两点： 1) 应用两级索引技术对两阶段流程检索算法的进行改进,在算法的过滤阶段通过动态创建的边索引对节点索引过滤后的候选模型集进行再次过滤，以大大减少候选模型数量，节省精化阶段的验证时间，提高大规模流程模型库的检索效率； 2) 将并行计算模式引入到流程检索算法中,提出了效率更高的多路并行检索算法. 本文提出的流程检索算法对于如何提高大规模流程模型库的检索效率具有一定的指导与实践意义.但本文的研究工作还需要进一步完善,例如,如何综合考虑节点的相关行为(分支、汇合)及节点关联的数据和资源,来增强节点索引的过滤能力,以进一步提高流程检索的效率及其准确度,这将是我们下一步需要完善和研究的工作. 参考文献 WANG J M, JIN T, WONG R, et al. Querying business process model repositories [J].World Wide Web, 2014, 10(17):427-454. ter HOFSTEDE A H M, OUYANG C, La ROSA M, et al．APQL: A process-model query language [DB/OL]. [2015-08-09] . http://ise.thss.tsinghua.edu.cn/AP-BPM/.DOI: 10.1007/978-3-319-02922-1_2 10.1007/978-3-319-02922-1_2 DUMAS M, GARCíA-BAUELOS L, DIJKMAN R M. Similarity search of business process models [J]. IEEE Data Eng Bull, 2009, 32(3): 23-28. JINT, WANG J M, La ROSA M, et al. Efficient querying of large process model repositories [J]. Computers in Industry, 2013, 64(1): 41-49. DIJKMAN R, DUMAS M, Van DONGET B, et al. Similarity of business process models: Metrics and evaluation [J]. Information Systems, 2011,36(2): 498-516. BECKER M, LAUE R.A comparative survey of business process similarity measures [J]. Computers in Industry, 2012, 63(2): 148-167. CORRALES J C, GRIGORI D, BOUZEGHOUB M. BPEL processes match making for service discovery [DB/OL]. [2015-09-09] . http://www.cs.rmit.edu.au/fedconf/coopis/2006 http://www.cs.rmit.edu.au/fedconf/coopis/2006 . SAKR S, AWAD A. A framework for querying graph-based business process models [DB/OL]. [2015-09-10] . http://www. www2010.org/www/ http://www. www2010.org/www/ . KUNZE M,WESKE M. Metric trees for efficient similarity search in large process model repositories [DB/OL]. [2015-08-10] . http://www.bpm2010. org/ http://www.bpm2010. org/ . JIN T, WANG J M, WEN L J. Efficient retrieval of similar workflow models based on behavior[DB/OL]. [2015-02-10] . http://link.springer.com/chapter/10.1007%2F978-3-642-29253-8_64 http://link.springer.com/chapter/10.1007%2F978-3-642-29253-8_64 . JIN T, WANG J M, WEN L J. Querying business process models based on semantics[DB/OL]. [2015-04-10] . http://www.cintec.cuhk.edu.hk/DASFAA 2011/ http://www.cintec.cuhk.edu.hk/DASFAA 2011/ . YAN Z Q, DIJKMAN R, GREFE P. FNet: An index for advanced business process querying [DB/OL]. [2015-05-10] . http://bpm2012.ut.ee/ http://bpm2012.ut.ee/ . ULLMANN J. An algorithm for subgraph isomorphism [J]. Journal of the ACM,1976,23(1):31-42． QIAO M, AKKIRAJU R, REMBERT A J. Towards efficient business process clustering and retrieval: combining language modeling and structure matching [DB/OL]. [2015-08-10] . http://www.irmuk.co.uk /bpm2011/ http://www.irmuk.co.uk /bpm2011/ . van der AALST W M P, ter HOFSTEDE A H M. YAWL: yet another workflow language [J]. Information Systems, 2005, 30(4): 245-275. WYNN M T, VERBEEK H M W E, van der AALST,et al. Reduction rules for YAWL workflows with cancellation regions and OR-joins [J]. Information & Software Technology, 2009, 51(6)：1010-1020. van DONGEN B F, de MEDEIROS A K A, VERBEEK H M W,et al. The ProM framework: A new era in process mining tool support [DB/OL]. [2015-06-09] . http://www.cs.fiu.edu/atpn2005 http://www.cs.fiu.edu/atpn2005 . 10.14188/j.1671-8836.2016.03.011 TP 311 whdxxblxb-62-03-275 国家自然科学基金 (61100017); 国家科技支撑计划课题(2012BAH25F02, 2013BAF02B01); 中央高校基本科研业务费专项资金(2012211020203,2042014kf0237)资助项目 2015-04-05 2016-06-24 2020-12-09 版权所有 © 《武汉大学学报(理学版)》编辑部 Copyright © 2016 Journal of Wuhan University (Natural Science Edition). All rights reserved. 2016 武汉大学学报(理学版) 3 62