# Toward Cost-effective Adaptive Random Testing: An Approximate Nearest
Neighbor Approach

Rubing Huang, Chenhui Cui, Junlong Lian, Dave Towey, Weifeng Sun, Haibo Chen
Rubing Huang and Chenhui Cui are with the School of Computer Science and
Engineering, Macau University of Science and Technology, Taipa, Macau 999078,
China. E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>Lian
and Haibo Chen are with the School of Computer Science and Communication
Engineering, Jiangsu University, Zhenjiang, Jiangsu 212013, China. E-mail:
{2211908018<EMAIL_ADDRESS>Towey is with the School of
Computer Science, University of Nottingham Ningbo China, Ningbo, Zhejiang
315100, China. E-mail<EMAIL_ADDRESS>Sun is with the
School of Big Data and Software Engineering, Chongqing University, Chongqing
401331, China. E-mail<EMAIL_ADDRESS>
###### Abstract

Adaptive Random Testing (ART) enhances the testing effectiveness (including
fault-detection capability) of Random Testing (RT) by increasing the diversity
of the random test cases throughout the input domain. Many ART algorithms have
been investigated according to different criteria, such as Fixed-Size-
Candidate-Set ART (FSCS) and Restricted Random Testing (RRT), and have been
widely used in many practical applications. Despite its popularity, ART
suffers from the problem of high computational costs during test case
generation, especially as the number of test cases increases. Although a
number of strategies have been proposed to enhance the ART testing efficiency,
such as the forgetting strategy and the $k$-dimensional tree strategy, these
algorithms still face some challenges, including: (1) Although these
algorithms can reduce the computation time, their execution costs are still
very high, especially when the number of test cases is large; and (2) To
achieve low computational costs, they may sacrifice some fault-detection
capability. In this paper, we propose an approach based on Approximate Nearest
Neighbors (ANNs), called Locality Sensitive Hashing ART (LSH-ART). When
calculating distances among different test inputs, LSH-ART identifies the
approximate (not necessarily exact) nearest neighbors for candidates in an
efficient way. LSH-ART attempts to balance ART testing effectiveness and
efficiency.

###### Index Terms:

Software testing, random testing (RT), adaptive random testing (ART),
approximate nearest neighbor (ANN), locality sensitive hashing (LSH), cost-
effectiveness.

##  I Introduction

Software testing is an essential software quality assurance activity in the
software development life-cycle [1, 2]. Among the many software testing
techniques, one fundamental approach is Random Testing (RT) [3], which simply
selects test cases in a random manner from the input domain (the set of all
possible test inputs). RT is considered popular due to the usual ease of
implementation, its efficient generation of random test cases, and its ability
to provide quantitative estimation of the reliability of software [4]. RT has
been widely applied to different software applications, including: SQL
database systems [5, 6]; embedded software systems [7]; Java Just-In-Time
(JIT) compilers [8]; security assessment [9]; and .NET error detection [10].
As Arcuri et al. [11] have pointed out, RT should be recommended as the first
choice for testing many practical software scenarios.

In spite of its popularity, though, RT has been criticized for generally
adopting little, or none, of the available information to support its test
case generation. Myers et al. [12], for example, described RT as perhaps the
“least effective” testing approach. Many approaches have been proposed to
enhance RT fault detection, including one of the most popular, Adaptive Random
Testing (ART) [13, 14]. ART is a family of enhanced RT methods that are
motivated by observations of clustering of failure regions (regions of test
inputs that can identify software failures) [15, 16, 17, 18, 19]. ART aims to
achieve an even spread of random test cases over the input domain, which may
deliver better test case diversity than RT [20]. Previous studies [14] have
shown ART to be more effective than RT, in terms of various evaluation
criteria, including: the number of test case executions required to detect the
first failure (F-measure) [21]; code coverage [22]; and test case distribution
[23].

(a) Point pattern

(b) Strip pattern

(c) Block pattern

Figure 1: Examples of three failure patterns and sample faulty programs in
two-dimensional input domains.

Many different strategies have been adopted for ART, resulting in multiple ART
implementations [14], the most well-known and widely used of which is the
Select-Test-From-Candidates Strategy (STFCS). STFCS chooses the next test case
from a set of random candidates based on some criteria or evaluation of the
previously-executed test cases [14]: Each random candidate is compared (in
some way) with each previously-executed test case, with the “best” candidate
being selected as the next test case. Two basic (and popular) STFCS
implementations are Fixed-Size-Candidate-Set ART (FSCS) [13] and Restricted
Random Testing (RRT) [24]. FSCS-ART chooses one of the candidates as the next
test case such that it is farthest away from the already-executed test cases;
RRT selects the next test case such that its distance from all previously-
executed test cases is greater than a given threshold value. Generating each
new test case requires calculation of the distance between each candidate and
each executed test case, which represents a high computational overhead,
especially when the number of executed test cases becomes large. STFCS
involves identifying the nearest neighboring executed test case for each
candidate, as part of the decision process to choose the “best” one as the
next test case. A key part of STFCS, therefore, can be viewed as an instance
of finding a Nearest Neighbor (NN) [25].

Various enhanced ART implementations have been proposed to address the STFCS
overheads problem, including forgetting [26], and a precise NN approach [27].
The forgetting approach involves discarding (“forgetting”) some of the
previously-executed test cases to reduce the number of distance computations
for each candidate. The precise NN approach, in contrast, often uses a tree-
index structure (such as a $k$-dimensional tree, KD-tree [28]) to speed up the
search process. Because forgetting does not use all the information of the
already-executed test cases, it can be considered to sacrifice some fault-
detection capability. The precise NN approach still needs to precisely
identify the nearest neighbor for each candidate, which can still be
computationally expensive, especially when the input domain dimensionality is
high, or the number of executed test cases is large [25].

In this paper, we propose an Approximate Nearest Neighbor (ANN) ART approach
using the well-known ANN algorithm Locality Sensitive Hashing (LSH)111Because
the set of executed test cases dynamically increases with ART, either the
dynamic LSH [29, 30] or Scalable LSH (SLSH) [31, 32] approaches need to be
used in place of the static LSH: We adopted SLSH. [33]: We call this LSH-ART.
LSH-ART attempts to balance testing effectiveness and efficiency: It makes use
of all previously-executed test cases, to maintain fault-detection
performance, but retrieves the approximate (not exact) nearest neighbor of
each candidate, thus reducing the search cost.

To evaluate our proposed approach, we conducted a series of simulations and
empirical studies with 34 real-life programs, comparing with the original ART
algorithms and their corresponding enhanced variants. The main contributions
and findings of this paper are:

  * •

To the best of our knowledge, this is the first paper that proposes an LSH-
based approach to enhance ART performance.

  * •

We propose a framework to support LSH-ART, and present two implementations:
LSH-FSCS and LSH-RRT.

  * •

LSH-ART maintains comparable testing effectiveness (including fault-detection
effectiveness) to the original ART and its variants, sometimes obtaining
better results, especially for high dimensions.

  * •

LSH-ART has better testing efficiency, generally incurring lower computational
costs (including for test case generation) than the original ART and its
variants, especially when the input domain dimensionality is high.

  * •

LSH-ART is much more cost-effective than the original ART, in all scenarios,
and outperforms the variants in most scenarios.

The rest of this paper is organized as follows: Section II presents some
background information. Section III introduces the proposed approach,
including a motivating example, the framework, algorithms, and complexity
analyses. Section IV explains the experimental set-up to examine the
performance of our proposed approach. Section V presents and analyzes the
experimental results, and provides some potential threats to validity. Section
VI provides some discussion regarding software failures and faults. Section
VII discusses some related work about ART. Section VIII concludes this paper,
and identifies some potential future work.

##  II Background

In this section, we present some of the preliminary concepts, including an
introduction to both ART and ANN.

###  II-A Preliminaries

Given a faulty software-system under test (SUT), a test case $t$ is called a
failure-causing input if the output or behavior of the SUT, when executed with
$t$, is not as expected, as determined by the test oracle [34, 35, 36].
Generally speaking, two fundamental features can be used to describe the
properties of the faulty SUT: the failure rate; and the failure pattern [37].
The failure rate is the number of failure-causing inputs as a proportion of
all possible inputs; and the failure pattern is the distributions of failure-
causing inputs across the input domain, including both the locations and
geometric shapes. Before testing, these two features are fixed, but unknown.

Figure 1 shows examples of the three broad categories of point, strip, and
block failure patterns, as originally identified by Chan et al. [37]: The
squares in the upper part of each subfigure represent the two-dimensional
input domain boundary; and the black dots, strip, or block represent the
failure-causing inputs (the failure pattern). The code snippets in each dashed
box in the subfigures represent sample faulty programs that can produce the
corresponding failure pattern. Previous studies have noted that block and
strip patterns are more commonly encountered than point patterns [15, 16, 17,
18, 19]. Although many different geometric shapes of failure patterns exist,
the three broad categories (of point, strip, and block) can generally
represent them all: For example, a two-dimensional (2D) failure region may be
a circle-like shape, which can be categorized as a block pattern, because a
circle-like failure region is also a block; similarly, a narrow (2D) eclipse
can be classified as a strip pattern; and so on.

###  II-B Adaptive Random Testing (ART)

An important observation, made, independently, by multiple researchers in
different areas, is that failure-causing inputs tend to cluster into connected
regions: failure regions [15, 16, 17, 18, 19]. Accordingly, if a test case
$t_{1}$ is a failure-causing input, then it is highly probable that its
neighbors are also failure-causing inputs; similarly, if $t_{2}$ is not a
failure-causing input, then its neighbors are also likely to not be failure-
causing. This is shown in Figure 2. Consider the two candidate test cases
$c_{1}$ and $c_{2}$ in Figure 2. Because $c_{1}$ is close to the failure-
causing input $t_{1}$, it is considered to have a higher probability to be a
failure-causing input. Similarly, because $c_{2}$ is close to the non-failure-
causing input $t_{2}$, is has a higher probability of being a non-failure
causing input. This leads to the heuristic that a program input far away from
non-failure-causing inputs may have a higher probability of causing failure
than neighboring test inputs. This has inspired Adaptive Random Testing (ART),
which aims to achieve a more diverse, or even spread of test cases across the
input domain [13, 20].

Figure 2: Motivation of ART.

1: Set $C\leftarrow\\{\\}$, and $E\leftarrow\\{\\}$ 2: Randomly generate a
test case ${t}$ from the input domain, according to uniform distribution  3:
Add ${t}$ into $E$, i.e., $E\leftarrow E\bigcup\\{{t}\\}$ 4: while The
stopping condition is not satisfied do 5: Randomly choose a specific number of
elements from $\mathcal{D}$ to form $C$ according to the specific criterion
6: Find a ${t}\in C$ as the next test case satisfying the specific criterion
7: $E\leftarrow E\bigcup\\{{t}\\}$ 8: end while 9: Report the result and exit

Figure 3: Framework pseudocode for STFCS ART [14].

ART refers to a family of testing approaches that randomly generate test cases
that are evenly spread over the entire input domain [2, 14]. Because there are
many approaches to generating these test cases, there are many different ART
implementations [14]. In this paper, we focus on the Select-Test-From-
Candidates Strategy (STFCS) ART category [14], which has been the most popular
and extensively-studied category. STFCS selects the next test case from a set
of randomly-generated candidates based on some criteria or evaluation
involving the previously-executed test cases. Figure 3 shows the STFCS
framework [14], which contains two components: random-candidate-set-
construction; and test-case-selection. STFCS makes use of two sets: one to
store the random candidates (the candidate set, $C$); and one to store the
previously-executed test cases (the executed set, $E$). Two of the most
popular ART STFCS algorithms are Fixed-Size-Candidate-Set ART (FSCS) [13] and
Restricted Random Testing (RRT) [24], both of which are examined in this
paper.

####  II-B1 Fixed-Size-Candidate-Set ART (FSCS)

When generating the next test case, FSCS randomly generates $k$ candidates to
form the candidate set $C$. Each candidate is then evaluated against all the
previously-executed test cases — all elements in $E$. An element $c$ from $C$
will be the “best” choice as the next test case if it satisfies the following
criterion:

$\forall c^{\prime}\in C,~{}\min_{e\in E}dist(c,e)\geq\min_{e\in
E}dist(c^{\prime},e),$ (1)

where $dist(c,e)$ is a function that measures the distance between two test
inputs $c$ and $e$. In other words, assessment of each random candidate
$c^{\prime}$ in $C$ involves identification of the closest element in $E$ —
the Nearest Neighbor (NN) of $c^{\prime}$ in $E$. Because $k$ is usually a
fixed constant ($10$ in most cases [38]), each next test case generation only
requires the identification of this fixed number of nearest neighbors.
However, as the size of $E$ increases, identification of each nearest neighbor
incurs an increasingly large amount of overhead. Therefore, the FSCS time
overheads mainly depend on the NN search process.

####  II-B2 Restricted Random Testing (RRT)

In contrast to FSCS, RRT continues to generate and check random candidates,
one by one, until the first suitable one is identified as the next test case.
This means that the number of random candidates is flexible, not fixed, during
test case generation. The RRT criterion to determine whether or not a random
candidate $c$ can be selected as the next test case, against $E$, is defined
as:

$\min_{e\in E}dist(c,e)>\sqrt[d]{\frac{\sigma_{d}\times A\times
R}{\pi^{\lfloor d/2\rfloor}\times|E|}},$ (2)

where $d$ is the dimension of the input domain $\mathcal{D}$; $A$ is the size
of $\mathcal{D}$; $R$ is a constant parameter (generally called the exclusion
ratio [39]); and $\sigma_{d}$ is the formula coefficient, which can be written
as:

$\sigma_{d}=\left\\{\begin{array}[]{rl}{(\sigma_{d-2}\times d)}/{2},&d>2,\\\
1,&d=2,\\\ 1/2,&d=1.\\\ \end{array}\right.$ (3)

Similar to FSCS, the RRT computational overheads are strongly connected to the
speed of identification of each NN, and can increase as the size of $E$
increases.

###  II-C Approximate Nearest Neighbor (ANN)

In this section, we first introduce the Nearest Neighbor (NN) problem, and
then focus on the Approximate Nearest Neighbor (ANN). A definition of NN is
[40, 41]:

######  Definition II.1 (Nearest Neighbor, NN).

Given a set $V$ of $m$ data points in a $d$-dimensional space $\mathbb{R}^{d}$
(i.e., $V\subset\mathbb{R}^{d}$), and given a query point
$q\in\mathbb{R}^{d}$, the point $v$ of $T$ is the nearest neighbor to $q$ such
that:

$\forall v^{\prime}\in V,~{}dist(v,q)\leq dist(v^{\prime},q),$ (4)

where $dist(v,q)$ gives the distance between points $v$ and $q$.

Although the NN problem can find the exact nearest neighbors, its query
efficiency (for both space and query time) can be low, especially when the
dimensionality is high. An alternative to NN is to query approximate (not
exact) nearest neighbors, as in the Approximate NN (ANN) problem: ANN may
enable a more efficient performance. The concept of ANN can be defined as [40,
41]:

######  Definition II.2 (Approximate Nearest Neighbor, ANN).

Given a set $V$ of data points in a metric space $\mathbb{R}^{d}$ (i.e.,
$V\subset\mathbb{R}^{d}$), and given a query point $q\in\mathbb{R}^{d}$, a
point $v$ from $V$ is a approximate nearest neighbor satisfying the following
condition:

$dist(v,q)\leq(1+\epsilon)dist(v^{*},q),$ (5)

where $v^{*}$ is the exact or real nearest neighbor to $q$, and $\epsilon$ is
an approximation factor parameter ($\epsilon>0$).

ANN algorithms aim to find a point whose distance from the query point is at
most $(1+\epsilon)$ times the distance from the query to the actual nearest
neighbor, where $(1+\epsilon)$ is generally called the approximation factor
[42].

####  II-C1 Locality Sensitive Hashing (LSH)

There are many techniques to solve the ANN problem, one of which is Locality
Sensitive Hashing (LSH) [33]. The basic principle of LSH is to make use of a
hash function from the same hash family for placing each data point into a
bucket such that the probability of collision is much higher for points that
are close to each other than for those that are far apart. An ANN search can
be carried out as follows: (1) Find the bucket to which a query point is
hashed and choose the data points in these buckets as candidates; and (2) Rank
candidates according to their actual distance to the query point to find the
nearest neighbor.

LSH relies on the existence of LSH functions. Given $\mathcal{H}$, a family of
hash functions mapping $\mathbb{R}^{d}$ to the integer set $\mathbb{N}$ (i.e.,
$\mathcal{H}=\\{h:\mathbb{R}^{d}\rightarrow\mathbb{N}\\}$), then a definition
of LSH [33] is described as follows:

######  Definition II.3 (Locality Sensitive Hashing, LSH).

A family $\mathcal{H}$ is called $(r_{1},r_{2},p_{1},p_{2},)$-sensitive if,
for any two points $v,q\in\mathbb{R}^{d}$,

$\left\\{\begin{array}[]{rl}\textrm{if~{}}dist(v,q)\leq
r_{1}\textrm{,~{}then~{}}\textrm{Pr}_{\mathcal{H}}[h(q)=h(v)]\geq p_{1},\\\
\textrm{if~{}}dist(v,q)\geq
r_{2}\textrm{,~{}then~{}}\textrm{Pr}_{\mathcal{H}}[h(q)=h(v)]\leq p_{2},\\\
\end{array}\right.$ (6)

where $h$ is a function selected randomly (with uniform distribution) from
$\mathcal{H}$; $\textrm{Pr}_{\mathcal{H}}[h(q)=h(v)]$ represents the
probability that $h(q)=h(v)$; and $r_{1}$, $r_{2}$, $p_{1}$, and $p_{2}$ are
parameters satisfying $p_{1}>p_{2}$ and $r_{1}<r_{2}$.

In this study, we adopted an LSH family based on $p$-stable
distributions222For example, a Cauchy distribution, defined by the density
function $g(x)=\frac{1}{\pi}\frac{1}{1+x^{2}}$, is 1-stable; however, a
Gaussian (normal) distribution, defined by the density function
$g(x)=\frac{1}{\sqrt{2\pi}}e^{-x^{2}/2}$, is 2-stable [43]. (also called
E2LSH) [43], that works for all $p\in(0,2]$. Formally, each hash function
$h_{\boldsymbol{a},b}(\boldsymbol{v})$: $\mathbb{R}^{d}\rightarrow\mathbb{N}$
maps a $d$-dimensional vector $\boldsymbol{v}$ onto the set of integers, which
is defined as:

$h_{\boldsymbol{a},b}(\boldsymbol{v})=\Bigg{\lfloor}\frac{\boldsymbol{a}\cdot\boldsymbol{v}+b}{w}\Bigg{\rfloor},$
(7)

where $\boldsymbol{a}$ is a random $d$-dimensional vector each entry in which
is selected independently from a $p$-stable distribution; $w$ is a fixed
parameter for the entire family ($w$ acts as a quantization width); and $b$ is
a real number selected uniformly from the range $[0,w)$. The
$h_{\boldsymbol{a},b}(\boldsymbol{v})$ corresponds to the composition of a
projection to a random direction with a random offset and a quantization by a
constant. According to Eq. (7), the collision probability between two points
$\boldsymbol{q}$ and $\boldsymbol{v}$ can be calculated as:

$\textrm{Pr}_{\mathcal{H}}[h(\boldsymbol{q})=h(\boldsymbol{v})]=\int_{0}^{w}\frac{1}{\alpha}\cdot
g\bigg{(}\frac{x}{\alpha}\bigg{)}\cdot\bigg{(}1-\frac{x}{w}\bigg{)}dx,$ (8)

where $\alpha=dist(\boldsymbol{q},\boldsymbol{v})$, and $g(x)$ is the density
function. It can be seen that with the increase of $\alpha$, the collision
probability decreases monotonically.

To make locality-sensitiveness actually useful, LSH employs a function family
$\mathcal{F}$ (a hash table) by concatenating $M$ hash functions from
$\mathcal{H}$, i.e.,
$\mathcal{F}=\\{f(\boldsymbol{v}):\mathbb{R}^{d}\rightarrow\mathbb{N}^{M}\\}$,
such that each $f\in\mathcal{F}$ can be represented as:
$f(\boldsymbol{v})=(h_{1}(\boldsymbol{v}),h_{2}(\boldsymbol{v}),\cdots,h_{M}(\boldsymbol{v}))$,
where $h_{i}\in\mathcal{H}~{}(1\leq i\leq M)$.

####  II-C2 Scalable Locality Sensitive Hashing

Figure 4: An example of an SLSH indexing structure.

Because traditional LSH (including E2LSH) deals with ANN for static data sets,
Scalable Locality Sensitive Hashing (SLSH) [31, 32] has been proposed for
dynamic data sets. In this study, we adopted the SLSH from Hu & Jiang [31],
which adjusts the original E2LSH in the following two ways:

  * •

Scalable hash family: SLSH extends the hash family $\mathcal{H}$ of E2LSH by
dynamically adjusting the value of $w$: If $\mathcal{H}(w)$ is a scalable hash
family, and $\forall\boldsymbol{v}\in\mathbb{R}^{d}$,
$\mathcal{H}(w)=\\{h(\boldsymbol{v},w):\mathbb{R}^{d}\rightarrow\mathbb{N}\\}$,
then
$\mathcal{H}(w)=\\{h_{1}(\boldsymbol{v},w_{1}),h_{2}(\boldsymbol{v},w_{2}),\cdots,h_{M}(\boldsymbol{v},w_{M})\\}$.

  * •

Scalable indexing structure: According to the scalable hash family, a scalable
hash table is designed as
$\mathcal{T}(\boldsymbol{w})=\\{t(\boldsymbol{v},\boldsymbol{w}):\mathbb{R}^{d}\rightarrow\mathbb{N}^{M}\\}$,
from which an individual hash table $t(\boldsymbol{v},\boldsymbol{w})$ can be
described as
$t(\boldsymbol{v},\boldsymbol{w})=(h_{1}(\boldsymbol{v},w_{1}),h_{2}(\boldsymbol{v},w_{2}),\cdots,h_{M}(\boldsymbol{v},w_{M}))$,
where $w_{1}>w_{2}>\cdots>w_{M}$. Unlike LSH, SLSH adopts a hierarchical
indexing structure to organize $M$ hash functions. SLSH introduces a new
parameter $m$ to configure the upper bound of the hash bucket capacity. If the
number of collision elements in a hash bucket exceeds the limit $m$ (this
ordinary hash bucket becomes a super hash bucket), then these elements will be
re-hashed to the next level of hash buckets. In other words, each ordinary
hash bucket stores data points, and each super hash bucket stores some
pointers to other hash buckets. Figure 4 presents an example of the scalable
indexing structure for SLSH, where it can be seen that different hash tables
may have different numbers of hash functions.

ART generates the new test cases based on a dynamic set of previously executed
test cases [13, 14]. Because SLSH is a scalable version of LSH, for dynamic
data sets, it is more suitable for ART. For ease of description, unless
explicitly stated otherwise, LSH in the following sections refers to SLSH.

##  III Proposed LSH-ART Approach

In this section, we propose a novel approach for ART STFCS based on the LSH
version of ANN: LSH based ART (LSH-ART). We first introduce the motivation of
this work, and then provide a framework to support LSH-ART. We also present
two detailed algorithms to implement the framework, and present their
complexity analyses.

Figure 5: A motivating example. Figure 6: LSH-ART Framework.

###  III-A A Motivating Example

As discussed in Sections II-B1 and II-B2, the computational overheads of both
FSCS and RRT depend strongly on the NN search process, especially when the
number of already executed test cases is large. This is because it is
necessary to consider all executed test cases in the NN search process. To
reduce the computational overheads, therefore, it is necessary to reduce the
number of executed test cases that need to be processed. One way to do this is
to sacrifice an amount of accuracy in the NN search, by adopting the ANN
search instead. We next present a motivating example to illustrate this.

Figure 5 shows a situation where eight test cases have already been executed,
$t_{1},t_{2},\cdots,t_{8}$. In FSCS (and somewhat similarly for RRT), nearest
(executed test case) neighbors for each of the four candidate test cases
($c_{1}$, $c_{2}$, $c_{3}$, and $c_{4}$) must be identified. To calculate the
NN of $c_{1}$, for example, the distance from $c_{1}$ to each executed test
case $t_{i}~{}(i=1,2,\cdots,8)$ is calculated, producing eight distances. With
an ANN (instead of exact NN) search, both $t_{1}$ and $t_{2}$ may be selected
as the (approximate) NN of $c_{1}$. (If $t_{1}$ is selected as the NN for
$c_{1}$, then the ANN search process is equivalent to the (exact) NN search
process.) Although $t_{2}$ is slightly farther away from $c_{1}$ than $t_{1}$,
it is still close. The $c_{2}$ candidate has a similar situation with $t_{3}$
and $t_{4}$, but the $c_{3}$ and $c_{4}$ candidates do not face this: $c_{3}$
and $c_{4}$ may have only one element for both NN and ANN search processes
($t_{5}$ for $c_{3}$; and $t_{6}$ for $c_{4}$), resulting in that element
being selected as the NN/ANN.

###  III-B Framework

Figure 6 shows the proposed LSH-ART framework, which consists of five
components: (1) Constructing random candidates; (2) Searching the hash bucket;
(3) Identifying the nearest neighbor (NN); (4) Determining a new test case;
and (5) Inserting the new test case into the LSH tree. We next explain each
component.

Component (1) involves constructing/selecting a random candidate (or some
random candidates) from the input domain. Component (2) consists of hashing
each random candidate in the corresponding ordinary hash bucket. The hashing
process of each candidate $c$ starts with the root of the LSH indexing
structure, and then checks its hash bucket type: If the current hash bucket
$\mathcal{B}$ is an ordinary hash bucket, $\mathcal{B}$ will be returned for
$c$ (i.e., $c$ should be included in $\mathcal{B}$); however, if $\mathcal{B}$
is a super hash bucket, then the hashing process is repeated to retrieve the
next levels, according to its hash function, until an ordinary hash bucket is
found for $c$.

For each candidate $c$, when an ordinary hash bucket $\mathcal{B}$ is
searched, it is believed that all elements in $\mathcal{B}$ are considered as
potential ANNs for $c$. Then, Component (3) identifies the NN within this hash
bucket $\mathcal{B}$ (compared with all executed test cases, however, this NN
is approximate). Component (4) then determines which candidate should be
selected as the next test case (i.e., the new test case), according to some
criterion. Once a new test case is determined, Component (5) inserts this test
case in the LSH indexing tree: If the corresponding ordinary hash bucket has
not exceeded its limit, then this new test case is directly inserted into the
hash bucket; otherwise, this ordinary hash bucket is promoted into a super
hash bucket (involving an updating process), and its elements are rehashed in
the ordinary hash buckets in the next level.

###  III-C Algorithms

In this study, we focus on the STFCS category of ART, proposing an STFCS
version of LSH-ART, LSH-based STFCS (LSH-STFCS). We first present the LSH-
STFCS algorithm, and then discuss two well-known implementations of STFCS ART
(FSCS [13] and RRT [24]). We then present the LSH-STFCS versions of FSCS and
RRT: LSH-based FSCS (LSH-FSCS); and LSH-based RRT (LSH-RRT).

####  III-C1 LSH-STFCS

1

Input : Input domain $\mathcal{D}$.

Output : Executed test cases $E$.

2

3$C\leftarrow\texttt{{EmptySet()}}$

4 $E\leftarrow\texttt{{EmptySet()}}$

5 $\mathcal{T}\leftarrow\texttt{{CreateHashBucket()}}$

6 $t\leftarrow\texttt{{ConstructCandidate(}}\mathcal{D}\texttt{{)}}$

7 Execute the test case $t$

8 $E\leftarrow\texttt{{Append(}}E,t\texttt{{)}}$

9

10while  _The stopping condition is not satisfied_ do

11 $\mathcal{T}\leftarrow\texttt{{InsertTest(}}\mathcal{T},t\texttt{{)}}$
$\triangleright$ Component (5)

12
$C\leftarrow\bigcup\\{\texttt{{ConstructCandidate(}}\mathcal{D}\texttt{{)}}\\}$
$\triangleright$ Component (1)

13 $S\leftarrow\texttt{{EmptySet()}}$

14

15 foreach  _$c\in C$_ do

16
$\mathcal{B}\leftarrow\texttt{{SearchHashBucket(}}\mathcal{T},c\texttt{{)}}$
$\triangleright$ Component (2)

17 $s\leftarrow\texttt{{IdentifyNN(}}\mathcal{B},c\texttt{{)}}$
$\triangleright$ Component (3)

18 $S\leftarrow S\bigcup\\{{s}\\}$

19

20 end foreach

21

22 $t\leftarrow\texttt{{DetermineNewTest(}}C,S\texttt{{)}}$ $\triangleright$
Component (4)

23 Execute the test case $t$

24 $E\leftarrow\texttt{{Append(}}E,t\texttt{{)}}$

25

26 end while

27return $E$

Algorithm 1 LSH-STFCS Pseudocode

Algorithm 1 shows a pseudocode description of LSH-STFCS. In the initialization
stage (Lines 1 to 3), $C$ is used to store random candidates, $E$ is used to
store the already-executed test cases, and $\mathcal{T}$ is an LSH table (or
an LSH indexing tree): $C$ and $E$ are initialized as empty sets; and
$\mathcal{T}$ is initialized as a null tree. The algorithm randomly constructs
a candidate $t$ from the input domain $\mathcal{D}$ as the next test case,
executes it, and then adds it into $E$ (Lines 4 and 5). The algorithm repeats
the generation process until the stopping condition is satisfied (Lines 6 to
18). When a random candidate $t$ is selected as the next test case, it is
inserted into the LSH indexing tree $\mathcal{T}$ using the function
$\texttt{{InsertTest(}}\mathcal{T},t\texttt{{)}}$ (Component (5) of the
framework) (Line 7). A set of random candidates are constructed from the input
domain $\mathcal{D}$ using the function
$\texttt{{ConstructCandidate(}}\mathcal{D}\texttt{{)}}$ (Component (1) of the
framework). The number of random candidates can be either fixed or flexible.
For each candidate $c$, the algorithm tries to find a potential ordinary hash
bucket $\mathcal{B}$ to store $c$, by searching the hash table $\mathcal{T}$
(function $\texttt{{SearchHashBucket(}}\mathcal{T},c\texttt{{)}}$ for
Component (2)). Then, the function
$\texttt{{IdentifyNN(}}\mathcal{B},c\texttt{{)}}$ identifies the NN of $c$ in
$\mathcal{B}$ (Component (3)). A new test case is determined, according to the
NN $s$ in $S$ of each candidate $c$ in $C$, using the function
$\texttt{{DetermineNewTest(}}C,S\texttt{{)}}$ (Component (4)).

1

Input : LSH indexing tree $\mathcal{T}$, candidate test case $c$.

Output : Hash bucket $\mathcal{B}$.

2

3$\mathcal{B}\leftarrow\mathcal{T}$

4 $flag\leftarrow\texttt{true}$

5

6while  _$flag$_ do

7 $flag\leftarrow\texttt{{IsSuperBucket(}}\mathcal{B}\texttt{{)}}$

8

9 if  _$flag$_ then

10 $\mathcal{B}\leftarrow\texttt{{GetHashBucket(}}\mathcal{B},c\texttt{{)}}$

11

12 else

13 $flag\leftarrow\texttt{false}$

14

15 end if

16

17 end while

18return $\mathcal{B}$

Algorithm 2 $\texttt{{SearchHashBucket(}}\mathcal{T},c\texttt{{)}}$

1

Input : Ordinary hash bucket $\mathcal{B}$, random candidate $c$.

Output : Nearest neighbor $s$.

2

3$\delta\leftarrow MaxValue$

4

5foreach  _$e\in\mathcal{B}$_ do

6 $l\leftarrow dist(e,c)$

7 if  _$l <\delta$_ then

8 $\delta\leftarrow l$

9 $s\leftarrow e$

10

11 end if

12

13 end foreach

14return $s$

Algorithm 3 $\texttt{{IdentifyNN(}}\mathcal{B},c\texttt{{)}}$

1

Input : LSH indexing tree $\mathcal{T}$, test case $t$.

Output : Updated LSH indexing tree $\mathcal{T}$.

2

3$\mathcal{B}\leftarrow\texttt{{SearchHashBucket(}}\mathcal{T},t\texttt{{)}}$

4

5$\mathcal{B}^{\prime}\leftarrow\mathcal{B}$

6 if  _$|\mathcal{B}^{\prime}|+1 <m$_ then

7 /* $m$ is the capacity of the ordinary hash bucket */

8
$\mathcal{B}^{\prime}\leftarrow\texttt{{Append(}}\mathcal{B}^{\prime},t\texttt{{)}}$

9

10else

11 $\mathcal{B}^{\prime}\leftarrow\texttt{{CreateHashTable()}}$

12
$\mathcal{B}^{\prime}\leftarrow\texttt{{HashElements(}}\mathcal{B}^{\prime},\mathcal{B}\texttt{{)}}$

13

14 end if

15$\mathcal{T}\leftarrow\texttt{{ReplaceHashBucket(}}\mathcal{T},\mathcal{B}^{\prime},\mathcal{B}\texttt{{)}}$

16

17return $\mathcal{T}$

Algorithm 4 $\texttt{{InsertTest(}}\mathcal{T},t\texttt{{)}}$

Because Components (1) and (4) can be implemented using different strategies,
we discuss them separately in the following sections. Here, we discuss the
common components, Components (2), (3), and (5) (the functions
$\texttt{{SearchHashBucket(}}\mathcal{T},c\texttt{{)}}$,
$\texttt{{IdentifyNN(}}\mathcal{B},c\texttt{{)}}$, and
$\texttt{{InsertTest(}}\mathcal{T},t\texttt{{)}}$). Algorithm 2 contains the
pseudocode for the function
$\texttt{{SearchHashBucket(}}\mathcal{T},c\texttt{{)}}$: The algorithm
repeatedly checks the hash bucket by hashing the candidate test case $c$ until
an ordinary hash bucket is found, in which $c$ will be stored. Algorithm 3 has
the implementation of the function
$\texttt{{IdentifyNN(}}\mathcal{B},c\texttt{{)}}$, which is used to identify
the nearest neighbor in an ordinary hash bucket $\mathcal{B}$ of a candidate
$c$, by calculating the distances between $c$ and each element
$e\in\mathcal{B}$.

Algorithm 4 lists the pseudocode for the function
$\texttt{{InsertTest(}}\mathcal{T},t\texttt{{)}}$, which starts by finding the
ordinary hash bucket $\mathcal{B}$ for $t$, using the function
$\texttt{{SearchHashBucket(}}\mathcal{T},t\texttt{{)}}$. The algorithm then
checks whether or not $\mathcal{B}$ needs to be updated, according to its
capacity limit threshold $m$ (defined in advance). If $\mathcal{B}$ is not
already at capacity, then $t$ is inserted directly; otherwise, $\mathcal{B}$
is promoted into a super hash bucket, and its elements are re-hashed into
ordinary hash buckets. Finally, the original $\mathcal{B}$ is replaced in
$\mathcal{T}$.

####  III-C2 LSH-FSCS

To maintain the failure-finding benefits of the original FSCS, LSH-FSCS keeps
the main FSCS processes, changing only those related to storing previously-
executed test cases, and searching for each candidate’s NN. Accordingly, the
LSH-FSCS Component (1) involves construction of the fixed number ($k$) of
randomly-generated candidates from the input domain (according to uniform
distribution). The LSH-FSCS Component (4) selects as the next test case that
candidate $c$ whose distance to its NN is greatest, in terms of Eq. (1).

####  III-C3 LSH-RRT

As with LSH-FSCS, LSH-RRT also retains the core original processes of RRT,
changing only how executed test cases are stored, and how the NNs for each
candidate are identified. As discussed in Section II-B2, RRT checks successive
randomly-generated candidates to determine whether or not they satisfy the
selection criteria, in terms of Eq. (2). In other words, RRT’s generation of
the next test case requires the construction and checking of a flexibly-sized
set of random candidates. More specifically, LSH-RRT uses Component (1) to
construct a random candidate and then Component (4) to check whether or not it
is valid. This process is repeated until a satisfactory new test case is
generated.

###  III-D Complexity Analysis

This section presents a brief investigation of the LSH-ART time and space
complexity, through a formal mathematical analysis. For ease of description,
$n$ denotes the number of $d$-dimensional test cases to be generated, and
$\mu_{n}$ is an upper bound of the number of hash functions used to generate
the $n$ test cases. As discussed by Hu & Jiang [31], $\mu_{n}$ is generally
equal to $\log(n)$. In addition, $\psi_{n}$ denotes the depth of the LSH
indexing tree when generating the $n$ test cases, where $\psi_{n}\leq\mu_{n}$.
Finally, an analysis of time and space complexity is given for different ART
implementations.

TABLE I: Comparisons of Time and Space Complexity Among Different Implementations for ART Complexity | Version | Different ART Implementations
---|---|---
Original | Forgetting | Distance-aware Forgetting | KD-tree | LSH
Time | FSCS | $O(k\cdot d\cdot n^{2})$ | $O(k\cdot d\cdot\lambda\cdot n)$ | $O(k\cdot\tau\cdot 3^{d}\cdot n)$ |  $O(k\cdot d^{2}\cdot n\cdot\log n)$* |  $O(k\cdot n\cdot\log n)$*
RRT | $O(d\cdot n^{2}\cdot\log n)$ | $O(d\cdot\lambda\cdot\log\lambda\cdot n)$ | $O(\log(\tau\cdot 3^{d})\cdot\tau\cdot 3^{d}\cdot n)$ |  $O(d^{2}\cdot n\cdot\log n\cdot\log(d^{2}\cdot\log n))$* |  $O(\log m\cdot n\cdot\log n)$*
Space | FSCS | $O(d\cdot n)$ | $O(d\cdot n)$ | $O(d\cdot 2^{d}\cdot n)$ | $O(d\cdot n)$ |  $O(n\cdot\log n)$*
RRT | $O(d\cdot n)$ | $O(d\cdot n)$ | $O(d\cdot 2^{d}\cdot n)$ | $O(d\cdot n)$ |  $O(n\cdot\log n)$*
* in the worst-case scenario.

####  III-D1 Time Complexity

The time complexity involved in generating the $i$-th ($1\leq i\leq n$) test
case from $k$ random candidates $C=\\{c_{1},c_{2},\cdots,c_{k}\\}$ using LSH-
ART is as follows. As discussed in Section III-C, each candidate $c\in C$
requires the following two steps that incur computational costs: (1) Searching
for the ordinary bucket $\mathcal{B}$ in the LSH indexing tree (or the LSH
table) to (potentially) store $c$; and (2) Identifying $c$’s NN in
$\mathcal{B}$. LSH-ART then needs to complete two further tasks: (3)
Determining the next test case $t$; and (4) Inserting $t$ into the hash table.

The worst case scenario for Step (1) is that the targeted ordinary bucket
$\mathcal{B}_{i}$ is in the $\psi_{i}$-th level (the deepest level) of the LSH
indexing tree, resulting in an $O(\psi_{i})$ order of time complexity for each
candidate. For Step (2), because each ordinary bucket $\mathcal{B}$ contains
at most $m$ previously-executed test cases, a maximum time complexity of
$O(d\times m)$ is needed to calculate the distance between each candidate and
the $m$ executed test cases, and a further complexity of $O(m)$ to identify
its NN. Therefore, a time complexity of $O(k\times(\psi_{i}+d\times m+m))$ is
required, for $k$ candidates, for (1) and (2). Step (3) involves LSH-ART
choosing an element from $k$ candidates as the next test case, resulting in a
time complexity of $O(k)$. For Step (4), LSH-ART requires a maximum time
complexity of $O(\psi_{i})$ to insert the new test case into the ordinary
bucket $\mathcal{B}$. If $\mathcal{B}_{i}$ exceeds its maximum capacity, then
it will be upgraded into a super bucket, and all elements will be re-hashed
into different ordinary buckets, resulting in a time complexity of $O(m)$. In
total, the worst time complexity for generating the $i$-th ($1\leq i\leq n$)
test case can be described as $O(k\times(\psi_{i}+d\times m+m)+k+\psi_{i}+m)$.

In conclusion, when generating $n$ test cases, the worst order of time
complexity of LSH-ART can be written as:

$\displaystyle O(\textrm{LSH-ART})$
$\displaystyle=O\Bigg{(}\sum_{i=1}^{n}{\Big{(}k\times(\psi_{i}+d\times
m+m)+k+\psi_{i}+m\Big{)}}\Bigg{)}$ $\displaystyle\leq
O\Bigg{(}\sum_{i=1}^{n}{\Big{(}k\times(\mu_{i}+d\times
m+m)+k+\mu_{i}+m\Big{)}}\Bigg{)}$ $\displaystyle\leq
O\Bigg{(}\sum_{i=1}^{n}{\Big{(}k\times(\log i+d\times m+m)+k+\log
i+m\Big{)}}\Bigg{)}$ $\displaystyle=O\Big{(}k\times(d\times
m+m+1)+m\Big{)}+O\Bigg{(}(k+1)\times\sum_{i=1}^{n}{\log i}\Bigg{)}$
$\displaystyle=O(k\times d\times m)+O\Big{(}k\times\log n!\Big{)}$
$\displaystyle<O(k\times d\times m)+O\Big{(}k\times n\times\log n\Big{)}$
$\displaystyle=O(k\times d\times m)+O(k\times n\times\log n).$ (9)

The input domain dimensionality ($d$) and the maximum size of the ordinary
bucket ($m$) are constants, set before testing begins. The number of random
candidates ($k$) is also a constant in LSH-FSCS, though not in LSH-RRT. As
explained by Mayer & Schneckenburger [44], however, the average number of
random candidates for RRT is probably logarithmic to the number of previously
executed test cases. Because the maximum size of each ordinary bucket is equal
to $m$, thus the LSH-RRT $k$ is, at most, approximately $\log m$, which can be
also considered a constant. In summary, therefore, the worst order of time
complexity of LSH-FSCS is $O(k\cdot n\cdot\log n)$, and that of LSH-RRT is
$O(\log m\cdot n\cdot\log n)$.

####  III-D2 Space Complexity

LSH-ART requires memory space to store (1) all $n$ executed test cases, (2)
all $k$ candidates, and (3) all hash buckets (both super and ordinary) of the
SLSH indexing structure. Obviously, the executed test cases need an order of
space complexity of $O(n\times d)$; while the candidate test cases need an
order of space complexity of $O(k\times d)$. For the hash buckets, in the
worst case scenario — when each ordinary hash bucket contains only one test
case, and all buckets are in the $\mu_{n}$-th level — the order of space
complexity is $O(n\times\psi_{n})$. Therefore, the worst order of space
complexity for LSH-ART can be described as:

$\displaystyle O(\textrm{LSH-ART})$ $\displaystyle=O(n\times d+k\times
d+n\times\psi_{n})$ $\displaystyle\leq O(n\times d+k\times d+n\times\mu_{n})$
$\displaystyle=O(n\times d+k\times d+n\times\log n)$ (10)

Because the input domain dimension $d$ is determined before LSH-ART is
applied, $d$ is a constant. In addition, $k$ is also a constant in both FSCS
and RRT versions of LSH-ART. Therefore, the worst order of LSH-ART space
complexity is $O(n\cdot\log n)$.

####  III-D3 Complexity Comparisons

The time complexity of some ART implementations has been examined in previous
studies [27, 44, 45, 46]. Chen et al. [45], for example, reported on the order
of time complexity of the original FSCS being equal to $O(n^{2})$, when
generating $n$ test cases. Mayer [44] showed the time complexity of the
original RRT to be of the order of $n^{2}\log n$. Mao et al. [27, 46] gave the
order of time complexity for FSCS with distance-aware forgetting as $O(n)$,
and for FSCS with KD-tree as $O(n\cdot\log n)$. To the best of our knowledge,
however, there are no time or space complexity analyses available for the
other ART implementations. In this paper, therefore, we provide an analysis of
time and space complexity for these ART implementations: Table I presents a
detailed comparison of these complexities, for different ART implementations,
when generating $n$ test cases. In the table, $d$ is the dimension of the
input domain; and $k$, $\lambda$, $\tau$, and $m$ the constant parameters.

##  IV Experimental Frameworks

In this section, we first present the research questions related to the
performance of our proposed approach, and then examine the experiments we
conducted to answer them, from the perspectives of testing effectiveness,
efficiency, and cost-effectiveness.

###  IV-A Research Questions

A goal of LSH-ART is to reduce the computational overheads of the original ART
(FSCS [13] and RRT [24]) methods. Therefore, examination of the test case
generation time is necessary. In addition to reducing the computational costs,
LSH-ART also aims to maintain comparable fault-detection, thus delivering a
high testing cost-effectiveness. The LSH-ART fault-detection performance,
thus, also needs to be examined, under different scenarios.

Unlike some other ART enhancements and variants, such as forgetting [26], LSH-
ART does not discard any test case information, and may thus achieve better
fault-detection, while maintaining comparable computational cost reductions.
Similarly, because LSH-ART implements ART with an ANN search, it should have
less computational overheads than an NN search (such as with a KD-tree ART, in
KDFC-ART [27]), while hopefully maintaining comparable fault-detection
effectiveness.

Based on this, we designed the following three research questions:

  * RQ1:

[Effectiveness] How effective is LSH-ART at identifying software failures?

    * RQ1.1:

How effective is LSH-ART at detecting the first software failure?

    * RQ1.2:

How effective is LSH-ART at triggering software failures when running a fixed
number of test cases?

  * RQ2:

[Efficiency] How efficient is LSH-ART at generating test cases?

  * RQ3:

[Cost-effectiveness] How cost-effective is LSH-ART at revealing software
failures?

For each research question, LSH-ART was compared with the original ART
algorithms and some enhanced variants.

###  IV-B Independent Variables

We focused on the test case generation methods and their parameters as the
independent variables.

####  IV-B1 Test Case Generation Methods

Because LSH-ART aims to enhance two well-known versions of STFCS ART, FSCS and
RRT, both LSH-FSCS and LSH-RRT were chosen for this variable; as were the
original FSCS and RRT (as baselines for comparisons). We also selected another
three types of enhanced variants of both FSCS and RRT [26, 27, 46]. The first
enhancement strategy was forgetting [26], which attempts to discard some
executed test cases during the test case generation process, to reduce
computation time. In this study, we considered two versions of forgetting,
Random Forgetting (RF) and Consecutive Retention (CR) [26]. When the number of
already-executed test cases exceeds a pre-defined parameter $\lambda$, RF
randomly selects $\lambda$ executed test cases for distance comparisons,
whereas CR uses only the most recent $\lambda$ executed test cases.

The second enhancement strategy is a Distance-aware forgetting strategy (DF)
[46], which tries to partition the input domain into some disjoint subdomains,
and then to discard some distance calculations to reduce the computational
overheads. The final enhancement strategy takes advantage of a KD-tree
structure to store the executed test cases (which corresponds to the KD-tree
strategy), thus speeding up the precise NN search.

Overall, for each of FSCS and RRT, in addition to the original ART strategy,
we also applied five others, resulting in six ART test case generation methods
in the experiments: We use ART, RF, CR, DF, KD, and LSH to represent these six
strategies. We also compared our proposed method with RT.

####  IV-B2 Test Case Generation Method Parameters

Each ART algorithm has a number of associated parameters, which are considered
as constants in the experiments. We used the recommended values for these
parameters as identified in their respective studies.

For all ART methods, because we used numerical input domains in this study,
the Euclidean distance was used to measure the distance between two test
cases. FSCS (both the original and its enhanced variants) constructs a fixed
number ($k$) of random candidates to generate each test case: As recommended
by Chen et al. [38], $k$ was set to 10. Similarly, RRT and its variants
require that the exclusion ratio, $R$ in Eq. (2), be set in advance: Following
previous studies [47, 48], $R$ was set to 0.75.

LSH-ART also has parameters that need to be set before testing, including the
quantization width $w$ and the hash bucket capacity $m$. The quantization
width $w$ should be neither very large nor very small — if $w$ is very large,
all data points could be assigned to the same hash bucket; however, if it is
very small, a large number of hash buckets could be created in the hash table,
potentially resulting in each bucket having only one data point. In this
study, we set the collision probability as $p=0.9$, and then made use of the
inverse of Eq. (8) to get the value of $\alpha$. If
$dist(\boldsymbol{q},\boldsymbol{v})$ is given, then the lower bound of $w$
can be calculated. For the lower bound of $w$ to be as large as possible,
$dist(\boldsymbol{q},\boldsymbol{v})$ should also be as large as possible,
which means that $\boldsymbol{q}$ and $\boldsymbol{v}$ are two data points
that are as far apart as possible in the input domain $\mathcal{D}$. In
addition, when an ordinary hash bucket is promoted into a super hash bucket,
all elements need to be re-hashed with a different $w$. To make the next level
of the hash function more powerful, $w$ should be decreased: $w_{i}>w_{j}$ for
$i<j$. Following previous studies [31], $w_{i+1}=w_{i}/2$ for any $i\geq 1$.

If the capacity of the ordinary hash bucket, $m$, is very large, then LSH-ART
degrades to the original ART; however, if it is very small, then data points
with a high collision probability may be assigned into different hash buckets.
Because of the lack of guidelines for how to choose an appropriate value of
$m$ [31], we conducted a simulation study to examine its impact on LSH-ART
performance, varying $m$ from 10 to 100 in increments of 10. We observed that
larger values of $m$ resulted in fewer test cases being required to reveal the
first failure (the F-measure), but with little difference for $m\geq 60$. We
therefore set $m=60$ in the experiments.

The forgetting strategy [26] also has few guidelines regarding the choice of
value for $\lambda$. However, because $\lambda$ restricts the number of
executed test cases used in distance calculations, it is similar to the LSH-
ART parameter $m$. To ensure fair comparisons, therefore, we also set
$\lambda=60$. Two parameters also need to be set for the distance-aware
forgetting strategy [46]: $p_{0}$ is the initial partition number in each
dimension; and $\tau$ is the pre-set threshold for the average number of test
cases in a cell. As suggested by Mao et al. [46], we set $p_{0}$ to 3, and
$\tau$ to 5. Because the DF strategy may not always provide an exact nearest
neighbor, due to the parameter configurations, it can be considered an ANN
approach. We choose the most efficient KD-tree strategy version [27], which,
through parameter design and configuration, can also implement an ANN search.

###  IV-C Dependent Variables

According to the research questions, there are three dependent variables,
relating to testing effectiveness; efficiency; and cost-effectiveness.

####  IV-C1 Testing Effectiveness

The dependent variable for RQ1 (for both RQ1.1 and RQ1.2) is the metric to
evaluate the fault-detection effectiveness.

(1) For RQ1.1, we adopted the F-measure [38], which is defined as the expected
number of test case executions required before detecting the first software
failure. When a software failure is identified, as explained by Chen et al.
[38], it is common to stop testing and commence the debugging process.
Therefore, F-measure is realistic from a practical testing perspective. In
addition, most ART approaches generally generate test cases one at a time
[14], which means that F-measure is an appropriate measure for evaluating ART.
Lower F-measure values indicate better testing performances.

Given a failure rate $\theta$, the F-measure of RT (according to uniform
distribution), is theoretically equal to $\theta^{-1}$ [38]. In this study, we
also use the F-ratio to denote the ratio of the F-measure for a method
$\mathcal{M}$ to RT’s theoretical F-measure, thus showing the F-measure
improvement of $\mathcal{M}$ over RT: An F-ratio of less than 1.0 indicates
that $\mathcal{M}$ requires fewer test cases than RT to detect the first
failure (i.e., has better testing effectiveness); in contrast, an F-ratio
greater than 1.0 indicates that RT performs better than $\mathcal{M}$.

(2) For RQ1.2, we adopted the P-measure [49], which is defined as the
probability of a given test set detecting at least one failure. Although the
P-measure may appear less practical than the F-measure, it has been widely
used in many testing scenarios, especially in automated software testing [50].
Another evaluation metric is the E-measure [49], which is defined as the
expected number of failures to be detected by a given test set. Similar to the
P-measure, the E-measure has also been applied to many automated software
testing scenarios [50]. However, because failure regions may tend to cluster
[15, 16, 17, 18, 19], higher E-measure values do not imply more faults or more
distinct failures [50]. Therefore, the P-measure may be a more appropriate
measure than the E-measure. Higher P-measure values indicate more effective
software-failure detection. If the total number of test sets is $N_{t}$ and
the number of test sets that identify at least one failure is $N_{f}$, then
the P-measure can be estimated as $N_{f}/N_{t}$ [50]. For RT, the expected
P-measure is equal to $1-(1-\theta)^{n}$ [37], where $n$ is the size of the
test set.

####  IV-C2 Testing Efficiency

The RQ2 dependent variable relates to the test case generation time, and
includes the time taken for both generation and execution of a certain number
of test cases.

####  IV-C3 Testing Cost-effectiveness

The RQ3 dependent variable needs to measure both the testing effectiveness and
the efficiency: As discussed in Huang et al. [14], the F-time — the time
required to detect the first failure — is a good measure of the ART cost-
effectiveness.

TABLE II: Subject Programs for the F-measure Evaluation Framework ID | Program | Size | Dimension |  Input Domain ($\mathcal{D}$) | Fault Type | Total | Failure Rate
---|---|---|---|---|---|---|---
(LOC) |  ($d$) | From | To | Faults |  ($\theta$)
P1 | airy | 43 | 1 | $-5000$ | $5000$ | CR | 1 | 0.000716
P2 | bessj0 | 28 | 1 | $-300000$ | $300000$ | AOR, ROR, SVR, CR | 5 | 0.001373
P3 | erfcc | 14 | 1 | $-30000$ | $30000$ | AOR, ROR, SVR, CR | 4 | 0.000574
P4 | probks | 22 | 1 | $-50000$ | $50000$ | AOR, ROR, SVR, CR | 4 | 0.000387
P5 | tanh | 18 | 1 | $-500$ | $500$ | AOR, ROR, SVR, CR | 4 | 0.001817
P6 | bessj | 99 | 2 | $(2,-1000)$ | $(300,15000)$ | AOR, ROR, CR | 4 | 0.000716
P7 | gammq | 106 | 2 | $(0,0)$ | $(1700,40)$ | ROR, CR | 4 | 0.000830
P8 | sncndn | 64 | 2 | $(-5000,-5000)$ | $(5000,5000)$ | SVR, CR | 5 | 0.001623
P9 | golden | 80 | 3 | $(-100,-100,-100)$ | $(60,60,60)$ | ROR, SVR, CR | 5 | 0.000550
P10 | plgndr | 36 | 3 | $(10,0,0)$ | $(500,11,1)$ | AOR, ROR, CR | 5 | 0.000368
P11 | cel | 49 | 4 | $(0.001,0.001,0.001,0.001)$ | $(1,300,10000,1000)$ | AOR, ROR, CR | 3 | 0.000332
P12 | el2 | 78 | 4 | $(0,0,0,0)$ | $(250,250,250,250)$ | AOR, ROR, SVR, CR | 9 | 0.000690
P13 | calDay | 37 | 5 | $(1,1,1,1,1800)$ | $(12,31,12,31,2200)$ | STD | 1 | 0.000632
P14 | complex | 68 | 6 | $(-20,-20,-20,-20,-20,-20)$ | $(20,20,20,20,20,20)$ | SVR | 1 | 0.000901
P15 | pntLinePos | 23 | 6 | $(-25,-25,-25,-25,-25,-25)$ | $(25,25,25,25,25,25)$ | CR | 1 | 0.000728
P16 | triangle | 21 | 6 | $(-25,-25,-25,-25,-25,-25)$ | $(25,25,25,25,25,25)$ | CR | 1 | 0.000713
P17 | line | 86 | 8 | $(-10,-10,-10,-10,-10,-10,-10,-10)$ | $(10,10,10,10,10,10,10,10)$ | ROR | 1 | 0.000303
P18 | pntTrianglePos | 68 | 8 | $(-10,-10,-10,-10,-10,-10,-10,-10)$ | $(10,10,10,10,10,10,10,10)$ | CR | 1 | 0.000141
P19 | twoLinePos | 28 | 8 | $(-15,-15,-15,-15,-15,-15,-15,-15)$ | $(15,15,15,15,15,15,15,15)$ | CR | 1 | 0.000133
P20 | calGCD | 26 | 10 | $(1,1,1,1,1,1,1,1,1,1)$ | $(1000,1000,1000,1000,1000,$ | AOR | 1 | NR*
$1000,1000,1000,1000,1000)$
P21 | nearestDistance | 24 | 10 | $(1,1,1,1,1,1,1,1,1,1)$ | $(15,15,15,15,15,$ | CR | 1 | 0.000256
$15,15,15,15,15)$
P22 | select | 117 | 11 | $(1,1,1,1,1,1,1,1,1,1,1)$ | $(100,100,100,100,100,100,$ | RSR, CR | 2 | NR*
$100,100,100,100,100)$
P23 | tcas | 182 | 12 | $(0,0,0,0,0,0,0,0,0,0,0,0)$ | $(1000,1,1,50000,1000,50000,$ | CR | 1 | NR*
$3,1000,1000,2,2,1)$
* NR indicates that the failure rate was not reported in the original paper.

###  IV-D Simulation Framework

We created a simulation framework to enable evaluation of our proposed
approach. This framework contains a number of configurable features,
including: the failure pattern; failure rate related to each failure pattern;
and the number of test cases in each test set (used for P-measure
evaluations).

####  IV-D1 Failure Pattern and Failure Rate

Within the input domain $\mathcal{D}$, a faulty program was simulated by
designating either a continuous region, or some disjoint regions. When a test
case was selected from inside such a region, a software failure was considered
to be triggered. The simulation framework, therefore, involves the setting up
of the failure pattern (the shape of the failure region(s)) and failure rate
$\theta$ (the size of the failure region(s)). The input domain dimensionality
$d$ must also be set in advance.

As discussed in Section II-A, Chan et al. [37] identified three common failure
patterns types: block; strip; and point (Figure 1). Following previous ART
studies [27, 46, 51, 52, 53, 54], we also used these patterns in our
simulation framework. Using a unit input domain ($\mathcal{D}$ was
$[0,1.0)^{d}$), the block pattern was simulated as a single hypercube randomly
constructed and located within $\mathcal{D}$. This was achieved by selecting a
random point and then extending the same length for each dimension (with
respect to $\theta$), producing, for example, a square in two dimensions, or a
cube in three dimensions. The strip pattern was simulated using a single strip
at any angle: As previously noted [27], because strips that are close to the
corners of the input domain result in “fat” but unrealistic strips, these
strips were excluded from the experiments. For the point pattern, 25 disjoint
equally-sized hypercubes were randomly generated within $\mathcal{D}$.
Representative values for $d$ and $\theta$ were selected based on previous ART
studies [27, 51], as follows:

  * •

Dimension ($d$): 1, 2, 3, 4, 5, and 10.

  * •

Failure rate ($\theta$): $1.0\times 10^{-2}$, $5.0\times 10^{-3}$, $2.0\times
10^{-3}$, $1.0\times 10^{-3}$, $5.0\times 10^{-4}$, $2.0\times 10^{-4}$, and
$1.0\times 10^{-4}$.

####  IV-D2 Number of Test Cases for P-measure Evaluations

Calculation of the P-measure requires that the number of test cases (denoted
$n$) in each test set $T$ be set in advance (i.e., $n=|T|$). As discussed by
Shahbazi et al. [50], a good choice of value for $n$ when using the P-measure
to analyze the test case generation approaches is the worst case according to
the standard error $SE$ (i.e., the maximum $SE$). This can be estimated as:

$SE=\frac{SD}{\sqrt{N_{t}}},$ (11)

where $SD$ is the standard deviation.

Because $N_{t}$ is a constant, the maximum $SD$ leads to the worst case of
$SE$. As reported by Chen et al. [55], the maximum $SD$ of the P-measure
calculation is $0.5$, and the expected P-measure $SD$ for RT can be
approximated as:

$SD\approx\sqrt{(1-\theta)^{n}-(1-\theta)^{2n}}.$ (12)

The value for $n$ can therefore be estimated using the following equation:

$n=\frac{\log(0.5)}{\log(1-\theta)}.$ (13)

Seven values of $\theta$ were selected for the simulations: $1.0\times
10^{-2}$; $5.0\times 10^{-3}$; $2.0\times 10^{-3}$; $1.0\times 10^{-3}$;
$5.0\times 10^{-4}$; $2.0\times 10^{-4}$; and $1.0\times 10^{-4}$. The
corresponding values of $n$, an integer, were calculated as: 69; 138; 346;
693; 1386; 3465; and 6931.

###  IV-E Empirical Study Framework

To further evaluate the proposed LSH approach, we conducted an empirical study
based on mutation testing [56]. This study made use of many independently-
produced subject programs.

Following previous ART studies [27, 50, 57], we adopted two different
evaluation frameworks, using the two different evaluation metrics (F-measure
and P-measure).

TABLE III: Subject Programs for the P-measure Evaluation Framework ID | Program | Size | Dimension |  Input Domain ($\mathcal{D}$) |  | Mutants
---|---|---|---|---|---|---
(LOC) |  ($d$) | From | To |  | Total Mutants | Equivalent Mutants | Mutants with Timeout | Easy Mutants | Appropriate Mutants
Q1 | Bessj | 131 | 2 | $(0,0)$ | $(4095,4095)$ |  | 1007 | 111 | 26 | 551 | 319
Q2 | Expint | 86 | 2 | $(0,0)$ | $(4095,4095)$ |  | 432 | 46 | 16 | 188 | 182
Q3 | Gammq | 89 | 2 | $(0,0)$ | $(4095,4095)$ |  | 258 | 0 | 37 | 213 | 8
Q4 | Remainder | 48 | 2 | $(0,0)$ | $(4095,4095)$ |  | 382 | 290 | 42 | 49 | 1
Q5 | Fisher | 71 | 3 | $(0,0,0)$ | $(255,255,255)$ |  | 615 | 0 | 16 | 599 | 0
Q6 | Triangle | 26 | 3 | $(0,0,0)$ | $(255,255,255)$ |  | 191 | 34 | 0 | 95 | 62
Q7 | Triangle2 | 41 | 3 | $(0,0,0)$ | $(255,255,255)$ |  | 333 | 47 | 0 | 118 | 168
Q8 | BubbleSort | 14 | 4 | $(0,0,0,0)$ | $(63,63,63,63)$ |  | 66 | 3 | 10 | 53 | 0
Q9 | Encoder | 65 | 4 | $(0,0,0,0)$ | $(63,63,63,63)$ |  | 283 | 123 | 0 | 160 | 0
Q10 | Median | 20 | 4 | $(0,0,0,0)$ | $(63,63,63,63)$ |  | 89 | 6 | 11 | 72 | 0
Q11 | Variance | 22 | 4 | $(0,0,0,0)$ | $(63,63,63,63)$ |  | 71 | 10 | 2 | 59 | 0

####  IV-E1 F-measure Evaluation Framework

The F-measure evaluation framework involved 23 subject programs, implemented
in Java, that have been used in previous studies [27, 38, 46, 47, 48]. Table
II presents the detailed information about these 23 programs. The programs
ranged in size from 14 to 182 lines of code (LOC), with their input domain
dimensions ranging from one to 12. As shown in the “Fault Types” column of
Table II, each program was seeded with one to nine faults using some common
mutation operators [56]: constant replacement (CR); arithmetic operator
replacement (AOR); relational operator replacement (ROR); scalar variable
replacement (SVR); statement deletion (STD); and return statement replacement
(RSR). The table also shows the input domain and failure rate data for each
program.

As noted by Huang et al. [14], the first 12 programs have been used in more
than 15 previous ART studies, and are considered to be the classic numeric-
input benchmark programs for ART. The other 11 programs, each of which has a
high-dimensional numeric input domain, can be considered new benchmark
programs. Although it may not be possible to collect all subject programs from
previous studies (due to a lack of available source code or other reasons),
our use of these 23 subject programs seems comprehensive and sufficient to
support the evaluation process. We directly adopted the program’s source code
and mutations, without any modification, in order to ensure fair comparisons.

####  IV-E2 P-measure Evaluation Framework

The P-measure evaluation framework used 11 Java subject programs that have
been used in the ART literature [50, 57]. In our study, we directly used the
original program source code, without any modification. Table III lists the
details of these programs.

The input domain for each program was constructed by assigning each dimension
as an integer range of $[0,2^{24/d}-1]$, leading to $2^{24}$ possible inputs —
for example, when $d=3$, the input domain is $[0,255]^{3}$. A total of 3727
mutants of the 11 subject programs were created using the well-known mutation
testing tool MuJava [58]. Exhaustive testing was conducted for each mutant:
Each mutant was executed with all $2^{24}$ different inputs. After the
exhaustive testing, the following mutants were excluded: (1) Equivalent
Mutants, whose outputs or behavior was identical to the original program for
all inputs; (2) Mutants with Timeout, whose execution did not terminate within
the time limit of 10 minutes; and (3) Easy Mutants, whose failure rates were
greater than $0.01$. This left a total of 780 Appropriate Mutants that were
used in the study [57].

We obtained all 3727 mutant programs used in the original study [57], and
reran the mutant exclusion process in our environment. Due to differences in
our experimental environment compared with the original study [57], 40 of the
780 mutants did not terminate within the time limit, and so we only used 740.
These 740 Appropriate Mutants were used, without any modification, to
calculate the P-measure of our proposed approach, and compare its performance
with the other ART approaches. The failure rate of the subject programs was
assumed to be unknown before testing. We set the test set sizes in the study
to range from 2 to 10, in intervals of 2; and from 10 to 100, in intervals of
5. Each approach was evaluated according to the P-measure for each test set
size.

TABLE IV: FSCS Version: Mean F-ratio Results and Statistical Pairwise Comparisons of LSH against other Methods for Block Pattern Simulations Dimension | Failure Rate | Methods |  | LSH
---|---|---|---|---
($d$) |  ($\theta$) | RT | ART | RF | CR | DF | KD | LSH |  | vs. RT | vs. ART | vs. RF | vs. CR | vs. DF | vs. KD
$d=1$ | $1.0\times 10^{-2}$ | 0.9866 | 0.5669 | 0.7012 | 0.6439 | 0.5706 | 0.5682 | 0.5564 |  | ✔ (0.61) | ❍ (0.51) | ✔ (0.53) | ❍ (0.52) | ❍ (0.51) | ❍ (0.51)
$5.0\times 10^{-3}$ | 0.9875 | 0.5712 | 0.8729 | 0.8312 | 0.5552 | 0.5586 | 0.5605 |  | ✔ (0.61) | ❍ (0.51) | ✔ (0.57) | ✔ (0.57) | ❍ (0.50) | ❍ (0.50)
$2.0\times 10^{-3}$ | 0.9574 | 0.5651 | 0.9718 | 0.9310 | 0.5687 | 0.5659 | 0.5533 |  | ✔ (0.61) | ❍ (0.51) | ✔ (0.61) | ✔ (0.60) | ❍ (0.51) | ❍ (0.51)
$1.0\times 10^{-3}$ | 1.0053 | 0.5605 | 0.9830 | 0.9956 | 0.5694 | 0.5570 | 0.5643 |  | ✔ (0.62) | ❍ (0.50) | ✔ (0.60) | ✔ (0.61) | ❍ (0.50) | ❍ (0.49)
$5.0\times 10^{-4}$ | 1.0160 | 0.5679 | 0.9913 | 0.9957 | 0.5532 | 0.5557 | 0.5546 |  | ✔ (0.62) | ❍ (0.51) | ✔ (0.62) | ✔ (0.61) | ❍ (0.50) | ❍ (0.50)
$2.0\times 10^{-4}$ | 0.9955 | 0.5527 | 0.9820 | 0.9775 | 0.5702 | 0.5530 | 0.5697 |  | ✔ (0.60) | ❍ (0.49) | ✔ (0.60) | ✔ (0.60) | ❍ (0.50) | ❍ (0.49)
$1.0\times 10^{-4}$ | 0.9899 | 0.5570 | 1.0025 | 1.0504 | 0.5629 | 0.5524 | 0.5671 |  | ✔ (0.60) | ❍ (0.49) | ✔ (0.61) | ✔ (0.62) | ❍ (0.50) | ❍ (0.49)
$d=2$ | $1.0\times 10^{-2}$ | 1.0152 | 0.6760 | 0.9123 | 0.9090 | 0.6719 | 0.6814 | 0.6828 |  | ✔ (0.57) | ❍ (0.50) | ✔ (0.54) | ✔ (0.54) | ❍ (0.50) | ❍ (0.50)
$5.0\times 10^{-3}$ | 1.0030 | 0.6716 | 0.9863 | 1.0185 | 0.6538 | 0.6532 | 0.6787 |  | ✔ (0.57) | ❍ (0.50) | ✔ (0.56) | ✔ (0.58) | ❍ (0.49) | ❍ (0.49)
$2.0\times 10^{-3}$ | 1.0227 | 0.6523 | 1.0651 | 1.0916 | 0.6390 | 0.6504 | 0.6596 |  | ✔ (0.58) | ❍ (0.50) | ✔ (0.59) | ✔ (0.60) | ❍ (0.49) | ❍ (0.50)
$1.0\times 10^{-3}$ | 1.0215 | 0.6456 | 1.0263 | 1.0642 | 0.6302 | 0.6359 | 0.6549 |  | ✔ (0.59) | ❍ (0.50) | ✔ (0.58) | ✔ (0.59) | ❍ (0.49) | ❍ (0.50)
$5.0\times 10^{-4}$ | 0.9954 | 0.6362 | 1.0706 | 1.0848 | 0.6300 | 0.6432 | 0.6706 |  | ✔ (0.57) | ❍ (0.49) | ✔ (0.58) | ✔ (0.59) | ❍ (0.48) | ❍ (0.49)
$2.0\times 10^{-4}$ | 0.9893 | 0.6289 | 1.0783 | 1.0780 | 0.6141 | 0.6354 | 0.6662 |  | ✔ (0.57) | ❍ (0.48) | ✔ (0.59) | ✔ (0.59) | ✖ (0.48) | ❍ (0.49)
$1.0\times 10^{-4}$ | 1.0004 | 0.6333 | 1.0506 | 1.0429 | 0.6363 | 0.6254 | 0.6666 |  | ✔ (0.58) | ❍ (0.50) | ✔ (0.59) | ✔ (0.59) | ❍ (0.50) | ❍ (0.49)
$d=3$ | $1.0\times 10^{-2}$ | 1.0325 | 0.8510 | 1.1764 | 1.1428 | 0.8461 | 0.8402 | 0.8659 |  | ❍ (0.52) | ❍ (0.50) | ✔ (0.56) | ✔ (0.55) | ❍ (0.50) | ❍ (0.50)
$5.0\times 10^{-3}$ | 0.9728 | 0.7827 | 1.2262 | 1.2463 | 0.8004 | 0.8069 | 0.8517 |  | ❍ (0.51) | ❍ (0.48) | ✔ (0.57) | ✔ (0.57) | ❍ (0.49) | ❍ (0.49)
$2.0\times 10^{-3}$ | 0.9796 | 0.7769 | 1.2688 | 1.2501 | 0.7563 | 0.7751 | 0.8337 |  | ✔ (0.52) | ❍ (0.49) | ✔ (0.59) | ✔ (0.58) | ✖ (0.48) | ❍ (0.49)
$1.0\times 10^{-3}$ | 1.0114 | 0.7567 | 1.2919 | 1.2824 | 0.7539 | 0.7298 | 0.8277 |  | ✔ (0.53) | ✖ (0.48) | ✔ (0.59) | ✔ (0.59) | ✖ (0.48) | ✖ (0.47)
$5.0\times 10^{-4}$ | 0.9982 | 0.7455 | 1.2486 | 1.2898 | 0.7388 | 0.7391 | 0.8310 |  | ✔ (0.53) | ✖ (0.48) | ✔ (0.58) | ✔ (0.58) | ✖ (0.47) | ✖ (0.47)
$2.0\times 10^{-4}$ | 1.0387 | 0.7215 | 1.2484 | 1.2674 | 0.7222 | 0.7233 | 0.8198 |  | ✔ (0.54) | ✖ (0.47) | ✔ (0.58) | ✔ (0.58) | ✖ (0.47) | ✖ (0.47)
$1.0\times 10^{-4}$ | 1.0088 | 0.6928 | 1.2068 | 1.2439 | 0.7138 | 0.7094 | 0.8023 |  | ✔ (0.54) | ✖ (0.47) | ✔ (0.58) | ✔ (0.58) | ✖ (0.47) | ✖ (0.47)
$d=4$ | $1.0\times 10^{-2}$ | 0.9774 | 1.0656 | 1.4415 | 1.4818 | 1.0279 | 1.0623 | 1.1108 |  | ✖ (0.44) | ❍ (0.49) | ✔ (0.55) | ✔ (0.55) | ✖ (0.48) | ❍ (0.50)
$5.0\times 10^{-3}$ | 0.9814 | 0.9743 | 1.5576 | 1.5498 | 0.9896 | 0.9670 | 1.0458 |  | ✖ (0.46) | ❍ (0.49) | ✔ (0.58) | ✔ (0.58) | ❍ (0.49) | ❍ (0.48)
$2.0\times 10^{-3}$ | 0.9999 | 0.9543 | 1.5852 | 1.6398 | 0.9268 | 0.9444 | 0.9929 |  | ❍ (0.48) | ❍ (0.50) | ✔ (0.60) | ✔ (0.60) | ❍ (0.49) | ❍ (0.50)
$1.0\times 10^{-3}$ | 0.9963 | 0.9239 | 1.5569 | 1.6138 | 0.8929 | 0.8920 | 0.9588 |  | ❍ (0.49) | ❍ (0.50) | ✔ (0.60) | ✔ (0.61) | ❍ (0.49) | ❍ (0.49)
$5.0\times 10^{-4}$ | 1.0128 | 0.8679 | 1.5486 | 1.5814 | 0.8831 | 0.8643 | 0.9724 |  | ❍ (0.49) | ✖ (0.48) | ✔ (0.59) | ✔ (0.60) | ✖ (0.48) | ✖ (0.47)
$2.0\times 10^{-4}$ | 0.9831 | 0.8373 | 1.4802 | 1.5168 | 0.8540 | 0.8654 | 0.9637 |  | ❍ (0.49) | ✖ (0.48) | ✔ (0.59) | ✔ (0.59) | ❍ (0.48) | ❍ (0.49)
$1.0\times 10^{-4}$ | 0.9981 | 0.8469 | 1.4976 | 1.5264 | 0.8222 | 0.8318 | 0.9643 |  | ❍ (0.50) | ✖ (0.48) | ✔ (0.59) | ✔ (0.59) | ✖ (0.48) | ✖ (0.47)
$d=5$ | $1.0\times 10^{-2}$ | 0.9850 | 1.3207 | 1.8729 | 1.9630 | 1.2984 | 1.3159 | 1.3484 |  | ✖ (0.40) | ❍ (0.50) | ✔ (0.56) | ✔ (0.57) | ❍ (0.49) | ❍ (0.50)
$5.0\times 10^{-3}$ | 0.9878 | 1.2490 | 1.9845 | 2.0510 | 1.2192 | 1.2001 | 1.2623 |  | ✖ (0.41) | ❍ (0.50) | ✔ (0.60) | ✔ (0.60) | ❍ (0.50) | ❍ (0.50)
$2.0\times 10^{-3}$ | 1.0600 | 1.1550 | 1.9957 | 2.0779 | 1.1506 | 1.1411 | 1.2049 |  | ✖ (0.43) | ❍ (0.49) | ✔ (0.59) | ✔ (0.61) | ❍ (0.49) | ❍ (0.49)
$1.0\times 10^{-3}$ | 0.9852 | 1.1074 | 2.0159 | 2.0654 | 1.1045 | 1.0399 | 1.1642 |  | ✖ (0.44) | ❍ (0.50) | ✔ (0.62) | ✔ (0.62) | ❍ (0.49) | ✖ (0.48)
$5.0\times 10^{-4}$ | 0.9949 | 1.0492 | 1.8778 | 2.0207 | 1.0523 | 1.0391 | 1.1114 |  | ✖ (0.45) | ❍ (0.49) | ✔ (0.61) | ✔ (0.63) | ❍ (0.49) | ❍ (0.49)
$2.0\times 10^{-4}$ | 1.0331 | 0.9593 | 2.0164 | 1.9705 | 1.0146 | 1.0069 | 1.0977 |  | ✖ (0.47) | ✖ (0.48) | ✔ (0.63) | ✔ (0.62) | ❍ (0.49) | ❍ (0.49)
$1.0\times 10^{-4}$ | 1.0146 | 0.9715 | 1.8741 | 1.8804 | 0.9739 | 0.9503 | 1.0856 |  | ✖ (0.48) | ❍ (0.48) | ✔ (0.61) | ✔ (0.61) | ❍ (0.48) | ✖ (0.48)
$d=10$ | $1.0\times 10^{-2}$ | 0.9950 | 3.9269 | 6.8133 | 7.2000 | 3.5567 | 3.8815 | 3.6978 |  | ✖ (0.17) | ✔ (0.52) | ✔ (0.63) | ✔ (0.63) | ✖ (0.47) | ❍ (0.52)
$5.0\times 10^{-3}$ | 0.9962 | 3.5159 | 7.9884 | 7.8587 | 3.4175 | 3.2698 | 3.3243 |  | ✖ (0.18) | ❍ (0.51) | ✔ (0.67) | ✔ (0.67) | ❍ (0.50) | ❍ (0.50)
$2.0\times 10^{-3}$ | 1.0482 | 3.1408 | 8.8285 | 8.4213 | 3.1135 | 2.9067 | 2.8955 |  | ✖ (0.22) | ✔ (0.52) | ✔ (0.72) | ✔ (0.72) | ❍ (0.52) | ❍ (0.51)
$1.0\times 10^{-3}$ | 0.9941 | 2.9168 | 9.1635 | 9.2257 | 2.7990 | 2.4650 | 2.5916 |  | ✖ (0.23) | ✔ (0.53) | ✔ (0.76) | ✔ (0.75) | ❍ (0.52) | ❍ (0.48)
$5.0\times 10^{-4}$ | 0.9913 | 2.6234 | 10.0563 | 9.8977 | 2.6057 | 2.3924 | 2.2903 |  | ✖ (0.26) | ✔ (0.54) | ✔ (0.77) | ✔ (0.77) | ✔ (0.53) | ❍ (0.51)
$2.0\times 10^{-4}$ | 0.9799 | 2.3712 | 9.7029 | 9.7759 | 2.4603 | 2.0818 | 2.1074 |  | ✖ (0.30) | ✔ (0.53) | ✔ (0.78) | ✔ (0.79) | ✔ (0.55) | ❍ (0.51)
$1.0\times 10^{-4}$ | 1.0215 | 2.2270 | 9.9951 | 9.7526 | 2.2100 | 1.9173 | 1.8729 |  | ✖ (0.33) | ✔ (0.55) | ✔ (0.80) | ✔ (0.80) | ✔ (0.55) | ❍ (0.51)
TABLE V: FSCS Version: Mean F-ratio Results and Statistical Pairwise Comparisons of LSH against other Methods for Strip Pattern Simulations Dimension | Failure Rate | Methods |  | LSH
---|---|---|---|---
($d$) |  ($\theta$) | RT | ART | RF | CR | DF | KD | LSH |  | vs. RT | vs. ART | vs. RF | vs. CR | vs. DF | vs. KD
$d=1$ | $1.0\times 10^{-2}$ | 0.9866 | 0.5669 | 0.7012 | 0.6439 | 0.5706 | 0.5682 | 0.5564 |  | ✔ (0.61) | ❍ (0.51) | ✔ (0.53) | ❍ (0.52) | ❍ (0.51) | ❍ (0.51)
$5.0\times 10^{-3}$ | 0.9875 | 0.5712 | 0.8729 | 0.8312 | 0.5552 | 0.5586 | 0.5605 |  | ✔ (0.61) | ❍ (0.51) | ✔ (0.57) | ✔ (0.57) | ❍ (0.50) | ❍ (0.50)
$2.0\times 10^{-3}$ | 0.9574 | 0.5651 | 0.9718 | 0.9310 | 0.5687 | 0.5659 | 0.5533 |  | ✔ (0.61) | ❍ (0.51) | ✔ (0.61) | ✔ (0.60) | ❍ (0.51) | ❍ (0.51)
$1.0\times 10^{-3}$ | 1.0053 | 0.5605 | 0.9830 | 0.9956 | 0.5694 | 0.5570 | 0.5643 |  | ✔ (0.62) | ❍ (0.50) | ✔ (0.60) | ✔ (0.61) | ❍ (0.50) | ❍ (0.49)
$5.0\times 10^{-4}$ | 1.0160 | 0.5679 | 0.9913 | 0.9957 | 0.5532 | 0.5557 | 0.5546 |  | ✔ (0.62) | ❍ (0.51) | ✔ (0.62) | ✔ (0.61) | ❍ (0.50) | ❍ (0.50)
$2.0\times 10^{-4}$ | 0.9955 | 0.5527 | 0.9820 | 0.9775 | 0.5702 | 0.5530 | 0.5697 |  | ✔ (0.60) | ❍ (0.49) | ✔ (0.60) | ✔ (0.60) | ❍ (0.50) | ❍ (0.49)
$1.0\times 10^{-4}$ | 0.9899 | 0.5570 | 1.0025 | 1.0504 | 0.5629 | 0.5524 | 0.5671 |  | ✔ (0.60) | ❍ (0.49) | ✔ (0.61) | ✔ (0.62) | ❍ (0.50) | ❍ (0.49)
$d=2$ | $1.0\times 10^{-2}$ | 0.9725 | 0.9168 | 0.9766 | 0.9572 | 0.9098 | 0.9234 | 0.9495 |  | ❍ (0.49) | ❍ (0.49) | ❍ (0.50) | ❍ (0.49) | ❍ (0.49) | ❍ (0.50)
$5.0\times 10^{-3}$ | 0.9979 | 0.9705 | 1.0244 | 0.9715 | 0.9361 | 0.9350 | 0.9248 |  | ❍ (0.51) | ✔ (0.52) | ✔ (0.52) | ❍ (0.51) | ❍ (0.50) | ❍ (0.51)
$2.0\times 10^{-3}$ | 0.9752 | 0.9676 | 0.9810 | 1.0029 | 0.9623 | 0.9654 | 0.9931 |  | ❍ (0.50) | ❍ (0.49) | ❍ (0.50) | ❍ (0.50) | ❍ (0.49) | ❍ (0.49)
$1.0\times 10^{-3}$ | 0.9782 | 0.9793 | 1.0154 | 0.9815 | 0.9570 | 0.9580 | 0.9749 |  | ❍ (0.49) | ❍ (0.50) | ❍ (0.51) | ❍ (0.49) | ❍ (0.49) | ❍ (0.50)
$5.0\times 10^{-4}$ | 1.0191 | 0.9717 | 1.0092 | 0.9900 | 0.9739 | 0.9418 | 0.9764 |  | ❍ (0.52) | ❍ (0.50) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51) | ❍ (0.49)
$2.0\times 10^{-4}$ | 1.0081 | 0.9281 | 0.9716 | 0.9982 | 0.9852 | 1.0017 | 0.9642 |  | ❍ (0.51) | ❍ (0.50) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.51)
$1.0\times 10^{-4}$ | 0.9997 | 0.9470 | 0.9923 | 1.0197 | 0.9836 | 0.9990 | 1.0098 |  | ❍ (0.49) | ❍ (0.49) | ❍ (0.49) | ❍ (0.50) | ❍ (0.49) | ❍ (0.49)
$d=3$ | $1.0\times 10^{-2}$ | 0.9971 | 0.9708 | 0.9912 | 1.0072 | 0.9794 | 0.9809 | 0.9811 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.50)
$5.0\times 10^{-3}$ | 1.0056 | 0.9797 | 0.9817 | 0.9843 | 0.9701 | 0.9908 | 0.9648 |  | ❍ (0.51) | ❍ (0.51) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.51)
$2.0\times 10^{-3}$ | 0.9676 | 0.9745 | 0.9876 | 0.9660 | 1.0026 | 0.9780 | 0.9956 |  | ❍ (0.49) | ❍ (0.49) | ❍ (0.49) | ❍ (0.49) | ❍ (0.50) | ❍ (0.49)
$1.0\times 10^{-3}$ | 1.0144 | 0.9898 | 0.9772 | 1.0029 | 1.0247 | 1.0006 | 1.0172 |  | ❍ (0.49) | ❍ (0.49) | ❍ (0.49) | ❍ (0.49) | ❍ (0.51) | ❍ (0.50)
$5.0\times 10^{-4}$ | 0.9956 | 0.9716 | 1.0279 | 0.9975 | 0.9912 | 1.0264 | 0.9938 |  | ❍ (0.50) | ❍ (0.49) | ❍ (0.50) | ❍ (0.50) | ❍ (0.49) | ❍ (0.50)
$2.0\times 10^{-4}$ | 0.9978 | 0.9962 | 1.0091 | 0.9973 | 1.0058 | 0.9914 | 1.0039 |  | ❍ (0.49) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.49) | ❍ (0.49)
$1.0\times 10^{-4}$ | 1.0174 | 0.9596 | 1.0408 | 0.9903 | 0.9869 | 0.9882 | 0.9862 |  | ❍ (0.50) | ❍ (0.49) | ❍ (0.51) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50)
$d=4$ | $1.0\times 10^{-2}$ | 0.9988 | 1.0162 | 1.0208 | 0.9697 | 0.9757 | 0.9903 | 1.0010 |  | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.48) | ❍ (0.49) | ❍ (0.50)
$5.0\times 10^{-3}$ | 1.0124 | 1.0008 | 1.0043 | 1.0321 | 0.9817 | 1.0180 | 1.0205 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.51) | ❍ (0.49) | ❍ (0.50)
$2.0\times 10^{-3}$ | 0.9726 | 0.9923 | 1.0148 | 0.9884 | 0.9891 | 1.0218 | 0.9917 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50)
$1.0\times 10^{-3}$ | 0.9894 | 0.9890 | 1.0207 | 0.9800 | 0.9846 | 1.0116 | 1.0092 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.49) | ❍ (0.50) | ❍ (0.50)
$5.0\times 10^{-4}$ | 1.0308 | 0.9687 | 0.9886 | 1.0097 | 1.0145 | 0.9970 | 1.0157 |  | ❍ (0.51) | ❍ (0.50) | ❍ (0.49) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50)
$2.0\times 10^{-4}$ | 0.9825 | 1.0148 | 0.9985 | 1.0044 | 0.9643 | 1.0402 | 1.0153 |  | ❍ (0.49) | ❍ (0.50) | ❍ (0.49) | ❍ (0.50) | ❍ (0.48) | ❍ (0.51)
$1.0\times 10^{-4}$ | 1.0068 | 0.9952 | 1.0348 | 1.0287 | 0.9936 | 0.9775 | 0.9921 |  | ❍ (0.51) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51) | ❍ (0.50) | ❍ (0.50)
$d=5$ | $1.0\times 10^{-2}$ | 0.9887 | 0.9786 | 1.0227 | 1.0102 | 0.9744 | 0.9994 | 1.0040 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.49) | ❍ (0.50)
$5.0\times 10^{-3}$ | 1.0094 | 0.9968 | 1.0336 | 1.0250 | 0.9856 | 0.9752 | 1.0187 |  | ❍ (0.50) | ❍ (0.49) | ❍ (0.51) | ❍ (0.50) | ❍ (0.49) | ❍ (0.49)
$2.0\times 10^{-3}$ | 1.0006 | 0.9949 | 0.9738 | 1.0227 | 0.9877 | 1.0202 | 1.0024 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.49) | ❍ (0.50) | ❍ (0.49) | ❍ (0.50)
$1.0\times 10^{-3}$ | 1.0341 | 0.9883 | 0.9986 | 1.0181 | 1.0171 | 1.0176 | 0.9711 |  | ❍ (0.52) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51)
$5.0\times 10^{-4}$ | 0.9774 | 0.9555 | 1.0036 | 0.9783 | 0.9675 | 1.0098 | 0.9890 |  | ❍ (0.50) | ❍ (0.49) | ❍ (0.50) | ❍ (0.49) | ❍ (0.49) | ❍ (0.51)
$2.0\times 10^{-4}$ | 1.0011 | 1.0053 | 1.0263 | 1.0087 | 1.0155 | 1.0029 | 1.0103 |  | ❍ (0.50) | ❍ (0.49) | ❍ (0.49) | ❍ (0.49) | ❍ (0.49) | ❍ (0.50)
$1.0\times 10^{-4}$ | 0.9943 | 0.9948 | 1.0262 | 1.0071 | 1.0197 | 1.0249 | 0.9946 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50)
$d=10$ | $1.0\times 10^{-2}$ | 0.9932 | 0.9707 | 0.9977 | 1.0079 | 1.0042 | 0.9787 | 1.0190 |  | ❍ (0.50) | ❍ (0.49) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.49)
$5.0\times 10^{-3}$ | 1.0100 | 0.9984 | 1.0350 | 1.0022 | 1.0010 | 1.0160 | 0.9844 |  | ❍ (0.51) | ❍ (0.50) | ❍ (0.52) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51)
$2.0\times 10^{-3}$ | 1.0275 | 1.0261 | 0.9959 | 1.0212 | 0.9956 | 0.9895 | 0.9949 |  | ❍ (0.51) | ❍ (0.50) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.50)
$1.0\times 10^{-3}$ | 1.0426 | 0.9743 | 0.9963 | 0.9930 | 1.0111 | 0.9690 | 0.9742 |  | ✔ (0.52) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.51) | ❍ (0.51)
$5.0\times 10^{-4}$ | 0.9836 | 1.0060 | 1.0262 | 0.9920 | 1.0117 | 1.0246 | 0.9932 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.51) | ❍ (0.51)
$2.0\times 10^{-4}$ | 0.9981 | 0.9584 | 1.0152 | 1.0521 | 0.9684 | 0.9861 | 0.9881 |  | ❍ (0.50) | ✖ (0.48) | ❍ (0.50) | ❍ (0.51) | ❍ (0.49) | ❍ (0.49)
$1.0\times 10^{-4}$ | 0.9779 | 1.0006 | 0.9798 | 1.0152 | 1.0007 | 0.9833 | 1.0020 |  | ❍ (0.49) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.49)
TABLE VI: FSCS Version: Mean F-ratio Results and Statistical Pairwise Comparisons of LSH against other Methods for Point Pattern Simulations Dimension | Failure Rate | Methods |  | LSH
---|---|---|---|---
($d$) |  ($\theta$) | RT | ART | RF | CR | DF | KD | LSH |  | vs. RT | vs. ART | vs. RF | vs. CR | vs. DF | vs. KD
$d=1$ | $1.0\times 10^{-2}$ | 1.0273 | 0.9467 | 1.0015 | 1.0352 | 0.9655 | 0.9861 | 0.9540 |  | ❍ (0.52) | ❍ (0.49) | ❍ (0.51) | ❍ (0.52) | ❍ (0.50) | ❍ (0.51)
$5.0\times 10^{-3}$ | 1.0057 | 0.9719 | 0.9949 | 0.9899 | 0.9797 | 0.9435 | 0.9583 |  | ❍ (0.51) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50)
$2.0\times 10^{-3}$ | 0.9869 | 0.9658 | 1.0017 | 0.9985 | 0.9690 | 0.9322 | 0.9510 |  | ❍ (0.51) | ❍ (0.51) | ❍ (0.51) | ❍ (0.50) | ❍ (0.51) | ❍ (0.49)
$1.0\times 10^{-3}$ | 0.9626 | 0.9598 | 0.9640 | 0.9839 | 0.9643 | 0.9548 | 0.9664 |  | ❍ (0.49) | ❍ (0.50) | ❍ (0.49) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50)
$5.0\times 10^{-4}$ | 1.0055 | 0.9628 | 0.9950 | 0.9913 | 0.9793 | 0.9728 | 0.9511 |  | ❍ (0.51) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.51)
$2.0\times 10^{-4}$ | 1.0111 | 0.9589 | 0.9974 | 0.9961 | 1.0095 | 0.9822 | 0.9637 |  | ❍ (0.51) | ❍ (0.49) | ❍ (0.51) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50)
$1.0\times 10^{-4}$ | 0.9984 | 0.9646 | 0.9920 | 1.0228 | 0.9803 | 0.9914 | 0.9570 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50)
$d=2$ | $1.0\times 10^{-2}$ | 1.0086 | 0.9883 | 1.0406 | 1.0322 | 0.9834 | 1.0103 | 0.9840 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50)
$5.0\times 10^{-3}$ | 1.0010 | 0.9961 | 1.0319 | 1.0702 | 0.9850 | 0.9760 | 0.9680 |  | ❍ (0.51) | ❍ (0.51) | ❍ (0.51) | ❍ (0.52) | ❍ (0.51) | ❍ (0.51)
$2.0\times 10^{-3}$ | 0.9962 | 0.9690 | 1.0361 | 1.0120 | 0.9676 | 0.9503 | 0.9723 |  | ❍ (0.51) | ❍ (0.50) | ❍ (0.52) | ❍ (0.51) | ❍ (0.50) | ❍ (0.50)
$1.0\times 10^{-3}$ | 0.9819 | 0.9597 | 1.0181 | 1.0534 | 0.9895 | 0.9788 | 0.9838 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.52) | ❍ (0.50) | ❍ (0.50)
$5.0\times 10^{-4}$ | 1.0150 | 0.9717 | 1.0103 | 1.0538 | 0.9509 | 0.9625 | 0.9691 |  | ❍ (0.51) | ❍ (0.50) | ❍ (0.50) | ❍ (0.52) | ❍ (0.50) | ❍ (0.50)
$2.0\times 10^{-4}$ | 1.0014 | 0.9281 | 1.0000 | 0.9966 | 0.9830 | 0.9628 | 0.9529 |  | ❍ (0.51) | ❍ (0.49) | ❍ (0.51) | ❍ (0.51) | ❍ (0.50) | ❍ (0.51)
$1.0\times 10^{-4}$ | 0.9906 | 0.9470 | 1.0122 | 1.0116 | 0.9661 | 0.9545 | 0.9594 |  | ❍ (0.51) | ❍ (0.50) | ❍ (0.51) | ❍ (0.51) | ❍ (0.50) | ❍ (0.49)
$d=3$ | $1.0\times 10^{-2}$ | 1.0367 | 1.1159 | 1.2016 | 1.1375 | 1.1287 | 1.1076 | 1.1265 |  | ✖ (0.48) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50)
$5.0\times 10^{-3}$ | 1.0138 | 1.0775 | 1.1561 | 1.1510 | 1.0471 | 1.0533 | 1.0681 |  | ✖ (0.48) | ❍ (0.50) | ❍ (0.51) | ❍ (0.51) | ❍ (0.50) | ❍ (0.49)
$2.0\times 10^{-3}$ | 1.0213 | 1.0194 | 1.1472 | 1.1205 | 1.0245 | 1.0334 | 1.0328 |  | ❍ (0.50) | ❍ (0.50) | ✔ (0.53) | ✔ (0.52) | ❍ (0.50) | ❍ (0.50)
$1.0\times 10^{-3}$ | 0.9892 | 1.0350 | 1.1095 | 1.0946 | 1.0296 | 1.0196 | 1.0223 |  | ❍ (0.48) | ❍ (0.50) | ❍ (0.51) | ❍ (0.51) | ❍ (0.50) | ❍ (0.50)
$5.0\times 10^{-4}$ | 1.0238 | 1.0248 | 1.0757 | 1.0796 | 1.0368 | 1.0196 | 1.0142 |  | ❍ (0.50) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51)
$2.0\times 10^{-4}$ | 1.0141 | 0.9972 | 1.0700 | 1.0921 | 1.0151 | 0.9875 | 1.0366 |  | ❍ (0.49) | ❍ (0.49) | ❍ (0.51) | ❍ (0.51) | ❍ (0.50) | ❍ (0.49)
$1.0\times 10^{-4}$ | 0.9890 | 0.9895 | 1.0464 | 1.0286 | 1.0035 | 0.9812 | 1.0238 |  | ❍ (0.49) | ❍ (0.49) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50)
$d=4$ | $1.0\times 10^{-2}$ | 0.9967 | 1.2852 | 1.4359 | 1.4677 | 1.2890 | 1.2843 | 1.3177 |  | ✖ (0.42) | ❍ (0.49) | ❍ (0.50) | ❍ (0.51) | ❍ (0.49) | ❍ (0.50)
$5.0\times 10^{-3}$ | 0.9748 | 1.2191 | 1.4129 | 1.4161 | 1.2087 | 1.2212 | 1.2178 |  | ✖ (0.44) | ❍ (0.50) | ✔ (0.53) | ✔ (0.53) | ❍ (0.50) | ❍ (0.50)
$2.0\times 10^{-3}$ | 0.9663 | 1.1811 | 1.3234 | 1.3089 | 1.1894 | 1.1706 | 1.1393 |  | ✖ (0.45) | ❍ (0.51) | ✔ (0.53) | ✔ (0.53) | ❍ (0.52) | ❍ (0.51)
$1.0\times 10^{-3}$ | 1.0181 | 1.1663 | 1.2912 | 1.2729 | 1.1578 | 1.1051 | 1.1385 |  | ✖ (0.47) | ❍ (0.51) | ✔ (0.53) | ✔ (0.52) | ❍ (0.51) | ❍ (0.50)
$5.0\times 10^{-4}$ | 1.0080 | 1.1139 | 1.2345 | 1.2336 | 1.1194 | 1.0910 | 1.0911 |  | ✖ (0.47) | ❍ (0.51) | ✔ (0.52) | ✔ (0.53) | ❍ (0.52) | ❍ (0.50)
$2.0\times 10^{-4}$ | 1.0178 | 1.1116 | 1.2083 | 1.2055 | 1.1003 | 1.0427 | 1.0602 |  | ❍ (0.49) | ❍ (0.52) | ✔ (0.53) | ✔ (0.53) | ❍ (0.51) | ❍ (0.50)
$1.0\times 10^{-4}$ | 1.0249 | 1.0555 | 1.2146 | 1.1905 | 1.0317 | 1.0585 | 1.0792 |  | ❍ (0.48) | ❍ (0.50) | ✔ (0.52) | ❍ (0.51) | ❍ (0.49) | ❍ (0.50)
$d=5$ | $1.0\times 10^{-2}$ | 1.0409 | 1.5487 | 1.7544 | 1.7187 | 1.4937 | 1.4976 | 1.5172 |  | ✖ (0.39) | ❍ (0.50) | ✔ (0.52) | ❍ (0.51) | ❍ (0.49) | ❍ (0.50)
$5.0\times 10^{-3}$ | 1.0082 | 1.4722 | 1.7652 | 1.7730 | 1.4504 | 1.3867 | 1.4570 |  | ✖ (0.39) | ❍ (0.50) | ✔ (0.53) | ✔ (0.54) | ❍ (0.50) | ❍ (0.49)
$2.0\times 10^{-3}$ | 1.0009 | 1.3422 | 1.6058 | 1.6745 | 1.3519 | 1.2768 | 1.3252 |  | ✖ (0.42) | ❍ (0.50) | ✔ (0.54) | ✔ (0.55) | ❍ (0.50) | ❍ (0.49)
$1.0\times 10^{-3}$ | 0.9944 | 1.2794 | 1.5522 | 1.5515 | 1.2854 | 1.2498 | 1.2532 |  | ✖ (0.43) | ❍ (0.51) | ✔ (0.54) | ✔ (0.54) | ❍ (0.51) | ❍ (0.50)
$5.0\times 10^{-4}$ | 0.9944 | 1.2439 | 1.4886 | 1.5262 | 1.2654 | 1.2318 | 1.2185 |  | ✖ (0.44) | ❍ (0.51) | ✔ (0.54) | ✔ (0.55) | ❍ (0.51) | ❍ (0.51)
$2.0\times 10^{-4}$ | 1.0149 | 1.2212 | 1.3994 | 1.4946 | 1.1679 | 1.1322 | 1.1783 |  | ✖ (0.45) | ❍ (0.51) | ✔ (0.54) | ✔ (0.55) | ❍ (0.50) | ❍ (0.49)
$1.0\times 10^{-4}$ | 1.0057 | 1.1281 | 1.3467 | 1.3691 | 1.1531 | 1.1334 | 1.1422 |  | ✖ (0.46) | ❍ (0.50) | ✔ (0.54) | ✔ (0.54) | ❍ (0.51) | ❍ (0.50)
$d=10$ | $1.0\times 10^{-2}$ | 1.0293 | 2.5080 | 3.0027 | 3.1504 | 2.1913 | 2.4785 | 2.4305 |  | ✖ (0.27) | ❍ (0.50) | ✔ (0.54) | ✔ (0.55) | ✖ (0.45) | ❍ (0.50)
$5.0\times 10^{-3}$ | 0.9749 | 2.7548 | 3.7525 | 3.6545 | 2.5803 | 2.7069 | 2.6010 |  | ✖ (0.23) | ❍ (0.51) | ✔ (0.57) | ✔ (0.56) | ✖ (0.48) | ❍ (0.51)
$2.0\times 10^{-3}$ | 1.0136 | 2.9162 | 4.4359 | 4.4004 | 2.7063 | 2.7202 | 2.5061 |  | ✖ (0.25) | ✔ (0.54) | ✔ (0.62) | ✔ (0.62) | ❍ (0.50) | ✔ (0.53)
$1.0\times 10^{-3}$ | 1.0355 | 2.8933 | 4.9950 | 4.8092 | 2.8142 | 2.5995 | 2.2507 |  | ✖ (0.28) | ✔ (0.56) | ✔ (0.68) | ✔ (0.67) | ✔ (0.55) | ✔ (0.53)
$5.0\times 10^{-4}$ | 1.0043 | 2.6884 | 5.2132 | 5.2301 | 2.6988 | 2.4270 | 2.0949 |  | ✖ (0.29) | ✔ (0.57) | ✔ (0.70) | ✔ (0.70) | ✔ (0.56) | ✔ (0.54)
$2.0\times 10^{-4}$ | 1.0045 | 2.5644 | 5.1711 | 5.1401 | 2.5497 | 2.2553 | 2.0251 |  | ✖ (0.30) | ✔ (0.56) | ✔ (0.71) | ✔ (0.70) | ✔ (0.56) | ✔ (0.53)
$1.0\times 10^{-4}$ | 1.0094 | 2.2833 | 4.9316 | 5.0699 | 2.3494 | 2.1527 | 1.8466 |  | ✖ (0.33) | ✔ (0.56) | ✔ (0.72) | ✔ (0.73) | ✔ (0.57) | ✔ (0.55)
TABLE VII: RRT Version: Mean F-ratio Results and Statistical Pairwise Comparisons of LSH against other Methods for Block Pattern Simulations Dimension | Failure Rate | Methods |  | LSH
---|---|---|---|---
($d$) |  ($\theta$) | RT | ART | RF | CR | DF | KD | LSH |  | vs. RT | vs. ART | vs. RF | vs. CR | vs. DF | vs. KD
$d=1$ | $1.0\times 10^{-2}$ | 0.9866 | 0.5980 | 0.6166 | 0.6004 | 0.7816 | 0.5945 | 0.6039 |  | ✔ (0.59) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ✔ (0.53) | ❍ (0.49)
$5.0\times 10^{-3}$ | 0.9875 | 0.5883 | 0.6048 | 0.5987 | 0.8748 | 0.6025 | 0.5975 |  | ✔ (0.60) | ❍ (0.49) | ❍ (0.51) | ❍ (0.50) | ✔ (0.56) | ❍ (0.51)
$2.0\times 10^{-3}$ | 0.9574 | 0.6074 | 0.5949 | 0.5949 | 0.9450 | 0.5887 | 0.6056 |  | ✔ (0.59) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ✔ (0.58) | ❍ (0.50)
$1.0\times 10^{-3}$ | 1.0053 | 0.5899 | 0.5938 | 0.5910 | 0.9820 | 0.5954 | 0.6020 |  | ✔ (0.60) | ❍ (0.49) | ❍ (0.50) | ❍ (0.49) | ✔ (0.59) | ❍ (0.50)
$5.0\times 10^{-4}$ | 1.0160 | 0.5851 | 0.6122 | 0.6097 | 0.9904 | 0.6028 | 0.6067 |  | ✔ (0.60) | ❍ (0.49) | ❍ (0.50) | ❍ (0.50) | ✔ (0.59) | ❍ (0.50)
$2.0\times 10^{-4}$ | 0.9955 | 0.5929 | 0.5821 | 0.6055 | 1.0392 | 0.5923 | 0.5991 |  | ✔ (0.59) | ❍ (0.49) | ❍ (0.49) | ❍ (0.50) | ✔ (0.61) | ❍ (0.49)
$1.0\times 10^{-4}$ | 0.9899 | 0.5955 | 0.5931 | 0.5975 | 0.9653 | 0.5947 | 0.6021 |  | ✔ (0.59) | ❍ (0.50) | ❍ (0.49) | ❍ (0.50) | ✔ (0.59) | ❍ (0.49)
$d=2$ | $1.0\times 10^{-2}$ | 1.0152 | 0.7202 | 0.8642 | 0.8270 | 0.7235 | 0.7159 | 0.7149 |  | ✔ (0.56) | ❍ (0.50) | ✔ (0.53) | ❍ (0.52) | ❍ (0.50) | ❍ (0.50)
$5.0\times 10^{-3}$ | 1.0030 | 0.7179 | 0.9279 | 0.8988 | 0.6940 | 0.7042 | 0.7212 |  | ✔ (0.56) | ❍ (0.50) | ✔ (0.54) | ✔ (0.54) | ❍ (0.49) | ❍ (0.50)
$2.0\times 10^{-3}$ | 1.0227 | 0.6840 | 0.9725 | 0.9590 | 0.6888 | 0.7129 | 0.7101 |  | ✔ (0.57) | ❍ (0.49) | ✔ (0.56) | ✔ (0.56) | ❍ (0.50) | ❍ (0.51)
$1.0\times 10^{-3}$ | 1.0215 | 0.6841 | 1.0039 | 1.0164 | 0.6755 | 0.6884 | 0.7237 |  | ✔ (0.57) | ❍ (0.49) | ✔ (0.57) | ✔ (0.57) | ❍ (0.49) | ❍ (0.49)
$5.0\times 10^{-4}$ | 0.9954 | 0.6907 | 1.0066 | 1.0156 | 0.6720 | 0.6901 | 0.7088 |  | ✔ (0.57) | ❍ (0.49) | ✔ (0.57) | ✔ (0.57) | ❍ (0.49) | ❍ (0.50)
$2.0\times 10^{-4}$ | 0.9893 | 0.6662 | 1.0295 | 0.9827 | 0.6896 | 0.6875 | 0.7147 |  | ✔ (0.56) | ✖ (0.48) | ✔ (0.57) | ✔ (0.55) | ❍ (0.49) | ❍ (0.49)
$1.0\times 10^{-4}$ | 1.0004 | 0.6813 | 1.0314 | 1.0009 | 0.6874 | 0.6823 | 0.7062 |  | ✔ (0.56) | ❍ (0.50) | ✔ (0.57) | ✔ (0.57) | ❍ (0.49) | ❍ (0.49)
$d=3$ | $1.0\times 10^{-2}$ | 1.0325 | 0.8283 | 0.9456 | 0.9156 | 0.8381 | 0.8242 | 0.8357 |  | ✔ (0.54) | ❍ (0.50) | ❍ (0.52) | ❍ (0.51) | ❍ (0.50) | ❍ (0.50)
$5.0\times 10^{-3}$ | 0.9728 | 0.7979 | 1.0052 | 0.9994 | 0.7917 | 0.7954 | 0.8254 |  | ✔ (0.53) | ❍ (0.49) | ✔ (0.54) | ✔ (0.54) | ❍ (0.49) | ❍ (0.49)
$2.0\times 10^{-3}$ | 0.9796 | 0.7746 | 1.0700 | 1.0638 | 0.8109 | 0.7788 | 0.8078 |  | ✔ (0.54) | ❍ (0.50) | ✔ (0.55) | ✔ (0.56) | ❍ (0.51) | ❍ (0.49)
$1.0\times 10^{-3}$ | 1.0114 | 0.7685 | 1.0826 | 1.0476 | 0.8052 | 0.7859 | 0.8207 |  | ✔ (0.54) | ❍ (0.49) | ✔ (0.56) | ✔ (0.55) | ❍ (0.51) | ❍ (0.49)
$5.0\times 10^{-4}$ | 0.9982 | 0.7583 | 1.0524 | 1.0589 | 0.7961 | 0.7811 | 0.8285 |  | ✔ (0.54) | ❍ (0.49) | ✔ (0.55) | ✔ (0.55) | ❍ (0.50) | ❍ (0.49)
$2.0\times 10^{-4}$ | 1.0387 | 0.7824 | 1.0300 | 1.0771 | 0.7759 | 0.7531 | 0.8273 |  | ✔ (0.55) | ❍ (0.49) | ✔ (0.54) | ✔ (0.55) | ❍ (0.49) | ❍ (0.48)
$1.0\times 10^{-4}$ | 1.0088 | 0.7988 | 1.0563 | 1.0318 | 0.7519 | 0.7617 | 0.8354 |  | ✔ (0.54) | ❍ (0.49) | ✔ (0.55) | ✔ (0.54) | ✖ (0.48) | ❍ (0.48)
$d=4$ | $1.0\times 10^{-2}$ | 0.9774 | 0.9447 | 1.0448 | 1.0315 | 0.9196 | 0.9338 | 0.9253 |  | ❍ (0.50) | ❍ (0.51) | ✔ (0.52) | ❍ (0.52) | ❍ (0.50) | ❍ (0.50)
$5.0\times 10^{-3}$ | 0.9814 | 0.9331 | 1.0313 | 1.0660 | 0.9437 | 0.9475 | 0.9215 |  | ❍ (0.51) | ❍ (0.51) | ❍ (0.52) | ✔ (0.53) | ❍ (0.51) | ❍ (0.52)
$2.0\times 10^{-3}$ | 0.9999 | 0.9026 | 1.1028 | 1.1364 | 0.8775 | 0.9064 | 0.8918 |  | ❍ (0.52) | ❍ (0.51) | ✔ (0.54) | ✔ (0.55) | ❍ (0.50) | ❍ (0.51)
$1.0\times 10^{-3}$ | 0.9963 | 0.8943 | 1.0935 | 1.1080 | 0.8876 | 0.8593 | 0.8991 |  | ❍ (0.52) | ❍ (0.51) | ✔ (0.55) | ✔ (0.55) | ❍ (0.50) | ❍ (0.50)
$5.0\times 10^{-4}$ | 1.0128 | 0.8713 | 1.1273 | 1.1265 | 0.8646 | 0.8730 | 0.9031 |  | ✔ (0.52) | ❍ (0.50) | ✔ (0.55) | ✔ (0.55) | ❍ (0.50) | ❍ (0.50)
$2.0\times 10^{-4}$ | 0.9831 | 0.8463 | 1.1189 | 1.0788 | 0.8514 | 0.8820 | 0.9045 |  | ❍ (0.51) | ❍ (0.49) | ✔ (0.55) | ✔ (0.54) | ❍ (0.49) | ❍ (0.50)
$1.0\times 10^{-4}$ | 0.9981 | 0.8315 | 1.1006 | 1.1278 | 0.8513 | 0.8776 | 0.9139 |  | ❍ (0.51) | ❍ (0.49) | ✔ (0.54) | ✔ (0.54) | ❍ (0.50) | ❍ (0.49)
$d=5$ | $1.0\times 10^{-2}$ | 0.9850 | 1.0252 | 1.1210 | 1.1198 | 1.0217 | 0.9899 | 0.9785 |  | ❍ (0.50) | ❍ (0.51) | ✔ (0.52) | ✔ (0.53) | ❍ (0.50) | ❍ (0.50)
$5.0\times 10^{-3}$ | 0.9878 | 0.9886 | 1.1123 | 1.1503 | 0.9918 | 1.0187 | 0.9831 |  | ❍ (0.49) | ❍ (0.50) | ✔ (0.52) | ✔ (0.53) | ❍ (0.50) | ❍ (0.51)
$2.0\times 10^{-3}$ | 1.0600 | 0.9914 | 1.1498 | 1.1779 | 1.0059 | 0.9910 | 0.9937 |  | ❍ (0.50) | ❍ (0.51) | ✔ (0.53) | ✔ (0.54) | ❍ (0.51) | ❍ (0.50)
$1.0\times 10^{-3}$ | 0.9852 | 0.9596 | 1.1743 | 1.1692 | 0.9665 | 0.9431 | 0.9777 |  | ❍ (0.50) | ❍ (0.50) | ✔ (0.54) | ✔ (0.54) | ❍ (0.50) | ❍ (0.49)
$5.0\times 10^{-4}$ | 0.9949 | 0.9791 | 1.1815 | 1.1504 | 0.9486 | 0.9517 | 0.9647 |  | ❍ (0.50) | ❍ (0.51) | ✔ (0.54) | ✔ (0.54) | ❍ (0.50) | ❍ (0.50)
$2.0\times 10^{-4}$ | 1.0331 | 0.9447 | 1.1383 | 1.1173 | 0.9263 | 0.9421 | 0.9825 |  | ❍ (0.50) | ❍ (0.49) | ✔ (0.52) | ✔ (0.53) | ❍ (0.49) | ❍ (0.49)
$1.0\times 10^{-4}$ | 1.0146 | 0.9325 | 1.1405 | 1.1221 | 0.9078 | 0.9349 | 0.9340 |  | ❍ (0.52) | ❍ (0.51) | ✔ (0.55) | ✔ (0.54) | ❍ (0.49) | ❍ (0.51)
$d=10$ | $1.0\times 10^{-2}$ | 0.9950 | 1.1288 | 1.1990 | 1.1422 | 1.1462 | 1.2120 | 1.1202 |  | ✖ (0.47) | ❍ (0.50) | ❍ (0.52) | ❍ (0.50) | ❍ (0.50) | ❍ (0.52)
$5.0\times 10^{-3}$ | 0.9962 | 1.2317 | 1.1873 | 1.1969 | 1.1818 | 1.1590 | 1.1456 |  | ✖ (0.47) | ❍ (0.52) | ❍ (0.50) | ❍ (0.52) | ❍ (0.51) | ❍ (0.50)
$2.0\times 10^{-3}$ | 1.0482 | 1.2133 | 1.1866 | 1.1957 | 1.2123 | 1.2319 | 1.0632 |  | ❍ (0.49) | ✔ (0.53) | ✔ (0.53) | ✔ (0.52) | ✔ (0.53) | ✔ (0.53)
$1.0\times 10^{-3}$ | 0.9941 | 1.2202 | 1.1741 | 1.2183 | 1.2018 | 1.1629 | 1.0581 |  | ✖ (0.48) | ✔ (0.53) | ❍ (0.51) | ✔ (0.53) | ✔ (0.53) | ✔ (0.52)
$5.0\times 10^{-4}$ | 0.9913 | 1.2265 | 1.1848 | 1.1951 | 1.0084 | 1.1418 | 1.0301 |  | ❍ (0.48) | ✔ (0.54) | ✔ (0.53) | ✔ (0.52) | ❍ (0.49) | ✔ (0.53)
$2.0\times 10^{-4}$ | 0.9799 | 1.1894 | 1.2283 | 1.2278 | 1.1738 | 1.0970 | 1.0254 |  | ❍ (0.49) | ✔ (0.54) | ✔ (0.54) | ✔ (0.54) | ✔ (0.54) | ❍ (0.51)
$1.0\times 10^{-4}$ | 1.0215 | 1.2076 | 1.2538 | 1.2383 | 1.2245 | 1.1028 | 0.9794 |  | ❍ (0.51) | ✔ (0.55) | ✔ (0.56) | ✔ (0.56) | ✔ (0.56) | ✔ (0.54)
TABLE VIII: RRT Version: Mean F-ratio Results and Statistical Pairwise Comparisons of LSH against other Methods for Strip Pattern Simulations Dimension | Failure Rate | Methods |  | LSH
---|---|---|---|---
($d$) |  ($\theta$) | RT | ART | RF | CR | DF | KD | LSH |  | vs. RT | vs. ART | vs. RF | vs. CR | vs. DF | vs. KD
$d=1$ | $1.0\times 10^{-2}$ | 0.9866 | 0.5980 | 0.6166 | 0.6004 | 0.7816 | 0.5945 | 0.6039 |  | ✔ (0.59) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ✔ (0.53) | ❍ (0.49)
$5.0\times 10^{-3}$ | 0.9875 | 0.5883 | 0.6048 | 0.5987 | 0.8748 | 0.6025 | 0.5975 |  | ✔ (0.60) | ❍ (0.49) | ❍ (0.51) | ❍ (0.50) | ✔ (0.56) | ❍ (0.51)
$2.0\times 10^{-3}$ | 0.9574 | 0.6074 | 0.5949 | 0.5949 | 0.9450 | 0.5887 | 0.6056 |  | ✔ (0.59) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ✔ (0.58) | ❍ (0.50)
$1.0\times 10^{-3}$ | 1.0053 | 0.5899 | 0.5938 | 0.5910 | 0.9820 | 0.5954 | 0.6020 |  | ✔ (0.60) | ❍ (0.49) | ❍ (0.50) | ❍ (0.49) | ✔ (0.59) | ❍ (0.50)
$5.0\times 10^{-4}$ | 1.0160 | 0.5851 | 0.6122 | 0.6097 | 0.9904 | 0.6028 | 0.6067 |  | ✔ (0.60) | ❍ (0.49) | ❍ (0.50) | ❍ (0.50) | ✔ (0.59) | ❍ (0.50)
$2.0\times 10^{-4}$ | 0.9955 | 0.5929 | 0.5821 | 0.6055 | 1.0392 | 0.5923 | 0.5991 |  | ✔ (0.59) | ❍ (0.49) | ❍ (0.49) | ❍ (0.50) | ✔ (0.61) | ❍ (0.49)
$1.0\times 10^{-4}$ | 0.9899 | 0.5955 | 0.5931 | 0.5975 | 0.9653 | 0.5947 | 0.6021 |  | ✔ (0.59) | ❍ (0.50) | ❍ (0.49) | ❍ (0.50) | ✔ (0.59) | ❍ (0.49)
$d=2$ | $1.0\times 10^{-2}$ | 0.9725 | 0.9090 | 0.9900 | 0.9470 | 0.9216 | 0.9171 | 0.9405 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50)
$5.0\times 10^{-3}$ | 0.9979 | 0.9319 | 0.9905 | 0.9899 | 0.9503 | 0.9491 | 0.9214 |  | ❍ (0.51) | ❍ (0.51) | ❍ (0.52) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51)
$2.0\times 10^{-3}$ | 0.9752 | 0.9534 | 1.0046 | 1.0268 | 0.9548 | 0.9643 | 0.9846 |  | ❍ (0.50) | ❍ (0.49) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.50)
$1.0\times 10^{-3}$ | 0.9782 | 0.9773 | 1.0061 | 1.0004 | 0.9870 | 0.9814 | 0.9769 |  | ❍ (0.49) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50)
$5.0\times 10^{-4}$ | 1.0191 | 0.9732 | 1.0066 | 1.0133 | 0.9733 | 0.9974 | 0.9976 |  | ❍ (0.51) | ❍ (0.49) | ❍ (0.50) | ❍ (0.50) | ❍ (0.49) | ❍ (0.50)
$2.0\times 10^{-4}$ | 1.0081 | 1.0110 | 0.9745 | 1.0100 | 1.0157 | 0.9727 | 0.9982 |  | ❍ (0.51) | ❍ (0.50) | ❍ (0.49) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50)
$1.0\times 10^{-4}$ | 0.9997 | 0.9945 | 0.9934 | 1.0075 | 1.0185 | 1.0189 | 0.9868 |  | ❍ (0.51) | ❍ (0.50) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51)
$d=3$ | $1.0\times 10^{-2}$ | 0.9971 | 0.9808 | 0.9588 | 0.9997 | 0.9508 | 0.9656 | 0.9492 |  | ❍ (0.51) | ❍ (0.51) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.51)
$5.0\times 10^{-3}$ | 1.0056 | 0.9770 | 0.9882 | 0.9742 | 0.9914 | 0.9683 | 1.0198 |  | ❍ (0.49) | ❍ (0.49) | ❍ (0.49) | ✖ (0.48) | ❍ (0.49) | ❍ (0.48)
$2.0\times 10^{-3}$ | 0.9676 | 0.9941 | 0.9621 | 0.9971 | 0.9869 | 0.9615 | 0.9950 |  | ❍ (0.49) | ❍ (0.49) | ❍ (0.48) | ❍ (0.50) | ❍ (0.49) | ❍ (0.50)
$1.0\times 10^{-3}$ | 1.0144 | 0.9990 | 0.9921 | 1.0066 | 0.9977 | 1.0153 | 0.9719 |  | ❍ (0.51) | ❍ (0.51) | ❍ (0.50) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51)
$5.0\times 10^{-4}$ | 0.9956 | 1.0040 | 0.9747 | 0.9777 | 1.0051 | 1.0044 | 0.9754 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.49) | ❍ (0.49) | ❍ (0.50) | ❍ (0.50)
$2.0\times 10^{-4}$ | 0.9978 | 0.9709 | 1.0180 | 1.0441 | 0.9521 | 1.0030 | 0.9823 |  | ❍ (0.50) | ❍ (0.49) | ❍ (0.51) | ❍ (0.51) | ❍ (0.49) | ❍ (0.50)
$1.0\times 10^{-4}$ | 1.0174 | 0.9931 | 1.0236 | 1.0117 | 1.0172 | 1.0076 | 0.9644 |  | ❍ (0.51) | ❍ (0.50) | ❍ (0.51) | ❍ (0.51) | ❍ (0.50) | ❍ (0.50)
$d=4$ | $1.0\times 10^{-2}$ | 0.9988 | 0.9750 | 1.0018 | 0.9913 | 0.9697 | 0.9652 | 0.9816 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50)
$5.0\times 10^{-3}$ | 1.0124 | 0.9576 | 0.9656 | 0.9866 | 0.9710 | 1.0171 | 1.0004 |  | ❍ (0.51) | ❍ (0.49) | ❍ (0.49) | ❍ (0.50) | ❍ (0.49) | ❍ (0.50)
$2.0\times 10^{-3}$ | 0.9726 | 0.9510 | 0.9742 | 0.9999 | 0.9851 | 1.0263 | 1.0048 |  | ❍ (0.49) | ❍ (0.48) | ❍ (0.49) | ❍ (0.50) | ❍ (0.50) | ❍ (0.51)
$1.0\times 10^{-3}$ | 0.9894 | 1.0437 | 1.0246 | 1.0071 | 0.9650 | 0.9939 | 0.9899 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.49) | ❍ (0.50)
$5.0\times 10^{-4}$ | 1.0308 | 1.0271 | 0.9724 | 0.9728 | 1.0037 | 0.9880 | 1.0030 |  | ❍ (0.51) | ❍ (0.51) | ❍ (0.49) | ❍ (0.49) | ❍ (0.50) | ❍ (0.50)
$2.0\times 10^{-4}$ | 0.9825 | 0.9962 | 0.9818 | 1.0191 | 0.9862 | 1.0016 | 0.9819 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.51)
$1.0\times 10^{-4}$ | 1.0068 | 1.0208 | 1.0009 | 0.9767 | 1.0035 | 0.9997 | 1.0149 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.49) | ❍ (0.49) | ❍ (0.49) | ❍ (0.49)
$d=5$ | $1.0\times 10^{-2}$ | 0.9887 | 0.9986 | 0.9879 | 0.9932 | 0.9920 | 0.9716 | 0.9660 |  | ❍ (0.51) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51)
$5.0\times 10^{-3}$ | 1.0094 | 1.0068 | 0.9915 | 0.9994 | 1.0121 | 0.9817 | 1.0091 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.49) | ❍ (0.50) | ❍ (0.50) | ❍ (0.49)
$2.0\times 10^{-3}$ | 1.0006 | 0.9735 | 0.9782 | 1.0120 | 0.9847 | 1.0022 | 0.9906 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.51)
$1.0\times 10^{-3}$ | 1.0341 | 0.9885 | 0.9844 | 0.9746 | 0.9961 | 1.0285 | 1.0118 |  | ❍ (0.51) | ❍ (0.50) | ❍ (0.50) | ❍ (0.49) | ❍ (0.50) | ❍ (0.50)
$5.0\times 10^{-4}$ | 0.9774 | 1.0077 | 1.0049 | 0.9923 | 0.9668 | 1.0090 | 0.9955 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.49) | ❍ (0.51)
$2.0\times 10^{-4}$ | 1.0011 | 0.9904 | 1.0334 | 1.0207 | 0.9840 | 0.9994 | 0.9925 |  | ❍ (0.50) | ❍ (0.49) | ❍ (0.51) | ❍ (0.50) | ❍ (0.49) | ❍ (0.50)
$1.0\times 10^{-4}$ | 0.9943 | 0.9962 | 0.9977 | 0.9795 | 1.0120 | 0.9992 | 1.0457 |  | ❍ (0.49) | ❍ (0.49) | ❍ (0.48) | ✖ (0.48) | ❍ (0.49) | ❍ (0.49)
$d=10$ | $1.0\times 10^{-2}$ | 0.9932 | 1.0299 | 0.9983 | 1.0008 | 0.9948 | 0.9652 | 0.9964 |  | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.50) | ❍ (0.49) | ❍ (0.49)
$5.0\times 10^{-3}$ | 1.0100 | 0.9628 | 1.0121 | 0.9767 | 0.9922 | 0.9922 | 1.0259 |  | ❍ (0.49) | ❍ (0.48) | ❍ (0.49) | ❍ (0.49) | ❍ (0.49) | ❍ (0.49)
$2.0\times 10^{-3}$ | 1.0275 | 1.0006 | 0.9734 | 1.0049 | 0.9936 | 0.9950 | 1.0047 |  | ❍ (0.51) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50)
$1.0\times 10^{-3}$ | 1.0426 | 1.0084 | 0.9520 | 1.0020 | 1.0122 | 1.0169 | 0.9936 |  | ❍ (0.51) | ❍ (0.50) | ❍ (0.48) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50)
$5.0\times 10^{-4}$ | 0.9836 | 1.0089 | 1.0002 | 0.9587 | 0.9772 | 0.9978 | 1.0186 |  | ❍ (0.49) | ❍ (0.50) | ❍ (0.49) | ✖ (0.48) | ❍ (0.49) | ❍ (0.49)
$2.0\times 10^{-4}$ | 0.9981 | 1.0016 | 0.9911 | 1.0199 | 1.0041 | 0.9652 | 1.0094 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.49) | ❍ (0.51) | ❍ (0.50) | ❍ (0.49)
$1.0\times 10^{-4}$ | 0.9779 | 0.9926 | 0.9985 | 1.0207 | 0.9734 | 1.0122 | 0.9813 |  | ❍ (0.49) | ❍ (0.50) | ❍ (0.51) | ❍ (0.51) | ❍ (0.50) | ❍ (0.51)
TABLE IX: RRT Version: Mean F-ratio Results and Statistical Pairwise Comparisons of LSH against other Methods for Point Pattern Simulations Dimension | Failure Rate | Methods |  | LSH
---|---|---|---|---
($d$) |  ($\theta$) | RT | ART | RF | CR | DF | KD | LSH |  | vs. RT | vs. ART | vs. RF | vs. CR | vs. DF | vs. KD
$d=1$ | $1.0\times 10^{-2}$ | 1.0273 | 0.9752 | 0.9478 | 0.9431 | 0.9779 | 0.9551 | 0.9780 |  | ❍ (0.51) | ❍ (0.50) | ❍ (0.50) | ❍ (0.49) | ❍ (0.49) | ❍ (0.50)
$5.0\times 10^{-3}$ | 1.0057 | 0.9291 | 0.9541 | 0.9514 | 0.9966 | 0.9353 | 0.9646 |  | ❍ (0.50) | ❍ (0.49) | ❍ (0.50) | ❍ (0.50) | ❍ (0.51) | ❍ (0.49)
$2.0\times 10^{-3}$ | 0.9869 | 0.9325 | 0.9359 | 0.9655 | 0.9724 | 0.9699 | 0.9639 |  | ❍ (0.50) | ❍ (0.49) | ❍ (0.49) | ❍ (0.50) | ❍ (0.49) | ❍ (0.50)
$1.0\times 10^{-3}$ | 0.9626 | 0.9805 | 0.9443 | 0.9666 | 0.9616 | 0.9611 | 0.9388 |  | ❍ (0.50) | ❍ (0.51) | ❍ (0.51) | ❍ (0.52) | ❍ (0.51) | ❍ (0.51)
$5.0\times 10^{-4}$ | 1.0055 | 0.9608 | 0.9877 | 0.9583 | 1.0172 | 0.9623 | 0.9444 |  | ❍ (0.51) | ❍ (0.51) | ❍ (0.52) | ❍ (0.51) | ❍ (0.52) | ❍ (0.51)
$2.0\times 10^{-4}$ | 1.0111 | 0.9541 | 0.9361 | 0.9716 | 1.0041 | 0.9504 | 0.9536 |  | ❍ (0.51) | ❍ (0.49) | ❍ (0.49) | ❍ (0.50) | ❍ (0.50) | ❍ (0.49)
$1.0\times 10^{-4}$ | 0.9984 | 0.9466 | 0.9872 | 0.9873 | 0.9755 | 0.9900 | 0.9315 |  | ❍ (0.51) | ❍ (0.50) | ❍ (0.51) | ❍ (0.51) | ❍ (0.50) | ❍ (0.51)
$d=2$ | $1.0\times 10^{-2}$ | 1.0086 | 0.9658 | 0.9802 | 1.0145 | 0.9489 | 1.0008 | 0.9792 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.51) | ❍ (0.49) | ❍ (0.51)
$5.0\times 10^{-3}$ | 1.0010 | 0.9719 | 0.9986 | 1.0036 | 0.9451 | 0.9853 | 0.9660 |  | ❍ (0.51) | ❍ (0.50) | ❍ (0.51) | ❍ (0.51) | ❍ (0.49) | ❍ (0.50)
$2.0\times 10^{-3}$ | 0.9962 | 0.9742 | 0.9878 | 1.0396 | 0.9872 | 0.9772 | 0.9728 |  | ❍ (0.51) | ❍ (0.51) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.51)
$1.0\times 10^{-3}$ | 0.9819 | 0.9886 | 1.0040 | 1.0297 | 0.9824 | 0.9487 | 0.9663 |  | ❍ (0.50) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51) | ❍ (0.50)
$5.0\times 10^{-4}$ | 1.0150 | 0.9723 | 0.9923 | 1.0142 | 0.9612 | 0.9556 | 0.9539 |  | ❍ (0.51) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.49) | ❍ (0.50)
$2.0\times 10^{-4}$ | 1.0014 | 0.9731 | 1.0059 | 1.0057 | 0.9322 | 0.9594 | 0.9711 |  | ❍ (0.51) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51) | ❍ (0.50) | ❍ (0.50)
$1.0\times 10^{-4}$ | 0.9906 | 0.9603 | 1.0060 | 1.0314 | 0.9872 | 0.9504 | 0.9412 |  | ❍ (0.51) | ❍ (0.51) | ❍ (0.51) | ✔ (0.52) | ❍ (0.52) | ❍ (0.50)
$d=3$ | $1.0\times 10^{-2}$ | 1.0367 | 1.0219 | 1.0412 | 1.0670 | 1.0134 | 1.0216 | 1.0176 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.49) | ❍ (0.49)
$5.0\times 10^{-3}$ | 1.0138 | 1.0440 | 1.0247 | 1.0487 | 1.0184 | 1.0263 | 0.9936 |  | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.50) | ❍ (0.51) | ❍ (0.51)
$2.0\times 10^{-3}$ | 1.0213 | 0.9850 | 1.0315 | 1.0176 | 0.9925 | 0.9689 | 0.9901 |  | ❍ (0.50) | ❍ (0.49) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.49)
$1.0\times 10^{-3}$ | 0.9892 | 1.0221 | 1.0221 | 1.0435 | 0.9682 | 0.9824 | 0.9838 |  | ❍ (0.49) | ❍ (0.51) | ❍ (0.50) | ❍ (0.51) | ❍ (0.49) | ❍ (0.50)
$5.0\times 10^{-4}$ | 1.0238 | 0.9991 | 1.0500 | 1.0154 | 0.9877 | 0.9652 | 1.0252 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.49) | ❍ (0.49) | ✖ (0.48)
$2.0\times 10^{-4}$ | 1.0141 | 0.9607 | 1.0042 | 1.0264 | 0.9891 | 0.9705 | 1.0219 |  | ❍ (0.49) | ✖ (0.48) | ❍ (0.49) | ❍ (0.49) | ❍ (0.49) | ❍ (0.48)
$1.0\times 10^{-4}$ | 0.9890 | 0.9762 | 0.9977 | 1.0409 | 0.9796 | 0.9970 | 1.0002 |  | ❍ (0.49) | ❍ (0.50) | ❍ (0.49) | ❍ (0.51) | ❍ (0.50) | ❍ (0.51)
$d=4$ | $1.0\times 10^{-2}$ | 0.9967 | 1.0678 | 1.0998 | 1.1509 | 1.0720 | 1.0746 | 1.0625 |  | ❍ (0.48) | ❍ (0.50) | ❍ (0.50) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51)
$5.0\times 10^{-3}$ | 0.9748 | 1.0599 | 1.1010 | 1.0935 | 1.0806 | 1.0347 | 1.0716 |  | ✖ (0.47) | ❍ (0.49) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.49)
$2.0\times 10^{-3}$ | 0.9663 | 1.0223 | 1.0958 | 1.0829 | 1.0151 | 1.0202 | 1.0326 |  | ✖ (0.48) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.49) | ❍ (0.50)
$1.0\times 10^{-3}$ | 1.0181 | 1.0113 | 1.0688 | 1.0993 | 0.9965 | 1.0234 | 0.9948 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.51) | ✔ (0.52) | ❍ (0.50) | ❍ (0.50)
$5.0\times 10^{-4}$ | 1.0080 | 1.0249 | 1.0582 | 1.0848 | 1.0252 | 1.0524 | 1.0052 |  | ❍ (0.49) | ❍ (0.51) | ❍ (0.51) | ✔ (0.52) | ❍ (0.51) | ❍ (0.51)
$2.0\times 10^{-4}$ | 1.0178 | 1.0225 | 1.0799 | 1.0437 | 1.0120 | 0.9975 | 1.0079 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.51) | ❍ (0.51) | ❍ (0.50) | ❍ (0.50)
$1.0\times 10^{-4}$ | 1.0249 | 1.0304 | 1.0421 | 1.0400 | 0.9892 | 1.0054 | 0.9887 |  | ❍ (0.51) | ❍ (0.52) | ❍ (0.51) | ❍ (0.51) | ❍ (0.50) | ❍ (0.50)
$d=5$ | $1.0\times 10^{-2}$ | 1.0409 | 1.1161 | 1.1479 | 1.1559 | 1.1543 | 1.0832 | 1.0783 |  | ❍ (0.48) | ❍ (0.50) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51) | ❍ (0.50)
$5.0\times 10^{-3}$ | 1.0082 | 1.1136 | 1.1604 | 1.1697 | 1.1245 | 1.0956 | 1.0525 |  | ❍ (0.48) | ❍ (0.51) | ✔ (0.52) | ✔ (0.52) | ✔ (0.52) | ❍ (0.51)
$2.0\times 10^{-3}$ | 1.0009 | 1.0492 | 1.1250 | 1.1274 | 1.0910 | 1.0676 | 1.0367 |  | ❍ (0.49) | ❍ (0.50) | ✔ (0.52) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51)
$1.0\times 10^{-3}$ | 0.9944 | 1.0946 | 1.1241 | 1.0804 | 1.0825 | 1.0471 | 1.0564 |  | ✖ (0.48) | ❍ (0.51) | ❍ (0.51) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50)
$5.0\times 10^{-4}$ | 0.9944 | 1.0901 | 1.0727 | 1.0824 | 1.0747 | 1.0728 | 1.0252 |  | ❍ (0.48) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51) | ❍ (0.51)
$2.0\times 10^{-4}$ | 1.0149 | 1.0481 | 1.0734 | 1.0863 | 1.0444 | 1.0263 | 0.9942 |  | ❍ (0.50) | ❍ (0.51) | ✔ (0.52) | ✔ (0.52) | ❍ (0.52) | ❍ (0.51)
$1.0\times 10^{-4}$ | 1.0057 | 1.0294 | 1.0417 | 1.0647 | 1.0523 | 1.0721 | 0.9689 |  | ❍ (0.51) | ❍ (0.52) | ❍ (0.52) | ✔ (0.52) | ✔ (0.53) | ✔ (0.53)
$d=10$ | $1.0\times 10^{-2}$ | 1.0293 | 1.0932 | 1.0835 | 1.0728 | 1.0878 | 1.0927 | 1.0668 |  | ❍ (0.49) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50)
$5.0\times 10^{-3}$ | 0.9749 | 1.1590 | 1.1157 | 1.1367 | 1.1079 | 1.1144 | 1.0490 |  | ✖ (0.48) | ✔ (0.52) | ❍ (0.51) | ❍ (0.52) | ❍ (0.51) | ❍ (0.51)
$2.0\times 10^{-3}$ | 1.0136 | 1.1648 | 1.1723 | 1.1066 | 1.1604 | 1.1462 | 1.0939 |  | ✖ (0.48) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.52) | ❍ (0.51)
$1.0\times 10^{-3}$ | 1.0355 | 1.1798 | 1.1443 | 1.1399 | 1.2147 | 1.1587 | 1.0866 |  | ✖ (0.48) | ❍ (0.51) | ❍ (0.50) | ❍ (0.51) | ✔ (0.53) | ❍ (0.51)
$5.0\times 10^{-4}$ | 1.0043 | 1.2300 | 1.1545 | 1.1450 | 1.2094 | 1.1782 | 1.0437 |  | ❍ (0.49) | ✔ (0.53) | ✔ (0.52) | ❍ (0.52) | ✔ (0.53) | ✔ (0.53)
$2.0\times 10^{-4}$ | 1.0045 | 1.2342 | 1.1471 | 1.1696 | 1.2764 | 1.1269 | 1.0318 |  | ❍ (0.48) | ✔ (0.54) | ✔ (0.53) | ✔ (0.52) | ✔ (0.55) | ✔ (0.52)
$1.0\times 10^{-4}$ | 1.0094 | 1.1967 | 1.1859 | 1.1300 | 1.2416 | 1.1405 | 0.9971 |  | ❍ (0.50) | ✔ (0.54) | ✔ (0.55) | ✔ (0.53) | ✔ (0.55) | ✔ (0.54)

###  IV-F Number of Runs and Statistical Analysis

Because ART involves random test case construction (which obviously involves
some randomness), it was necessary to repeat the experiments a number of times
to obtain a large enough sample size to ensure reliable statistical estimates.
There were different requirements for the F-measure and P-measure, which are
discussed in the following.

####  IV-F1 F-measure Settings

Arcuri and Briand [59] have recommended that experiments involving
randomization should be run at least 1000 times for each subject program: In
our study, therefore, there were 3000 runs for each approach under each
testing scenario (or experiment), resulting in 3000 sets of data points
(F-measure or F-time data) for further statistical analysis.

The two-tailed nonparametric Mann-Whitney U test (U-test) [60] has been
recommended for detecting statistical differences in interval-scale results
[59]. Both the F-measure and F-time generally have interval-scale results.
When comparing two ART approaches, therefore, we used the U-test to collect
$p$-values to identify significant differences in F-measure or F-time results
(at a significance level of 1%). Similarly, standardized effect size measures
were also used: Vargha and Delaney’s $\hat{\textrm{A}}_{12}$ statistic [61]
compares two approaches, $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$, as:

$\hat{\textrm{A}}_{12}(\mathcal{M}_{1},\mathcal{M}_{2})=(R_{1}/X-(X+1)/2)/Y,$
(14)

where $R_{1}$ is the rank sum of the first data group under comparison; $X$ is
the number of observations in the data sample of $\mathcal{M}_{1}$; and $Y$ is
the number of observations in the data sample of $\mathcal{M}_{2}$. Vargha and
Delaney’s $\hat{\textrm{A}}_{12}$ statistic shows the magnitude of improvement
of one ART approach over another —
$\hat{\textrm{A}}_{12}(\mathcal{M}_{1},\mathcal{M}_{2})$ indicates the
probability that algorithm $\mathcal{M}_{1}$ outperforms algorithm
$\mathcal{M}_{2}$. For example,
$\hat{\textrm{A}}_{12}(\mathcal{M}_{1},\mathcal{M}_{2})=0.68$ means that
$\mathcal{M}_{1}$ outperforms $\mathcal{M}_{2}$ with a probability of 68%. In
general, $\hat{\textrm{A}}_{12}(\mathcal{M}_{1},\mathcal{M}_{2})=0.5$ means
$\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ have equal performance;
$\hat{\textrm{A}}_{12}(\mathcal{M}_{1},\mathcal{M}_{2})>0.5$, means that
$\mathcal{M}_{1}$ is better than $\mathcal{M}_{2}$; and
$\hat{\textrm{A}}_{12}(\mathcal{M}_{1},\mathcal{M}_{2})<0.5$, means that
$\mathcal{M}_{2}$ is better than $\mathcal{M}_{1}$.

####  IV-F2 P-measure Settings

A number of test sets, $N_{t}$, is needed to calculate the P-measure. In our
P-measure simulations, following previous studies [50], we generated
$N_{t}=100$ distinct test sets for RT, ART, RF, CR, DF, KD, and LSH. Because
each failure pattern was randomly constructed within the input domain, we ran
the experiments 3000 times (resulting in 3000 different failure patterns). In
the empirical P-measure study, because the number of mutants was fixed (740),
more distinct test sets were needed ($N_{t}=10000$) than for the empirical
studies.

When the result of an experiment is dichotomous — i.e., either one finds a
solution to the problem (_success_) or one does not (_fail_) — it is
recommended to adopt the _Fisher exact test_ [62] has been recommended [59] to
measure whether or not two approaches are significantly different (at a
significance level of 1%). When calculating the P-measure, each fixed-size
test set is executed on the program, yielding a dichotomous result (the
software failure is triggered or not). The Fisher exact test was therefore
appropriate for measuring the significant differences in the P-measure
experiments. When calculating the standardized effect size measures, the odds
ratio $\psi$ [63] has been recommended for dichotomous results between the two
algorithms [59]. Its definition is as follows:

$\psi(\mathcal{M}_{1},\mathcal{M}_{2})=\frac{a_{1}+\rho}{n+\rho-
a_{1}}\Big{/}\frac{a_{2}+\rho}{n+\rho-a_{2}},$ (15)

where $a_{1}$ and $a_{2}$ are the number of success times for the algorithms
$\mathcal{M}_{1}$ and $\mathcal{M}_{2}$, respectively; $n$ is the number of
observations; and $\rho$ is any arbitrary positive constant (usually
$\rho=0.5$) used to avoid problems with zero occurrences. In general,
$\psi(\mathcal{M}_{1},\mathcal{M}_{2})=1.0$ indicates that there is no
difference between $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$;
$\psi(\mathcal{M}_{1},\mathcal{M}_{2})>1.0$ means that algorithm
$\mathcal{M}_{1}$ has higher chances of success (of identifying a failure)
than algorithm $\mathcal{M}_{1}$; and
$\psi(\mathcal{M}_{1},\mathcal{M}_{2})<1.0$ means that $\mathcal{M}_{2}$
outperforms $\mathcal{M}_{1}$.

##  V Experimental Results and Discussions

In this section, we provide the experimental results and statistical analyses
to answer the three research questions. In the analyses, when comparing two
methods $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$, we used the ❍ symbol to
indicate that there was no statistical difference between them (their
$p$-value was greater than 0.01); the ✔ symbol to indicate that
$\mathcal{M}_{1}$ was significantly better ($p$-value was less than 0.01, and
the effect size was greater than 0.50 for F-measure or 1.0 for P-measure); and
the ✖ symbol to indicate that $\mathcal{M}_{2}$ was significantly better
($p$-value was less than 0.01, and the effect size was less than 0.50 for
F-measure or 1.0 for P-measure). Each effect size value, i.e.,
$\hat{\textrm{A}}_{12}(\mathcal{M}_{1},\mathcal{M}_{2})$ for F-measure and
$\psi(\mathcal{M}_{1},\mathcal{M}_{2})$ for P-measure, is listed in the
parenthesis immediately following by the comparison symbol.

###  V-A Answer to RQ1.1: Effectiveness: F-measure Simulations

Tables IV to VI present the FSCS F-measure simulation results for block,
strip, and point patterns, respectively. Tables VII to IX show the
corresponding RRT F-measure simulation results. Each table presents the mean
F-ratio results and statistical pairwise comparisons of LSH against the other
methods.

####  V-A1 General LSH F-measure Observations

Based on all the F-measure simulation results (Tables IV to IX), we have the
following general observations for LSH:

  * (1)

Similar to the original ART algorithms (both FSCS and RRT), the F-measure of
LSH depends on many factors, including the failure pattern, dimension $d$, and
the failure rate $\theta$.

  * (2)

For a fixed failure rate $\theta$, the LSH F-ratio increases as $d$ increases,
irrespective of the failure pattern types. This indicates that LSH has poorer
fault-detection performance in higher dimensions.

  * (3)

For a fixed dimensionality $d$, as $\theta$ decreases, the LSH F-ratio
decreases for block and point patterns, but remains very similar for the strip
pattern.

####  V-A2 F-measure Simulation Observations: Block Pattern

Based on the block pattern F-measure simulation results (Tables IV and VII),
we have the following observations:

  * _(1)_

LSH vs. RT: The FSCS version of LSH has much better performance than RT when
$d$ is low ($d\leq 3$). As $d$ increases, however, LSH becomes inferior to RT,
regardless of failure rates. The RRT version of LSH also significantly
outperforms RT, when $d\leq 3$, but becomes similar to RT when $d\geq 4$, even
in the case of $d=10$. The statistical pairwise comparisons between LSH and RT
generally support these observations.

  * _(2)_

LSH vs. ART: The FSCS version of LSH is similar, or slightly worse, than ART
for $d\leq 5$, but significantly better for $d=10$. The RRT version of LSH has
very similar performance to ART when $d\leq 5$, and, when $d=10$, is similar
to, or slightly better than, ART. The $p$-values and effect size values
indicate that most comparisons between LSH and ART have no significant
differences.

  * _(3)_

LSH vs. RF: The F-ratio of the FSCS version of LSH is much less than that of
RF, in all cases, irrespective of failure rates and dimensions. The RRT
version of LSH, when $d=1$, has very similar performance to RF, and performs
significantly better than RF when $d\geq 2$. Compared with the FSCS version,
however, the F-ratio difference is relatively small.

  * _(4)_

LSH vs. CR: The comparisons between LSH (both FSCS and RRT) and CR are very
similar to LSH vs. RF: LSH shows significantly better fault-detection
capability than CR for FSCS, and similar, or better, for RRT.

  * _(5)_

LSH vs. DF: The FSCS version of LSH has similar or slightly worse performance
than DF when $d\leq 5$. However, for $d=10$, apart from one case with
$\theta=1.0\times 10^{-2}$, LSH has better performance than DF. For the RRT
version, when $d=1$ or $d=10$, the mean F-ratio differences between LSH and DF
are large, with LSH generally performing better. For other dimensions,
however, the mean F-ratio differences are relatively small, which means that
LSH and DF have very similar performances.

  * _(6)_

LSH vs. KD: The mean F-ratio values for the FSCS version of LSH are similar or
slightly greater than those of KD, in most cases. However, the differences are
relatively small. Similarly, the F-ratio differences between LSH-RRT and KD
are very small, when $d\leq 5$. When $d=10$, LSH is similar to, or slightly
better than, KD. Overall, the statistical comparisons show no significant
differences between LSH and KD in most cases.

TABLE X: F-measure Simulation Scenarios where LSH is Significantly Superior (✔), Indistinguishable (❍), or Significantly Inferior (✖), with respect to Failure Pattern ART Version | Failure Pattern |  | LSH vs. RT |  | LSH vs. ART |  | LSH vs. RF |  | LSH vs. CR |  | LSH vs. DF |  | LSH vs. KD
---|---|---|---|---|---|---|---|---|---|---|---|---|---
| ✔ | ❍ | ✖ |  | ✔ | ❍ | ✖ |  | ✔ | ❍ | ✖ |  | ✔ | ❍ | ✖ |  | ✔ | ❍ | ✖ |  | ✔ | ❍ | ✖
FSCS Version | Block Pattern |  | 19 | 7 | 16 |  | 6 | 28 | 8 |  | 42 | 0 | 0 |  | 41 | 1 | 0 |  | 3 | 29 | 10 |  | 0 | 34 | 8
Strip Pattern |  | 8 | 34 | 0 |  | 1 | 40 | 1 |  | 8 | 34 | 0 |  | 6 | 36 | 0 |  | 0 | 42 | 0 |  | 0 | 42 | 0
Point Pattern |  | 0 | 21 | 21 |  | 5 | 37 | 0 |  | 21 | 21 | 0 |  | 19 | 23 | 0 |  | 4 | 36 | 2 |  | 5 | 37 | 0
Sum |  | 27 | 62 | 37 |  | 12 | 105 | 9 |  | 71 | 55 | 0 |  | 66 | 60 | 0 |  | 7 | 107 | 12 |  | 5 | 113 | 8
RRT Version | Block Pattern |  | 22 | 17 | 3 |  | 5 | 36 | 1 |  | 30 | 12 | 0 |  | 30 | 12 | 0 |  | 11 | 30 | 1 |  | 4 | 38 | 0
Strip Pattern |  | 7 | 35 | 0 |  | 0 | 42 | 0 |  | 0 | 42 | 0 |  | 0 | 39 | 3 |  | 7 | 35 | 0 |  | 0 | 42 | 0
Point Pattern |  | 0 | 36 | 6 |  | 4 | 37 | 1 |  | 6 | 36 | 0 |  | 8 | 34 | 0 |  | 6 | 36 | 10 |  | 4 | 37 | 1
Sum |  | 29 | 88 | 9 |  | 9 | 115 | 2 |  | 36 | 90 | 0 |  | 38 | 85 | 3 |  | 24 | 101 | 1 |  | 8 | 117 | 1
FSCS + RRT | Block Pattern |  | 41 | 24 | 19 |  | 11 | 64 | 9 |  | 72 | 12 | 0 |  | 71 | 13 | 0 |  | 14 | 59 | 11 |  | 4 | 72 | 8
Strip Pattern |  | 15 | 69 | 0 |  | 1 | 82 | 1 |  | 8 | 76 | 0 |  | 6 | 75 | 3 |  | 7 | 77 | 0 |  | 0 | 84 | 0
Point Pattern |  | 0 | 57 | 27 |  | 9 | 74 | 1 |  | 27 | 57 | 0 |  | 27 | 57 | 0 |  | 10 | 72 | 12 |  | 9 | 74 | 1
Sum |  | 56 | 150 | 46 |  | 21 | 220 | 11 |  | 107 | 145 | 0 |  | 104 | 145 | 3 |  | 31 | 208 | 13 |  | 13 | 230 | 9
TABLE XI: F-measure Simulation Scenarios where LSH is Significantly Superior (✔), Indistinguishable (❍), or Significantly Inferior (✖), with respect to Dimension ART Version | Dimension |  | LSH vs. RT |  | LSH vs. ART |  | LSH vs. RF |  | LSH vs. CR |  | LSH vs. DF |  | LSH vs. KD
---|---|---|---|---|---|---|---|---|---|---|---|---|---
| ✔ | ❍ | ✖ |  | ✔ | ❍ | ✖ |  | ✔ | ❍ | ✖ |  | ✔ | ❍ | ✖ |  | ✔ | ❍ | ✖ |  | ✔ | ❍ | ✖
FSCS Version | $d=1$ |  | 14 | 7 | 0 |  | 0 | 21 | 0 |  | 14 | 7 | 0 |  | 12 | 9 | 0 |  | 0 | 21 | 0 |  | 0 | 21 | 0
$d=2$ |  | 7 | 14 | 0 |  | 1 | 20 | 0 |  | 8 | 13 | 0 |  | 7 | 14 | 0 |  | 0 | 21 | 0 |  | 0 | 21 | 0
$d=3$ |  | 5 | 14 | 2 |  | 0 | 17 | 4 |  | 8 | 13 | 0 |  | 8 | 13 | 0 |  | 0 | 16 | 5 |  | 0 | 17 | 4
$d=4$ |  | 0 | 17 | 4 |  | 0 | 18 | 3 |  | 13 | 8 | 0 |  | 12 | 9 | 0 |  | 0 | 18 | 3 |  | 0 | 19 | 2
$d=5$ |  | 0 | 7 | 14 |  | 0 | 20 | 1 |  | 14 | 7 | 0 |  | 13 | 8 | 0 |  | 0 | 21 | 0 |  | 0 | 19 | 2
$d=10$ |  | 1 | 6 | 14 |  | 11 | 9 | 1 |  | 14 | 7 | 0 |  | 14 | 7 | 0 |  | 7 | 11 | 3 |  | 5 | 16 | 0
Sum |  | 27 | 62 | 37 |  | 12 | 105 | 9 |  | 71 | 55 | 0 |  | 66 | 60 | 0 |  | 7 | 107 | 12 |  | 5 | 113 | 8
RRT Version | $d=1$ |  | 14 | 7 | 0 |  | 0 | 21 | 0 |  | 0 | 21 | 0 |  | 0 | 21 | 0 |  | 14 | 7 | 0 |  | 0 | 21 | 0
$d=2$ |  | 7 | 14 | 0 |  | 0 | 20 | 1 |  | 7 | 14 | 0 |  | 7 | 14 | 0 |  | 0 | 21 | 0 |  | 0 | 21 | 0
$d=3$ |  | 7 | 14 | 0 |  | 0 | 20 | 1 |  | 6 | 15 | 0 |  | 6 | 14 | 1 |  | 0 | 20 | 1 |  | 0 | 20 | 1
$d=4$ |  | 1 | 18 | 2 |  | 0 | 21 | 0 |  | 6 | 15 | 0 |  | 8 | 13 | 0 |  | 0 | 21 | 0 |  | 0 | 21 | 0
$d=5$ |  | 0 | 20 | 1 |  | 0 | 21 | 0 |  | 10 | 11 | 0 |  | 10 | 10 | 1 |  | 2 | 19 | 0 |  | 1 | 20 | 0
$d=10$ |  | 0 | 15 | 6 |  | 9 | 12 | 0 |  | 7 | 14 | 0 |  | 7 | 13 | 1 |  | 8 | 13 | 0 |  | 7 | 14 | 0
Sum |  | 29 | 88 | 9 |  | 9 | 115 | 2 |  | 36 | 90 | 0 |  | 38 | 85 | 3 |  | 24 | 101 | 1 |  | 8 | 117 | 1
FSCS + RRT | $d=1$ |  | 28 | 14 | 0 |  | 0 | 42 | 0 |  | 14 | 28 | 0 |  | 12 | 30 | 0 |  | 14 | 28 | 0 |  | 0 | 42 | 0
$d=2$ |  | 14 | 28 | 0 |  | 1 | 40 | 1 |  | 15 | 27 | 0 |  | 14 | 28 | 0 |  | 0 | 42 | 0 |  | 0 | 42 | 0
$d=3$ |  | 12 | 28 | 2 |  | 0 | 37 | 5 |  | 14 | 28 | 0 |  | 14 | 27 | 1 |  | 0 | 36 | 6 |  | 0 | 37 | 5
$d=4$ |  | 1 | 35 | 6 |  | 0 | 39 | 3 |  | 19 | 23 | 0 |  | 20 | 22 | 0 |  | 0 | 39 | 3 |  | 0 | 40 | 2
$d=5$ |  | 0 | 27 | 15 |  | 0 | 41 | 1 |  | 24 | 18 | 0 |  | 23 | 18 | 1 |  | 2 | 40 | 0 |  | 1 | 39 | 2
$d=10$ |  | 1 | 21 | 20 |  | 20 | 21 | 1 |  | 21 | 21 | 0 |  | 21 | 20 | 1 |  | 15 | 24 | 3 |  | 12 | 30 | 0
Sum |  | 56 | 150 | 46 |  | 21 | 220 | 11 |  | 107 | 145 | 0 |  | 104 | 145 | 3 |  | 31 | 208 | 13 |  | 13 | 230 | 9
Total Sum |  | 56 | 150 | 46 |  | 21 | 220 | 11 |  | 107 | 145 | 0 |  | 104 | 145 | 3 |  | 31 | 208 | 13 |  | 13 | 230 | 9

####  V-A3 F-measure Simulation Observations: Strip Pattern

Based on the strip pattern F-measure simulation results (Tables V and VIII),
we have the following observations:

  * (1)

LSH vs. RT: When $d=1$, LSH (both FSCS and RRT) has much better performance
than RT for the strip pattern, regardless of failure rates — the strip pattern
is equivalent to the block pattern in one-dimensional space. When $d\geq 2$,
LSH has similar, or slightly better, F-measure performance, for all dimensions
and failure rates.

  * (2)

LSH vs. ART: The LSH and original ART have very similar F-ratio performance,
regardless of failure rates and dimensions. All $p$-values (other than two
LSH-FSCS cases) indicate a lack of significance; and all
$\hat{\textrm{A}}_{12}$ are around 0.50, indicating very little difference
between LSH and ART performance.

  * (3)

LSH vs. RF: The FSCS version of LSH is much better than RF when $d=1$. For all
other cases (FSCS when $d>1$, all RRT), however, the LSH and RF performance is
very similar.

  * (4)

LSH vs. CR: The comparison of LSH and CR is very similar to LSH vs. RF. When
$d=1$, LSH-FSCS is significantly better than CR, but LSH and CR have very
similar performance in all other cases.

  * (5)

LSH vs. DF: The FSCS version of LSH has very similar F-ratio results to DF,
for all failure rates and dimensions. The situation is similar for the RRT
version, except for when $d=1$ (for which LSH has much better performance than
DF).

  * (6)

LSH vs. KD: The performance of LSH (both FSCS and RRT) and KD are very
similar, regardless of failure rates and dimensions. The $p$-values for all
the related statistical pairwise comparisons are greater than 0.01, which
indicates no significant differences.

TABLE XII: FSCS Version: Mean F-measure Results and Statistical Pairwise Comparisons of LSH for Real-life Programs ID | Program | Methods |  | LSH
---|---|---|---|---
RT | ART | RF | CR | DF | KD | LSH |  | vs. RT | vs. ART | vs. RF | vs. CR | vs. DF | vs. KD
P1 | airy | 1444.64 | 794.02 | 1400.15 | 1440.76 | 788.61 | 803.70 | 788.23 |  | ✔ (0.62) | ❍ (0.50) | ✔ (0.61) | ✔ (0.62) | ❍ (0.50) | ❍ (0.51)
P2 | bessj0 | 760.24 | 437.02 | 750.17 | 712.10 | 443.36 | 445.48 | 443.03 |  | ✔ (0.61) | ❍ (0.50) | ✔ (0.60) | ✔ (0.59) | ❍ (0.50) | ❍ (0.50)
P3 | erfcc | 1867.60 | 1032.28 | 1897.29 | 1839.75 | 1033.04 | 1045.93 | 1018.20 |  | ✔ (0.62) | ❍ (0.51) | ✔ (0.62) | ✔ (0.62) | ❍ (0.51) | ❍ (0.51)
P4 | probks | 2590.02 | 1468.08 | 2527.86 | 2681.32 | 1428.13 | 1440.23 | 1473.70 |  | ✔ (0.60) | ❍ (0.50) | ✔ (0.60) | ✔ (0.62) | ❍ (0.49) | ❍ (0.49)
P5 | tanh | 556.28 | 303.59 | 551.62 | 528.89 | 303.43 | 308.54 | 313.58 |  | ✔ (0.61) | ❍ (0.49) | ✔ (0.61) | ✔ (0.60) | ❍ (0.49) | ❍ (0.49)
P6 | bessj | 778.47 | 433.47 | 516.64 | 498.96 | 544.76 | 457.08 | 462.24 |  | ✔ (0.62) | ❍ (0.49) | ❍ (0.52) | ❍ (0.51) | ✔ (0.54) | ❍ (0.50)
P7 | gammq | 1246.62 | 1076.85 | 1067.20 | 1043.79 | 1064.96 | 1060.88 | 1128.44 |  | ✔ (0.52) | ❍ (0.49) | ❍ (0.48) | ✖ (0.48) | ✖ (0.48) | ❍ (0.49)
P8 | sncndn | 622.61 | 613.62 | 629.84 | 625.18 | 611.38 | 616.85 | 621.60 |  | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.49) | ❍ (0.50)
P9 | golden | 1847.63 | 1792.73 | 1805.71 | 1715.81 | 1833.62 | 1786.20 | 1828.17 |  | ❍ (0.50) | ❍ (0.49) | ❍ (0.50) | ❍ (0.48) | ❍ (0.50) | ❍ (0.49)
P10 | plgndr | 2701.59 | 1620.91 | 1108.47 | 1112.56 | 1520.86 | 1573.64 | 1682.47 |  | ✔ (0.61) | ❍ (0.49) | ✖ (0.40) | ✖ (0.40) | ✖ (0.46) | ❍ (0.49)
P11 | cel | 2998.85 | 1588.90 | 2103.34 | 2040.76 | 1977.56 | 1543.65 | 1606.12 |  | ✔ (0.65) | ❍ (0.50) | ✔ (0.57) | ✔ (0.56) | ✔ (0.56) | ❍ (0.49)
P12 | el2 | 1399.04 | 692.76 | 729.77 | 735.42 | 709.31 | 730.49 | 782.19 |  | ✔ (0.65) | ✖ (0.47) | ❍ (0.49) | ❍ (0.49) | ❍ (0.48) | ❍ (0.49)
P13 | calDay | 1631.33 | 1241.15 | 1491.29 | 1514.96 | 1358.25 | 1272.54 | 1274.34 |  | ✔ (0.56) | ❍ (0.50) | ✔ (0.55) | ✔ (0.55) | ✔ (0.52) | ❍ (0.51)
P14 | complex | 1185.39 | 1204.34 | 1243.80 | 1245.59 | 1209.19 | 1162.68 | 1220.67 |  | ❍ (0.49) | ❍ (0.50) | ❍ (0.51) | ❍ (0.51) | ❍ (0.50) | ❍ (0.49)
P15 | pntLinePos | 1361.16 | 1473.44 | 1574.85 | 1645.63 | 1501.06 | 1439.63 | 1446.11 |  | ✖ (0.47) | ❍ (0.50) | ❍ (0.52) | ✔ (0.53) | ❍ (0.50) | ❍ (0.49)
P16 | triangle | 1411.06 | 1349.37 | 1405.37 | 1353.53 | 1358.71 | 1367.38 | 1362.67 |  | ❍ (0.51) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.49) | ❍ (0.50)
P17 | line | 3175.25 | 3368.37 | 3607.22 | 3479.19 | 3413.45 | 3406.65 | 3553.09 |  | ✖ (0.48) | ❍ (0.49) | ❍ (0.51) | ❍ (0.50) | ❍ (0.49) | ❍ (0.49)
P18 | pntTrianglePos | 5631.50 | 5910.23 | 5700.59 | 5884.85 | 5780.71 | 5732.40 | 5581.19 |  | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.52) | ❍ (0.51) | ❍ (0.50)
P19 | twoLinesPos | 6980.25 | 9397.73 | 10130.81 | 10203.24 | 9507.52 | 8590.03 | 8582.56 |  | ✖ (0.44) | ❍ (0.52) | ✔ (0.53) | ✔ (0.53) | ✔ (0.52) | ❍ (0.50)
P20 | calGCD | 986.34 | 1000.10 | 1015.27 | 1029.68 | 988.74 | 1019.25 | 1004.32 |  | ❍ (0.49) | ❍ (0.50) | ❍ (0.50) | ❍ (0.51) | ❍ (0.50) | ❍ (0.50)
P21 | nearestDistance | 1933.48 | 1131.15 | 1168.33 | 1174.18 | 1221.33 | 1124.78 | 1286.17 |  | ✔ (0.60) | ✖ (0.47) | ✖ (0.48) | ✖ (0.48) | ❍ (0.50) | ✖ (0.47)
P22 | select | 3130.59 | 2607.52 | 2758.34 | 2684.43 | 2725.50 | 2706.77 | 2785.58 |  | ✔ (0.54) | ❍ (0.49) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50) | ❍ (0.50)
P23 | tcas | 1944.33 | 2490.33 | 1994.09 | 2015.11 | 2623.27 | 2486.45 | 2335.84 |  | ✖ (0.47) | ❍ (0.51) | ✖ (0.48) | ✖ (0.47) | ✔ (0.53) | ❍ (0.51)

####  V-A4 F-measure Simulation Observations: Point Pattern

Based on the point pattern F-measure simulation results (Tables VI and IX), we
have the following observations:

  * (1)

LSH vs. RT: The FSCS version of LSH has different performance to the RRT
version for the point pattern simulations: When $d\leq 3$, LSH-FSCS is similar
to, or slightly better than, RT; but RT significantly outperforms LSH-FSCS
overall when $d\geq 4$. LSH-RRT, however, has similar F-measure results to RT,
regardless of dimension and failure rates.

  * (2)

LSH vs. ART: When $d\leq 5$, LSH is very similar to the original ART (both
FSCS and RRT), regardless of failure rates. When $d=10$, however, LSH performs
slightly better than ART. The $p$-values and effect size values, when $d\leq
5$, nearly all indicate no significant difference. When $d=10$, however, some
$p$-values do indicate significant differences, for both FSCS and RRT,
especially when the failure rate is low.

  * (3)

LSH vs. RF: LSH-FSCS has similar, or slightly better, F-ratio results than RF
when $d\leq 3$; and performs significantly better than RF when $d\geq 4$. LSH-
RRT is different to LSH-FSCS, overall achieving a similar or slightly better
performance than RF, which is supported by the statistical comparisons.

  * (4)

LSH vs. CR: The comparisons between LSH and CR are very similar to those
between LSH and RF: LSH-FSCS has similar performance to CR when $d\leq 3$, but
is much better than CR when $d\geq 4$, regardless of the failure rates. LSH-
RRT, however, performs similarly to, or slightly better than, CR for all
values of $d$.

  * (5)

LSH vs. DF: LSH-FSCS performs similarly to DF when $d\leq 5$; significantly
better than DF for low failure rates when $d=10$; but slightly worse than DF
when $d=10$ for high failure rates (such as $\theta=1.0\times 10^{-2}$ and
$\theta=5.0\times 10^{-3}$). LSH-RRT overall achieves similar, or slightly
better, F-ratio results than DF, regardless of failure rates and dimensions.
For high dimensions ($d=10$), LSH has significantly better performance than
DF, especially when the failure rate is low.

  * (6)

LSH vs. KD: When $d\leq 5$, LSH has very similar performance to KD, for both
FSCS and RRT. When $d=10$, however, LSH performs significantly better,
especially for lower failure rates.

####  V-A5 Analysis and Summary

Table X presents the numbers of simulation scenarios, for each failure
pattern, where LSH is significantly superior (✔), indistinguishable (❍), or
significantly inferior (✖) to each compared technique, in terms of the
F-measure. Each failure pattern has 42 scenarios for pairwise comparison — 6
dimensions $\times$ 7 failure rates. Table XI presents the F-measure
comparisons for each dimension: Each dimension has 21 scenarios for each
pairwise comparison (3 failure patterns $\times$ 7 failure rates).

Previous studies have shown that block and strip patterns are more favourable
for ART than for RT [21]. However, as the dimensionality increases, ART may