The basic definition scenario
The following definitions related with service are defined by Wu et al. [5, 6].
Definition 1
A service is a composite s = {•s, s•, O}, where •s is the set of input parameters, and s• is the set of output parameters, and O is a set of service attributes, e.g., QoS.
Definition 2
A user’s request can be represented as Q = (Qp, Qr), where Qp and Qr represent the set of service parameters provided by users and the set of service parameters requested by users, respectively.
Definition 3
Service retrieval can be defined as Re (A, S) = {s|•s ⊆ A∧ s (in) S}, where A is the given parameter set and S is a service set. The service retrieval parameter is often used to receive a set of parameters to define the user requirements, which usually returns the services invoked by the received set of parameters.
Definition 4
Service discovery Dc (Q, L(O), S) = { s| Re (Qp, S) ∧ Qr ⊆ s• ∧ s.O (angle) L(O)}, where L(O) is a set of constraints for any other attributes, S is a service set, and s.O (angle) L(O) means that s satisfies these constraints.
In this paper, service retrieval is defined to find services that can be invoked according to users’ provided parameter sets. Service discovery is to find services that can be invoked and satisfy users’ requirements according to their requests. As shown in Definition 4, service retrieval is a part of service discovery. If the time for service retrieval is reduced, then the time for service discovery will also be reduced. Service composition requires successive service retrievals to combine different services to satisfy users’ requirements that any single service cannot meet complete the users’ requests. Therefore, efficient service retrieval improves the efficiency of service discovery and composition.
The same three services from the service discovery and combination scenario in Fig. 1 are used as an example, namely ‘hotel booking’, ‘flight booking’ and ‘navigation’, all of which are indexed in the service repository. Figure 2 illustrates the redundancy in the classic inverted index and illustrates the importance of the key selection method by comparing Figs. 2, 3 and 4.
The inverted index of three services used in Fig. 1
The key index of three services used in Fig. 1
A different key index of three service used in Fig. 1, which is used to illustrate that the key selection affects retrieval efficiency
Figure 2 shows the inverted index of these three services. Assume city and date are given for a retrieval of s1, then, from city, s1 is searched, and from date, s1 and s2 are searched. The services have been searched three times in total (s1 is searched once and s2 is searched twice) before s1 can be retrieved.
Figure 3 illustrates the idea of the key index. Date is the key of s1 and s2, and hotel address is the key of s3. For the same retrieval of s1, from city, no service needed to be searched since city is not a key, and from date, s1 and s2 are searched. The services have been searched twice in total (s1 is searched once and s2 is searched once) before s1 can be retrieved, which is less than that of the inverted index (i.e. three times). Figure 3 illustrates how the key reduces redundancy and further improves service retrieval performance.
Figure 4 shows a different key index. City, departure and hotel address are the keys of s1, s2 and s3, respectively. For the same retrieval of s1, from city, s1 is searched, and from date, no service needed to be searched since date is not a key. Hence, the targeted s1 is searched only once, which is less than that of the index illustrated in Fig. 3 (twice). From the example illustrated in Figs. 3 and 4, it can be seen that the key selection methods can affect service retrieval performance. This paper focuses on the study of the key selection method under the condition of unequal service invoking frequency.
Multilevel index models
Based on the characteristics of integrity, non-redundancy and certainty of equivalence relations, Wu et al. [6] proposed an efficient multilevel index model for service retrieval based on equivalence relations, which stores and manages large-scale service repositories. This model can reduce the scope of service retrieval quickly and can improve the efficiency of the service retrieval process, thus the time for service discovery and service composition can be reduced. The multilevel index model is divided into four levels, which are:
The First Level Index (L1I): This is an index between a service s and a similar class Cs if s ∈ Cs.
The Second Level Index (L2I): This is an index between a similar class Cs and an input-similar class (C_{is}) if Cs ∈ (C_{is}).
The Third Level Index (L3I): This is an index between an input-similar class (C_{is}) and a key class (C_{k}) if (C_{is}) ∈ (C_{k}).
The Fourth Level Index (L4I): This is an index between a key class (C_{k}) and a key, key (in) К if fk((C_{k})) = key.
The relationship diagram of the entire multilevel index model is shown in Fig. 5. Firstly, the service set S is divided into many subsets, and each subset contains the same input and output parameters, which are called similar classes and denoted as Cs. Therefore, the index between service S and Cs is denoted as L1I, which can reduce the redundancy of repeated retrieval caused by services having the same input and output parameters. Secondly, the services containing the same input in the similar class Cs are divided into a class, called input-similar class and denoted as (C_{is}). The index between Cs and (C_{is}) is denoted as L2I, which can reduce the redundancy caused by the same input parameters of services. Then, the services that have the same key in the input-similar class (C_{is}) are divided into a set, which is called key class, denoted as Ck, while the index between (C_{is}) and (C_{k}) is denoted as L3I. The unique index established between each (C_{k}) and key value К is denoted as L4I, which can improve the service retrieval efficiency by selecting a unique key К to retrieve the required services.
The multilevel index model (full index model) of services
Figure 6 shows a specific multilevel index of services. There are five services s1–s5 in the service repository. Firstly, s1 and s2 compose a similar class since they have the same inputs and outputs. Other services compose different similar classes, respectively. Secondly, the first and the second similar class compose an input-similar class since they have the same inputs. Other similar classes compose different input-similar classes, respectively. Finally, the second and the third input-similar classes compose a key class since they have the same key. The other input-similar class composes a key class alone.
An example of the multilevel index
Flexible deployment
The multilevel index model can be deployed using three different methods [21] including the primary index model (L3I-L4I), the partial index model (L2I-L4I) and the multilevel index model (L1I-L4I). Both the partial and primary index models, as shown in Figs. 7 and 8, can be used for different service repositories with different sizes and characteristics.
The partial index model of services
The primary index model of services
Different key selection methods
The following five key selection methods have been studied and evaluate our proposed key selection method against their efficiency in terms of service retrieval and addition operation.
-
1)
The original key selection method
The original key selection method, which makes |(C_{k})| as close to (sqrt{left|{R}_{2}right|}) as possible. Algorithm 1 presents the operation of the original key selection method.
-
2)
The minimum key count selection method
The principle of the minimum key count selection method uses an existing key as the key of newly added services and maintains key classes as smaller as possible. If the parameters of a given service cannot be found in the existed key classes, then randomly select an input of s as its key.
-
3)
The maximum key count selection method
On the contrary to the minimum key count selection method, the maximum key count selection method uses the existing key as the key of newly added services and maintains the number of key classes as bigger as possible.
-
4)
The random key selection method
The random key selection method randomly selects one of the service input parameters as the key of the service through a random number function.
-
5)
The designated key selection method
The designated key selection method narrows down search space when a new service is added to the partial or full index, and determines a unique parameter in the service input parameter as the key.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Disclaimer:
This article is autogenerated using RSS feeds and has not been created or edited by OA JF.
Click here for Source link (https://www.springeropen.com/)
