H.C. Vazquez et al

Santiago Vidal, ISISTAN-CONICET.

# Retrieving and Ranking Relevant JavaScript Technologies from Web
Repositories

Hernan C. Vazquez  J. Andres Diaz Pace  Claudia Marcos  Santiago Vidal
ISISTAN-CONICET, Tandil, Buenos Aires, Argentina  ISISTAN-CIC, Tandil, Buenos
Aires, Argentina<EMAIL_ADDRESS>H. Vazquez  J.A. Diaz Pace  C.
Marcos  S. Vidal

(26 April 2016; 6 June 2016; 6 June 2016)

###### Abstract

[Summary]The selection of software technologies is an important but complex
task. We consider developers of JavaScript (JS) applications, for whom the
assessment of JS libraries has become difficult and time-consuming due to the
growing number of technology options available. A common strategy is to browse
software repositories via search engines (e.g., NPM, or Google), although it
brings some problems. First, given a technology need, the engines might return
a long list of results, which often causes information overload issues.
Second, the results should be ranked according to criteria of interest for the
developer. However, deciding how to weight these criteria to make a decision
is not straightforward. In this work, we propose a two-phase approach for
assisting developers to retrieve and rank JS technologies in a semi-automated
fashion. The first-phase (ST-Retrieval) uses a meta-search technique for
collecting JS technologies that meet the developer’s needs. The second-phase
(called ST-Rank), relies on a machine learning technique to infer, based on
criteria used by other projects in the Web, a ranking of the output of ST-
Retrieval. We evaluated our approach with NPM and obtained satisfactory
results in terms of the accuracy of the technologies retrieved and the order
in which they were ranked.

, , , and (2020), An Automated Machine Learning Approach for Retrieving and
Ranking Relevant JavaScript Technologies from Web Repositories, Software
Evolution and Process, 2017;00:1–6.

###### keywords:

JavaScript, Information overloading, Web repositories

††articletype: Article

##  1 Introduction

Software technologies are an essential part of current software development
practices. The use of software technologies, such as libraries and frameworks,
can greatly improve developers’ productivity. Nonetheless, an inappropriate
technology selection can negatively affect the software product being built,
and also the business goals of the organization 1. In this context, the task
of selecting a software technology that fulfills the specific needs of a
development task is generally a complex and time-consuming decision-making
process. One of the reasons for this complexity is the availability of a large
number of software technologies in the market, in response to the growing
demand from software companies. Keeping up-to-date with technological
developments is challenging for developers.

In particular, this situation is very common in JavaScript (JS) development,
as developers have to regularly search, evaluate and compare candidate JS
libraries/frameworks for their applications. This process can be perceived by
developers as a “technological
fatigue"111https://medium.com/@ericclemmons/javascript-fatigue-48d4011b6fc4.
This phenomenon is due to the extensive number of JS technologies available in
Web repositories, such as NPM222https://www.npmjs.com/ (Node Package Manager),
which promote reuse by lowering production costs and speeding up software
delivery 2.

We argue that one of the reasons for JS technological fatigue is the lack of
precision in the search engines for JS repositories. As a consequence,
developers often resort to general-purpose search engines (e.g., Google or
Bing) with the hope of having better results. However, the downside of such
engines is that they tend to return long lists of documents, and then
developers have to navigate within each result to find possible JS
technologies. This leads to information overload issues. Furthermore, once the
developer identifies a set of candidate technologies for her application, she
must analyzed each technology to decide which one better fits her needs.
Normally, this decision is driven by features of the technology, such as:
popularity in the community, or number of downloads, among others. Assigning
weights to these features for comparison purposes is not straightforward. For
instance, NPM uses the AHP (Analytic Hierarchy Process) 3 technique to support
comparisons of JS technologies.

The problem of information overload has been studied in various disciplines 4,
and Web search engines are one of the main tools to face the problem 5. The
usage of search engines for Web-based software repositories has received some
attention in the literature, but there are still challenges for finding
technologies being relevant to a particular development (or technological)
need 6. Previous works on software technology selection have addressed the
problem from different perspectives 7891011. Nonetheless, most works focus on
the evaluation of candidate technologies based on specific characteristics,
departing from a given group of technologies, and they leave aside the problem
of searching for relevant candidates. In addition, the characteristics for
decision making are often manually assessed by developers.

In this article, we propose an approach to assist developers in searching and
ranking JS technologies. The approach works in two phases called _ST-
Retrieval_ and _ST-Rank_. Given a developer’s query expressing a JS
technological need, _ST-Retrieval_ applies a meta-search strategy 12, which
combines the search results of both a JS-specific engine and general-purpose
engines. Based on the technologies recovered by _ST-Retrieval_ , _ST-Rank_
generates a ranking of those technologies for the developer by means of a
pair-wise learning to rank method. The ranking is based on an (automated)
analysis of technology features extracted from JS projects on the Web (e.g.,
number of stars in the repository, number of releases in the last year, number
of contributors, etc.). To assess the relevance of the projects, we employ a
popularity metric called CDSel. CDSel measures the relationship between the
number of projects in which the technology was selected and how popular are
those projects.

We have evaluated the approach on the NPM repository for JS, using a
predefined set of queries and 1000 popular projects from GitHub. For _ST-
Retrieval_ , our experiments reported an average precision improvement of 20%,
and we were able to recover a larger number of relevant JS technologies than
using the default search engine provided by NPM. Regarding _ST-Rank_ , we
observed improvements of at least 20% on average when compared to the default
ranking strategy followed by NPM. Based on these initial results, our approach
makes two contributions: (i) it can boost the performance of the NPM search
system by leveraging on results provided by multiple search engines, and (ii)
it helps developers by ranking first those technologies being widely used in
the JS community.

The rest of the article is structured as follows. In Section 2, we provide a
brief description of the software technology selection problem, along with a
motivational scenario in JS development. In Section 3, we describe the two
phases of the approach in detail. Section 4 presents the evaluation of _ST-
Retrieval_ and _ST-Rank_ , and discusses their pros and cons. Section 5 covers
related work. Finally, Section 6 gives the conclusions and outlines future
lines of work.

##  2 Software Technology Selection

From a development perspective, the selection of software technologies has an
influential role in both the development process and the quality of the final
product 13. The successful application of a given technology (e.g., a JS
package) means that its usage for a particular task produces a desired
objective 7. This success also depends on contextual features (e.g., alignment
between the developer’s requirement and the chosen package, maintenance of the
package, type of license, or package usability, among others).

As a motivational example of the technology selection problem for JS
development, let us consider a JS developer that needs to extract a barcode
from an image, with the goal of automating a process for extracting codes from
a series of image files. The application context for this functionality is a
Web browser. Initially, she goes to the NPM package repository and submits the
query “extract barcode from image” to its search engine, which returns only
the package _bytescout_ 333https://bytescout.com/ as output. Bytescout is a JS
client for a cloud service of the same name. When reading about Bytescout, our
developer finds out that it is a paid service and that the JS client is not
open-source. Also, when she looks at the package description, NPM reports that
Bytescout has been downloaded 40 times in the last month, which for a JS
package might indicate that it is not very popular in the community. Let us
assume that our developer is not convinced with these features, or they are
not aligned with the standards of her project. However, bytescout is the only
technology returned by NPM. In this context, our developer has several
options, namely: (i) adopt the package despite her disagreement with its
features, (ii) implement a solution from scratch to read the barcodes, (iii)
try a modified query with the hope of getting more results from NPM, or (iv)
use alternative information sources (e.g. Google, or NPMSearch, among other
engines) to find alternative technologies. Let us suppose here that she goes
for the third option and re-phrases the query as “barcode reader", which makes
NPM return now 16 results. After inspecting each result, our developer is
still unconvinced of using any of the technologies, since they do not seem to
be very popular nor receive enough maintenance. The scenario so far shows the
current limitations of JS-specific search engines, like NPM.

Next, let us assume that our developer decides to go for the fourth option,
and she submits the query “extract barcode from image javascript package" to
Google (the last phrase intend to prevent Google form returning results for
libraries in other languages). This query returns a list of Web pages, and our
developer then inspects each page in order to check whether some JS
technologies are mentioned. In doing so, she realizes that a technology called
_QuaggaJS_ 444https://serratus.github.io/quaggaJS/ is referenced in 3 results
from the top-10 pages of the list. As she is not aware of this technology, she
goes back to the NPM repository and finds that QuaggaJS is more popular than
bytescout, it is open-source, and is well-maintained by the community. At this
point, our developer can pick QuaggaJS for her development need, or keep
looking for other technologies. This scenario illustrates the challenge of
using general-purpose search engines for JS, but also the issues related to
the comparison of technologies.

The bottom line of the example has two implications. First, the search and
comparison of JS technologies should take advantage of different information
sources. Second, the developer’s manual analysis of technologies (e.g., by
looking at Web sites) should be minimized, in the sense that semi-automated
rankings could be created from criteria or feedback provided by other
projects. Based on these ideas, we developed the _ST-Retrieval_ and _ST-Rank_
components of our approach.

##  3 Approach

Figure 1: Overview of the two-phase approach.

For retrieving and ranking relevant JS technologies, we propose two-phase
approach as shown in Figure 1. The first phase, called _ST-Retrieval_ , takes
a query given by the JS developer and returns a list of candidate technologies
matching the query. The query is written in natural language and specifies a
technological requirement (e.g. “extract barcode from image"). The goal of
this phase is to leverage on various search engines. Afterwards, the second
phase, called _ST-Rank_ , is fed with the outputs of _ST-Retrieval_ along with
an application context555Since some technologies only work in a specific
context, our approach needs to be informed of the application context in which
the developer is going to apply the technology (i.e. Web browser, Node.js,
etc.) provided by the developer, and generates a ranking of JS technologies
based on their relevance. The goal of this phase is to infer a ranking by
“learning" from technology features and decisions made in other projects. To
do so, a machine learning (ML) model is built. Each phase internally involves
different steps. Gray boxes in the figure correspond to steps or artifacts
provided at setup, while white boxes refer to steps performed every time a new
query is entered by the developer.

###  3.1 ST-Retrieval

We model the search and retrieval of JS technologies as a meta-search problem
12. In meta-search, the original query is sent in parallel to a set of search
engines, each one returning an ordered list of items that satisfy the query.
The meta-search system combines all the lists into a new one that is expected
to keep the “best" items of the individual lists.

The meta-search strategy for _ST-Retrieval_ works in three steps (Figure 1),
as follows. First, the input query is sent to both domain-specific engines
(e.g. NPM) and general-purpose engines (e.g., Google, Bing). The domain-
specific engines directly return a list of JS technologies. However, the
general-purpose engines produce a list of Web pages, which might include names
of JS technologies. Second, these Web pages are processed in order to extract
a list of JS technologies. Third, the lists from each search engine are merged
into one single list, which is passed on to the second phase.

The technical aspects of each step are explained below.

####  3.1.1 Process query

In this step, we aim at leveraging on the capabilities of existing search
engines. Specifically, we use four engines, namely: NPM,
NPMSearch666https://npmsearch.com, Google, and Bing777https://www.bing.com. In
general, the possible engines envisioned in our approach fall into two types:
(i) _domain-specific (DS)_ , and (ii) _general-purpose (GP)_. The former are
especially designed for the search of JS technologies (NPM and NPMSearch),
while the latter are often used for general queries (Google and Bing).

Both types of engines allow developers to enter queries in natural language.
Developers’ queries can express functional or non-functional requirements that
should be met by a JS technology. Stop-words (e.g., articles, pronouns,
prepositions, etc.) that do not provide information to the search engine are
removed from the query. For _GP_ engines, it also augment the query to avoid
results from other domains (e.g., technologies in a language incompatible with
the project). Since we are retrieving JS technologies, the query is expanded
with the suffix "javascript package". Once the query was expanded, it is ready
for execution in the corresponding engine. The result of this execution is a
set of Web pages (or documents) in HTML, XML or JSON format.

####  3.1.2 Extract technologies

This step is concerned with obtaining the technologies named in the documents
being returned by a query. Technologies are represented as a tuple
$<name,\,repository_{-}url,\,home_{-}url,\,description>$ where:

  * •

_name_ : corresponds to the name of the technology in the repository (e.g.,
“quagga”).

  * •

_repository_url_ : is the technology URL on the repository site (e.g.,
“https://www.npmjs.com/package/quagga”).

  * •

_home_url_ : is the URL of the technology site (e.g.,
“https://serratus.github.io/quaggaJS/”).

  * •

_description_ : is the description of the technology (e.g., “An advanced
barcode-scanner written in JavaScript”).

On one hand, for _DS_ engines, each result will map one-to-one with existing
technologies in the repository via its _name_ and _repository_url_. On the
other hand, for _GP_ engines, the search results are Web documents, which
might refer to zero, one or many technologies. For this reason, those names of
the technologies should be recovered. This information extraction task can be
seen as a Named Entity Recognition (NER) problem. NER 14 aims at classifying
entities found in a given text into predefined categories (e.g., people,
organizations, places, time expressions, among others). In our work, the named
entity category is "software technology", and we employ a rule-based strategy
for string-matching 15. By means of these rules, all the technologies whose
name or address (_home_url_ , _repository_url_) match the category are
extracted.

This step requires a repository of JS technologies as input (Figure 1), which
includes the information of the tuples. We generated this repository in
advance via a process of Web crawling on the NPM site888In order to complement
the information found in NPM, we only selected technologies whose repositories
were publicly available in GitHub. Figure 2 shows an example of results and
technologies obtained from the NPM and Google engines, along with their
mappings for the query “extract barcode from image". In the example, NPM
returned a single result (bytescout) matching the name of a technology in the
repository. Unlike NPM, Google returned an HTML document, whose text was
parsed for matches of names or addresses of technologies. In particular, the
technology name in the resulting page (QuaggaJS) did not match the technology
name in the repository (quagga) but the address of the site did match
(_home_url_ , https://serratus.github.io/quaggaJS/).

Figure 2: Matching search results with technologies for different engines.

####  3.1.3 Merge technology results

Based on the set of named technologies, this step creates an ordered list of
technologies per search engine. For _DS_ engines, the sorting function is
straightforward, and each technology is assigned to the position of the result
where it is named999this is because each result corresponds unequivocally with
a technology. For _GP_ engines, a result can be related to many named
technologies. In this case, the sorting function is based on the order in
which the technologies were named. If two technologies are named within the
same result, the first one named will appear in the list before than the one
named afterwards. For example, if the first result contains the text "You can
use Quagga or Barcode-Reader" and the next result contains the text "You
should use Bytescout", then the candidates will be ordered as 1) Quagga, 2)
Barcode- Reader, and 3) Bytescout.

After all search engines produced their individual lists, they are merged into
a single list. In meta-search, this process is known as a ranking aggregation
function 16. Aggregation functions can be classified into two main types 17:
(i) those that use similarity scores returned by the search engine, and (ii)
those that use ranking positions. When engines do not expose their similarity
scores for their results, as in the cases of Google or Bing, ranking positions
can be used instead. For this reason, we decided to use _Borda Fuse_ in our
approach. Borda Fuse is a positional aggregation function that is
computationally simple to implement 16, and it performs well in the context of
Web searching 12.

In the Borda Fuse method, each search engine is considered as a voter. Each
voter presents a list of _n_ ordered candidates (i.e., technologies). For each
list, the best first candidate receives _n_ points, the second candidate
receives _n-1_ points, and so on. Then, the points awarded by the different
voters are added and the candidates are ranked in descending order according
to the total of points obtained. Table 1 shows an aggregation example using
the _Borda Fuse_ method. Each list gives a maximum of 4 points (equal to the
maximum length of individual lists) and decreases by one to each position of
the list, i.e. the second position gives 3 points, the third position gives 2
points, and the last position gives 1 point. The scores are added and a final
list from highest to lowest scores is created. In our example, the most
relevant results, quagga and bytescout, are in the top-ranked positions of the
final list.

Table 1: Borda Fuse aggregation example ([points] name).  NPM | Google | Bing | Candidate list
---|---|---|---
[4] bytescout | [4] quagga | [4] quagga | [8] quagga
| [3] bcreader | [3] bc-js | [6] bytescout
| [2] bytescout | [2] _bwip-js_ | [4] bcreader
| [1] _jaguar_ | [1] bcreader | [3] bc-js
|  |  | [2] _bwip-js_
|  |  | [1] _jaguar_

###  3.2 ST-Rank

_ST-Retrieval_ outputs a set of candidate technologies for the developer’s
query. Since these technologies have the same goals, the developer has to
scrutinize them to find the technology that best fulfills her needs. This
analysis often involves indicators provided by the repository (e.g., the
number of downloads, dependent projects, or contributors, among others) and
also searching for developers’ opinions in blogs and forums. In this context,
_ST-Rank_ assists developers to select the “best" technology by creating a
ranking based on the choices made by other developers. The assistance consists
of four steps (Figure 1), as follows. First, information about popular
technologies used by other developers in open-source repositories is
collected. Second, a dataset is created by taking into account the previous
information and the application context of each technology (e.g., Web browser,
Node.js, etc.). A training dataset is derived from the dataset, and we apply a
supervised machine learning algorithm to build a ranking model for JS
technologies. These three steps happen during the setup of the approach. At
last, the machine learning model predicts a ranking for the technologies given
by _ST-Retrieval_ , according to the “patterns" inferred from the training
dataset.

The technical aspects of each step are explained below.

(a) Collect data

(b) Build dataset

Figure 3: Example of derivation of a training dataset.

####  3.2.1 Collect data

The input of this step is a group of popular open-source JS projects. We are
interested in the dependencies of every project and their features. In NPM,
these dependencies are in the _package.json_ of each project101010Since both
the “reference projects” and their dependencies are JS projects themselves,
for the sake of clarity we refer to the former as “projects” and to the latter
as “technologies”.

The processing of each dependency involves three tasks. The first task is to
look for alternatives to the technologies identified. For example, project
_Chart.js_ 111111https://www.npmjs.com/package/chart.js depends on _moment_
121212https://www.npmjs.com/package/moment, which is a library to manipulate
dates (Figure 3). Thus, alternative technologies solving the same need are
sought, such as _date-fns_ 131313https://www.npmjs.com/package/date-fns and
_momentjs_ 141414https://www.npmjs.com/package/momentjs. We implemented this
search by automatically scraping the website of
NPMCompare151515https://npmcompare.com. For a given technology, the website
gives a list of related packages.

The second task is to assess the “popularity" of the dependency (or JS
technology). To do so, we propose a metric called _CDSel (Community Degree of
Selection)_ for a technology. CDSel is intended to capture the relationship
between the number of projects in which the technology was selected and the
relevance of those projects. Let $n$ be the number of reference projects,
$rel(P_{i})$ the relevance of project $i$, and $s=1$ when the technology was
selected in $P_{i}$ (0 otherwise), then CDSel is computed as follows:

$CDSel=\sum_{i=1}^{n}s*\frac{rel(P_{i})}{log_{2}(i+1)}$

The logarithm serves as an attenuating factor in the ranking, so as to produce
a controlled reduction in the values of the metric. For example, in our
dataset we obtained a CDSel value of 396.192 for _moment_ , 15.646 for _date-
fns_ , and 1.791 for _momentjs_ , which means that _moment_ is most often
selected by relevant repositories than _date-fns_ and _momentjs_ (Figure 3).
Regarding $rel(P_{i})$, it is computed as follows:

$rel(P)_{i}=z-(rankPosition(P_{i}))$

where $z$ is the length of the ranking and $rankPosition(P_{i})$ is the
position in the ranking of project $(P_{i})$. The ranking is based on the
stars of each project in GitHub.

The third task is to access to the NPM and GitHub repositories for retrieving
features that characterize each technology. We focus on features that can be
used as criteria for decision making, such as: number of developers that
maintain the technology, #daily downloads, or #dependencies, among others.
More than 40 features are taken into account161616The full list of features
can be found in the Supplementary Material zip file at
https://bit.ly/2w9sOzV.. It should be noticed that all the technologies are
represented with the same set of features. It is up to the machine learning
algorithm to decide which features are relevant. Our rationale is that, if a
technology $T$ was chosen in a project (over other available options), then
there should be a criterion over some technology features, upon which $T$ was
considered more relevant than the other options. Thus, being able to learn the
selection criteria depends on the features collected from the technologies.

####  3.2.2 Create dataset

This step assembles the dataset to be used for building the machine learning
(ranking) model. We refer to this dataset as the _training dataset_ (Figure
1), and it contains a set of _training instances_. A given training instance
captures a pair of technologies.

Initially, a _training ranking_ is computed for each technology according to
its CDSel value. In our example, _moment_ will be ranked first since its CDSel
value is higher than the CDSel value of _date-fns_ and _momentjs_. Then, each
technology is represented as a feature vector $[FT_{i1},FT_{i2},...,FT_{in}]$
where $FT$ is a particular feature and $n$ is the total number of features.
Each vector is normalized via feature scaling 18, so that its values are
between $0$ and $1$. For example, in Figure 3 vector (1, 10, 5) for _moment_
becomes (1, 0.77, 1) after normalization.

At last, a set of _training instances_ is created. Specifically, for each
possible pair of technologies in a _training ranking_ , a vector is created by
concatenation of their normalized feature vectors. A label of $1$ is added to
this vector when the first technology is more relevant than the second one, or
$0$ otherwise. In our example, the pair _(moment,date-fns)_ is labeled to $1$
because _moment_ is ranked before _date-fns_.

####  3.2.3 Build ML model

This step applies a “learning-to-rank" 19 technique on the training instances
of the dataset. A pairwise supervised variant is used, since the order of two
given technologies is not affected by other technologies in the list. For
example, _moment_ is more relevant than _date-fns_ regardless of other
alternative technologies. Among the various learning-to-rank algorithms
reported in the literature 20, we chose GBRank 21 due to its effectiveness in
Web search ranking 22, 23, 24. GBRank is based on a gradient boosting method
for minimizing wrong preference predictions.

####  3.2.4 Rank technologies

Given two technologies, the ML model (above) is able to predict an order for
them according to their relevance. Finally, this step takes all possible pairs
of technologies (from the _Merge technology results step_) and runs them
through the ML model, in order to generate a ranking. The pairs are filtered
according to the application context defined by the JS developer. Those
technologies being most relevant (i.e., popular) should be ranked first by the
ML model.

##  4 Evaluation

We performed an empirical evaluation of the _ST-Retrieval_ and _ST-Rank_
components using datasets sampled from JS projects. The following research
questions were addressed:

  * •

RQ#1: How does the performance of _ST-Retrieval_ compare to that of existing
search engines?

  * •

RQ#2: What is the quality of the rankings proposed by _ST-Rank_ with respect
to the rankings from NPM and NPMCompare?

The experiments to answer RQ#1 and RQ#2 are reported in sub-sections 4.1 and
4.2 respectively.

###  4.1 Evaluation of ST-Retrieval

The main goal is to determine whether the performance of _ST-Retrieval_ for
retrieving a set of JS technologies is better than the performance of _DS_ and
_GP_ search engines.

Table 2: Reference Queries.  Queries
---
check valid email address
download web videos
send sms
quick sort algorithm
filter adult content images
user authentication
extract barcode from image
convert data formats
download free music
convert typewritten image to text
sentiment analysis
third party authentication
convert text to speech
calculate word similarity
translate english to spanish
credit card validation
health tracker
captcha authentication
detect text language
rank aggregation algorithms
mobile app framework
DOM manipulation utils
lightweight 3D graphic library
mathematical functions
scraper

####  4.1.1 Experimental Design and Operation

We used NPM as the basis for the evaluation, as NPM is the de-facto package
repository for JS technologies. First, we downloaded the technology registry
from the NPM repository. With this information, we built the repository of
technologies (Figure 1) to a given date (08/28/17), as described in sub-
section 3.1.2. Then, we asked two senior JS developers to record any search
(i.e., queries) for technologies in NPM that they would make, during 2 weeks,
in their normal projects. After filtering some of their search results (in
order to remove very similar queries), we obtained a _reference set_ of 25
queries (Table 2) representing a variety of technological needs. We ran _ST-
Retrieval_ 25 times on this set (once for each query) and stored the lists of
outputted technologies. The length of the queries was selected as a normal
distribution over the most usual length 25. The search engines were: NPM,
NPMSearch, Google, and Bing. We also ran a retrieval effectiveness test for
search engines 26.

During the _Process query_ step, we only took into account the first 20
documents from the list of results. This was because users searching the Web
(e.g., using Google) are very likely to consider only the first results 27.
These documents were recorded in order each time we ran the step. As part of
the _Extract technologies_ step, we stored all the technologies identified. At
the end, we retrieved a total of 2760 JS technologies (in general, multiple
technologies were extracted from the documents returned by _Google_ and
_Bing_). Then, in order to establish a _baseline_ , we asked 12 JS senior
developers (different from the ones that produced the reference set of
queries) to assess the technology results. Each developer was given all the
technologies for a query in random order, and was asked to judge the
technology relevance using a binary scale (yes/no). The developers did not
know which search engine produced a particular result, and duplicate results
(i.e. results returned by more than one engine) were presented to them only
once. In particular, 11 developers analyzed the results of 2 queries and 1
developer analyzed the results of 3 queries. On average, each JS developer
analyzed 230 technologies.

####  4.1.2 Metrics

Information Retrieval metrics were used for gauging performance28, such as:
precision, recall, MAP (Mean Average Precision) and DCG (Discounted Cumulative
Gain). We leveraged on the reference set of queries and the technology
baseline described previously.

In our domain, _precision_ is the ratio between the number of relevant
technologies recovered and the total number of technologies recovered. The
closer the precision value is to $1$, the greater the number of relevant
technologies recovered with _ST-Retrieval_._Recall_ is the ratio between the
number of relevant technologies recovered and the total relevant technologies
known. A recall of $1$ indicates that all relevant technologies have been
recovered. In addition, _MAP_ 29 measures, for a set of queries, the average
precision for each query. MAP values close to $1$ mean that the relevant
technologies are within the top-ranked positions. At last, _DCG_ 30 measures
the quality of rankings, in terms of the utility (gain) of a result based on
its relevance and position in the ranking. DCG can be divided by the maximum
value taken from among all the queries, and then, the values for each query
can be averaged to measure the average quality of the rankings. This variant
of DCG is called _Normalized DCG_(_nDCG_).

####  4.1.3 Analysis of Results

_Recall_ and _Precision_ were calculated in different positions of the ranking
in order to establish the value of the metric in that position. In addition,
the reported results are the arithmetic mean of the values for each query.

Figure 4: Hits, Precision, and Recall at K position (_ST-Retrieval_).

Figure 4 shows the results for the four search engines and the Borda Fuse
function considering each position ($k$) of the ranking (k = 1, first
position). The first chart shows the average number of hits (_Hits_). A result
is said to be a hit if it is relevant to the query. The other charts show the
results for _Precision_ , and _Recall_. As it can be observed, _ST-Retrieval_
presents high values in all positions for all the metrics. _Google_ and _NPM_
behave similarly to _ST-Retrieval_ until around the third position. From that
position on, _ST-Retrieval_ exhibits a considerable improvement. We argue that
this improvement is due to the aggregation of results, and also to the ability
of _Borda Fuse_ to find the global relevance of a result based on its position
in the results relative to the different search engines. The maximum precision
obtained by _ST-Retrieval_ was 0.72 (8% increase when compared to the search
engines) and the maximum recall was of 0.77 (34% more than the search
engines). This difference in performance is also observed in the nDCG and MAP
metrics for ranking quality metrics.

Table 3: Metrics for search engines (_ST-Retrieval_). Method/Metric | H@1 | H@5 | H@10 | H@20 | P@5 | P@10 | P@20 | nD(r=5) | nD(r=10) | nD(r=20) | M(r=5) | M(r=10) | M(r=20)
---|---|---|---|---|---|---|---|---|---|---|---|---|---
NPM | 0.600 | 2.680 | 4.760 | 7.680 | 0.536 | 0.476 | 0.384 | 0.635 | 0.639 | 0.660 | 0.632 | 0.620 | 0.615
NPMSearch | 0.320 | 1.240 | 2.480 | 4.280 | 0.248 | 0.248 | 0.214 | 0.322 | 0.333 | 0.361 | 0.348 | 0.336 | 0.325
Google | 0.640 | 2.480 | 3.480 | 4.040 | 0.496 | 0.348 | 0.202 | 0.720 | 0.736 | 0.750 | 0.712 | 0.704 | 0.695
Bing | 0.560 | 1.920 | 2.280 | 2.320 | 0.384 | 0.228 | 0.116 | 0.662 | 0.675 | 0.677 | 0.638 | 0.639 | 0.639
BordaFuse | 0.720 | 3.240 | 5.480 | 9.400 | 0.648 | 0.548 | 0.470 | 0.775 | 0.770 | 0.831 | 0.805 | 0.776 | 0.749

Table 3 shows the values for _nDCG_ (nD) and _MAP_ (M) for ranking sizes of 5,
10, and 20. Table 3 also shows the values of _Hits_ (H) and _Precision_ (P) in
positions 5, 10, and 20, respectively. Interestingly, _Borda Fuse_ shows the
best performance along all positions. In the case of the search engines, _NPM_
obtained the best results. For this reason, we compared _Borda Fuse_ against
_NPM_. For instance, _NPM_ is outperformed by the _BordaFuse_ technique in
19.06% (in average) for all positions in _Hits_. This means that around
position 5 _Borda Fuse_ is able to return one more relevant technology than
_NPM_. Thus, the precision of _NPM_ is outperformed by _Borda Fuse_ by 19.06%
(in average) over all positions.

Regarding the ranking quality, _Borda Fuse_ obtained a _nDCG_ of 22.04%, 20.5%
and 25.9% higher than the same metric for _NPM_ , for ranking lengths of 5, 10
and 20 respectively. When it comes to _MAP_ , the improvements of _Borda Fuse_
with respect to _NPM_ were of 27.37%, 25.16%, and 21.78% for ranking lengths
of 5, 10 and 20 respectively. The improvement in ranking quality can be
related to the improvements in precision and recall. On one hand, by
increasing the precision in the top-ranked positions, the relevant results
near the top of the ranking increase and so do the values of nDCG and MAP
(since both metrics reward results in the top-ranked positions). On the other
hand, by increasing recall, the amount of relevant results that add up along
the nDCG and MAP calculations also increases.

After observing that the performance values of _ST-Retrieval_ were higher than
those of the search engines,we tested the statistical significance of the
results using the non-parametric Wilcoxon Signed Rank Test 31 with a
significance level $\alpha=0.05$. We stated the null hypothesis ($H1_{0}$) as:
“The metric values from _ST-Retrieval_ are equal to those from other search
engines". The alternative hypothesis ($H1_{1}$) states that there is a
difference between these metrics. Table 4 shows the p-values obtained for each
metric (treatment) reported in Table 3 after running the tests. With the
exception of the number of hits at first position (H@1), all p-value values
are less than 0.05. This means that we can reject $H1_{0}$ for all the metrics
(except H@1), and conclude that the differences between _ST-Retrieval_ and the
existing search engines are statistically significant. Finally, we
successfully answer RQ#1 by saying that _ST-Retrieval_ does improve the search
results.

Table 4: Comparison on the retrieval metrics using Wilcoxon signed rank test (_ST-Retrieval_). ST-Retrieval vs | H@1 | H@5 | H@10 | H@20 | P@5 | P@10 | P@20 | nD(r=5) | nD(r=10) | nD(r=20) | M(r=5) | M(r=10) | M(r=20)
---|---|---|---|---|---|---|---|---|---|---|---|---|---
NPM | .317 | <.001 | <.001 | <.001 | <.001 | <.001 | <.001 | <.05 | <.05 | <.05 | <.05 | <.001 | <.001
NPMSearch | <.05 | <.001 | <.001 | <.001 | <.001 | <.001 | <.001 | <.001 | <.001 | <.001 | <.001 | <.001 | <.001
Google | .317 | <.001 | <.001 | <.001 | <.001 | <.001 | <.001 | <.05 | <.05 | <.05 | <.001 | <.001 | <.001
Bing | .248 | <.001 | <.001 | <.001 | <.001 | <.001 | <.001 | <.05 | <.001 | <.001 | <.001 | <.001 | <.001

###  4.2 Evaluation of ST-Rank

The main goal is to determine whether _ST-Rank_ improves the rankings
generated by NPM.

####  4.2.1 Experimental Design and Operation

In order to obtain a “group of popular projects" for the _Collect data_ step,
we selected the top-1000 most popular projects according to GitHub, from the
repository of technologies (Figure 1) used in the _ST-Retrieval_ experiment.
NPM and NPMCompare were employed for obtaining features and alternatives for
each technology. In the _Create dataset_ step, we then created around 250
_training rankings_ of between 2 and 6 technologies each. In total, more than
1000 _training instances_ were created171717The training dataset can be found
in the Supplementary Material zip file at https://bit.ly/2w9sOzV..

To assess the rankings produced by _ST-Rank_ , we defined a _test set_ by
randomly removing 20% of the _training rankings_ (along with their _training
instances_). Specifically, we shuffled the order of each _training ranking_.
Then, we presented the technologies of each ranking to two senior JS
developers and asked them to produce _reference rankings_ by sorting the
technologies in descending order of relevance181818The reference rankings can
be found in the Supplementary Material zip file at https://bit.ly/2w9sOzV..
The remaining 80% of the _training instances_ were divided to perform a k-fold
cross-validation 32 with $k=5$, in order to train the ML model and find the
best configuration of hyper-parameters for GBRank. Specifically, we used
random search 33 to explore the possible values of the hyper-parameters, and
the values close to the best random configuration achieved by a grid search 34
were applied. In the end, GBRank was run with parameters
$learning\\_rate=0.004$, $max\\_depth=50$, $min\\_samples\\_split=50$, and
$min\\_samples\\_leaf=10$.

For the application contexts, we manually classified the JS technologies based
on their execution environment. We considered three possible environments,
namely: (i) technologies running in a Web browser (_Web_), (ii) technologies
to be used in the Node.js execution environment (_Node_), and (iii)
technologies that do not require a specific environment (_No context_). From
these application contexts, we configured 5 possible scenarios, as follows:
(i) _All_ \- the developer makes no distinction among application contexts
(i.e. the three execution environments are considered), (ii) _Web_ \- the
developer needs a technology for a Web browser (i.e. _Web_ and _No context_
are considered), (iii) _Node_ \- the developer needs a technology for Node.js
(_Node_ and _No context_ are considered), (iv) _OnlyWeb_ \- the developer
needs a technology specifically developed for the Web browser (only _Web_ is
considered), and (v) _OnlyNode_ \- the developer needs a technology
specifically developed for Node.js (only _Node_ is considered). Based on these
scenarios, we need _ST-Rank_ to classify the inputted technologies and the
_training rankings_. Thus, we ran _ST-Rank_ 5 times, once for each scenario.
At last, we compared our results with the default ranking techniques supported
by NPM and NPMCompare, which are the Analytic Hierarchy Process (AHP) 3 and
the Weighted Average Method (WAM) 35, respectively.

####  4.2.2 Metrics

We use three metrics to evaluate the performance of the rankings, namely: MAP
(see Section 4.1.2), SRCC (Spearman Rank Correlation Coefficient) 36, and MRR
(Mean Reciprocal Rank) 37. SRCC measures the correlation between the rankings
created by _ST-Rank_ (and also by AHP and WAM) against the reference rankings
created by the senior JS developers. In particular, we calculated SRCC for
each ranking and then averaged them to obtain a value that summarizes the
“stability" of each technique. MRR, in turn, evaluates if the highest-ranked
items are relevant. The closer the MRR value is to $1$, the greater the number
of relevant technologies in the highest positions.

####  4.2.3 Analysis of Results

Table 5: Ranking results for different scenarios (_ST-Rank_). | All | Web | Node | OnlyWeb | OnlyNode
---|---|---|---|---|---
Technique | M@3 | M@5 | SRCC | MRR | M@3 | M@5 | SRCC | MRR | M@3 | M@5 | SRCC | MRR | M@3 | M@5 | SRCC | MRR | M@3 | M@5 | SRCC | MRR
AHP | 0.517 | 0.541 | 0.454 | 0.654 | 0.756 | 0.762 | 0.731 | 0.865 | 0.541 | 0.561 | 0.365 | 0.667 | 0.785 | 0.725 | 0.621 | 0.880 | 0.461 | 0.478 | 0.310 | 0.672
WAM | 0.813 | 0.798 | 0.656 | 0.863 | 0.744 | 0.729 | 0.669 | 0.836 | 0.793 | 0.806 | 0.668 | 0.869 | 0.928 | 0.928 | 0.878 | 0.952 | 0.822 | 0.796 | 0.750 | 0.883
GBRank | 0.925 | 0.914 | 0.788 | 0.915 | 0.910 | 0.864 | 0.835 | 0.942 | 0.874 | 0.889 | 0.886 | 0.932 | 0.952 | 0.962 | 0.950 | 0.964 | 0.933 | 0.909 | 0.907 | 0.966

Table 5 shows the metric values for the scenarios. In the case of MAP, we
computed it for different ranking lengths (M@3 and M@5 means MAP considers a
ranking of 3 and 5 technologies respectively). The values in bold in the
columns correspond to the best value for the metric along that column. As it
can be observed, GBRank shows the best results for all the metrics. For
example, for the _All_ scenario, when considering MAP, GBRank outperforms AHP
and WAM by around 44% and 12% respectively. Similarly, in the case SRCC,
GBRank improves the values of AHP and WAM by around 42% and 17%. MRR shows
smaller improvements of GBRank, 28% and 6% for AHP and WAM respectively. The
differences between the techniques are similar for the other scenarios. On
average, the improvements of _ST-Rank_ over AHP and WAM are of 10%, 20% at
least, and 5% for MAP, SRCC, and MRR, respectively. The smallest improvement
was that of MRR, although this result was expected. MRR only takes into
account the first element of the ranking. That is, if the first element of the
reference ranking is in the first position of the ranking being evaluated,
this ranking has a maximum value of MRR (although the other elements are
disordered). However, in the problem of ranking of technologies, it is
important that the other elements are also ordered. If for some reason (e.g.,
due to a technical limitation) the first technology cannot be used, the rest
of the technologies should be as orderly as possible. This might happen if the
JS developer needs to develop a proof-of-concept, and she should be able to
find the right technology as quickly as possible.

Table 6: Results of Wilcoxon signed rank test (_ST-Rank_). ST-Rank vs | M@3 | M@5 | SRCC | MRR
---|---|---|---|---
AHP | 4.41$e^{-12}$ | 1.31$e^{-13}$ | 2.35$e^{-16}$ | 4.27$e^{-12}$
WAM | 5.52$e^{-05}$ | 1.01$e^{-06}$ | 1.67$e^{-10}$ | 5.79$e^{-04}$

To analyze if the results are statistically significant, we tested the results
using the non-parametric Wilcoxon Signed Rank Test with a significance level
$\alpha=0.05$. We stated the null hypothesis ($H2_{0}$) as: “The metric values
from _ST-Rank_ are equal to those provided by the other techniques (i.e. AHP
and WAM)”. The alternative hypothesis ($H2_{1}$) states that there is a
difference between these metrics. Table 6 shows the p-values obtained for each
metric reported in Table 5 after running the tests. As it can be seen, all
p-value values are less than 0.05. This means that we can reject $H2_{0}$ for
all the metrics. Thus, we can conclude that the differences between _ST-Rank_
and AHP and WAM are statistically significant. In summary, we successfully
answer RQ#2 by saying that the ranking proposed by _ST-Rank_ are better than
the ranking generated by the existing engines.

###  4.3 Threats to Validity

A threat to construct validity has to do with the queries (reference set) and
technology searches (baseline) used in the experiments. We tried to rely on
queries and searches being representative of real-world JS development. To
this end, we extracted a dataset from the NPM repository using the public JS
package registry. While we used only 25 queries, they returned 2760 JS
technologies that were manually analyzed. Since the analysis of query results
from search engines takes a substantial amount of time from experts, we
preferred not to do a detailed query analysis and leave this for future work.

A threat to internal validity is the usage of Borda Fuse to order the list of
technologies in _ST-Retrieval_ , which might have biased the results, and also
affected the outputs of _ST-Rank_. Alternative aggregation methods could
return different orderings and should be explored in future works. Similarly,
for _ST-Rank_ we used a particular learning-to-rank technique, but other
techniques could have led to different results.

Another threat is that the training rankings _ST-Rank_ were based on the CDSel
metric. This metric was chosen as a proxy for the popularity of JS packages,
but it might not correctly represent the relevance of the packages for the
community. Thus, a better validation of this metrics should be pursued.

To mitigate threats to external validity, we considered queries with different
sizes, purposes and domains. However, our dataset might not be representative
of all kinds of JS projects, and further experimentation and surveys of JS
projects are necessary. Furthermore, the off-line evaluation showed that the
computations of _ST-Retrieval_ sometimes take a considerable time, which might
be a problem in an online search engine. We have not consider yet the
computation time of the search engines as a comparison factor.

##  5 Related Work

Several approaches have been developed to support selection of software
technologies 10. In general, these approaches are based on creating a list of
technologies that are compared and presented to developers, so they can decide
which ones to apply to their projects. Some works have focused on the
evaluation of a set of pre-established candidate technologies and do not deal
with the problem of searching/retrieving the technologies from (Web)
repositories. For example, given a set of predefined candidates, Ernst et al.
38 proposes a scorecard to help developers to select a given technology. The
scorecard is based on performance, maintenance, and community criteria.

Software repositories 6 are one of the main sources for search/retrieval of
candidate technologies. However, existing repositories have not been very
successful for this task, despite improvements in their underlying technology,
such as the Web 6. One of the reasons is the performance of the search
engines, which sometimes fail to produce the desired results. Based on the
above, several works have tried to improve the search offered by the
repositories. As far as we know, no works about meta-search targeted to
software technologies have been proposed. However, there are a few works that
bear similarities with our approach. Agora 39 is a research prototype that
intended to replace the idea of software repositories by creating a global
database of JavaBeans and CORBA components, which was automatically generated
and indexed. However, a major drawback was its reliance on the syntactic
interface of JavaBeans and CORBA to carry out its search function. In
addition, Agora did not use search engines for software repositories. Another
recent work is Dolphin 40, which indexes open-source projects from version
control repositories (e.g., OpenHub, SourceForge) and ranks them according to
their influence in discussions of forum communities (e.g., StackOverflow,
OSChina). Our main difference with this work is that Dolphin searches open-
source code from version control repositories, while _ST-Retrieval_ focuses on
software released and stored in repositories (e.g., NPM). Another difference
is that Dolphin does not use general-purpose search engines.

LibFinder 41 is a search-based recommendation system for Java that uses multi-
objective optimization to recommend software libraries, that combine GitHub
and Maven repositories. However, it does not allow user queries to find
technologies. Instead, it is based on the source code to recommend libraries
that can replace pieces of source code made by hand. LibFinder does not use
general-purpose search engines. Soliman et. al. 42 developed an approach to
retrieve architectural design decisions and solution alternatives. The
approach uses StackOverflow as an example of an online repository of
architecture knowledge. However, this approach is based on a mapping between
text and a “de-facto" ontology, and its applicability to other contexts is yet
to be determined.

Regarding the order in which the technologies are created, there are works
that address the problem from different perspectives 8, 7, 9. However, most of
these works create ranking strategies manually, based on specific candidate
characteristics. For example, Franch and Carvallo 43 propose the adoption of a
structured quality model to evaluate software packages. This model provides a
taxonomy of software quality characteristics and metrics to calculate its
value for a given domain. Jadhav et. al 13 classifies package ranking
strategies into two groups, those using AHP and those using WAM. Then, an
expert system is used. This approach is difficult to implement, since it
depends on experts to construct rules in a manual fashion. Grande et al. 10
define the selection problem as a multi-objective optimization problem and
develop a framework for its treatment. They apply genetic algorithms to solve
the multi-objective problem. One limitation of this approach is the creation
and maintenance of the repository of technologies and their characteristics.

##  6 Conclusions

In this article we proposed an approach targeted to JS technologies based on
two complementary phases, called _ST-Retrieval_ and _ST-Rank_. _ST-Retrieval_
helps developers to search and retrieve JS technologies using a meta-search
strategy. _ST-Rank_ assists developers in ranking the candidate JS
technologies identified by the previous phase. To achieve this goal, _ST-Rank_
uses a machine learning strategy that learns how to create rankings of
technologies from previous choices made by the development community in
popular open-source projects.

An initial evaluation of the approach using the NPM repository showed
satisfactory results. In the case of _ST-Retrieval_ , precision and recall
values of around 80% were obtained, improving other search engines by
approximately 20%. Regarding _ST-Rank_ , improvements of around 5% for MRR,
10% for MAP, and 20% for SRCC, were obtained in the ranking metrics. Despite
these results, the approach still presents some drawbacks. First, the
technology extraction function using string-matching in _ST-Retrieval_ can be
expensive in computational terms. This might limit the application of the
approach for online searching. For this reason, we will analyze the
possibility of building an extraction function using other NER techniques and
exploring their influence on the _ST-Retrieval_ results. Second the CDSel
metric to measure the degree of selection of a technology in the community in
_ST-Rank_ still needs further validation. Although reasonable results were
obtained during the evaluations with CDSel using 1000 projects, considering
alternative parameters in this metric can have an impact on the quality of the
rankings.

As future work, in the case of _ST-Retrieval_ , we will apply aggregation
functions other than Borda Fuse. In the case of _ST-Rank_ , we will explore
alternatives to GBRank for the learning-to-rank task. In addition, we plan to
conduct a study with subjects (JS developers as users of our approach) in
order to corroborate our findings. Further work can extend our approach to
technology repositories for other programming languages (e.g., Ruby, Python or
Java, among others). Finally, following ideas of XAI (eXplainable AI) 44, it
would be interesting to add support for generating explanations of the
rankings, so that the comparison strategies are easier to understand by
developers.

## References

  * 1 Lin HY, Hsu PY, Sheen GJ. A fuzzy-based decision-making procedure for data warehouse system selection. Expert systems with applications 2007; 32(3): 939–953.
  * 2 Wittern E, Suter P, Rajagopalan S. A look at the dynamics of the JavaScript package ecosystem. In: ACM. ; 2016: 351–361.
  * 3 Saaty TL. Decision making with the analytic hierarchy process. International journal of services sciences 2008; 1(1): 83–98.
  * 4 Eppler MJ, Mengis J. The concept of information overload: A review of literature from organization science, accounting, marketing, MIS, and related disciplines. The information society 2004; 20(5): 325–344.
  * 5 Berghel H. Cyberspace 2000: Dealing with information overload. Communications of the ACM 1997; 40(2): 19–24.
  * 6 Clayton N, Biddle R, Tempero E. A study of usability of Web-based software repositories. In: ; 2000: 51-58
  * 7 Birk A. Modelling the application domains of software engineering technologies. In: IEEE. ; 1997: 291–292.
  * 8 Basili VR, Rombach HD. Support for comprehensive reuse. Software engineering journal 1991; 6(5): 303–316.
  * 9 Klein J, Gorton I. Design assistant for NoSQL technology selection. In: ACM. ; 2015: 7–12.
  * 10 Grande ADS, Rodrigues RDF, Dias-Neto AC. A Framework to Support the Selection of Software Technologies by Search-Based Strategy. In: IEEE. ; 2014: 979–983.
  * 11 Vegas S, Basili V. A characterisation schema for software testing techniques. Empirical Software Engineering 2005; 10(4): 437–466.
  * 12 Aslam JA, Montague M. Models for metasearch. In: ACM. ; 2001: 276–284.
  * 13 Jadhav AS, Sonar RM. Framework for evaluation and selection of the software packages: A hybrid knowledge based system approach. Journal of Systems and Software 2011; 84(8): 1394–1407.
  * 14 Nadeau D, Sekine S. A survey of named entity recognition and classification. Lingvisticae Investigationes 2007; 30(1): 3–26.
  * 15 Navarro G. A guided tour to approximate string matching. ACM computing surveys (CSUR) 2001; 33(1): 31–88.
  * 16 Dwork C, Kumar R, Naor M, Sivakumar D. Rank aggregation methods for the web. In: ACM. ; 2001: 613–622.
  * 17 Liu TY. Learning to rank for information retrieval.  Springer Science & Business Media .  2011\.
  * 18 Jain YK, Bhandare SK. Min max normalization based data perturbation method for privacy protection. International Journal of Computer & Communication Technology 2011; 2(8): 45–50.
  * 19 Li H. Learning to rank for information retrieval and natural language processing. Synthesis Lectures on Human Language Technologies 2011; 4(1): 1–113.
  * 20 Li P, Wu Q, Burges CJ. Mcrank: Learning to rank using multiple classification and gradient boosting. In: ; 2008: 897–904.
  * 21 Zheng Z, Zha H, Zhang T, Chapelle O, Chen K, Sun G. A general boosting method and its application to learning ranking functions for web search. In: ; 2008: 1697–1704.
  * 22 Bai J, Diaz F, Chang Y, Zheng Z, Chen K. Cross-market model adaptation with pairwise preference data for web search ranking. In: Association for Computational Linguistics. ; 2010: 18–26.
  * 23 Kanungo T, Ghamrawi N, Kim KY, Wai L. Web search result summarization: title selection algorithms and user satisfaction. In: ACM. ; 2009: 1581–1584.
  * 24 Bian J, Liu Y, Agichtein E, Zha H. Finding the right facts in the crowd: factoid question answering over social media. In: ACM. ; 2008: 467–476.
  * 25 Taghavi M, Patel A, Schmidt N, Wills C, Tew Y. An analysis of web proxy logs with query distribution pattern approach for search engines. Computer Standards & Interfaces 2012; 34(1): 162–170.
  * 26 Lewandowski D. Evaluating the retrieval effectiveness of Web search engines using a representative query sample. Journal of the Association for Information Science and Technology 2015; 66(9): 1763–1775.
  * 27 Höchstötter N, Lewandowski D. What users see–Structures in search engine results pages. Information Sciences 2009; 179(12): 1796–1812.
  * 28 Büttcher S, Clarke CL, Cormack GV. Information retrieval: Implementing and evaluating search engines.  Mit Press .  2016\.
  * 29 Caruana R, Niculescu-Mizil A. An empirical comparison of supervised learning algorithms. In: ACM. ; 2006: 161–168.
  * 30 Järvelin K, Kekäläinen J. IR evaluation methods for retrieving highly relevant documents. In: ACM. ; 2000: 41–48.
  * 31 Lavrenko V, Croft WB. Relevance-based language models. In: . 51. ACM. ; 2017: 260–267.
  * 32 Refaeilzadeh P, Tang L, Liu H. Cross-validation. Encyclopedia of database systems 2009: 532–538.
  * 33 Bergstra J, Bengio Y. Random search for hyper-parameter optimization. Journal of Machine Learning Research 2012; 13(Feb): 281–305.
  * 34 Bergstra JS, Bardenet R, Bengio Y, Kégl B. Algorithms for hyper-parameter optimization. In: ; 2011: 2546–2554.
  * 35 Perez M, Rojas T. Evaluation of Workflow-type software products: a case study. Information and software technology 2000; 42(7): 489–503.
  * 36 Zwillinger D, Kokoska S. CRC standard probability and statistics tables and formulae.  Crc Press .  1999\.
  * 37 Chapelle O, Metlzer D, Zhang Y, Grinspan P. Expected reciprocal rank for graded relevance. In: ACM. ; 2009: 621–630.
  * 38 Ernst N, Kazman R, Bianco P. Component Comparison, Evaluation, and Selection: A Continuous Approach. In: IEEE; 2019.
  * 39 Seacord RC, Hissam SA, Wallnau KC. Agora: A search engine for software components. IEEE Internet computing 1998; 2(6): 62.
  * 40 Zhan Y, Yin G, Wang T, Yang C, Li Z, Wang H. Dolphin: A search engine for OSS based on crowd discussions across communities. In: IEEE. ; 2016: 599–605.
  * 41 Ouni A, Kula RG, Kessentini M, Ishio T, German DM, Inoue K. Search-based software library recommendation using multi-objective optimization. Information and Software Technology 2017; 83: 55–75.
  * 42 Soliman M, Galster M, Riebisch M. Developing an Ontology for Architecture Knowledge from Developer Communities. In: IEEE. ; 2017: 89–92.
  * 43 Franch X, Carvallo JP. A quality-model-based approach for describing and evaluating software packages. In: IEEE. ; 2002: 104–111.
  * 44 Gunning D. Explainable artificial intelligence (xai). Defense Advanced Research Projects Agency (DARPA), nd Web 2017\.


# Cellular Automata model for period-$n$ synchronization: A new universality
class.

Divya D. Joshi & Prashant M. Gade<EMAIL_ADDRESS>Department of
Physics, Rashtrasant Tukadoji Maharaj Nagpur University, Amravati Road, Ram
Nagar, Maharashtra, Nagpur, India-440033

###### Abstract

There are few known universality classes of absorbing phase transitions in one
dimension and most models fall in the well-known directed percolation (DP)
class. Synchronization is a transition to an absorbing state and this
transition is often DP class. With local coupling, the transition is often to
a fixed point state. Transitions to a periodic synchronized state are seldom
observed. Recently a transition to a synchronized period-3 state that is not
in DP class is observed. We model it using a cellular automata model with
states 1 to $n$. The rules are a) Each site in state $i$ changes to state
$i+1$ for $i<n$ and 1 if $i=n$. b) After this update, it takes value of either
neighbor unless it is in state 1. With these rules, we observe a transition to
synchronization with critical exponents different from those of DP for $n>2$.
For $n=2$, a different exponent is observed.

##  1 Introduction

The theory of phase transitions is a major success story in statistical
physics in the 70’s. The concepts of renormalization group as well as
universality class were introduced in those times. It was fascinating that the
second-order phase transition in quark-gluon plasma is in the same
universality class as the Ising model [1]. Thus, seemingly different systems
arising in very different contexts are in the same universality class
depending mainly on the dimension and symmetries. There has been huge progress
in phase transitions in equilibrium systems and several nonequilibrium systems
have also been studied from the phase transition viewpoint. Among the
nonequilibrium transitions, transitions to absorbing states are most
extensively investigated [2]. These transitions are in a few different
universality classes such as directed percolation, directed Ising, Manna class
etc.[3]. Whether or not the pair contact process with diffusion (PCPD) is a
new universality class has been a long-standing problem with no clear solution
in sight [4, 5]. The essential limitation is that the Monte-Carlo simulations
are for finite-size lattices for finite time and can lead to uncertain
conclusions. The overall evidence in the recent past indicates that PCPD is
likely to be in the same universality class as a DP in the thermodynamic and
asymptotic limit [6].

Figure 1: Plot for $O(t)$ vs $t$ for states $k=3$, $N=10^{5}$. The decay
exponent for this case is $\delta=0.82$. Figure 2: Defect dynamics of the
model for $N=4000$, $k=3$. The dynamics for this differ from that of directed
percolation. Figure 3: Plot $O(t)N^{z\delta}$ vs $t/N^{z}$ for different size
of lattice i.e., $N=500,1000,2000$ and 4000. Here $k=3$, $\delta=0.82$ and
$z=2$. Figure 4: Plot for $O(t)$ vs $t$ for states $k=20$, $N=10^{5}$. The
decay exponent for this case is $\delta=0.82$. Figure 5: Plot for $O(t)$ vs
$t$ for states $k=2$, $N=10^{5}$. The decay exponent for this case is
$\delta=0.5$. Figure 6: Defect dynamics of the model for $N=1000$, $k=2$. In
this case the dynamics of the model resemble to the random walk model. Figure
7: Plot $O(t)N^{z\delta}$ vs $t/N^{z}$ for different size of lattice i.e.,
$N=500,1000,2000$ and 4000. Here $k=2$, $\delta=0.5$ and $z=2$.

Of these different universal classes, the directed percolation universality
class is the most observed. The Jannsen-Grassberger conjecture states that
“the universality class of DP contains all continuous transitions from a dead
or absorbing state to an active one with a single scalar order parameter,
provided the dead state is not degenerate and provided some technical points
are fulfilled: short-range interactions both in space and time, the
nonvanishing probability for any active state to die locally, translational
invariance (absence of frozen randomness), and absence of multicritical
points” [7, 8] and it is observed even in the most unexpected places where the
absorbing state has no long-range order in space. The phase space is divided
into bands and all sites return to the previous band after a certain period.
Thus it could be described as a periodic state with that period only in a
coarse-grained sense [9, 10].

Recently, a transition to a period-3 synchronized state has been observed in
coupled Gaussian maps. Gaiki et al observed that this transition is in a new
universality class and report exponents that do not match with previous
reports [10]. We present a stochastic cellular automata model that reproduces
the exponents for period-3. In this model, we obtain exponents close to those
obtained in the above work. Now one may wonder if a transition to a
synchronized state with a period different from three has a different
universality class. We investigate this possibility. However, within our
numerical error, except for period-2, the exponents for any period are not
very different from those obtained for period-3. In this model, all sites are
updated like a clock. Except for sites in a certain preferred state, all other
sites are influenced by its neighbors.

##  2 The model

We consider a $1D$ lattice of length $N$. The state at each site $i$ is
denoted by $s_{t}(i)$. At $t=0$, we assign each site a spin state $s_{0}(i)$
as $l$ where $l=1,2,\ldots k$ with equal probability. The states of the sites
are updated synchronously in two steps.

i) In the first step, we update the sites cyclically i.e., the state 1 changes
to 2, 2 changes to 3 and $k$ changes to 1. We introduce one more arbitrary
variable $s^{\prime}_{t}(i)$. Thus $s^{\prime}_{t+1}(i)=s_{t}(i)+1$ if
$s_{t}(i)<k$ and $s^{\prime}_{t+1}(i)=1$ if $s_{t}(i)=k$.

ii) In the second step, except for sites in a certain preferred state, all
other sites mimic the state of randomly chosen neighbor. In other words, if
$s^{\prime}_{t+1}(i)\neq 1$, $s_{t+1}(i)=s^{\prime}_{t+1}(i-1)$ or
$s_{t+1}(i)=s^{\prime}_{t+1}(i+1)$ with probability ${\frac{1}{2}}$. If
$s^{\prime}_{t+1}(i)=1$, we assign $s_{t+1}(i)=1$. Thus, the site which is in
state $1$ is not affected by its nearest neighbors. This rule breaks the
symmetry between states. In coupled map lattices, different states are not
exactly equivalent. Thus all possible transitions are not equally probable.
This rule models the possibility that some states are less affected by
neighbours than others.

For synchronization, we define an order parameter
$O(t)={\frac{1}{N}}\sum_{i}H(|s_{t}(i)-s_{t}(i-1)|)$ where $H(x)=1$ iff $x\leq
0$ and $H(x)=1$ otherwise. In other words, this order parameter is the number
of domain walls where the spin values of consecutive sites on the lattice are
different. The order parameter is zero for synchronized state and is nonzero
otherwise.

First, let us consider the case $k=3$ which is the case of transition to
synchronized period-3 studied by Gaiki et al [10]. In Fig. 1, we plot $O(t)$
as a function of time $t$ on a logarithmic scale. We find a power-law
behaviour $O(t)\sim t^{-\delta}$ with $\delta\sim 0.82$ which is similar to
the exponent observed in the above paper. In Fig. 2, we show how defects, (the
sites where spins of consecutive sites are different) propagate in time. The
defects propagate in a straight line and annihilate after meeting (This is
very similar to Fig. 5f of [10]). This behaviour is unlike the directed
percolation universality class where defects propagate in a cone (See Fig.1 of
[11]). We find that the defects take a preferred direction and there is very
little random or zig-zag motion over and above this direction. We also study
the evolution of the order parameter for different system sizes. In Fig. 3 we
show the evolution of the order parameter for different system sizes. There is
a power-law behaviour followed by cusp and exponential decay. The decay time
scales as $N^{2}$ and if we plot $t/N^{z}$ versus $O(t)N^{z\delta}$ with
$z=2$, we observe an excellent collapse. (For comparison, see Fig.9 of [10].)

Now we consider $k>3$ say $k=20$. For $k>3$, we find that the order parameter
decays as $t^{-\delta}$ with $\delta\sim 0.82$ which is not very different
from $k=3$ (see Fig. 4). Hence, we conclude that the universality class does
not change for $k\geq 3$.

For $k=1$ there is no possibility of defects. Now we consider case $k=2$. For
$k=2$, $O(t)\sim t^{-\delta}$ with $\delta\sim{\frac{1}{2}}$. (Fig. 5) If we
investigate the time evolution of defects, it looks more like annihilating
random walkers which explains the exponent ${\frac{1}{2}}$. (Fig. 6) We also
study the size dependence of absorption for $k=2$ and we obtain excellent
collapse if we plot $t/N^{z}$ versus $O(t)N^{z\delta}$ with $z=2$ and
$\delta=1/2$ (Fig. 7).

##  3 Discussion and Conclusion

We have studied a model of cellular automaton for period-$n$ synchronization.
We used cellular automaton to model a transition to the synchronized
period-$n$ state. This model is updated in two steps. In the first step, the
states of sites are updated cyclically. In the next step, the sites randomly
take the state of their neighbour, except for sites with state 1. Sites with
this state remain unaltered. We define the order parameter as the difference
between the state values of the neighbouring states. The order parameter is a
nonzero quantity when the neighbouring sites have different states. In this
work, we have studied three cases, i.e., $k=2,3,$ and 20 in detail. For $k=2$,
it is observed that the defects grow as a power-law with the dynamic exponents
$\delta=\frac{1}{2}$ and $z=2$. This suggests the model behaves like a random
walk model for $k=2$. On the other hand, we get $\delta=0.82$ and $z=2$ for
this model with $k=3$ and 20. For $k\geq 3$, the model shows the same
behaviour. These values have been recently observed in a transition to
period-3 in the coupled Gaussian map. These exponents are novel and have not
been seen in any other universality classes. Thus, these findings may suggest
the existence of a new universality class.

##  4 Acknowledgment

PMG and DDJ thank DST-SERB for financial assistance (Ref. CRG/2020/003993).

##  5 References

## References

  * [1] D. H. Rischke, The quark–gluon plasma in equilibrium, Progress in Particle and Nuclear Physics 52 (1) (2004) 197–296.
  * [2] H. Hinrichsen, Non-equilibrium critical phenomena and phase transitions into absorbing states, Advances in physics 49 (7) (2000) 815–958.
  * [3] M. Henkel, M. Pleimling, Non-Equilibrium Phase Transitions: Volume 2: Ageing and Dynamical Scaling Far from Equilibrium, Springer Science & Business Media, 2011.
  * [4] M. Henkel, H. Hinrichsen, The non-equilibrium phase transition of the pair-contact process with diffusion, Journal of Physics A: Mathematical and General 37 (28) (2004) R117.
  * [5] D. Gredat, H. Chaté, B. Delamotte, I. Dornic, Finite-scale singularity in the renormalization group flow of a reaction-diffusion system, Physical Review E 89 (1) (2014) 010102.
  * [6] M. B. Matte, P. M. Gade, Persistence as the order parameter in a generalized pair-contact process with diffusion, Journal of Statistical Mechanics: Theory and Experiment 2016 (11) (2016) 113203.
  * [7] P. Grassberger, On phase transitions in schlögl’s second model, in: Nonlinear Phenomena in Chemical Dynamics: Proceedings of an International Conference, Bordeaux, France, September 7–11, 1981, Springer, 1981, pp. 262–262.
  * [8] P. D. Bhoyar, M. C. Warambhe, S. Belkhude, P. M. Gade, Robustness of directed percolation under relaxation of prerequisites: role of quenched disorder and memory, The European Physical Journal B 95 (4) (2022) 64.
  * [9] S. S. Pakhare, P. M. Gade, Novel transition to fully absorbing state without long-range spatial order in directed percolation class, Communications in Nonlinear Science and Numerical Simulation 85 (2020) 105247.
  * [10] P. M. Gaiki, A. D. Deshmukh, S. S. Pakhare, P. M. Gade, Transition to period-3 synchronized state in coupled gauss maps, Chaos: An Interdisciplinary Journal of Nonlinear Science 34 (2) (2024).
  * [11] T. Janaki, S. Sinha, N. Gupte, Evidence for directed percolation universality at the onset of spatiotemporal intermittency in coupled circle maps, Physical Review E 67 (5) (2003) 056218.