Research On Key Selection Strategy For Multilevel Index Model Under Equal And Unequal Probability Conditions

With the explosive growth of service-oriented computing(SOC)and extensive use of Web service technology,more and more services are gathered in cloud platform which greatly increase the number of Web services.An urgent issue is that large amounts of services need to be efficiently stored and managed.Many works studied storage structures of services.Among them,a multilevel index model has proved to be very efficient for service storage in large-scale service repositories.The model reduces the execution time of service discovery and service composition.It has the advantages of high efficiency and stability,is easy to manage and maintain,as well as reduces redundancy.A novel conception of“key”in multilevel index model was proposed and applied to the logic of addition,which was used to remove much redundancy and speedup service retrieval as well as addition significantly.However,they did not discuss to what extent a key selection method can affect retrieval efficiency and whether it affects retrieval stability and addition efficiency.Focusing on these questions,an optimized and efficient key selection method is explored.Based on the findings during the exploration of multilevel indices of large-scale service,the key selection methods and their performance analysis are proposed and evaluated on account of average distribution based on service invocation.Average distribution perhaps is too idealistic,some services are"hot"and invoked frequently while others are"cold"and seldom invoked for the reasons given above.Focusing on these questions,the multilevel index model under unequal probability needs to be built and an optimized key selection method based on that needs to be further explored.The main research of this paper is as follows.(1)As key selection strategy of previous research was inappropriate,we deduced the co-variation relationship between key and retrieval time based on the process of key selection.Our theoretical analysis and experiments proved that,in a multilevel index,different key selection methods cannot affect retrieval efficiency but do affect retrieval stability and addition efficiency.Then,we proposed the three key selection methods on the basis of derived formulas.An improved key selection method is selected.The results of simulated experiments show that it saves addition time and reduces instability(measured by standard deviation)without loss of retrieval efficiency.As a result,the proposed key selection method can improve the efficiency of service discovery and service composition effectively according to experimental proving.(2)Furthermore,as previous researches were unpractically based on equal probability of service distribution and invocation,we designed and implemented unequal probability model of multilevel indices according to the existing model and separately analyzed the two situations of unequal probability of service:the unequal distribution of services input parameters and the unequal invocation of requested retrieval parameter.To simulate the unequal distribution of service inputs,we randomly select repetitive lists from input parameters generated under equal probability.In addition,Monte Carlo method was used to generated random numbers with normal distribution to simulate the unequal invocation of retrieval parameters.Then,we reduced mathematics issue from key selection under unequal probability.Due to the above conditions,we proposed overall optimal key selection method by analyzing and discussing relationship between retrieval time y and invoked counts of each key class x_i,invoking probability of each key class p_i.The time complexity of the service retrieval is deduced and overall optimal key selection method is proposed according to the function.The results of simulated experiments is carried out on multilevel indices under unequal probability for efficiency test between original,improved key selection methods and overall optimal key selection method.As a consequence,overall optimal key selection method is proved as efficient and valid.The results of simulated experiments show that it reduces retrieval time.