Exploiting named entity recognition for improving syntactic-based web service discovery

Abstract

Web Services have become essential to the software industry as they represent reusable, remotely accessible functionality and data. Since Web Services must be discovered before being consumed, many discovery approaches applying classic Information Retrieval techniques, which store and process textual service descriptions, have arisen. These efforts are affected by term mismatch: a description relevant to a query can be retrieved only if they share many words. We present an approach to improve Web Service discoverability that automatically augments Web Service descriptions and can be used on top of such existing syntactic-based approaches. We exploit Named Entity Recognition to identify entities in descriptions and expand them with information from public text corpora, for example, Wikidata, mitigating term mismatch since it exploits both synonyms and hypernyms. We evaluated our approach together with classical syntactic-based service discovery approaches using a real 1274-service dataset, achieving up to 15.06% better Recall scores, and up to 17% Precision-at-1, 8% Precision-at-2 and 4% Precision-at-3.

Keywords

Information retrieval named entity recognition natural language processing service-oriented computing web Services

1. Introduction

Many years have passed since service-oriented computing (SOC) first appeared. Nowadays, with thousands of available Web Services, SOC has become essential for developing Web 2.0 applications. SOC is a computing paradigm that promotes assembling Internet-accessible components, called services, to create new applications. Then, applications are developed using services as the basic building blocks, decreasing development costs. Web Services, the most common technological materialisation of SOC, are of utmost importance to the industry as they expose functionality/data that can be accessed remotely. Furthermore, as social networks and Cloud Computing have become more popular, new applications which combine Web Services from different sources – also known as ‘Web mashups’– emerged [1].

Web Service descriptions allow consumers to invoke services without the necessity of knowing how they are implemented as such descriptions act as individual application programming interface (API) descriptions. These descriptions define not only service data types and operations, but also support communication protocols, such as hypertext transfer protocol (HTTP) or simple object access protocol (SOAP), and data formats, such as JavaScript object notation (JSON) or extensible markup language (XML). Web Services descriptions are produced using markup-based Web Service description languages [2], which build on standard markup languages – mainly XML – and textual content or semantic description languages [3,4], which exploit ontologies. Moreover, these descriptions can be SOAP based or representational state transfer (REST) based. SOAP-based Web Services are described by markup-based description languages such as web services description language (WSDL) or by semantic description languages such as web ontology language (OWL) or Web Service Description Language-Semantic (WSDL-S). On the other hand, REST Web Services use newer yet not widely adopted descriptions such as web application description language (WADL) for markup-based descriptions or semantic annotations for representational state transfer (SA-REST) for semantic descriptions.

Once the service descriptions are published, services need to be discovered. On the SOAP side, the Universal Description, Discovery and Integration (UDDI) standard was first proposed to address this issue. Although UDDI has not been widely accepted, the importance of service discovery has motivated a wide range of research [5]. Analogously, discovery is also an important research topic in REST services [6 –8]. Currently, regardless of service type, there are two main approaches for service discovery: semantic based [9] and syntactic based [8]. The former requires Web Service descriptions to be annotated with semantic information from ontologies. Although in theory these types of semantic Web Services can be unambiguously described and therefore easily discovered, they are rather uncommon in real-life applications because they are difficult to describe with semantics. On the other hand, syntactic-based approaches rely on markup-based Web Service descriptions which are easier to produce, but bad specification practices [10] make this kind of Web Services difficult to discover and consume [11].

Most syntactic-based discovery approaches exploit traditional information retrieval (IR) techniques to match keyword-based queries against a stored collection of markup-based Web Service descriptions (documents), which potentially contain such keywords. When a user’s query contains multiple topic-specific keywords that approximate the needed service, the Web Service registry is probably to return good matches. However, users often introduce ambiguous and short natural language sentences. This makes it difficult to retrieve relevant documents because only words within the query are considered for the search, leading to term mismatch. This problem is known as the vocabulary problem [12], compounded by polysemy (same word with different meanings, e.g. ‘java’) and synonymy (different words with the same or similar meanings, e.g. ‘TV’ and ‘television’).

Several efforts have been made in the IR community to cope with the vocabulary problem beyond Web Service discovery. Query expansion [13] intends to solve this phenomenon by finding features correlated with query terms. This expansion can be applied to both queries and documents. Query-oriented techniques consist of adding terms which are not initially included in a query and can be derived from the others, for example, synonyms. Document-oriented techniques operate on the same basis, but using documents as source instead. Although operating on a document might introduce noise since the amount of terms to expand is bigger, it also paves the way for newer context-aware natural language processing (NLP) techniques.

Traditionally, query expansion has been performed using different corpora, most commonly WordNet, and it is a very common strategy to improve discoverability [3,14]. Some Web Service–specific techniques enhance queries by taking advantage of partial, structured service interfaces at the consumer end [15]. On the other hand, document expansion can take advantage of the much higher number of terms documents contain compared with queries. This allows extracting terms while exploiting their context. Also, document expansion is performed differently on Web Service descriptions because they have a distinctive structure compared with natural language texts. Web Service descriptions are organised in sections, that is, operations, port types and messages, each containing documentation that can be taken as independent pieces of text. Also, in the case of REST-inspired service descriptions, there are a high percentage of nouns [10], while in SOAP-based services there is a mix of nouns and verbs [11]. This creates an opportunity for advanced NLP techniques that take advantage of these particularities for expanding Web Service descriptions with meaningful information.

In this article, we present an approach for improving Web Service discoverability by automatically expanding Web Service descriptions. The approach can be applied to any syntactic-based Web Service registry, for example, as a preprocessing step prior to searching or storing documents. As a first step, our approach uses Named Entity Recognition (NER) [16] to identify entities in Web Service descriptions. A named entity is an atomic piece of text that belongs to a predefined category, for example, ‘Washington’ is a city while ‘NBA’ and ‘NFL’ are organisations. Then, these entities are expanded with definitions extracted from Wikidata [17]. Conceptually, this improves discoverability by reducing term mismatch since it adds relevant related words (e.g. synonyms and hypernyms) to the service description. We assessed our approach using a 1274-Web Service dataset. The results have shown an improvement of up to 17.24% for Precision-at-1, 8.62% for Precision-at-2 and 4.59% for Precision-at-3. In addition, Recall was greatly improved (up to 15.06%) along with other relevant metrics such as normalised discounted cumulative gain (NDCG) and F-Measure. We also compared our approach against traditional WordNet expansion and against that of Chen et al. [18] which proposes a kernel-based approach combined with WordNet Dimensionality Reduction (WDR).

The rest of the article is organised as follows. Section 2 discusses background work in service discovery, for example, both syntactic-based and semantic-based approaches. Section 3 presents state-of-the-art work along with a discussion section of how our approach contributes to the area. Then, section 4 describes two broad types of syntactic-based Web Service registries we have used for assessing our approach. Section 5 outlines the proposed approach. Section 6 presents its evaluation. Finally, section 7 concludes the article and introduces future research opportunities.

2. Background

Syntactic-based Web Service discovery employs well-known IR techniques to retrieve relevant services. Some languages for describing syntactic-based Web Services are the WSDL [2] for SOAP-based services and WSDL 2.0 or WADL for REST-based services. Service descriptions written in these languages provide details about the service-exposed functionality/data, data types, access protocols and endpoints through which consumers can access the service. On the other hand, semantics-based service discovery uses languages such as the OWL [13,19] or the Web Service Modelling Ontology (WSMO) [4] to describe services and support matchmaking.

Semantic Web Services aim at systematising and annotating Web Service descriptions using machine-understandable concepts explicitly defined in ontologies. These ontologies are used to provide metadata for the effective manipulation of available information, including discovering concept relationships, restrictions and properties. Unfortunately, annotations require manual intervention to be properly defined and ontologies are difficult to define and tie to a domain. As a result, semantic Web Services are not as popular as their syntactic counterpart. Notice that in semantic Web Services ontologies drive the building of Web Service descriptions, which differs from syntactic Web Services that might optionally employ ontologies for achieving increased discoverability [20,21].

On the other hand, syntactic Web Services are widely adopted by the industry, mainly because of the simplicity they provide to describe functionality. Initial research on syntactic Web Service discovery adapted well-known IR techniques such as the vector space model (VSM) to the Web Services field. VSM considers documents as vectors in which each dimension represents a term in a document. A typical way of determining the importance of a term in a document is term frequency–inverse document frequency (TF-IDF). TF-IDF is a numerical statistic that measures how relevant a term is in a document by considering how many times the term appears in the document and how common the term is within the whole corpus.

3. State of the art

Many techniques have been proposed to reduce complexity and improve discoverability of semantic Web Services. Some works take advantage of NLP to extract information from user queries [22] and map extracted terms to concepts in ontologies. Once a query is processed, ontology linking is used to retrieve concepts probably to appear in the documents. Ontology linking maps domain ontologies to upper merged and mid-level ontologies as well as domain-level ontologies, unhiding semantic relations between a specific query and published services. As a final step, a matchmaking technique based on significant concept properties in referenced ontologies is applied to determine similarity. Likewise, Ma et al. [23] perform query expansion using WordNet and domain ontologies. The approach takes entire WSDL descriptions as queries. Once the query (description) is refined and expanded, it is sent to a ranking module that compares the request against each service description from the service registry.

Syntactic-based Web Services are the de facto standard for developing services. Consequently, many researchers have focused on improving discoverability in this area. The work by Platzer and Dustdar [24] proposes a distributed scheme that combines VSM with cosine similarity to retrieve services from many UDDI registries. Another work by Sajjanhar et al. [25] applies a classic TF-IDF scheme combined with singular value decomposition (SVD) to find similar Web Services. SVD reduces the dimensionality of the TF-IDF matrix, filtering irrelevant services. Similarly, Elshater et al. [26] use a TF-IDF scheme combined with VSM implemented as a KDTree structure. Each node in the tree splits on a particular hyperplane dimension given by each term. Then, when a user’s query arrives, the value for that dimension in the query vector is recursively compared to follow the appropriate subtree. Once a leaf node is reached, the nearest neighbour services associated to this leaf node are retrieved, achieving $O (\log_{2} N)$ search complexity. Wang and Stroulia [27] take a different direction and propose a structural matching algorithm. The similarity of two services is given by the similarity of the textual information (TF-IDF + VSM) and by how structurally similar operations and parameter types are. To calculate this, they establish a degree of similarity between primitive types and then use this to calculate the similarity of more complex data types. Other approaches take advantage of WordNet to improve discoverability. Sotolongo et al. [28] combine WordNet with a linear discriminant function. The algorithm parses the WSDL descriptions to extract documentation and name attributes. Then, the authors create two separate VSM spaces: one for the original WSDL and another that comprises the synonyms of each word using WordNet. Finally, they combine cosine similarity applied on both spaces with a linear function to calculate query–service similarity. Another work by Chen et al. [18] presents an approach to improve discoverability by combining two original ideas (1) WDR and (2) kernel functions. WDR tries to reduce the dimensionality of the term matrix by merging words that are synonyms, eliminating noise. On the other hand, a sigmoid kernel is used to calculate the similarity between the query and the service descriptions. The work by Czyszczoń and Zgrzywa [29] proposes a modified TF-IDF scheme that considers sections in a service description as different bags of words. This has two implications: (1) as TF-IDF values are calculated for each bag, document similarity scores drastically change, and (2) multiple term vectors are created (one for each section), increasing memory consumption. To mitigate the latter (2), the approach merges such sections and computes the average weight of all service operation’s parameters. Finally, the approach uses latent semantic indexing (LSI), an extension of the VSM model (see section 3.1), to calculate document similarity. Similarly, Paliwal et al. [20] also uses LSI for calculating document similarity but combined with ontology linking. The authors build a service request vector according to the corresponding domain ontology. Then, the request is projected with LSI and compared using cosine similarity to retrieve relevant documents. Other works [30,31] use clustering to improve retrievability. Dong et al. [30] present Woogle, a Web Service search engine that exploits Web Service descriptions’ structure and employs clustering on parameter names to extract meaningful concepts. These concepts along with operation names and descriptions are then used to search. Ma et al. [31] take a different direction and combine KMeans clustering for filtering Web Services with probabilistic latent semantic analysis (LSA) to create clusters of concept-related services. The last step involves comparing the query against these concepts to retrieve the most relevant services. Finally, some approaches exploit the document structure prescribed by WSDL. Hao and Zhang [32] take advantage of the WSDL tree structure. First, traditional VSM is performed to retrieve candidate documents. Then, given a structured query in natural language they apply tree edit distance to retrieve the most similar services.

Other works have focused their efforts on the query side. The work by Paliwal et al. [21] proposes a two-step approach for service discovery. The first step comprises a semantic categorisation of services published in a UDDI registry. The second step involves query refinement, which consists of input/output parameter analysis, to select a set of services that best represent the desired functionality and query expansion with relevant ontology terms. Another work by Crasso et al. [15] considers additional information provided by a Query by Example approach [33], which allows discoverers to partially prespecify the necessary service functionality by providing examples (source code) in their preferred programming language. This enriches query information by extracting terms from parameter names and operation names from the example, which are then used to compute similarity using VSM [34] and cosine similarity.

3.1. Discussion

Our research focuses on improving syntactic Web Services discoverability using information extraction techniques. In particular, our approach considers service descriptions as the main source of information for improving the discovery process. Since service descriptions contain a lot more information than queries, this opens the possibility to take advantage of context-dependant NLP techniques. Specifically, we used NER to identify opportunities to expand these descriptions by exploiting knowledge databases.

NER is nowadays a hot research topic in the NLP community, as it became essential for many information extraction tasks such as semantic annotation, question answering, semantic web applications or opinion mining [35] and it is widely used in other domains such as Biomedicine [36].

Since NER became so powerful to perform such tasks, this work proposes the application of such technique to boost existing syntactic Web Service discovery approaches. Web Service descriptions are self-contained, structured documents that describe the functionality that a service has to offer. One main difference between these descriptions and traditional natural language documents is that Web Service descriptions have technical content since they are intended to be read by developers. This means that, as in domain-specific fields (e.g. Biomedicine), they tend to contain more acronyms and references to technologies or libraries that are not usually found in traditional documents. This opens the opportunity to apply techniques capable of identifying this domain-specific content. One way is to use NER and take advantage of Named Entities to expand service descriptions. In our case, we opted to combine this with knowledge databases to add descriptions of Named Entities to Web Service descriptions. To the best of our knowledge, from all the works in the area none has considered such approach to improve syntactic-based service discoverability. Our technique can be applied to any existing syntactic Web Service registry, such as the ones mentioned above, as a prior step in document preprocessing as it is not tied to any specific Web Service description language.

4. Syntactic web service discovery

An important issue when developing an SOC application is deciding whether to implement some application component, or reuse an existing implementation instead. In order to use a service, it must first be discovered [37]. Web Services allow providers to wrap any piece of software or resource and publish it to a registry. Publishing services comprises supplying the registry with a technical description of the offered functionality. This description is processed by the registry in order to make it available to potential consumers. This process consists of two steps, namely, preprocessing and indexing.

Syntactic Web Service descriptions are usually written in a structured specification language such as WSDL or WADL. These specifications contain useful information for the service to be consumed. However, they also contain structural information that is not relevant to the user, for example, markup tags. Then, Web Service registries usually perform a preprocessing step that transforms the document into a filtered bag of words that ideally contains only search-relevant terms. This step usually includes stemming, stopword removal and optionally document expansion. The output of this process is taken by the search engine to perform the indexing step. In this context, indexing can group the documents in a non-partitioned schema (section 3.1), in which documents are in the same search space, or in a partitioned schema (section 3.2), in which documents are placed in clusters. When a user searches for a Web Service, the registry performs a search against the index that holds all the published services.

4.1. Non-partitioned indexing

Maintaining documents grouped in the same search space is a classic technique for document retrieval. The archetype of this technique is VSM, in which documents are seen as a collection of terms, whereas each dimension of the space corresponds to a separate term (usually single words). For example, Figure 1 represents a document containing the terms ‘currency’ and ‘exchange’. As a result, documents which have similar contents are represented as vectors located near each other in the vector space, thus searching for related documents translates into searching for nearest neighbours in the space. Figure 2 depicts two vectors and their angle Ω that is used to calculate the similarity between documents as the cosine of the angle Ω. As Web Services are described using documents, these could be translated onto vectors. Therefore, by representing queries as vectors, service lookup operates by comparing such vectors. Specifically, the vector representing a query is matched against the vectors in the space (i.e. the available services). The service, the vector of which maximises the spatial nearness to the query vector, is retrieved.

Figure 1.

Vector space model: representation.

Figure 2.

Vector space model: comparison.

Although very popular, VSM only addresses syntactic term relationship. One major challenge towards improving discoverability is to analyse documents to find the underlying meaning of words. The problem with retrieving documents that are relevant to the user resides in deciphering users’ needs. Ideally, different words should be directly related to different concepts, as shown in Figure 3. Unfortunately, natural languages have multiple words that are associated with the same concepts as shown in Figure 4, hiding the real meaning or concept behind the words. There are many attempts to solve this problem such as LSA [38] or latent Dirichlet allocation (LDA) [39]. In particular, LSA works by analysing word co-occurrence in documents. If two words usually appear in the same context, they will probably be related. For example, the words ‘currency’ and ‘dollar’ might usually appear in finance-related documents. To do this, LSA uses SVD, which maps words into concepts by reducing the number of dimensions of the term occurrence matrix. Words are then compared by calculating the cosine of the angle between the two vectors representing the words as concepts.

Figure 3.

Terms and concepts: ideal case.

Figure 4.

Terms and concepts: real case.

4.2. Partitioned indexing

Partitioning the search space consists of forming groups of highly related documents. This has the advantage of better search performance than the non-partitioned scheme because it reduces the number of documents to brute-force search.

A commonplace approach for partitioning the search space is clustering [6]. Clustering is the task of grouping sets of elements into a way that these elements are more related to each other than with elements from different groups. Clustering has an advantage over other similar approaches such as classification because the former does not require a manually labelled dataset to be trained. In this context, KMeans is the most widespread implementation of clustering and it has been used previously for performing service discovery [31, 40, 41]. KMeans works by calculating vectors called centroids that represent a set of elements. To achieve this, the algorithm starts with random centroids. The first step is determining which documents are nearer to each centroid. Then, the algorithm adjusts the centroids by recalculating them as the mean of the distances of each element. These steps are repeated until a convergence criterion is met or the predefined number of iterations is exceeded.

5. NER for web services

Finding the underlying meaning of service descriptions or queries is key to improve discoverability, but many current service matching techniques fail to consider service semantics in a transparent non-intrusive way. Particularly, semantic Web Services require developers to add extra information in the form of annotations with concepts from shared ontologies in order to ‘semantify’ service specifications.

In recent years, there have been significant advances in the NLP area. In particular, sequence models and classifiers enabled for elaborating semantic information extraction techniques by identifying hidden text patterns and structures. To do this, such models are trained with large datasets which provide information that allows the models to learn, for example, grammatical relationships or co-occurrence between words. These advances provided the basis for more complex information extraction techniques such as NER to become readily available. A named entity is an atomic piece of text that belongs to a predefined category, for example, ‘Washington’ is a city while ‘National Basketball Association’ and ‘NFL’ are organisations. Roughly, our approach (see Figure 5 for an overview) uses NER for identifying relevant entities in Web Service descriptions. Once an entity is identified, we expand the meaning by extracting additional information from a knowledge base. Web Service descriptions are technical documents that are intended to be read by developers, as opposed to traditional natural language documents. This means that service descriptions usually contain many acronyms, references to technologies or libraries, which are in fact Named Entities.

Figure 5.

NER for Web Services.

There are currently two main approaches for identifying Named Entities, handcrafted or statistical models (i.e. machine learning (ML)). Handcrafted techniques achieve better results, but they need to be crafted by computational linguistics and take months to be created. ML statistical models, on the other side, achieve excellent results but require manually annotated datasets. ML statistical models can be categorised as generative and discriminative. Generative models try to describe how a label vector y can ‘generate’ a feature vector x. On the other hand, discriminative models will try to assign a label y to a feature x. For example, in the context of NER, a generative model will calculate which category (PERSON, ORGANISATION, LOCATION, OTHER) is more probably to ‘generate’ a given word. A discriminative model, on the other hand, will try to assign a category to a given word based on the features that characterise that word. More formally, a generative model will try to optimise $p (x, y)$ , while a discriminative model will optimise $p (y | x)$ . For the task of NER where proper names are mostly rare in datasets, it makes it difficult to learn categories given only the word identity. To label unseen words, it is easier to rely on other simpler features such as word capitalisation, neighbouring, prefixes and suffixes. Discriminative models are better suited to include new features, making them more suitable for the task of NER.

Statistical models can also be catalogued in classification or sequence models. Classification models predict only a single class variable given a set of features. On the other side, sequence models consider how the context affects the variable. For example, to identify Named Entities one approach could be to classify each word into any of PERSON, ORGANISATION, LOCATION and OTHER, where OTHER means that it is not a Named Entity. However, this approach does not consider how relationships between subsequent words affect the task. For example, ‘New York’ is a LOCATION, while ‘New York Times’ is an ORGANISATION. One way to solve this problem is to consider the sequence of words as a linear chain. This is the approach taken by sequence models such as hidden Markov models where the immediate predecessor and the current state are considered to identify a Named Entity. Currently, the best known implementation of NER is Stanford’s [16], which uses a discriminative sequential model known as conditional random field (CRF).

The benefits of expanding Named Entities are twofold. On one hand, it arguably improves service discoverability by adding keywords that are related to the document and cannot be discovered by analysing other words (e.g. synonyms). On the other hand, it helps establish a relationship between similar documents by adding common keywords.

As we mentioned earlier, expansion usually takes place after the document is tokenised. We considered operation names, parameter names and documentation sections to feed the tokeniser. Then, our approach takes the bag of words resulting from the tokenisation step, identifies Named Entities and expands them with descriptions. These descriptions are then appended to the original bag of words that represents the service. Finally, these enriched bags of words are saved into persistent memory so subsequent queries do not require service documents to be expanded again. Each time a new service is added to the registry, this task is executed again and the new bag of words is saved for later use.

To illustrate the rationale of our approach to improve discoverability, let us consider the two services in Figures 6 and 7, which provide an operation for obtaining currency information. Also, let us imagine that a user enters the following query upon searching for services: ‘currency information’. Clearly, we can infer that both Bitcoin and Dollar are currencies, and consequently both are relevant services. However, a traditional keyword-based search technique will not be able to discover this relationship in case the term ‘currency’ does not appear in any of the documents. Even with more advanced techniques such as identifying synonyms, this relationship will not be discovered.

Figure 6.

Bitcoin information service.

Figure 7.

Dollar information service.

In the example, ‘currency’ is a hypernym for ‘Bitcoin’ and ‘Dollar’, but current tools such as WordNet, although powerful and precise, lack abundance of vocabulary and relationships between words. Our approach will identify Bitcoin and Dollar as Named Entities and expand these entities with Wikidata information. Figures 8 and 9 show the before and after state of applying NER expansion to the two services. As we can observe, the extra information enables traditional keyword search to discover these documents as they now contain the term ‘currency’. However, this is not the only feature our approach provides to service discoverability. It also adds relevant terms such as ‘payment’ or ‘treasury’ which would have been difficult to derive from the service description or query’s terms. More specifically, the proposed approach can add words that would be difficult to derive from the original text using conventional grammar relationships such as synonyms, hypernyms or hyponyms. Our hypothesis is that this can greatly improve the performance of algorithms like LSA or clustering because it provides additional meaningful context.

Figure 8.

Example without NER expansion.

Figure 9.

Example with NER expansion.

One might think that our approach obscures the results due to excessive term addition. However, the extra information represents a low percentage of the total document’s content (less than 1% average for the experiments described next). In the next section, we will assess how our approach improves service discoverability by applying it on top of traditional syntactic-based Web Service discovery – described in section 3 – with a real Web Service dataset.

6. Experiments

Our approach focuses on expanding Web Service descriptions by including descriptions of Named Entities found in the text. We exploit NER to identify Named Entities as well as a knowledge database to expand their meaning. Our main experimental hypothesis, which is assessed in this section, is that this process improves discoverability in syntactic-based Web Services in terms of IR performance metrics.

First, we built a dataset containing 1274 Web Service descriptions from Mashape.com, an API portal that contains services published by developers all over the world. For this dataset, we created 29 queries and manually determined which services were relevant to each query. Both the relevant set of services and the queries were created by third-party people (students) who had used such queries in the past to serve different experiments or as a part of an undergraduate thesis. A service was considered relevant for a query only if it fulfilled the intended functionality, without taking into account the terms the description contained. For example, given two services offering functionality for reading PDF documents and writing PDF documents, it does not matter that both contain the term ‘PDF’: if a user searches for PDF writing services, only the latter will be considered as relevant. This query–service mapping was used to assess the improvement our approach provides when applied to the base techniques presented in section 3. Also, in order to identify Named Entities we used the Stanford NER [16], an implementation of a linear chain CRF model [42] which is a discriminative sequence model (section 4). It is important to denote that Named Entity expansion is performed in memory during the preprocessing step every time a new service is added. Then, TF-IDF is used to transform the service description into a 2-dimensional vector space where one dimension is the number of documents and the other dimension is the vocabulary. Later, the expanded description is no longer needed and discarded. This means that expansion only hurts performance if new words are added to the vocabulary, which will increase the dimension of the TF-IDF matrix. However, as word stemming is performed before TF-IDF computation, the chances of new words being added to the vocabulary are reduced.

As any ML model, CRF must be trained. In particular, we used Stanford’s 3-class model which was trained with MUC 6 and MUC 7 datasets.¹ Finally, we used four classic IR metrics, namely, Recall, Precision, F-Measure and NDCG, to assess the techniques and determine the improvement NER expansion provides to the different syntactic-based approaches considered.

Recall is a metric that measures the fraction of relevant documents that are retrieved by the registry. For example, if the dataset contains four service descriptions relevant for a given query and the retrieved list of descriptions only has one of them, Recall is 0.25. Formally, Recall is defined as

Recall = \frac{retreived Relevant Documents}{relevant Documents}

(1)

Precision measures the fraction of relevant elements in the retrieved list. For example, if the registry retrieved five descriptions for a given query, but only two of them are relevant to the query, Precision is 0.2. Formally

Precision = \frac{retreived Relevant Documents}{retrieved Documents}

(2)

The F-Measure metric combines the two previous metrics using the harmonic mean. F-Measure is defined as

F - Measure = 2 * \frac{Precision * Recall}{Precision + Recall}

(3)

Finally, DCG is a measure for ranking quality and measures the usefulness (gain) of an item based on its relevance and position in the provided list. The higher the DCG, the better the ranked list. Formally, DCG is defined as

DCG = re l_{1} + \sum_{i = 2}^{p} \frac{re l_{i}}{\log_{2} i}

(4)

where p is the size of the candidate list and $re l_{i}$ indicates if the candidate retrieved at the $i th$ position of the list was relevant. The DCG metric can be divided by the maximum value it can take, and then the values for each query can be averaged to obtain a measure of the average performance of a ranking algorithm, named NDCG.

To assess our approach, we implemented two variants based on the work described by Chen et al. [18] considering the original approach which performs WDR along with a sigmoid kernel function for similarity calculation (Kernel-WDR) and another version that just uses the sigmoid kernel (Kernel). Also, we implemented the approaches described in section 3. All the variants were implemented using Python, scikit-learn,² Gensim³ and Natural Language Toolkit (NLTK).⁴ We assessed these approaches using their original version (no expansion), a version using document expansion via NER, and another version using WordNet in queries and documents. In particular, WordNet expansion was performed by adding synonyms, which is commonplace, leaving aside hyponyms or hypernyms.

The reported results are the arithmetic means of the values obtained for each query. We have also used variants of these metrics known as Recall-at-X, Precision-at-X and F-Measure-at-X. The derived metrics are defined as above, but only the first X retrieved documents are considered in the calculations. This was done because in general users who search the Web are highly probably to consider only the first results and disregard the rest, which can be extrapolated to Web Service registries. Furthermore, the probability that a user considers a given result decreases drastically with the result position [18], being nearly zero after the tenth position. Therefore, we have considered Recall-at-1, Recall-at-10, F-Measure-at-1 and F-Measure-at-10.

Figures 10 –14 show the average Precision for each position using Bézier curves. As it can be observed, NER expansion achieves higher values of Precision in almost all cases, especially improving Precision in the first positions. The only case NER does not perform well at all is when considering WDR. The reason that NER expansion does not improve discovery in this scenario is due to the WDR which reverses the effects of applying NER. While NER expansion adds new words to the document to reduce term-mismatch, WDR tries to combine or merge these words to reduce the size of the vocabulary. Although we can observe that NER does not greatly improve Precision when not considering WDR, in Figure 14, it drastically improves Recall as it can be observed in Figure 15. In fact, NER expansion not only improves Precision but also Recall in almost all cases. Another interesting result is that when WordNet (corpus) is combined with WDR the result is equivalent as if we do not perform dimensionality reduction, achieving similar results of Precision than when no expansion is applied (Figure 14).

Figure 10.

Precision-at-X of LSA.

Figure 11.

Precision-at-X of VSM.

Figure 12.

Precision-at-X of KMeans.

Figure 13.

Precision-at-X of Kernel-WDR.

Figure 14.

Precision-at-X of Kernel no WDR.

Figure 15.

Recall-at-10.

More specifically, with exception of the Kernel or Kernel-WDR [18] variants, NER expansion improves Precision-at-1 between 10.34% and 17.24%, around 8% for Precision-at-2, and between 2.29% and 4.59% for Precision-at-3. Based on these results, a user has at least 27% more probability of finding relevant services in the first three positions. It is important to note that in all cases Precision-at-X decreases as the position increases. This is mainly because most queries have less than 10 relevant documents, and hence the probability of retrieving a relevant document in a higher position is substantially low. Nevertheless, exploiting NER improves Recall-at-10 between 7.41% and 15.06% with the exception of the Kernel-WDR approach.

On the other hand, WordNet (query) expansion performs better than NER when WDR is used. The main reason for this is that query expansion is not directly affected by WDR, unlike NER which performs document expansion. WordNet (corpus) also performs well because it is undoing the effects of WDR, achieving similar results than the Kernel approach. Also, Precision was greatly improved on KMeans when WordNet was applied to the query side (up to 5.17%), and slightly improved when applied to the document side in all cases (up to 2.49%). Query expansion does not add as many words as its document counterpart. Nevertheless, these extra words can help the Web Service registry to find the right cluster, explaining why it does perform better on KMeans. On the other hand, WordNet document-side expansion adds more words than NER or WordNet query-side expansion. This probably helps find related documents, but it might not lead to finding a specific document, because adding more words can lead to making different documents appearing more similar. This explains why document-side WordNet improves Precision in the last positions.

In addition, Figure 16 shows that NER expansion achieves good values of NDCG even when WDR is used. This is because while our approach returns at least one relevant document for most queries, the approach proposed by Chen et al. [18] fails at returning relevant documents on some queries. This drastically affects the NDCG score which is in fact 0 for those queries. Another interesting result is that WordNet (Document) holds the best result when WDR is used; as we mentioned before, this is because it reverses the WDR operation, achieving similar results than when WDR is not applied (Original).

Figure 16.

NDCG Kernel: WDR versus no WDR.

Finally, Table 1 depicts the results for Recall, F-Measure and NDCG. Results show that NER expansion improves not only Precision-at-X, but also Recall. As it can be observed, F-Measure shows a major improvement in the first position due to the fact that NER expansion achieves better Precision-at-X results in the first positions. Also, NDCG is increased by at least 12%. On the other hand, WordNet shows small improvements ranging from 2% to 5% for Recall and F-Measure when applied to queries.

Table 1.

Performed experiments: metrics (R = Recall, F1 = F-Measure)

	Metric	Original	NER	WordNet (Query-oriented)	WordNet (Document-oriented)
VSM	R@1	0.126	0.209	0.149	0.151
	R@10	0.519	0.603	0.501	0.495
	F1@1	0.203	0.317	0.232	0.231
	F1@10	0.306	0.323	0.309	0.308
	NDCG	0.668	0.795	0.795	0.636
LSA	R@1	0.126	0.243	0.142	0.086
	R@10	0.488	0.639	0.487	0.498
	F1@1	0.203	0.360	0.220	0.143
	F1@10	0.297	0.346	0.300	0.305
	NDCG	0.620	0.743	0.616	0.608
KMeans	R@1	0.128	0.232	0.186	0.117
	R@10	0.381	0.516	0.469	0.406
	F1@1	0.208	0.343	0.282	0.179
	F1@10	0.253	0.298	0.300	0.261
	NDCG	0.608	0.685	0.632	0.510
Kernel-WDR	R@1	0.066	0.055	0.082	0.138
	R@10	0.378	0.333	0.390	0.521
	F1@1	0.107	0.087	0.133	0.214
	F1@10	0.213	0.195	0.232	0.310
	NDCG	0.443	0.500	0.470	0.689
Kernel	R@1	0.126	0.151	0.149	0.151
	R@10	0.519	0.604	0.501	0.495
	F1@1	0.203	0.234	0.232	0.231
	F1@10	0.306	0.330	0.309	0.308
	NDCG	0.668	0.715	0.651	0.636

NER: Named Entity Recognition; VSM: vector space model; NDCG: normalised discounted cumulative gain; LSA: latent semantic analysis; WDR: WordNet Dimensionality Reduction.

The Bold values represent the best result achieved in that metric.

6.1. Performance

Although NER expansion provides performance improvement in terms of Precision and Recall when applied to traditional discovery techniques, it is important to assess how NER expansion affects execution time for both document indexing and querying process. The execution time was assessed in an Intel Core i5-4460, 16 GB of RAM and 128 GB solid-state drive (SSD). All experiments were performed inside a Docker⁵ container to avoid other processes interfering with the execution.

As we mentioned in section 5, NER is applied during the preprocessing and indexing step that occurs when a user publishes a new service. In this context, Table 2 depicts the mean, deviation and percentage deviation when applying NER versus not applying it over 100 indexing executions. Although NER expansion delays indexing time significantly, this only occurs when the engine is executed for the first time or as a maintenance task. Usually, when a user publishes a new service only one document is expanded, and thus the time incurred is significantly smaller. For example, considering the execution times from Table 2, expanding a single document with NER would take roughly 18.961 ms (total time/number of documents in the corpus). Also, we measured the time it takes for a user to discover a service using NER. We executed each of the 29 queries 1000 times and average the times for each approach. Table 3 depicts the results. As expected, we can observe that the query execution time is neglectable when applying NER during the discovery step, since the time-consuming process occurs during preprocessing.

Table 2.

Indexing execution time of the entire dataset (1274 documents) in seconds

	Mean	Deviation	Deviation %
NER expansion	24.157	0.251	1.041
No expansion	8.804	0.018	0.214

NER: Named Entity Recognition.

Table 3.

Average query execution times in milliseconds

	Mean	Mean (NER)	Deviation	Deviation (NER)	Deviation %	Deviation % (NER)
VSM	11.011	12.598	0.173	0.264	1.573	2.102
LSA	3.630	3.683	0.175	0.201	4.839	5.474
KMeans	7.829	8.412	0.190	0.236	2.432	2.815
Kernel-WDR	15.314	17.442	0.209	0.356	1.370	2.045
Kernel	16.879	19.393	0.266	0.277	1.578	1.433

NER: Named Entity Recognition; VSM: vector space model; LSA: latent semantic analysis; WDR: WordNet Dimensionality Reduction.

6.2. Threats to validity

There are two external validity threats. On one side, the implementation of the NER entity recogniser could affect the expansion mechanism. To mitigate this problem, we used the most popular implementation of NER [16] which is to date the one which holds the best results worldwide. Another concern is the size of the dataset, which includes 1274 Web Services. From a purely software engineering standpoint, this is not a large sample. However, to the best of our knowledge, this dataset is the largest pure REST Web Service repository that contains operation and parameter descriptions available on the Internet.

7. Conclusion

This article presented an approach for improving syntactic Web Service discoverability using NER-based document expansion. Our approach uses NER to identify Named Entities in service description documents that will be later expanded with information extracted from a knowledge database such as Wikidata. This information enriches a document’s content by adding relevant terms and thus mitigating term mismatch since synonyms and hypernyms are added. As a result, the metrics that quantify discovery performance show a considerable improvement in both traditional VSM-based approaches and probability-based approaches such as LSI. Last but not least, another contribution of this article is a 1274-REST service dataset gathered from the Mashape.com repository, which is available upon request.

Our research investigated how our NER expansion improved some of the classic Web Service discoverability techniques. We intend to study whether our approach also improves service discovery when applied in conjunction with approaches that also consider structural information such as service data types [44]. In addition, we are currently building new datasets and also analysing different knowledge databases such as Google Knowledge Graph or BabelNet, which also provide a graph of semantic-like connections which could allow us, for example, to establish relationships between different words that are not necessarily synonyms and thus improve entity expansion. Also, we intend to incorporate new techniques for finding keywords that could be relevant to a query. In this context, we are exploring Neural Network–based techniques, such as word2vec [43], to perform similarity calculation between words, which could also improve expansion by adding entities that have ‘hidden’ relationships with the original words. Another work involves improving our approach to consider functional aspects of Web Service descriptions such as parameter types or resource structure. For example, by analysing how different primitive and complex parameter types affect service’s Web Service interface compatibility at the consumer application. This work has been addressed for SOAP-based services in previous work [45] but it will be analysed for the case of REST-based services. Finally, non-functional aspects of Web Services will be taken into consideration as this topic has not been studied in depth for REST-based Web Services [1] so far, and hence the topic remains rather unexplored. In fact, as of 2015, only 17% of systems for building service mashups contemplated quality of service (QoS) aspects at several levels.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship and/or publication of this article.

Funding

The authors acknowledge the financial support by ANPCyT through the grant PICT-2013-0464.

Notes

ORCID iD

Ignacio Lizarralde

Alejandro Zunino

References

Garriga

Mateos

Flores

et al . RESTful service composition at a glance: a survey. J Network Comput Appl 2016; 60: 32–53.

Chinnici

Moreau

Ryman

et al . Web Services Description Language (WSDL) version 2.0 Part 1: core language. W3C Recomm 2007; 26: 19.

David

Mark

Drew

et al . Bringing semantics to web services with OWL-S. World Wide Web 2007; 10(3): 243–277.

Roman

Keller

Lausen

et al . Web service modeling ontology. Appl Ontol 2005; 1(1): 77–106.

WSDL term tokenization methods for IR-style web services discovery. Sci Comput Program 2012; 77(3): 355–374.

Rodriguez

Zunino

Mateos

et al . Improving REST service discovery with unsupervised learning techniques. In: Proceedings of the ninth international conference on complex, intelligent, and software intensive systems (CISIS), Blumenau, 8–10 July 2015, pp. 97–104. New York: IEEE.

John

Rajasree

. A framework for the description, discovery and composition of restful semantic web services. In: Proceedings of the second international conference on computational science, engineering and information technology, Coimbatore, India, 26–28 October 2012, pp. 88–93. New York: ACM.

Liu

et al . Towards automatic discovering for a real-world RESTful web service. In: Proceedings of the ninth web information systems and applications conference (WISA), Birmingham, AL, 16 November 2012, pp. 39–42. New York: IEEE.

Lathem

Gomadam

Sheth

AP.

SA-REST and (S)mashups: adding semantics to RESTful services. In: Proceedings of the international conference on semantic computing (ICSC 2007), Irvine, CA, 17–19 September 2007, pp. 469–476. New York: IEEE.

10.

Palma

Gonzalez-Huerta

Moha

et al . Are RESTful APIs well-designed? Detection of their linguistic (anti)patterns. In: Proceedings of the international conference on service-oriented computing, Malaga, 13–16 November 2015, pp. 171–187. Berlin: Springer.

11.

Rodriguez

Crasso

Zunino

et al . Improving web service descriptions for effective service discovery. Sci Comput Program 2010; 75(11): 1001–1021.

12.

Furnas

Landauer

Gomez

et al . The vocabulary problem in human-system communication. Commun ACM 1987; 30(11): 964–971.

13.

Carpineto

Romano

A survey of automatic query expansion in information retrieval. ACM Comput Surv 2012; 44(1): 1.

14.

Vechtomova

Karamuftuoglu

Query expansion with terms selected using lexical cohesion analysis of documents. Inform Process Manag 2007; 43(4): 849–865.

15.

Crasso

Zunino

Campo

Combining query-by-example and query expansion for simplifying web service discovery. Inform Syst Front 2011; 13(3): 407–428.

16.

Finkel

Grenager

Manning

Incorporating non-local information into information extraction systems by Gibbs sampling. In: Proceedings of the 43rd annual meeting on association for computational linguistics, Ann Arbor, MI, 25–30 June 2005, pp. 363–370. Stroudsburg, PA: Association for Computational Linguistics.

17.

Vrandečić

Krötzsch

Wikidata: a free collaborative knowledgebase. Commun ACM 2014; 57(10): 78–85.

18.

Chen

Yang

Wang

et al . WordNet-powered web services discovery using kernel-based similarity matching mechanism. In: Proceedings of the 2010 fifth IEEE international symposium on service oriented system engineering (SOSE), Nanjing, China, 4–5 June 2010, pp. 64–68. New York: IEEE.

19.

Martino

Cretella

Esposito

et al . An OWL ontology to support cloud portability and interoperability. Int J Web Grid Serv 2015; 11(3): 303–326.

20.

Paliwal

Adam

Bornhovd

Web service discovery: adding semantics through service request expansion and latent semantic indexing. In: Proceedings of the IEEE international conference on services computing, Salt Lake City, UT, 9–13 July 2007, pp. 106–113. New York: IEEE.

21.

Paliwal

Shafiq

Vaidya

et al . Semantics-based automated service discovery. IEEE T Serv Comput 2012; 5(2): 260–275.

22.

Adala

Tabbane

. A novel semantic approach for web service discovery using computational linguistics techniques. In: Proceedings of the international conference on communications and networking (ComNet), Hammamet, Tunisia, 19–22 March 2014, pp. 1–6. New York: IEEE.

23.

Tsai

et al . Web service discovery using lexical and semantic query expansion. In: Proceedings of the 2013 IEEE 10th international conference on e-business engineering, Coventry, 11–13 September 2013, pp. 423–428. New York: IEEE.

24.

Platzer

Dustdar

. A vector space search engine for web services. In: Proceedings of the third IEEE European conference on web services, Växjö, 14–16 November 2005, p. 9. New York: IEEE.

25.

Sajjanhar

Hou

Zhang

. Algorithm for web services matching. In: Xu

Lin

et al . (eds) Advanced web technologies and applications. New York: Springer, 2004, pp. 665–670.

26.

Elshater

Elgazzar

Martin

goDiscovery: web service discovery made efficient. In: Proceedings of the IEEE international conference on web services (ICWS), New York, 27 June–2 July 2015, pp. 711–716. New York: IEEE.

27.

Wang

Stroulia

. Flexible interface matching for web-service discovery. In: Proceedings of the fourth international conference on web information systems engineering, Rome, 12 December 2003, pp. 147–156. New York: IEEE.

28.

Sotolongo

Kobashikawa

Dong

et al . Algorithm for web service discovery based on information retrieval using WordNet and linear discriminant functions. JACIII 2008; 12(2): 182–189.

29.

Czyszczoń

Zgrzywa

. Latent semantic indexing for web service retrieval. In: Proceedings of the international conference on computational collective intelligence, Nicosia, Cyprus, 24–27 September 2014, pp. 694–702. Berlin: Springer.

30.

Dong

Halevy

Madhavan

et al . Similarity search for web services. In: Proceedings of the thirtieth international conference on very large data bases, vol. 30, Toronto, ON, Canada, 31 August–3 September 2004, pp. 372–383. New York: ACM.

31.

Zhang

Efficiently finding web services using a clustering semantic approach. In: Proceedings of the 2008 international workshop on context enabled source and service selection, integration and adaptation: organized with the 17th international World Wide Web conference (WWW 2008), Beijing, China, 22 April 2008, p. 5. New York: ACM.

32.

Hao

Zhang

. Web services discovery based on schema matching. In: Proceedings of the thirtieth Australasian conference on computer science, vol. 62, Ballarat, VIC, Australia, 30 January–02 February 2007, pp. 107–113. Darlinghurst, NSW, Australia: Australian Computer society, Inc.

33.

Whang

Ammann

Bolmarcich

et al . Office-by-Example: an integrated office system and database manager. ACM T Inform Syst 1987; 5(4): 393–427.

34.

Salton

Wong

Yang

CS.

A vector space model for automatic indexing. Commun ACM 1975; 18(11): 613–620.

35.

Marrero

Urbano

Sánchez-Cuadrado

et al . Named entity recognition: fallacies, challenges and opportunities. Comp Stand Inter 2013; 35(5): 482–489.

36.

Saha

Sarkar

Mitra

Feature selection techniques for maximum entropy based biomedical named entity recognition. J Biomed Inf 2009; 42(5): 905–911.

37.

Paul

Roy

Hussain

. Web service discovery based on IR models: a review. In: Proceedings of the international conference on communication and electronics systems (ICCES), Coimbatore, 21–22 October 2016, pp. 1–6. New York: IEEE.

38.

Kontostathis

Pottenger

WM.

A framework for understanding latent semantic indexing (LSI) performance. Inform Process Manage 2006; 42(1): 56–73.

39.

Omar

Lee

et al . LDA topics: representation and evaluation. J Inform Sci 2015; 41(5): 662–675.

40.

Xia

Fan

Tan

et al . Category-aware API clustering and distributed recommendation for automatic Mashup creation. IEEE T Serv Comput 2015; 8(5): 674–687.

41.

Chen

Zheng

Yin

Deng

WTCluster: Utilizing tags for web services clustering. In: InInternational Conference on Service-Oriented Computing, 5 December 2011, pp. 204–218. Berlin: Springer.

42.

Sutton

McCallum

An introduction to conditional random fields. Found Trends Mach Learn 2012; 4(4): 267–373.

43.

Goldberg

Levy

word2vec explained: deriving Mikolov et al.’s negative-sampling word-embedding method. Arxiv Preprint Arxiv:1402.3722, 2014, https://arxiv.org/abs/1402.3722

44.

Garriga

Flores

Mateos

et al . Service selection based on a practical interface assessment scheme. Int J Web Grid Serv 2013; 9(4): 369–393.

45.

Garriga

De Renzis

Lizarralde

et al . A structural-semantic web service selection approach to improve retrievability of web services. Inform Syst Front 2016; 1: 1–26.