词法多重散列与包容语义相结合的服务查找  

Service discovery based on integrating lexical multi-level hashing with subsumption semantics

作　　者：傅朝阳[1,2] 高济[1] 周尤明[1] 

机构地区：[1]浙江大学人工智能研究所,浙江杭州310027 [2]苏州科技学院电子系,江苏苏州215011

出　　处：《浙江大学学报（工学版）》2010年第12期2274-2283,共10页Journal of Zhejiang University：Engineering Science

基　　金：国家"973"重点基础研究发展规划资助项目(2003CB317005);国家"863"高技术研究发展计划资助项目(2007AA01Z187);国家自然科学基金资助项目(60775029);浙江省自然科学基金资助项目(Y1090734)

摘　　要：为进一步提升服务组合性能,提出将词法多重散列与包容语义相结合的快速服务查找法.该方法有如下特点:将服务描述模型分解为不同粒度的词法和语义子块,同时将服务查找过程转换为按词法子块粒度递增的多重散列过程,利用子块间的包容语义消解散列冲突,实现降低查找失败时间至最低;所建立的服务库一方面通过缩减服务组合路径搜索空间降低查找成功时间,另一方面为设计高效组合路径查找算法提供了基础;可提供近似常数时间的原子服务查找和服务建库过程.实验证明该方法查找准确,较当前权威组织提供的基准服务查找方法效率提升显著,并具有查找时间几乎与服务库规模无关的良好稳定性.A method of fast service discovery based on integrating lexical multi-level hashing with subsumption semantics was presented to promote the performance of service composition.This method decomposes the service description into both lexical and semantic blocks of different granularity,and transforms the process of traditional discovery into a multi-level hashing in term of the ascending order by the granularity of lexical blocks.The subsumption semantics of blocks is utilized to resolve the collision during hashing,and the time for failed discoveries is reduced to the lowest.The service repository constructed accordingly can be used to decrease both the searching space of service composition paths and the time of succeeded service discoveries,and can provide an infrastructure for effective composition algorithm.This method has a nearly-constant time complexity for both atomic service searching and repository constructing.Experiments showed that both the time complexity and the accuracy of this service discovery is improved significantly compared to the benchmark one approbated by a current authority organization,and almost independent of with the size of service repository.

关 键 词：词法散列 服务查找 快速匹配 语义包容关系 有向带环加权多图 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]