The least-used key selection method for information retrieval in large-scale Cloud-based service repositories

Lu Liu, Jiayan Gu, Ashiq Anjum, Yan Wu, Lu Liu 0001, John Panneerselvam, Yao Lu, Bo Yuan

TL;DR

This paper introduces a novel "least-used key selection" method to improve the efficiency of retrieving services from large cloud-based repositories. By intelligently choosing service keys based on how frequently their parameters are requested, this method significantly speeds up service discovery, especially when parameter usage is uneven.

What Problem Does This Paper Address?

The proliferation of the Internet of Things (IoT) has led to an exponential increase in the number of services available in cloud-based repositories. Efficiently finding and managing these services is crucial. Existing service indexing models, like the multilevel index model, aim to improve service discovery and composition. However, these models often assume uniform probabilities for service parameter usage. In reality, some service parameters are much more popular than others, leading to performance bottlenecks. When popular parameters are used as keys, the search scope can become too broad, slowing down retrieval. This paper addresses this challenge by proposing a key selection method that accounts for the unequal probability of parameter usage in service retrieval requests.

Methods

The core of this paper is the least-used key selection method. This method is designed to work with the existing multilevel index model. The key idea is to select a service's "key" (a parameter used for indexing) based on the least frequent appearance of that parameter in user retrieval requests. The hypothesis is that if a service is frequently invoked, its corresponding key class should be smaller, and vice-versa.

The method is formalized by considering the retrieval probability of different key classes. By minimizing the total number of retrieved input-similar classes (represented by equation 2 in the paper), the method aims to reduce the search space. Algorithm 6 outlines the process: it iterates through a service's input parameters and selects the one with the lowest "appearing probability" in retrieval requests as the key. The paper also modifies this for scenarios where service input parameters have unequal probabilities, though it notes this has less impact on retrieval efficiency.

The authors compare their proposed method against five other key selection methods:

  • Original key selection method
  • Random key selection method
  • Minimum key count selection method
  • Maximum key count selection method
  • Designated key selection method

These methods are evaluated within primary, partial, and full multilevel index models.

Datasets

The paper does not mention specific real-world datasets used for training. Instead, it describes an experimental setup using a simulation platform developed in Microsoft Visual Studio using C#. They created artificial datasets for testing.

  • Services: 50,000 services.
  • Parameter Sets: Size of 1000.
  • Service Parameters: Each service has 10 input and 10 output parameters.
  • Retrieval Requests: Each request contains 32 parameters.
  • Dataset Size: 1000 retrieval requests per dataset.
  • Artificial Data Sets: 20 artificial data sets were used for testing.

The unequal probabilities of parameters were simulated using a Monte Carlo method with a specific probability density function.

Key Insights and Ideas

  • Unequal Parameter Probability is Key: The most significant insight is that the uneven distribution of parameter usage in service retrieval requests is a critical factor affecting retrieval efficiency, and existing methods largely ignore this.
  • "Least-Used" is "Most Efficient": Counter-intuitively, selecting the least frequently used parameter as a key for indexing leads to the most efficient service retrieval. This is because it helps to create smaller, more targeted key classes.
  • Service Retrieval vs. Addition: While the least-used key selection method excels at retrieval, the "designated key selection" method shows an advantage in service addition efficiency. This highlights a trade-off that might be important for different repository management strategies.
  • Index Model Matters, But Less Than Key Selection: The experiments show that while different multilevel index models (primary, partial, full) have some impact, the choice of key selection method has a more pronounced effect on retrieval efficiency, especially under unequal parameter distributions.

Key Results

The experimental results demonstrate the superiority of the proposed "least-used key selection" method, particularly under conditions of unequal parameter probabilities in service retrieval requests.

  • Service Retrieval Efficiency:
    • In primary, partial, and full index models, the least-used key selection method significantly reduced retrieval time when parameters in service retrieval requests had unequal probabilities.
  • It improved retrieval efficiency by over 450% compared to the designated key selection method in these conditions.
  • The average retrieval time for the least-used key method was as low as 72.7ms (on primary index models with unequal request parameters).
  • Service Addition Efficiency:
    • Both the designated key selection method and the least-used key selection method showed significant superiority in service addition over other methods in partial and full index models.
  • The designated key selection method showed around 100% improvement in service addition efficiency compared to the least-used key method in these scenarios.
  • Equal Probabilities: Under equal parameter appearing probabilities, the performance differences between the six key selection methods were not significant, validating previous research.

Limitations and Future Work

  • Known Distributions: The current experiments assume that the distributions of service parameters are known. In real-world scenarios, these distributions can change over time.
  • Adaptive Key Selection: The authors propose studying an adaptive key selection method in future work, which would adjust keys dynamically as parameter distributions change.
  • Complex and Dynamic Conditions: They plan to evaluate and improve the performance of the least-used key selection method under more complex and dynamic conditions.
  • Optimizing Service Addition Time: Further optimization of service addition time is also a future research direction.

Summary updated

Abstract

As the number of devices connected to the Internet of Things (IoT) increases significantly, it leads to an exponential growth in the number of services that need to be processed and stored in the large-scale Cloud-based service repositories. An efficient service indexing model is critical for service retrieval and management of large-scale Cloud-based service repositories. The multilevel index model is the state-of-art service indexing model in recent years to improve service discovery and combination. This paper aims to optimize the model to consider the impact of unequal appearing probability of service retrieval request parameters and service input parameters on service retrieval and service addition operations. The least-used key selection method has been proposed to narrow the search scope of service retrieval and reduce its time. The experimental results show that the proposed least-used key selection method improves the service retrieval efficiency significantly compared with the designated key selection method in the case of the unequal appearing probability of parameters in service retrieval requests under three indexing models.
BibTeX
@article{liu2022least,
  author = {Lu Liu and Jiayan Gu and Ashiq Anjum and Yan Wu and Lu Liu and John Panneerselvam and Yao Lu and Bo Yuan},
  title = {{The least-used key selection method for information retrieval in large-scale Cloud-based service repositories}},
  journal = {J. Cloud Comput},
  year = {2022},
  doi = {10.1186/s13677-022-00297-3},
}
Figure