A Comparative Study of Vectorization-Based
Static Test Case Prioritization Methods
Hirohisa Aman
Center for Information Technology
Ehime University
Matsuyama, Ehime, Japan
aman@ehime-u.ac.jp

Sousuke Amasaki
Tomoyuki Yokogawa
Faculty of Computer Sc. & Systems Eng.
Okayama Prefectural University
Soja, Okayama, Japan

Abstract—To enhance the efﬁciency of software testing, researchers have studied various test case prioritization (TCP)
methods. A topic model-based TCP is one of the promising
methods, which expresses test cases by topic vectors and prioritizes them in the order such that the set of already-prioritized
test cases have the maximum dispersion in the vector space.
However, the topic model is not the only option available forvectorizing test cases. Moreover, the distance metric in the vector
space and the scheme to prioritize test cases (the way to ﬁnd thetest case that is the farthest from the set of already-prioritizedones) also have some available options. Because the combinationsof the above options have not been well-discussed in the past,this paper conducts a comparative study of 36 TCP methods,
which are the combinations of (1) three vectorization methods,(2) three distance metrics, and (3) four prioritization schemes(36=3x3x4). The empirical results show the following ﬁndings.
The choice of the vectorization method has a signiﬁcant impact
on the testing efﬁciency: a promising option is Doc2Vec (PVDBoW). The combination with the distance metric may also
be impactful: a useful combination is Doc2Vec (PV-DBoW) andEuclidean distance. The third aspect, i.e., the choice of the scheme
to ﬁnd the farthest test case, is not always inﬂuential.
Index Terms—testing, test case prioritization, vectorization

I. I NTRODUCTION
Software testing is an essential activity to ensure the qualityof the software system under development and maintenance.
Developers prepare various test cases and execute them tominimize the risk of missing faults that lie latent in theirsoftware system, the system under test (SUT) [1]. Although
it is ideal for executing a great variety of test cases, a testing
activity sometimes becomes expensive and time-consuming[2], [3]. To overcome such a challenge, researchers havestudied various approaches for promoting the testing efﬁciency[4]. Test case prioritization (TCP) [5]–[7] is one of the mostuseful testing approaches.
TCP approaches seek to ﬁnd the ideal execution order oftest cases to detect more faults as early as possible. The
prioritization aims at maximizing the expected number ofdetected faults even if the testing is halted at an arbitrary
point. Various TCP approaches have been proposed in thepast. For example, Jeffrey and Gupta [8] proposed to utilizes
the program slicing technique to link a modiﬁed part with therelated test cases and prioritize test cases by using the slicebased data. Carlso et al. [9] leveraged a clustering approach

Minoru Kawahara
Center for Information Technology
Ehime University
Matsuyama, Ehime, Japan

together with code coverage information and code complexity
metric data to prioritize test cases. Kim and Porter [10]focused on the test history (the results of prior test executions)and proposed to quantify the expectation that a test casecauses a failure at the next test. Moreover, there have beenstudies utilizing the genetic algorithm (GA) that seeks the best
execution order of test cases in which their ﬁtness functions(evaluation functions) use the above test-related data [11].
Although the above TCP approaches are useful, they require
the test case execution history or advanced program analysis(e.g., the program slicing), which may not always be easy
to collect or perform [12]. If we add new test cases to thetest suite, we cannot obtain the test history of them. When
SUT is a large-scale system, it is highly expensive and timeconsuming to perform an advanced program analysis for all
programs included in the SUT. Therefore, researchers haverecently studied light-weight static TCP approaches as well,which require neither the execution of test cases nor anadvanced program analysis like the program slicing [13]–[16]; A recent approach focuses on the textual data of test
cases [13], which evaluated the similarity between test cases
by using the string edit distance (Manhattan distance) andprioritized test cases through maximizing the diversity oftest cases [14], [15]. Thomas et al. [16] proposed a moresophisticated approach that is based on the topic model [17],[18]. In [16], Thomas et al. performed a topic analysis for all
test cases and expressed test cases by the corresponding topic
vectors. Then, they proposed to prioritize test cases throughmaximizing the diversity of test cases in the topic vector space.
Although Thomas et al. empirically proved that the topic
vector-based approach is useful for prioritizing test cases
effectively, we have a simple question “How does it workwhen we replace the vectorization method with another one?”
In the world of natural language processing, the Doc2Vec[19]–[21] has become a promising method for producing avector representation of a document in recent years. That is,
a Doc2Vec-based approach may be a better option for thevectorization-based static TCP methods.
Moreover, we have some options for the distance metric as
well. To quantify the distance between test cases, we need todeﬁne the distance metric in the vector space. Although theprevious work [16] used the Manhattan distance, the use of

A. Static TCP and Its Evaluation Criterion
We present a formal deﬁnition of the static TCP.

Detectable
Fault

F1
F2
F3
F4

✓

t2
✓

Test Case
t3
t4
✓

✓

t5
✓
✓

Def. 1 (Static test case prioritization problem):Given a test suite T , which consists of n(> 0) test cases ti(for i = 1, 2, . . . , n). Let PT be the set of all permutationsof T . The static test case prioritization seeks to ﬁnd the
permutation P To ∈ PT such that∀P T (∈ PT ) f (P To ) ≥ f (P T ) ,(1)

where f (·) is the evaluation function of a permutation; The
higher the value, the better the permutation, in terms of thetest case prioritization.
□
For example, when we have test suite T = { t1 , t2 , t3 }, PT
consists of six permutations: PT = { (t1 , t2 , t3 ), (t1 , t3 , t2 ),(t2 , t1 , t3 ), (t2 , t3 , t1 ), (t3 , t1 , t2 ), (t3 , t2 , t1 ) }. The static TCP
is to ﬁnd the best permutation in these six candidates, which
has the highest evaluation value computed by f (·).
According to previous studies of TCP methods [4], [16], we
adopt the Average Percentage of Fault-Detection (APFD) [7]as our evaluation function in Eq.(1).
Def. 2 (Average Percentage of Fault-Detection (APFD)):
Given a permutation of the test suite, P T . Suppose m(> 0)
different faults are detectable by executing all test cases in
P T . The Average Percentage of Fault-Detection (APFD) of
P T is deﬁned asm
1
1 ∑T Fi +APFD(P T ) = 1 −,(2)
nm i=12nwhere T Fi = k if and only if the i-th fault is ﬁrst detected byexecuting the k-th test case in P T .
□   To demonstrate a TCP evaluation using the APFD, weconsider an example shown in Table I, where we have ﬁvetest cases T = {t1 , t2 , t3 , t4 , t5 } and four detectable faults{F1 , F2 , F3 , F4 }. The checkmarks (✓) indicate that the corresponding fault is detectable by the corresponding test case(s)1 ;

 






 




In this section, we brieﬂy explain the TCP method of interest(Sects. II-A, II-B) and describe the details of three aspects
that compose a TCP method: (1) the vectorization method(Sect. II-C), (2) the distance metric (Sect. II-D), and (3) theprioritization scheme (Sect. II-E). Then, we summarize the
combinations of their options that are the subjects of ourcomparative study (Sect. II-F).

t1



II. V ECTORIZATION -BASED S TATIC T EST C ASE
P RIORITIZATIONTABLE IS IMPLE EXAMPLE OF RELATIONSHIPS AMONG TEST CASES AND
DETECTABLE FAULTS ( FAULT MATRIX )

different distance metrics may have an impact on the TCP
performance. Furthermore, we also need to focus on the wayof maximizing the diversity of test cases. During the test caseprioritization process, the following two steps are iterated: (a)ﬁnd the test case that is the farthest from the set of alreadyprioritized test cases, and (b) append the farthest test case to
the set of already-prioritized ones. Here, to decide the farthest
test case, we have to deﬁne the distance between a single
test case and a set of test cases. The clustering methods [22]provide some options for such distance computation.
Hence, we can consider the following three aspects thatcompose a vectorization-based static TCP method: (1) the
vectorization method, (2) the distance metric, and (3) theprioritization scheme (the way to ﬁnd the test case that is thefarthest from the set of already-prioritized ones). To the bestof our knowledge, the combinations of the above three aspects
have not been well-discussed. Thus, toward a better static TCP
method, we conduct a comparative study and report the resultsin this paper. The key contributions of this paper include:• We report the performances of 36 vectorization-based
static TCP methods, which are combinations of– Three vectorization methods: topic model, Doc2Vec(PV-DM), and Doc2Vec (PV-DBoW),– Three distance metrics: Manhattan distance, Euclidean distance, and angular distance, and– Four prioritization schemes: single linkage-based
scheme, complete linkage-based scheme, average
linkage-based scheme, and Ward’s method-based
scheme.
• We empirically proved that the choice of the vectorization
method has a signiﬁcant impact on the testing efﬁciency,
and the combination with the distance metric may also be
impactful: promising options are Doc2Vec (PV-DBoW)
and Euclidean distance. The third aspect, i.e., the choiceof the scheme to ﬁnd the farthest test case, did not always
become inﬂuential.
The remainder of this paper is organized as follows. Section
II describes the TCP method of interest and the details of theabove three aspects that compose a TCP method. Section III
presents the results of our comparative study of vectorizationbased TCP methods. Finally, Section IV concludes the paperand outlines directions for future work.

       

(a) P Ta        

(b) P Tb

Fig. 1. Comparison of fault detection processes between P Ta and P Tb .
1 A test case can ﬁnd at most one “failure.” After a fail of a test, we analyze
the SUT and detect the fault causing the failure. In the analysis, we may detect
two or more faults. Test cases t2 and t5 in Table I correspond to such cases.

For example, F1 is detected when we execute t2 or t4 .
Now we consider two permutations P Ta and P Tb : P Ta =(t1 , t2 , t3 , t4 , t5 ), and P Tb = (t2 , t5 , t1 , t3 , t4 ). Fig. 1 shows
the differences between the fault detection processes of P Ta
and P Tb . In the ﬁgure, the horizontal axis signiﬁes thepercentage of executed test cases. Because we have ﬁve test
cases in this example, one execution of a test case corresponds
to a 0.2 increase on the axis. The vertical axis indicates thepercentage of detected faults, and it increases by 0.25 withevery detection because we have four detectable faults in total.
The earlier the curve grows, the better the TCP is. Hence, T Pb
is better than T Pa in terms of early fault detection.
The APFD is the area under the curve shown in Fig. 1,
and can be a reasonable evaluation value of the corresponding
TCP method. By Eq.(2), we obtain the following evaluations:
1
1• APFD(P Ta ) = 1 − 20 (2 + 5 + 2 + 1) + 10 = 0.6, and1
1• APFD(P Tb ) = 1 − 20 (1 + 2 + 1 + 2) + 10 = 0.8,
i.e., we get the relationship APFD(P Ta ) < APFD(P Tb ),which indicates that T Pb is better than T Pa .
B. Steps of Vectorization-Based Static TCP
We can perform a vectorization-based static TCP in thefollowing steps.
1) Vectorization of Test Cases:
As the ﬁrst step, we vectorize our test cases by usinga natural language processing (NLP) technique (Fig. 2).
We describe the options for the vectorization techniques
in Sect. II-C. Hereafter, we denote the vector corresponding to the test case ti by v i (for i = 1, . . . , n).
2) Computation of Distances between Test Cases:
For each pair of test cases (ti , tj ), we compute thedistance between them in the vector space, d(v i , v j ).
Because there are some options for the distance metric,
we elaborate them in Sect. II-D.
3) Prioritization of Test Cases:a) At ﬁrst, we ﬁnd the test case tx that is the farthestfrom the others {ti |i ̸= x}, and then we assign
the highest priority to tx . In this paper, we denotethe set of vectors corresponding to the alreadyprioritized test cases by A. That is, right after theabove selection, we have A = {v x }.
To determine the farthest test case, we need todeﬁne the distance between a single vector v i anda set of vectors A; We denote the distance between
them by D(v i , A). Because there are some options
for D, we elaborate them in Sect. II-E.

 










 





















A = {v 2 }farthest: v 5

A = {v 2 , v 5 }farthest: v 1

A = {v 2 , v 5 , v 1 }farthest: v 3

Fig. 3. Example of the TCP process.

b) After that, we single out the test case ty , which isthe farthest from A, s.t. ∀i D(v y , A) ≥ D(v i , A).
Then, we append v y to A, i.e., A ← A ∪ {v y }.
c) By iterating the above step b), i.e., a selection of
the farthest test case and an update of A, we obtain
the prioritized set of test cases.
□
Fig. 3 illustrates an example of the prioritization process.
Suppose v 2 is the farthest from the others, and we start the
TCP with A = {v 2 }. Next, we ﬁnd that v 5 is the farthest fromA, and then we update A as A = {v 2 , v 5 }. After that, we ﬁndv 2 is the farthest from A, and we obtain A = {v 2 , v 5 , v 1 }.
By iterating the similar steps, we prioritize the test cases.
C. Vectorization Method
We describe two primary NLP techniques to obtain a vector
representation of a document. In the context of this study, adocument corresponds to a test case.
1) Topic Model: The topic model [18] is a model for analyzing the latent semantic of a document. The model considers
some topics and estimates the probability distributions whichlink the terms (words) with the topics. In the topic model, oneword may belong to two or more topics. Hence, one document
may have two or more topics, i.e., a mix-up of topics. Fig. 4
presents a simple image structure of a topic model in which
we have four documents, eight words, and three topics. For
example, document-1 contains three words w1 , w2 , and w3 .
Because these words belong to topic-1 or topic-2, we regard
that document-1 is a mix-up of topic-1 and topic-2.
Since we cannot observe the topics directly, we estimate therelationship between each word and each latent topic by using
a probability distribution. One of the most popular methods isthe latent Dirichlet allocation (LDA) [23]–[25], which uses
the Dirichlet distribution; the LDA performs the maximum
likelihood estimation to associate a word with a topic. By using

  




























 

 



    

   

Fig. 2. Vectorization of test cases.

Fig. 4. Simple image of the topic model.

the probabilistic model of topics, we can quantify the weightof each topic in each document. In other words, “topics”
correspond to “soft clusters,” and the topic modeling is a softclustering of documents. The weight of a topic in a document
expresses the degree that the document belongs to the topic.
When we consider K(> 0) topics, we can obtain Kdimensional vector for a document in which the i-th element
indicates the weight of the i-th topic in the document (fori = 1, . . . , K). We use such a vector as a vector representationof a document, i.e., a test case in our context. In the previous
work [16], the topic model (built by the LDA) was used tovectorize test cases.























 


 









 



2) Doc2Vec: The Doc2Vec [19] is one of the most promising NLP techniques to obtain a vector representation of adocument [20]. For a pair of similar documents, a well-trained
Doc2Vec produces a pair of vectors that are close to eachother in the vector space. The Doc2Vec is an extension of theWord2Vec [26] technique that vectorizes a word. Both of thesetechniques utilize a neural network that learns words.
Fig. 5 presents a simple image structure of a neural network
used in a Word2Vec model. Suppose we have a training
sentence “I play tennis every weekend,” and we focus on
the word “tennis.” As a training of the neural network, we
input one word which appears around “tennis” (e.g., “play”)
and expect the neural network to output “tennis.” Throughthe training using various sentences, we update the weights
between layers iteratively. After the training, we look at theweight between the i-th unit of the input layer and the j-th unitof the hidden layer, wij . These weights form a map of the word
onto a multidimensional space whose number of dimensions
is the unit count in the hidden layer. We use the vector ofweights for the i-th unit, wi = (wi1 , wi2 , · · · , wij , · · · )T , asa vector expression of the i-th word2 . This vector is referred
to as a “distributed representation” of the word. Although it
is hard to interpret the meaning of each element of the vector,
the combination of the elements can form a well-produced
map of the semantic relationship among words. If two words
semantically similar to each other, the trained neural network
would make a similar output for either of these two words.
That is, the weight vectors for these two words are also close
to each other. Notice that the above example of the learning
is called Continuous Bag-of-Words (CBoW) model; There is  

another learning model called Skip-gram in which the focused
word (“tennis”) is used as the input, and its neighborhood word(e.g., “play”) is expected as the output of the neural network.
The Doc2Vec uses not only the words in a document but
also the document ID to extend the Word2Vec. There are twodifferent learning models for Doc2Vec.
• Paragraph Vector Distributed Memory (PV-DM):
The PV-DM is similar to the CBoW model of theWord2Vec. The inputs of the neural network are thedocument ID and the words appearing in the document.
• Paragraph Vector Distributed Bag-of-Words (PV-DBoW):
PV-DBoW is similar to the Skip-gram model of theWord2Vec. It uses the document ID as the input. Noticethat PV-DBoW does not take into account the order ofwords in the sentence.
In this paper, we denote the Doc2Vec models trained by
PV-DM and PV-DBoW by Doc2Vec-DM and Doc2Vec-DBoW,
respectively. These models can become our options for thevectorization method of test cases as well as the topic model.
D. Distance Metric
Next, we describe metrics to quantify the distance between
two vectors, i.e., two test cases. In this subsection, let K be thedimension number of vector, and v i = (vi1 , vi2 , . . . , viK )T be
the corresponding vector of test case ti (for i = 1, 2, . . . , n).
1) Manhattan Distance: In the previous work [16], Thomas
et al. used the Manhattan distance:K∑|vik − vjk | .
(3)d(v i , v j ) =k=1

The reason why they used the Manhattan distance is dueto the comparison conducted in their empirical study. They
compared the topic model-based TCP method with the conventional string similarity-based method [13]. Because the stringbased method had used the Manhattan distance and it is also
applicable to the topic model-based TCP method, Thomas etal. adopted it as the distance metric.
2) Euclidean Distance: As we explained in Sect. II-B, we
express test cases by multidimensional vectors and prioritize
them while considering the distances among them. The prioritization procedure has a similar characteristic3 to a clusteringof data [22]. Because the Euclidean distance is widely used inclustering methods, it is natural that we consider the Euclidean
distance as an option for the distance metric in this study:√d(v i , v j ) =(v i − v j )T (v i − v j ) .
(4)3) Angular Distance: In the NLP studies, the cosine similarity is a well-known measure of the closeness between two
feature vectors [27]:
CosSim(v i , v j ) = √v Ti v j√
v Ti v i
v Tj v j.

(5)

Fig. 5. Simple image of the neural network learning a word.
2 Symbol T signiﬁes the transpose of a vector.

3 Although a clustering method usually seeks to ﬁnd the nearest data point,
we try to ﬁnd the farthest one.

Since our vectorization methods for test cases are NLP techniques, we may consider an inverted cosine similarity to be an
option for the distance metric. Although the inverted measure“1 − CosSim(v i , v j )” evaluates a dissimilarity between two
vectors, we cannot use it as a distance metric because it
does not satisfy the triangle inequality4 , one of the necessary
conditions of a distance metric. Thus, we use the following
angular distance instead:1
arccos(CosSim(v i , v j )) .
(6)πThis metric focuses on the angle between the vectors rather
than the cosine value because arccos(cos θ) = θ.
d(v i , v j ) =E. Scheme to Find the Farthest Test Case
When one or more test cases are already prioritized, a static
TCP method seeks to ﬁnd the test case that is the farthest fromthe set of the already-prioritized ones (see step 3 in Sect. II-B
and Fig. 3). To this end, we need to deﬁne the distance between
a single vector v i and a set of vectors A, i.e., D(v i , A);
Using D(v i , A), we can ﬁnd the farthest vector v y such that∀i D(v y , A) ≥ D(v i , A). Because the process of ﬁnding thefarthest vector is essentially identical5 to a clustering of data,
we leverage the following representative methods in this study.
1) Single Linkage Method: For a vector v i (̸∈ A), thesingle linkage method focuses on the vector v c (∈ A) thatis the closest to v i and considers d(v i , v c ) to be the distance
between v i and A. That is, we haveD(v i , A) = min [ d(v i , v c ) ] ,(7)v c ∈A

and ﬁnd the farthest test case using Eq.(7). For example,
when we have v i and A = {v 1 , v 2 , v 3 } shown in Fig. 6 (1),D(v i , A) is the distance between v i and its closest one within
A, i.e., d(v i , v 2 ).
In this paper, we call the above scheme as the single
linkage-based scheme. Thomas et al. used this scheme in theirempirical work [16].

2) Complete Linkage Method: In contrast to the single
linkage method, the complete-link method looks at the farthest
vector v f (∈ A) and deﬁnes the distance as:
D(v i , A) = max [ d(v i , v f ) ] .
v f ∈A(8)

For example, when we have v i and A shown in Fig. 6 (2),D(v i , A) is the distance between v i and its farthest one within
A, i.e., d(v i , v 1 ). Hereafter, we refer to the prioritization
scheme using Eq.(8) as the complete linkage-based scheme.
3) Avarage Linkage Method: The average linkage method
uses the following deﬁnition of D, which is the average of
distances of all pairs:
1 ∑d(v i , v a ) .
(9)D(v i , A) =|A|
v a ∈AFor example, when we have v i and A shown in Fig. 6 (3),D(v i , A) is the average of d(v i , v 1 ), d(v i , v 2 ), and d(v i , v 3 ).
It is also the distance between v i and the mean vector of{v 1 , v 2 , v 3 } (v in Fig. 6 (3)). We call the prioritization scheme
using Eq.(9) as the average linkage-based scheme.
4) Ward’s Method: Ward’s method has a different perspective from the above three methods, and it focuses on thevariance within the cluster. Let S(A) be the sum of squared
deviation within the set A:∑(10)
S(A) =d(v s , v)2 ,v s ∈A

where
v=

1 ∑
vs .
|A|
v s ∈AIf we append a vector v i to A, the above sum of squared
deviation increases. Ward’s method considers the increment
to be the distance between v i and A:
D(v i , A) = S(A ∪ {v i }) − S(A) .

(11)

We refer to the prioritization scheme using Eq.(11) as Ward’s
method-based scheme.
F. Available TCP methods: Combinations of Aspects



















  

    






    

Fig. 6. Simple examples of D(v i , A).
4 Suppose we have three vectors v , v , and v , and CosSim(v , v ) =
1
2
3
1
2
cos(π/3) = 1/2 and CosSim(v 1 , v 3 ) = CosSim(v 3 , v 2 ) = cos(π/6) =√′′3/2. If we use d (v i , v j ) = 1−CosSim(v i , v j ), we√obtain d (v 1 ,√v 2 ) =1 − 1/2 = 1/2 and d′ (v 1 , v 3 ) = d′ (v 3 ,√v 2 ) = 1 − 3/2 = (2 − 3)/2.
Here, d′ (v 1 , v 3 ) + d′ (v 3 , v 2 ) = 2 − 3 > 1/2. That is, the triangle
inequality d′ (v 1 , v 2 ) ≤ d′ (v 1 , v 3 ) + d′ (v 3 , v 2 ) is not satisﬁed.
5 In the case of clustering, we seek to ﬁnd the nearest vector rather than thefarthest one.

In this section, we have described three aspects of thevectorization-based static TCP methods. Here, we have 36
combinations of these aspects because
1) the vectorization method has three options: Topic model,
Doc2Vec-DM, and Doc2Vec-DBoW;
2) the distance metric has three options: Manhattan distance, Euclidean one, and the angular one;3) the prioritization scheme has four options: the single
linkage-based scheme, the complete linkage-based one,the average linkage-based one, and Ward’s methodbased one.
Table II shows these combinations. The previous work [16]used the combination “Topic model / Manhattan distance /single linkage-based scheme” (T-m-S). We compare it to theremaining 35 combinations in our comparative study.

TABLE IIC OMBINATIONS OF T HREE A SPECTS F ORMING TCP METHODSDistance
Metric[m]
Manhattan[e]Euclidean[a]angular

Schemeto Findthe Farthest[S] single[C] complete[A] average[W] Ward[S] single[C] complete[A] average[W] Ward[S] single[C] complete[A] average[W] Ward[T] Topic
Model
T-m-S∗
T-m-C
T-m-A
T-m-W
T-e-S
T-e-C
T-e-A
T-e-W
T-a-S
T-a-C
T-a-A
T-a-W

Vectorization Method
[Dm]
[Db]
Doc2Vec-DM
Doc2Vec-DBoW
Dm-m-S
Db-m-S
Dm-m-C
Db-m-C
Dm-m-A
Db-m-A
Dm-m-W
Db-m-W
Dm-e-S
Db-e-S
Dm-e-C
Db-e-C
Dm-e-A
Db-e-A
Dm-e-W
Db-e-W
Dm-a-S
Db-a-S
Dm-a-C
Db-a-C
Dm-a-A
Db-a-A
Dm-a-W
Db-a-W(∗ Combination “T-m-S” is the conventional method used in the previous work [16].)

III. C OMPARATIVE S TUDY
We conducted a comparative study of 36 vectorization-based
static TCP methods shown in Table II. We report on ourcomparative study and discuss the results in this section.
A. Aim and Dataset
Toward a better static TCP, this study aims to reveal theeffects of the vectorization method, the distance metric, thescheme to ﬁnd the farthest test case in the vector space, andtheir combinations through the comparisons in terms of testing
efﬁciency (APFD value). To this end, we tackle the following
two research questions (RQs).
RQ1: Which TCP method would work well?
RQ2: Which options or combinations of them would be
useful in the static TCP method?
RQ1 is a straightforward question about our comparison. If
some TCP methods work better than the conventional method(“T-m-S” in Table II), this comparative study is worth doing
for the promotion of the static TCP method. RQ2 seeks togain a more in-depth insight into the components (options) of
the vectorization-based static TCP methods. By analyzing theimpacts of the options and their combinations, we can advise
a promising TCP method for future testing.
Our dataset consists of ﬁve sets of test cases shown in
Table III, which is the same as the dataset used in [16]. They
are available at the Software-artifact Infrastructure Repository(SIR) [28] and contain the source ﬁles of SUT, the test cases(test programs), and the fault matrices that present the links
between a test case and the detectable faults.
All of the test programs included in the dataset are Java
programs. The test programs for Ant are JUnit6 test casesthat are descendants of junit.framework.TestCase. On
the other hand, although the test cases for Derby are also
Java programs, they adopt another style of testing otherthan the JUnit framework. The test cases provide Java
code to run some tasks on Derby, and the test harnessorg.apache.derbyTesting.functionTests.harness.RunTest
executes each test case and checks its result.
6 https://junit.org/

TABLE IIIS YSTEMS U NDER T EST, N UMBER OF T EST C ASES AND N UMBER OF
FAULTS TO BE D ETECTED
Software
Ant
Derby
Derby
Derby
Derby

Version
1.5.3
10.1.2.1
10.1.3.1
10.2.1.6
10.3.1.4# of Test Cases
105
98
106
120
53

# of Faults
6
7
9
16
26

B. Procedure
We conducted our comparative study in the following steps7 .
1) Preprocessing of test cases: As with the previous work[16], we perform the following tasks for each test case.
a) Remove non-alphabetical characters and the keywords of the programming language (Java).
b) Split the identiﬁers by the camel case rule and thesnake case rule.
c) Stem all words and remove English stop words8 .
2) Vectorization of test cases: We build the following three
types of vectorization models using the preprocessed
test cases: Topic model, Doc2Vec-DM, and Doc2VecDBoW. We use LdaModel class and Doc2Vec classprovided in gensim library of Python [25] for themodel construction. To mitigate a threat to the constructvalidity caused by the random seed setting during themodel construction, we iterate the model constructions
30 times9 while changing the random seed, i.e., we build
different 30 instances for each model.
Notice that we need to specify the dimension number ofthe vector when we build the above models. Accordingto [16], we use n/2.5 as the dimension number where
n is the number of test cases; when n/2.5 is not an
integer, we round it to the nearest integer.
3) Evaluation of TCP methods: For each of the 36 TCP
methods (Table II), we compute the APFD as the evaluation value. Because we have 30 instances for each
vectorization model, we obtain 30 APFD values for eachmethod. To answer RQ1 and RQ2, we analyze the resultsby checking the mean APFD and by performing theanalysis of variance (ANOVA).
C. Results
Table IV presents the mean APFD of each static TCP
method for each SUT. In the table, we emphasize the highest
value within each SUT by boldface and asterisk(∗ ).
As a result, the conventional TCP method used in [16], i.e.,the combination “T-m-S,” did not show the best performancefor any SUT; the best TCP method having the highest mean
APFD varies among different SUT. Nonetheless, for all SUT,
the best TCP methods use Doc2Vec-DBoW or Doc2Vec-DM
as their vectorization methods. From the perspectives of the
7 We developed tools to perform the preprocessing and the vectorization.
Our tools are available at http://se.cite.ehime-u.ac.jp/tool/SEAA2020/.
8 We used the Natural Language Toolkit (https://www.nltk.org/).
9 The number of iterations (30) is decided according to [16].

TABLE IV
E VALUATION VALUES : M EAN APFD VALUE FOR EACH COMBINATION

[m]

[e]

[a]

[S]
[C]
[A]
[W]
[S]
[C]
[A]
[W]
[S]
[C]
[A]
[W]

[T]
0.875
0.872
0.872
0.872
0.873
0.872
0.871
0.872
0.874
0.873
0.873
0.873

(a) Ant 1.5.3
[Dm]
[Db]
0.876
0.878
0.877
0.884∗
0.871
0.877
0.870
0.877
0.876
0.878
0.876
0.884∗
0.870
0.878
0.868
0.878
0.878
0.876
0.878
0.883
0.876
0.871
0.874
0.867

(b) Derby 10.1.2.1
[T]
[Dm]
[Db]
0.977
0.974
0.977
0.974
0.974
0.978
0.976
0.974
0.977
0.976
0.974
0.976
0.976
0.974
0.977
0.978
0.974
0.979∗
0.977
0.974
0.977
0.977
0.974
0.977
0.978
0.974
0.975
0.975
0.974
0.975
0.976
0.974
0.974
0.976
0.974
0.974

(c) Derby 10.1.3.1
[T]
[Dm]
[Db]
0.885
0.871
0.851
0.866
0.871
0.865
0.880
0.870
0.851
0.878
0.869
0.851
0.870
0.871
0.851
0.887
0.871
0.870
0.885
0.871
0.851
0.888
0.871
0.851
0.880
0.870
0.857
0.876
0.891
0.978
0.894
0.870
0.928
0.894
0.863
0.979∗TABLE VN ORMALIZED EVALUATION VALUESDistance
Metric[m]
Manhattan[e]Euclidean[a]angular

Schemeto Findthe Farthest[S] single[C] complete[A] average[W] Ward[S] single[C] complete[A] average[W] Ward[S] single[C] complete[A] average[W] Ward[T] Topic
Model+0.148−0.251−0.045−0.134−0.071+0.061−0.147−0.065+0.123−0.206+0.100+0.123Vectorization Method
[Dm]
[Db]
Doc2Vec-DM
Doc2Vec-DBoW−0.110+0.237−0.120+0.232−0.311+0.185−0.340−0.010−0.145+0.245−0.133+0.382−0.373+0.252−0.433+0.228+0.315−0.327+0.483+0.425−0.175−0.143−0.238+0.236

distance metric and the scheme to ﬁnd the farthest test case,there does not seem to be a common trend.
To compare an average performance of the TCP methods
across SUT, we normalize the raw APFD values to z scores10
within each SUT and compute the average of the z scores foreach TCP method. Table V shows the results. In the table, we
emphasize the z scores that are higher than the conventional
method (= 0.148) by boldface. As a result, most of themethods using Doc2Vec-DBoW show better performances
than the conventional one (see the column of [Db]).
Next, to see the impacts caused by each of the three factors(the vectorization method, the distance metric, and the scheme
to ﬁnd the farthest test case) and the interactions among
them, we performed a three-way ANOVA. We present theresults in Table VI. In the table, the columns Df, SS, MS,F, p, and η 2 signify the degree of freedom, the sum ofsquares, the mean square, the F statistic, the p-value, andthe effect size, respectively; we emphasize the effect size (η 2 )corresponding to a large effect by boldface and an asterisk(∗ ),and the one corresponding to a medium effect by a dagger(† ),respectively11 .
As a result, the vectorization methods had large or medium
impacts on the testing efﬁciency for four out of ﬁve SUT;
Nonetheless, for the remaining SUT (c), the interaction be10 For a raw score x, the corresponding z score is (x − x)/s where x ands are the mean of all scores and the standard deviation of them, respectively.
11 Cohen [29] presented the rules on magnitudes of effect size: the thresholdsof the large effect and the medium effect are 0.14 and 0.06, respectively.

(d) Derby 10.2.1.6
[T]
[Dm]
[Db]
0.967
0.968
0.996∗
0.961
0.956
0.964
0.967
0.960
0.994
0.965
0.962
0.985
0.966
0.966
0.996∗
0.966
0.956
0.972
0.960
0.957
0.996∗
0.961
0.957
0.996∗
0.968
0.996∗ 0.962
0.964
0.962
0.962
0.970
0.956
0.965
0.970
0.956
0.990

(e) Derby 10.3.1.4
[T]
[Dm]
[Db]
0.925
0.917
0.908
0.926
0.927
0.909
0.928
0.923
0.909
0.918
0.921
0.908
0.923
0.914
0.908
0.919
0.927
0.909
0.917
0.923
0.909
0.917
0.922
0.909
0.923
0.925
0.906
∗
0.918
0.967 0.909
0.926
0.925
0.910
0.928
0.925
0.910

tween the vectorization method and the distance metric had
the highest effect that is a medium-level impact. On the other
hand, the distance metric showed a medium-level effect only
for the SUT (c), and the prioritization scheme did only for
the SUT (a) and (d). As a consequence, although most of thefactors and their interactions showed statistically-signiﬁcant(α = 0.001) impacts on the testing efﬁciency, only a limited
number of them showed large or medium impacts.
D. Discussion
1) [RQ1] Which TCP method would work well?: In thisstudy, we compared 36 static TCP methods that are the combinations of the vectorization methods, the distance metric,
and the scheme to ﬁnd the farthest test case. As a result,although the best TCP method differs among SUT (Table
IV), the conventional topic model-based method was not thebest TCP method for any SUT, and Doc2Vec-based methods
showed better performances (Table V).
In Table V, although “Dm-a-C” has the highest z score,
there are also many negative scores in the row of [Dm]. On
the other hand, most of the z scores in the row of [Db] arepositive and better than the conventional one, including thesecond-highest z score. Hence, it would be better to choose“Db”, i.e., to use Doc2Vec-DBoW as the vectorization method
rather than the topic model.
Although the method using “Db” did not show the top
performance in Table V, the main reason would be that thosemethods showed relatively-low APFD values for only the SUT(e) (see Table IV). Because the SUT (e) has the fewest test
cases and the most faults among all SUT (Table III), it might
have a different trend from the other SUT.
Now, we answer to the RQ1 as follows. The TCP methods
using Doc2Vec-DBoW tend to work well. Although the performance of the conventional topic model-based method is not
low, TCP methods using Doc2Vec-DBoW can outperform theconventional one in many cases.
2) [RQ2] Which options or combinations of them would be
useful in the static TCP method?: We conducted a three-way
ANOVA for the APFD values to examine which options or
combinations of them have signiﬁcant impacts on the testing
efﬁciency. Although the results varied among SUT, as shownand Euclidean distance.

TABLE VIR ESULTS OF THE THREE - WAY ANOVA(a) Ant 1.5.3
SourceDf
Vector (V)2Metric (M)2Scheme (S)
3
V×M
4
V×S
6
M×S
6
V×M×S
12
Error
1044

SS
0.004340.000020.00498
0.003160.003120.00009
0.00130
0.02337MS
0.002170.00001
0.00166
0.000790.000520.00001
0.000110.00002F
96.9840.427
74.08735.33823.222
0.634
4.83

p
< 0.001
0.652< 0.001< 0.001< 0.001
0.703< 0.001

η2
0.108†
0.000
0.123†
0.078†
0.077†
0.002
0.032(b) Derby 10.1.2.1
Vector (V)2Metric (M)2Scheme (S)
3
V×M
4
V×S
6
M×S
6
V×M×S
12
Error
1044

0.000820.00033
0.000030.000410.000120.000130.000170.009510.000410.000170.00001
0.000100.000020.000020.00001
0.0000145.10118.2861.003
11.249
2.262
2.339
1.51

< 0.001< 0.001
0.391< 0.001
0.036
0.030
0.114

0.071†
0.029
0.002
0.036
0.011
0.011
0.014

(c) Derby 10.1.3.1
Vector (V)2Metric (M)2Scheme (S)
3
V×M
4
V×S
6
M×S
6
V×M×S
12
Error
1044

0.026800.217200.054800.311100.094900.071200.12340
1.530700.013390.10858
0.01827
0.077780.01582
0.011860.010290.00147

9.131
74.05412.45753.047
10.791
8.092
7.016< 0.001< 0.001< 0.001< 0.001< 0.001< 0.001< 0.001

0.011
0.089†
0.023
0.128†
0.039
0.029
0.051

(d) Derby 10.2.1.6
Vector (V)2Metric (M)2Scheme (S)
3
V×M
4
V×S
6
M×S
6
V×M×S
12
Error
1044

0.075690.001120.025770.02968
0.029490.004910.029020.19600

0.03784
0.00056
0.00859
0.007420.00491
0.00082
0.002420.00019201.571
2.977
45.74639.52526.1794.36
12.882< 0.001
0.051< 0.001< 0.001< 0.001< 0.001< 0.001

0.193∗
0.003
0.066†
0.076†
0.075†
0.013
0.074†(e) Derby 10.3.1.4
Vector (V)2Metric (M)2Scheme (S)
3
V×M
4
V×S
6
M×S
6
V×M×S
12
Error
1044

0.06251
0.007450.00674
0.010090.01787
0.00434
0.01886
0.31367

0.03125
0.00372
0.00225
0.00252
0.00298
0.000720.00157
0.00030

104.028
12.395
7.475
8.396
9.915
2.409
5.232

< 0.001< 0.001< 0.001< 0.001< 0.0010.026< 0.001

0.142∗
0.017
0.015
0.023
0.040
0.010
0.043

in Table VI, it seems to be a common trend that the vectorization method is the most inﬂuential on the performance of static
TCP method. By combing with the results regarding RQ1, we
can say that Doc2Vec-DBoW would be a useful option.
On the other hand, the choice of the remaining two aspects
cannot always be impactful for enhancing the static TCP
method. However, the interaction between the vectorization
method and the distance metric may have a medium-level
impact (Table VI). Because all options using both Doc2VecDBoW and Euclidean distance showed better performancevalues in Table V, the combination of them may also be usefulin the static TCP method.
From the above results, we answer to the RQ2 as follows.
The choice of vectorization method plays the most important role in the static TCP method, and the better option
is Doc2Vec-DBoW rather than the topic model. Moreover,the interaction with the distance metric may also becomeinﬂuential, and the promising combination is Doc2Vec-DBoW

3) Impact of Vectorization Method: The above analysis
showed that the vectorization method has the most signiﬁcant
impact on testing efﬁciency. In this study, we have three
options for vectorization methods, Topic model, Doc2VecDM, and Doc2Vec-DBoW. Although the dimension number ofvectors representing a test case is common to all methods, thecompositions of vectors differ among the vectorization methods, and such differences would cause the above variations in
the observed results.
The topic model focuses on a co-occurrence relation amongwords (tokens) in test cases and performs a soft clusteringof words. Each element of the test case vector presents thelikelihood that the test case belongs to the corresponding softcluster. On the other hand, the Doc2Vec models are basedon the notion of word embedding, and the produced vectors
map semantic features of words on the vector space. That is,the vector elements are not independent of each other, andtheir combinations represent some semantics of words anddocuments. Thus, a Doc2Vec model and a topic model would
produce different vectors for the same test case. Moreover,
Doc2Vec-DM and Doc2Vec-DBoW become different models
due to the difference in learning algorithm even if they learned
the same dataset: Doc2Vec-DBoW does not take into accountthe order of words in test cases. These differences in thevectorization methods would cause the variation of observed
data (testing efﬁciency values).
As a result, Doc2Vec-DBoW seems to be useful for prioritizing test cases. Although the Doc2Vec-DBoW model isinsensitive to the order of words, it would be better to evaluate
the similarity among test cases because some test cases run
some of the same functions in different orders; The Doc2VecDM may be sensitive to such a difference of word orders intest cases, and consequently, it might be less appropriate toevaluate the test case similarity.
E. Threats to Validity
Construct validity: The setting of parameters has an impact
on the training of vectorization models. If we train the topic
models and Doc2Vec models using different parameters, we
may obtain different empirical results. However, to conduct afair comparison of TCP methods, we used the default parameters of gensim library, except for the dimension number ofthe vector; As the default dimension number differs between
LdaModel and Doc2Vec, we set the same number to them.
Internal validity: Both the topic model and the Doc2Vec
model use the words (terms) appearing in the test cases. When
there are compound terms that disobey the camel case rule or
the snake case rule (e.g., “ﬁlename”), the vectorization methods may not treat the semantic features of such terms properly
because we fail to split them appropriately. Although we
adopted the same preprocessing method as the previous work[16], it would be better to leverage the advanced identiﬁersplitting studies [30], and this is our future work.
Our TCP scheme described in Sect. II-B (Step 3) can be
another threat to the internal validity. Although we selecttest cases to maximize the diversity of selected (alreadyprioritized) test cases, the selection algorithm is the greedy
algorithm. That is, it might not provide the optimal solution
in terms of the diversity of test cases. We may mitigate thisthreat by adopting another sophisticated algorithm, such as thegenetic algorithm [11]. It is also our signiﬁcant future work.
External validity: Because our dataset is limited to ﬁvesets obtained from the SIR [28] and all of them are Java
programs, our ﬁndings may not work well for the testing ofanother system. That is, we would not be able to generalize
our empirical results to any software systems. To mitigate
this threat to validity, we would need to perform a further
comparative study using various systems, including other open
source products and commercial ones, as our future work.
Furthermore, we also have to use other systems written inprogramming languages other than Java to examine the impactof the programming language on the results.
IV. C ONCLUSION AND F UTURE W ORK
In this paper, we conducted a comparative study of 36
vectorization-based static TCP methods focusing on three
aspects (1) the vectorization method, (2) the distance metric,and (3) the scheme to ﬁnd the test case that is the farthestfrom the set of already-prioritized test cases. As a result, we
empirically proved that the TCP methods using Doc2Vec (PVDBoW) tend to work well in terms of the testing efﬁciency.
Moreover, the combination of Doc2Vec (PV-DBoW) and Euclidean distance may be useful in the static TCP. On the other
hand, the choice of the scheme (the above third aspect) may
not be inﬂuential. The empirical results would become a usefulbaseline toward further development of vectorization-based
static TCP methods.
From the results, the vectorization method seems to be themost promising factor in enhancing the static TCP. Because
a vectorization method such as Doc2Vec has many adjustableparameters, a further study of the parameter turning approachfor test cases is our signiﬁcant future work. Other of our future
work includes: (1) a real-world validation using test suites forcommercial software products, (2) applying the vectorization
methods to the dynamic TCP, and (3) enhancing the TCP
scheme by adopting a sophisticated algorithm such as thegenetic algorithm.
ACKNOWLEDGMENT
This work was supported by JSPS KAKENHI #18K11246
and #20H04184.
R EFERENCES[1] A. P. Mathur, Foundations of Software Testing.
Delhi: Pearson
Education, 2008.
[2] J. Hartmann and D. J. Robson, “Techniques for selective revalidation,”
IEEE Softw., vol. 7, no. 1, pp. 31–36, Jan 1990.
[3] I. Sommerville, Software Engineering, 10th ed. Essex, UK: Pearson
Education, 2016.
[4] S. Yoo and M. Harman, “Regression testing minimization, selection andprioritization:a survey,” Softw. Test. Verif. Reliab., vol. 22, no. 2, pp.
67–120, Mar. 2012.

[5] W. Wong, J. R. Horgan, S. London, and A. P. Mathur, “Effect of test set
minimization on fault detection effectiveness,” in Proc. 17th Int. Con.
Softw. Eng., Apr. 1995, pp. 41–50.
[6] G. Rothermel, R. H. Untch, Chengyun Chu, and M. J. Harrold, “Prioritizing test cases for regression testing,” IEEE Trans. Softw. Eng., vol. 27,
no. 10, pp. 929–948, Oct. 2001.
[7] S. Elbaum, A. G. Malishevsky, and G. Rothermel, “Test case prioritization: a family of empirical studies,” IEEE Trans. Softw. Eng., vol. 28,
no. 2, pp. 159–182, Feb. 2002.
[8] D. Jeffrey and N. Gupta, “Test case prioritization using relevant slices,”in Proc. 30th Int. Comp. Softw. App. Conf., Sept. 2006, pp. 411–420.
[9] R. Carlson, H. Do, and A. Denton, “A clustering approach to improving
test case prioritization: An industrial case study,” in Proc. 27th Int. Conf.
Softw. Maintenance, Sep. 2011, pp. 382–391.
[10] J.-M. Kim and A. Porter, “A history-based test prioritization techniquefor regression testing in resource constrained environments,” in Proc.
24th Int. Conf. Softw. Eng., May 2002, pp. 119–129.
[11] A. Bajaj and O. P. Sangwan, “A systematic literature review of test
case prioritization using genetic algorithms,” IEEE Access, vol. 7, pp.
126 355–126 375, 2019.
[12] L. Zhang, J. Zhou, D. Hao, L. Zhang, and H. Mei, “Prioritizing junit
test cases in absence of coverage information,” in Proc. Int. Conf. Softw.
Maintenance, Sep. 2009, pp. 19–28.
[13] Y. Ledru, A. Petrenko, S. Boroday, and N. Mandran, “Prioritizing test
cases with string distances,” Auto. Softw. Eng., vol. 19, no. 1, pp. 65–95,
Mar. 2012.
[14] H. Hemmati, L. C. Briand, A. Arcuri, and S. Ali, “An enhanced test caseselection approach for model-based testing: an industrial case study,” inProc. 18th Int. Symp. Foundations Softw. Eng., Nov. 2010, pp. 267–276.
[15] H. Hemmati, A. Arcuri, and L. Briand, “Empirical investigation of theeffects of test suite properties on similarity-based test case selection,”in Proc. 4th Int. Conf. Softw. Test. V. & V., Mar. 2011, pp. 327–336.
[16] S. W. Thomas, H. Hemmati, A. E. Hassan, and D. Blostein, “Static
test case prioritization using topic models,” Empir. Softw. Eng., vol. 19,
no. 1, pp. 182–212, Feb. 2014.
[17] T. Hofmann, “Probabilistic latent semantic indexing,” in Proc. 22nd Int.
Conf. Research & Dev. Inf. Retrieval, Aug. 1999, pp. 50–57.
[18] D. M. Blei, “Probabilistic topic models,” Commun. ACM, vol. 55, no. 4,
pp. 77–84, Apr. 2012.
[19] Q. Le and T. Mikolov, “Distributed representations of sentences anddocuments,” in Proc. 31st Int. Conf. Machine Learning, vol. 32, no. 2,
Jun. 2014, pp. 1188–1196.
[20] J. H. Lau and T. Baldwin, “An empirical evaluation of doc2vec withpractical insights into document embedding generation,” in Proc. 1stWorkshop Representation Learning for NLP, Aug. 2016, pp. 78–86.
[21] R. Řehůřek, “gensim: models.word2vec—deep learning with word2vec,”
https://radimrehurek.com/gensim/models/word2vec.html, Mar. 2018.
[22] A. K. Jain, M. N. Murty, and P. J. Flynn, “Data clustering: a review,”
ACM Computing Surveys, vol. 31, no. 3, pp. 264–323, Sep. 1999.
[23] D. M. Blei, A. Y. Ng, and M. I. Jordan, “Latent dirichlet allocation,” J.
Machine Learning Research, vol. 3, pp. 993–1022, Jan. 2003.
[24] D. M. Blei and M. I. Jordan, “Modeling annotated data,” in Proc. 26th
Int. Conf. Research & Dev. Inf. Retrieval, Jul. 2003, pp. 127–134.
[25] R. Řehůřek and P. Sojka, “Software framework for topic modelling withlarge corpora,” in Proc. LREC 2010 Workshop New Challenges for NLP
Frameworks, May 2010, pp. 45–50.
[26] T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean,“Distributed representations of words and phrases and their compositionality,” in Advances Neural Inf. Processing Syst., vol. 26, Dec. 2013,
pp. 3111–3119.
[27] A. Singhal, “Modern information retrieval: A brief overview,” Bulletin
IEEE Comp. Society Tech. Committee Data Eng., vol. 24, no. 4, pp.
35–43, Dec. 2001.
[28] H. Do, S. Elbaum, and G. Rothermel, “Supporting controlled experimentation with testing techniques: An infrastructure and its potential
impact,” Empir. Softw. Eng., vol. 10, no. 4, pp. 405–435, Oct. 2005.
[29] J. Cohen, Statistical Power Analysis for the Behavioral Sciences, 2nd ed.
London: Routledge, 1988.
[30] E. Hill, D. Binkley, D. Lawrie, L. Pollock, and K. Vijay-Shanker, “Anempirical study of identiﬁer splitting techniques,” Empir. Softw. Eng.,
vol. 19, no. 6, pp. 1754–1780, Dec. 2014.