匡雯 顾佳燕

摘 要：大规模服务存储结构模型研究中，多级索引模型被证明是非常高效的存储结构，具有稳定、易管理、易维护、低冗余的优势。目前的研究建立在服务调用概率平均分布这一假设之上，然而现实服务调用是不等概率的，这意味着多级索引模型在服务调用的不等概率情况下还不是最优。为提高服务调用不等概率条件下多级索引模型的检索效率，通过分析多级索引模型的检索特性，推导出检索操作的时间复杂度函数。利用函数极值，设计了不等概率条件下键值的优化选择方法。实验结果显示，该方法比随机选键方法提高检索效率15%左右，证明优化选择方法能有效提高服务检索效率。

关键词：服务计算;服务检索;服务存储;多级索引模型

DOI：10. 11907/rjdk. 181798

中图分类号：TP301文献标识码：A文章编号：1672-7800（2019）001-0040-05

Abstract： Many works studied storage structures of services. Among them， a multilevel index model was proved to be very efficient for service storage for large-scale service repositories. It has the advantages of non-redundancy， stability， being easy managed and maintained. Previous works are proposed and evaluated on the assumption that the probability of service invoking is equal. However， it is too strict in reality， which means the efficiency of service retrieval is not optimal. In order to improve the efficiency of service retrieval under the condition of unequal probability of service invoking， the time complexity of the service retrieval is deduced and an optimal key selection method is proposed according to the function. Our experimental results show that the optimal key selection method reduces 15% of retrieval time. Therefore， the effectiveness and efficiency of the proposed optimal key selection method under unequal probability of service invoking are valid.

0 引言

隨着互联网技术的飞速发展和产业规模的不断扩大，Web服务呈现高速增长趋势[1]，这对软件产业提出了更高要求。随时可用性、松散耦合性、灵活的可扩展性和分布式以及更高的可重用性，是现代软件产业的突出特点[2]，服务组合是研究热点。Web服务组合指提供复杂新功能的组合服务过程[3]。工作流技术[4-6]、自动机[7]、Petri网[8-9]、人工智能规划[10]等理论和方法在服务组合领域都有应用。一些研究成果提出采用自己的服务存储结构减少服务组合时间，如Graph结构[11-13]、倒排索引[14]、Service Net[15-17]等，但仍存在一些缺陷，如复杂度高、可靠性差、用户满意度低等。

Wu等[2]基于等价类、等价划分、商集……