Mining compact high utility sequential patterns
Tai Dinh（TheKyoto Collegeof Graduate
Studies for Informatics)
Miningcompacthigh utility
sequential
patterns

Philippe Fournier-Viger (College ofComputer Science and Software Engineering, Shenzhen University)
Tai Dinh1, Philippe Fournier-Viger2, Huynh Van Hong3
Huynh Van Hong (Ho Chi Minh University of Natural Resources and Environment)
1 The Kyoto College of Graduate Studies for Informatics

2 College of Computer Science and Software Engineering, Shenzhen University
3 Ho Chi Minh University of Natural Resources and Environment

Abstract
High utility sequential pattern mining (HUSPM) aims to mine all patterns that yield a high utility (profit) in asequence dataset. HUSPM is useful for several applications such as market basket analysis, marketing, andwebsite clickstream analysis. In these applications, users may also consider high utility patterns frequently
appearing in the dataset to obtain more fruitful information. However, this task is high computation sincealgorithms may generate a combinatorial explosive number of candidates that may be redundant or of low
importance. To reduce complexity and obtain a compact set of frequent high utility sequential patterns (FHUSPs),
this paper proposes an algorithm named CHUSP for mining closed frequent high utility sequential patterns(CHUSPs). Such patterns keep a concise representation while preserving the same expressive power of thecomplete set of FHUSPs. The proposed algorithm relies on a CHUS data structure to maintain information during
mining. It uses three pruning strategies to eliminate early low-utility and non-frequent patterns, thereby reducing
the search space. An extensive experimental evaluation was performed on six real-life datasets to evaluate theperformance of CHUSP in terms of execution time, memory usage, and the number of generated patterns.
Experimental results show that CHUSP can efficiently discover the compact set of CHUSPs under different userdefined thresholds.
Keywords: data mining, high utility sequential patterns, closed high utility sequential patterns
1. Introduction

sales volumes may greatly fluctuate. Suppose retailers
know that some products yield a high profit and are
frequently purchased; they can change businessstrategies for these items to increase sales andimprove inventory management. In marketing,marketers want to know some sets of products
frequently sold with high revenue. They can better
understand customers’ preferences and then design
efficient marketing strategies. In website clickstream
analysis, the number of clicks or time spent on each
web page or user interface (UI) element can be viewed
as the quantities of items in sequences. Thus,
administrators can discover the elements where users
spend most of their time. Based on that,administrators can improve functions and UI to suitthese important behaviors better.
Although the problem of HUSPM and its
extensions have been studied in several previous

Frequent high utility sequential pattern mining(FHUSPM) finds sequential patterns with high utility
and frequently appear in sequence datasets. Suchpatterns appear commonly in various real-life
applications such as market basket analysis, web- site
clickstream analysis, customer behavior analysis, andstock market analysis. In market basket analysis,
when analyzing customer transactions, a retail store
manager may be interested in finding the high utility
patterns that appear regularly and have a high salevolume. Detecting these purchase patterns is usefulfor understanding customers’ behavior and thus
adopting effective sales and marketing strategies. For
example, high-end electronic devices and jewelry may
generate more profit than many daily-life products.
However, they may be sold infrequently, and their
1

NAIS Journal

43

studies [1–7], these algorithms discover a full set of
HUSPs requiring exponential complexity. Therefore,
in this paper, we extend the concept of closed patterns
from frequent sequential pattern mining [8] for
HUSPM. A closed (frequent) high utility sequential
pattern (CHUSP) is a HUSP having no proper supersequences that are HUSPs and appear in the same
number of sequences. Such patterns are alsomeaningful for real-life applications since they are thelargest FHUSPs common to groups of customers.
Detecting the largest sets of items yielding high profit
and frequently sold supports sellers to understandbetter what customers need, adapt their business andmarketing strategies, and improve their services.
There is a work [9] focusing on this topic in literature.
However, the computational complexity of thisalgorithm is still high. In addition, the experimental
evaluation was conducted on small-scale datasets
which a few differences in characteristics. Last, thiswork did not provide the application accompanying its
proposed algorithms.
The above observations motivated the design of an
efficient algorithm that can mine CHUSPs. Generally,
we highlighted the major contributions andinnovations of this paper as follows:− We proposed an efficient pattern-growth-basedalgorithm named CHUSP to discover the set of
CHUSPs interesting for some tasks. CHUSP
mines the patterns from the dataset in a divideand-conquer approach. It first derives the set ofsize-1 quantitative sequences, and for eachsequence p, it derives p’s conditional (or projected)
dataset by partitioning it and recursively mining
the projected dataset. An innovation of the CHUSP
is that the algorithm checks the “closed” propertyof the generated pattern at each round of themining process. Thanks to this property, at the endof the mining process, we obtain a small set of
CHUSPs. The algorithm uses three pruning
strategies to eliminate early low-utility and nonfrequent patterns. Thus, the algorithm achieves
good performances on large-scale datasets.
− An extensive experiment was conducted on real
datasets to evaluate the performance of CHUSP interms of runtime, memory usage, and the numberof generated patterns. Experimental results showthat CHUSP can efficiently discover all CHUSPs.
In addition, its performance is independent of thedatasets’ characteristics if they contain utility
information, i.e., it can work on both quantitativetransaction and quantitative sequence datasets.
− We provide the application of CHUSP. The
application can be used for any dataset if its format
matches the input requirement.
The rest of this paper is organized as follows. Section
2 reviews related work; section 3 introduces thepreliminaries; section 4 describes the proposed
CHUSP algorithm; section 5 shows a comparative
experiment; section 6 concludes and outlines the
direction for future work.
2. Related WorkHigh utility sequential patterns mining aims tofind all sequential patterns with a utility greater thanor equal to a minimum utility threshold minUtil in asequence dataset. HUSPM is quite challenging as theutility measure is neither monotone nor antimonotone, unlike the support measure traditionallyused in SPM. Numerous algorithms have been
proposed for HUSPM, and its extension [1–7, 10–20].
A thorough survey of HUSPM can be found in thiswork [21]. Yin et al. [1] proposed an algorithm named
USpan for HUSPM. This algorithm builds alexicographic q-sequence tree (LQS-Tree) to maintainall generated sequences during the mining process. In
addition, it uses two concatenation mechanisms: IConcatenation and S-Concatenation, in combination
with two pruning strategies: width and depth pruning.
Wang et al. [2] proposed an algorithm named HUSSpan. The algorithm uses a utility-chain structure to
represent the search space of HUSPM. It also
introduces two tight utility upper bounds: prefix
extension utility (PEU) and reduced sequence utility(RSU), as well as two companion pruning strategies to
identify HUSPs. The experimental evaluation showedthat HUS-Span outperforms USpan in terms ofexecution time. The reason is that by using PEU and
RSU, HUS-Span can generate fewer candidates than
USpan.
Le et al. [3] proposed two algorithms, AHUS and2

44

NAIS Journal

AHUS-P. The algorithms use a pure array structure(PAS) to represent sequences. This data structure isvery compact and contains sufficient information on
sequences. Thus, it can reduce memory usage andeffectively support the mining process. Moreover, thetwo algorithms use two upper bounds to prune thesearch space. AHUS-P uses a parallel mining strategy
to discover patterns concurrently by sharing thesearch space with multiple processors. Each processor
independently performs its mining task and does not
wait for other tasks. AHUS-P is more efficient than
the serial AHUS algorithm for large-scale datasets.
Lin et al. [22] proposed a sequence-utility (SU)-Chain
algorithm for HUSPM. A lexicographic enumeration(LE)-tree is used in the algorithm to represent the
search space for promising candidates. The projecting
approach is used to accelerate the progress ofgenerating promising candidates. In addition,
multiple pruning strategies are used to identify
information not relevant to the mining progress.
For frequent high utility sequential pattern mining,
Gupta et al. [23] proposed a hybrid pattern growthbased algorithm named HUFTI-SPM to minesequential patterns satisfying both frequency andutility thresholds. It uses support–utility table tomaintain information on support and utility at various
time intervals. It uses sequence support as thedownward closure property to reduce the search space.
Ni et al. [24] proposed an algorithm named FHUSOM
to mine the architecture design requirements from theoperational scenario data. The algorithm uses a data
structure called FHUDS to keep all patterns andcombines four pruning strategies called SWU, PEU,
RSU, and MFP to reduce the search space. The
algorithm supports the design of an integrated multiplatform mission system (MPMS) architect and isefficient in the process of integrated architecture
design.
For closed high utility sequential pattern mining,
Truong et al. [9] proposed an algorithm named
FMaxCloHUSM to mine the set of frequent maximal
and closed high utility sequences. The algorithm uses
width and depth pruning strategies to remove low
utility sequences and a novel local pruning strategy
named LPCHUS to remove non-closed and nonmaximal high utility sequences. FMaxCloHUSM uses

a data structure called SIDUL to represent the dataset
in a vertical format and calculate utility information ofsequences and their extensions.
3. Preliminaries

3

Given a set of m distinct items I = {𝑖𝑖𝑖𝑖1 , 𝑖𝑖𝑖𝑖2 , … , 𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚 } . A
quantitative item (q-item) is a pair of the form (𝑖𝑖𝑖𝑖, 𝑞𝑞𝑞𝑞)
where i ∈ 𝐼𝐼𝐼𝐼 and q is a positive number representing
how many units of this item were purchased (internal
utility). The quantity of a q-item i in s is denoted asq(𝑖𝑖𝑖𝑖, 𝑠𝑠𝑠𝑠) . Each item 𝑖𝑖𝑖𝑖𝑘𝑘𝑘𝑘 ∈ 𝐼𝐼𝐼𝐼 (1 ≤ 𝑘𝑘𝑘𝑘 ≤ 𝑚𝑚𝑚𝑚) is associatedwith a weight denoted as p(𝑖𝑖𝑖𝑖𝑘𝑘𝑘𝑘 ) representing the unit
profit or importance (external utility) of 𝑖𝑖𝑖𝑖𝑘𝑘𝑘𝑘 . A
quantitative
itemset(q-itemset)
X=[(𝑖𝑖𝑖𝑖1 , 𝑞𝑞𝑞𝑞1 )(𝑖𝑖𝑖𝑖2 , 𝑞𝑞𝑞𝑞2 ) … (𝑖𝑖𝑖𝑖𝑘𝑘𝑘𝑘 , 𝑞𝑞𝑞𝑞𝑘𝑘𝑘𝑘 )] is a set of one or more qitems where �𝑖𝑖𝑖𝑖𝑗𝑗𝑗𝑗 , 𝑞𝑞𝑞𝑞𝑗𝑗𝑗𝑗 � is a q-item (1 ≤ 𝑗𝑗𝑗𝑗 ≤ 𝑘𝑘𝑘𝑘) . In thefollowing, brackets are omitted for brevity if a qitemset contains only one q-item. In addition, without
loss of generality, assume that q-items in a q-itemset
are sorted according to the lexicographical order suchas a ≺ 𝑏𝑏𝑏𝑏 ≺ 𝑐𝑐𝑐𝑐 ≺ 𝑑𝑑𝑑𝑑 ≺ 𝑒𝑒𝑒𝑒 ≺ 𝑓𝑓𝑓𝑓 ≺ 𝑔𝑔𝑔𝑔. A quantitative
sequence (q-sequence) s is an ordered list of q-itemsetss = ⟨𝐼𝐼𝐼𝐼1 𝐼𝐼𝐼𝐼2 … 𝐼𝐼𝐼𝐼𝑙𝑙𝑙𝑙 ⟩ where 𝐼𝐼𝐼𝐼𝑗𝑗𝑗𝑗 (1 ≤ 𝑗𝑗𝑗𝑗 ≤ 𝑙𝑙𝑙𝑙) is a q-itemset. A
quantitative sequence dataset is a set of n q-sequences
SDB = {𝑠𝑠𝑠𝑠1 , 𝑠𝑠𝑠𝑠2 , … , 𝑠𝑠𝑠𝑠𝑛𝑛𝑛𝑛 }, where each sequence 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 ∈𝑆𝑆𝑆𝑆 (1 ≤ 𝑠𝑠𝑠𝑠𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 ≤ 𝑛𝑛𝑛𝑛) is a subset of I, and sid is its unique
identifier.
For example, Table 1 shows the items and theirrespective unit profits appearing in an online retailstore. In this example, the external utility of each item
a, b, c, d, e, f, g are 2, 5, 3, 4, 6, 1, 7, respectively.
Table 2 shows five shopping q-sequences withquantities, having the sequence identifiers (sid) 1 to 5
(denoted 𝑠𝑠𝑠𝑠1 to 𝑠𝑠𝑠𝑠5 ). Each q-sequence comprises one ormore transactions (q-itemsets). Each transaction in a
q-sequence has a unique transaction identifier tid, andconsists of one or many q-items.
The q-sequence 𝑠𝑠𝑠𝑠4 contains three q-itemsets[(𝑏𝑏𝑏𝑏, 1)𝑐𝑐𝑐𝑐(1)(𝑒𝑒𝑒𝑒, 2)(𝑔𝑔𝑔𝑔, 5)], [(𝑎𝑎𝑎𝑎, 3)(𝑏𝑏𝑏𝑏, 2)(𝑒𝑒𝑒𝑒, 4)(𝑓𝑓𝑓𝑓, 2)] and[(𝑏𝑏𝑏𝑏, 2)(𝑐𝑐𝑐𝑐, 1)(𝑒𝑒𝑒𝑒, 2)] in which the internal utility of qitem e in the first, second and third q-itemsets are 2, 4
and 2, respectively. We use the notation 𝑖𝑖𝑖𝑖𝑡𝑡𝑡𝑡𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 to refer tothe occurrence of the item i in the tid − thtransactions of a q-sequence. In 𝑠𝑠𝑠𝑠2 , the notation 𝑐𝑐𝑐𝑐1
means that the q-item c appears in the first q-itemset

NAIS Journal45

of 𝑠𝑠𝑠𝑠2 , that is (𝑐𝑐𝑐𝑐, 2), while 𝑐𝑐𝑐𝑐3 represents (𝑐𝑐𝑐𝑐, 1) in thethird q-itemset of 𝑠𝑠𝑠𝑠2 , and 𝑐𝑐𝑐𝑐1 ≺ 𝑐𝑐𝑐𝑐3 in 𝑠𝑠𝑠𝑠2 .

𝑞𝑞𝑞𝑞𝑏𝑏𝑏𝑏𝑗𝑗𝑗𝑗2 , … , 𝑖𝑖𝑖𝑖𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚 = 𝑖𝑖𝑖𝑖𝑏𝑏𝑏𝑏𝑗𝑗𝑗𝑗𝑚𝑚𝑚𝑚 ∧ 𝑞𝑞𝑞𝑞𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚 = 𝑞𝑞𝑞𝑞𝑏𝑏𝑏𝑏𝑗𝑗𝑗𝑗𝑚𝑚𝑚𝑚 then 𝑋𝑋𝑋𝑋𝑏𝑏𝑏𝑏 is said tocontain 𝑋𝑋𝑋𝑋𝑎𝑎𝑎𝑎 , denoted as 𝑋𝑋𝑋𝑋𝑎𝑎𝑎𝑎 ⊆ 𝑋𝑋𝑋𝑋𝑏𝑏𝑏𝑏 . For example, qitemset [(𝑎𝑎𝑎𝑎, 1)(𝑏𝑏𝑏𝑏, 1)(𝑒𝑒𝑒𝑒, 3)] in 𝑠𝑠𝑠𝑠3 contains (𝑎𝑎𝑎𝑎, 1), (𝑏𝑏𝑏𝑏, 1),(𝑒𝑒𝑒𝑒, 3) , [(𝑎𝑎𝑎𝑎, 1)(𝑏𝑏𝑏𝑏, 1)] , [(𝑎𝑎𝑎𝑎, 1)(𝑒𝑒𝑒𝑒, 3)] , [(𝑏𝑏𝑏𝑏, 1)(𝑒𝑒𝑒𝑒, 3)] ,[(𝑎𝑎𝑎𝑎, 1)(𝑏𝑏𝑏𝑏, 1)(𝑒𝑒𝑒𝑒, 3)].

Table 1: External utility valuesaitem
unit profit 2

b c
5 3

d
4

e
6

f
1

Table 2: External utility values

sid
1
2
3
4
5

tid

transactions

1
2
3
1
2
3
1
2
3
4
1
2
3

(𝑎𝑎𝑎𝑎, 5)(𝑐𝑐𝑐𝑐, 2)(𝑔𝑔𝑔𝑔, 5)(𝑎𝑎𝑎𝑎, 3)(𝑏𝑏𝑏𝑏, 1)(𝑐𝑐𝑐𝑐, 3)(𝑓𝑓𝑓𝑓, 2)(𝑏𝑏𝑏𝑏, 3)(𝑑𝑑𝑑𝑑, 2)(𝑒𝑒𝑒𝑒, 2)(𝑐𝑐𝑐𝑐, 2)(𝑒𝑒𝑒𝑒, 1)(𝑎𝑎𝑎𝑎, 2)(𝑏𝑏𝑏𝑏, 2)(𝑓𝑓𝑓𝑓, 5)(𝑏𝑏𝑏𝑏, 2)(𝑐𝑐𝑐𝑐, 1)(𝑒𝑒𝑒𝑒, 4)(𝑔𝑔𝑔𝑔, 6)(𝑎𝑎𝑎𝑎, 1)(𝑏𝑏𝑏𝑏, 1)(𝑒𝑒𝑒𝑒, 3)(𝑐𝑐𝑐𝑐, 3)(𝑑𝑑𝑑𝑑, 2)(𝑔𝑔𝑔𝑔, 3)(𝑏𝑏𝑏𝑏, 2)(𝑒𝑒𝑒𝑒, 1)(𝑑𝑑𝑑𝑑, 3)(𝑏𝑏𝑏𝑏, 1)(𝑐𝑐𝑐𝑐, 1)(𝑒𝑒𝑒𝑒, 2)(𝑔𝑔𝑔𝑔, 5)(𝑎𝑎𝑎𝑎, 3)(𝑏𝑏𝑏𝑏, 2)(𝑒𝑒𝑒𝑒, 4)(𝑓𝑓𝑓𝑓, 2)(𝑏𝑏𝑏𝑏, 2)(𝑐𝑐𝑐𝑐, 1)(𝑒𝑒𝑒𝑒, 2)1(𝑎𝑎𝑎𝑎, 4)(𝑑𝑑𝑑𝑑, 2)(𝑓𝑓𝑓𝑓, 2)(𝑔𝑔𝑔𝑔, 10)

tu

g
7

Definition 3 (q-subsequence)
Given q-sequences 𝐴𝐴𝐴𝐴 = ⟨𝐴𝐴𝐴𝐴1 𝐴𝐴𝐴𝐴2 … 𝐴𝐴𝐴𝐴𝑛𝑛𝑛𝑛 ⟩ and 𝐵𝐵𝐵𝐵 =⟨𝐵𝐵𝐵𝐵1 𝐵𝐵𝐵𝐵2 … 𝐵𝐵𝐵𝐵𝑛𝑛𝑛𝑛′ ⟩(𝑛𝑛𝑛𝑛 ≤ 𝑛𝑛𝑛𝑛′ ) , where 𝐴𝐴𝐴𝐴α , 𝐵𝐵𝐵𝐵β are q-itemsets(1 ≤ α ≤ 𝑛𝑛𝑛𝑛, 1 ≤ β ≤ 𝑛𝑛𝑛𝑛′ ) . If there exists positive
integers 1 ≤ 𝑗𝑗𝑗𝑗1 ≤ 𝑗𝑗𝑗𝑗2 ≤ ⋯ ≤ 𝑗𝑗𝑗𝑗𝑛𝑛𝑛𝑛 ≤ 𝑛𝑛𝑛𝑛′ , such that 𝐴𝐴𝐴𝐴1 ⊆𝐵𝐵𝐵𝐵𝑗𝑗𝑗𝑗1 , 𝐴𝐴𝐴𝐴2 ⊆ 𝐵𝐵𝐵𝐵𝑗𝑗𝑗𝑗2 , … , 𝐴𝐴𝐴𝐴𝑛𝑛𝑛𝑛 ⊆ 𝐵𝐵𝐵𝐵𝑗𝑗𝑗𝑗𝑛𝑛𝑛𝑛 , then 𝐴𝐴𝐴𝐴 is a q-subsequence of
𝐵𝐵𝐵𝐵 and 𝐵𝐵𝐵𝐵 is a q-supersequence of 𝐴𝐴𝐴𝐴, denoted as 𝐴𝐴𝐴𝐴 ⊆⟨[(𝑎𝑎𝑎𝑎, 5)(𝑐𝑐𝑐𝑐, 2)(𝑔𝑔𝑔𝑔, 5)]⟩
𝐵𝐵𝐵𝐵. For
example,and⟨[(𝑎𝑎𝑎𝑎, 3)(𝑏𝑏𝑏𝑏, 1)(𝑐𝑐𝑐𝑐, 3)(𝑓𝑓𝑓𝑓, 2)]⟩ are q-subsequences of 𝑠𝑠𝑠𝑠1 .

su51
22 10835
12
19 110
79
25
38
91
16
12
55
42 122
25
88

Definition 4 (Utility of a q-sequence)
The utility of an (𝑖𝑖𝑖𝑖, 𝑞𝑞𝑞𝑞) in 𝑠𝑠𝑠𝑠 is denoted and defined as𝑢𝑢𝑢𝑢(𝑖𝑖𝑖𝑖, 𝑞𝑞𝑞𝑞) = 𝑝𝑝𝑝𝑝(𝑖𝑖𝑖𝑖) × 𝑞𝑞𝑞𝑞(𝑖𝑖𝑖𝑖). The utility of a q-itemset 𝑋𝑋𝑋𝑋 in 𝑠𝑠𝑠𝑠
is denoted and defined as 𝑢𝑢𝑢𝑢(𝑋𝑋𝑋𝑋) = ∑𝑚𝑚𝑚𝑚
𝑘𝑘𝑘𝑘=1 𝑢𝑢𝑢𝑢(𝑖𝑖𝑖𝑖𝑘𝑘𝑘𝑘 , 𝑞𝑞𝑞𝑞𝑘𝑘𝑘𝑘 ). The
utility of 𝑠𝑠𝑠𝑠 is denoted and defined as 𝑢𝑢𝑢𝑢(𝑠𝑠𝑠𝑠) =∑𝑛𝑛𝑛𝑛𝑗𝑗𝑗𝑗=1 𝑢𝑢𝑢𝑢�𝑋𝑋𝑋𝑋𝑗𝑗𝑗𝑗 �.

88For example, the utility of 𝑔𝑔𝑔𝑔 in 𝑠𝑠𝑠𝑠1 is 𝑢𝑢𝑢𝑢(𝑔𝑔𝑔𝑔, 5) = 7 × 5 =35. The utility of [(𝑎𝑎𝑎𝑎, 5)(𝑐𝑐𝑐𝑐, 2)(𝑔𝑔𝑔𝑔, 5)] in 𝑠𝑠𝑠𝑠1 is𝑢𝑢𝑢𝑢([(𝑎𝑎𝑎𝑎, 5)(𝑐𝑐𝑐𝑐, 2)(𝑔𝑔𝑔𝑔, 5)]) = 𝑢𝑢𝑢𝑢(𝑎𝑎𝑎𝑎, 5) + 𝑢𝑢𝑢𝑢(𝑐𝑐𝑐𝑐, 2) + 𝑢𝑢𝑢𝑢(𝑔𝑔𝑔𝑔, 5) =2 × 5+3 × 2+7 × 5 = 51. The utility of 𝑠𝑠𝑠𝑠1 is 𝑢𝑢𝑢𝑢(𝑠𝑠𝑠𝑠1 ) =𝑢𝑢𝑢𝑢([(𝑎𝑎𝑎𝑎, 5)(𝑐𝑐𝑐𝑐, 2)(𝑔𝑔𝑔𝑔, 5)]) + u ([(𝑎𝑎𝑎𝑎, 3)(𝑏𝑏𝑏𝑏, 1)(𝑐𝑐𝑐𝑐, 3)(𝑓𝑓𝑓𝑓, 2)]) +𝑢𝑢𝑢𝑢([(𝑏𝑏𝑏𝑏, 3)(𝑑𝑑𝑑𝑑, 2)(𝑒𝑒𝑒𝑒, 2)]) = 51 + 22 + 35 = 108.

Definition 1 (The size and length of a q-sequence) The
size of 𝑠𝑠𝑠𝑠 is the number of q-itemsets it contains. The
length of s is the number of q-items in 𝑠𝑠𝑠𝑠 . In otherwords, 𝑠𝑠𝑠𝑠 is called k-sequence if and only if there are kq-items in 𝑠𝑠𝑠𝑠, i.e., |𝑠𝑠𝑠𝑠| = 𝑘𝑘𝑘𝑘, where |𝑠𝑠𝑠𝑠| = ∑𝐼𝐼𝐼𝐼𝑗𝑗𝑗𝑗⊆𝑠𝑠𝑠𝑠�𝐼𝐼𝐼𝐼𝑗𝑗𝑗𝑗 � and �𝐼𝐼𝐼𝐼𝑗𝑗𝑗𝑗 �Definition 5 (Utility matrix)
A utility matrix of 𝑠𝑠𝑠𝑠 is 𝑚𝑚𝑚𝑚 × 𝑛𝑛𝑛𝑛 matrix, where 𝑚𝑚𝑚𝑚 and 𝑛𝑛𝑛𝑛
are the number of q-items and q-itemsets(transactions) in 𝑠𝑠𝑠𝑠, respectively. The element at theposition (𝑘𝑘𝑘𝑘, 𝑗𝑗𝑗𝑗) (0 ≤ 𝑘𝑘𝑘𝑘 < 𝑚𝑚𝑚𝑚, 0 ≤ 𝑗𝑗𝑗𝑗 < 𝑛𝑛𝑛𝑛) of the utility
matrix stores the utility 𝑢𝑢𝑢𝑢(𝑖𝑖𝑖𝑖𝑘𝑘𝑘𝑘 , 𝑞𝑞𝑞𝑞) of the q-item (𝑖𝑖𝑖𝑖𝑘𝑘𝑘𝑘 , 𝑞𝑞𝑞𝑞) in
the q-itemset 𝑗𝑗𝑗𝑗. Table 3 shows the utility matrix of 𝑠𝑠𝑠𝑠3
for the sequence dataset 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐵𝐵𝐵𝐵 depicted in Table 2.

is the total number of q-items in the q-itemset 𝐼𝐼𝐼𝐼𝑗𝑗𝑗𝑗 . For
example, the size and length of 𝑠𝑠𝑠𝑠4 in Table 1 are 3 and11, respectively.
Definition 2 (q-itemset containment)

Let 𝑋𝑋𝑋𝑋𝑎𝑎𝑎𝑎 = ��𝑖𝑖𝑖𝑖𝑎𝑎𝑎𝑎1 , 𝑞𝑞𝑞𝑞𝑎𝑎𝑎𝑎1 ��𝑖𝑖𝑖𝑖𝑎𝑎𝑎𝑎2 , 𝑞𝑞𝑞𝑞𝑎𝑎𝑎𝑎2 � … �𝑖𝑖𝑖𝑖𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚 , 𝑞𝑞𝑞𝑞𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚 �� and 𝑋𝑋𝑋𝑋𝑏𝑏𝑏𝑏 =��𝑖𝑖𝑖𝑖𝑏𝑏𝑏𝑏1 , 𝑞𝑞𝑞𝑞𝑏𝑏𝑏𝑏1 ��𝑖𝑖𝑖𝑖𝑏𝑏𝑏𝑏2 , 𝑞𝑞𝑞𝑞𝑏𝑏𝑏𝑏2 � … �𝑖𝑖𝑖𝑖𝑏𝑏𝑏𝑏𝑚𝑚𝑚𝑚′ , 𝑞𝑞𝑞𝑞𝑏𝑏𝑏𝑏𝑚𝑚𝑚𝑚′ �� be two q-itemsets,

where 𝑖𝑖𝑖𝑖𝑎𝑎𝑎𝑎𝑘𝑘𝑘𝑘 ∈ 𝐼𝐼𝐼𝐼(1 ≤ 𝑘𝑘𝑘𝑘 ≤ 𝑚𝑚𝑚𝑚) and 𝑖𝑖𝑖𝑖𝑏𝑏𝑏𝑏𝑘𝑘𝑘𝑘′ ∈ 𝐼𝐼𝐼𝐼(1 ≤ 𝑘𝑘𝑘𝑘 ′ ≤ 𝑚𝑚𝑚𝑚′ ) .

Definition 6 (Remaining utility)
Given a sequence 𝑠𝑠𝑠𝑠 = ⟨𝑋𝑋𝑋𝑋1 𝑋𝑋𝑋𝑋2 … 𝑋𝑋𝑋𝑋𝑛𝑛𝑛𝑛 ⟩ where 𝑋𝑋𝑋𝑋𝑘𝑘𝑘𝑘 =𝑚𝑚𝑚𝑚 , such that 𝑖𝑖𝑖𝑖𝑎𝑎𝑎𝑎1 = 𝑖𝑖𝑖𝑖𝑏𝑏𝑏𝑏𝑗𝑗𝑗𝑗1 ∧ 𝑞𝑞𝑞𝑞𝑎𝑎𝑎𝑎1 = 𝑞𝑞𝑞𝑞𝑏𝑏𝑏𝑏𝑗𝑗𝑗𝑗1 , 𝑖𝑖𝑖𝑖𝑎𝑎𝑎𝑎2 = 𝑖𝑖𝑖𝑖𝑏𝑏𝑏𝑏𝑗𝑗𝑗𝑗2 ∧ 𝑞𝑞𝑞𝑞𝑎𝑎𝑎𝑎2 =The remaining utility of q-item 𝑖𝑖𝑖𝑖𝑘𝑘𝑘𝑘𝑚𝑚𝑚𝑚 in s is denoted andIf there exist positive integers 1 ≤ 𝑗𝑗𝑗𝑗1 ≤ 𝑗𝑗𝑗𝑗2 ≤ ⋯ ≤ 𝑗𝑗𝑗𝑗𝑚𝑚𝑚𝑚 ≤��𝑖𝑖𝑖𝑖𝑘𝑘𝑘𝑘1 , 𝑞𝑞𝑞𝑞𝑘𝑘𝑘𝑘1 ��𝑖𝑖𝑖𝑖𝑘𝑘𝑘𝑘2 , 𝑞𝑞𝑞𝑞𝑘𝑘𝑘𝑘2 � … �𝑖𝑖𝑖𝑖𝑘𝑘𝑘𝑘𝑚𝑚𝑚𝑚 , 𝑞𝑞𝑞𝑞𝑘𝑘𝑘𝑘𝑚𝑚𝑚𝑚 �� is a q-itemset of s.

′

4

46

NAIS Journalsequence. For instance, sequence ⟨(𝑒𝑒𝑒𝑒)⟩ matches
respectively the q-subsequence ⟨(𝑒𝑒𝑒𝑒, 3)⟩ and ⟨(𝑒𝑒𝑒𝑒, 1)⟩ inthe first and third q-itemsets of 𝑠𝑠𝑠𝑠3 . Sequence ⟨[𝑎𝑎𝑎𝑎𝑐𝑐𝑐𝑐]⟩
matches both the q-subsequences ⟨[(𝑎𝑎𝑎𝑎, 5)(𝑐𝑐𝑐𝑐, 2)]⟩ and⟨[(𝑎𝑎𝑎𝑎, 3)(𝑐𝑐𝑐𝑐, 3)]⟩ of 𝑠𝑠𝑠𝑠1 .

defined as 𝑟𝑟𝑟𝑟𝑢𝑢𝑢𝑢�𝑖𝑖𝑖𝑖𝑘𝑘𝑘𝑘𝑚𝑚𝑚𝑚 , 𝑠𝑠𝑠𝑠� =∑𝑠𝑠𝑠𝑠 ′ ∈𝑠𝑠𝑠𝑠∧𝑠𝑠𝑠𝑠𝑘𝑘𝑘𝑘𝑚𝑚𝑚𝑚 ≺𝑠𝑠𝑠𝑠 ′ 𝑢𝑢𝑢𝑢(𝑖𝑖𝑖𝑖 ′ ). For example,

the values 𝑟𝑟𝑟𝑟𝑢𝑢𝑢𝑢(𝑎𝑎𝑎𝑎1 , 𝑠𝑠𝑠𝑠3 ) , 𝑟𝑟𝑟𝑟𝑢𝑢𝑢𝑢(𝑏𝑏𝑏𝑏1 , 𝑠𝑠𝑠𝑠3 ) and 𝑟𝑟𝑟𝑟𝑢𝑢𝑢𝑢(𝑏𝑏𝑏𝑏3 , 𝑠𝑠𝑠𝑠3 ) arerespectively equal to 89, 84 and 18.
Table 3: The utility matrix of 𝑠𝑠𝑠𝑠3

Definition 9 (Ending q-item maximum utility)
Given a sequence 𝑠𝑠𝑠𝑠 = ⟨𝑋𝑋𝑋𝑋1 𝑋𝑋𝑋𝑋2 … 𝑋𝑋𝑋𝑋𝑛𝑛𝑛𝑛 ⟩ where 𝑋𝑋𝑋𝑋𝑗𝑗𝑗𝑗 (1 ≤ 𝑗𝑗𝑗𝑗 ≤𝑛𝑛𝑛𝑛) is a q-itemset and a sequence 𝑡𝑡𝑡𝑡 = ⟨𝑡𝑡𝑡𝑡1 𝑡𝑡𝑡𝑡2 … 𝑡𝑡𝑡𝑡𝑚𝑚𝑚𝑚 ⟩. If any
q-subsequence 𝑠𝑠𝑠𝑠𝑎𝑎𝑎𝑎 = �𝑋𝑋𝑋𝑋𝑎𝑎𝑎𝑎1 𝑋𝑋𝑋𝑋𝑎𝑎𝑎𝑎2 … 𝑋𝑋𝑋𝑋𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚 � (𝑠𝑠𝑠𝑠𝑎𝑎𝑎𝑎 ⊆ 𝑠𝑠𝑠𝑠 ∧ 𝑠𝑠𝑠𝑠𝑎𝑎𝑎𝑎 ∼item tid1 tid2 tid3 tid4
a

2

0

0

0

b

5

0

10

0

c

0

9

0

0

d

0

8

0

12

e

18

0

6

0

g

0

21

0

0

𝑡𝑡𝑡𝑡) where 𝑋𝑋𝑋𝑋𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚 = ��𝑖𝑖𝑖𝑖𝑎𝑎𝑎𝑎1 , 𝑞𝑞𝑞𝑞𝑎𝑎𝑎𝑎1 ��𝑖𝑖𝑖𝑖𝑎𝑎𝑎𝑎2 , 𝑞𝑞𝑞𝑞𝑎𝑎𝑎𝑎2 � … �𝑖𝑖𝑖𝑖𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚 , 𝑞𝑞𝑞𝑞𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚 ��, then

�𝑖𝑖𝑖𝑖𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚 , 𝑞𝑞𝑞𝑞𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚 � is called the ending q-item of sequence 𝑡𝑡𝑡𝑡 in𝑠𝑠𝑠𝑠. The ending q-item maximum utility of a sequence 𝑡𝑡𝑡𝑡
in 𝑠𝑠𝑠𝑠 is denoted and defined as 𝑢𝑢𝑢𝑢(𝑡𝑡𝑡𝑡, 𝑖𝑖𝑖𝑖, 𝑠𝑠𝑠𝑠) =max { 𝑢𝑢𝑢𝑢(𝑠𝑠𝑠𝑠′)|𝑠𝑠𝑠𝑠′ ∼ 𝑡𝑡𝑡𝑡 ∧ 𝑠𝑠𝑠𝑠′ ⊆ 𝑠𝑠𝑠𝑠 ∧ 𝑖𝑖𝑖𝑖 ∈ 𝑠𝑠𝑠𝑠′}.
For example, the ending q-items of 𝑡𝑡𝑡𝑡 = ⟨𝑏𝑏𝑏𝑏𝑑𝑑𝑑𝑑⟩ in 𝑠𝑠𝑠𝑠3 are
𝑑𝑑𝑑𝑑2 , 𝑑𝑑𝑑𝑑4 and their ending q-item maximum utility are𝑢𝑢𝑢𝑢(⟨𝑏𝑏𝑏𝑏𝑑𝑑𝑑𝑑⟩, 𝑑𝑑𝑑𝑑2 , 𝑠𝑠𝑠𝑠3 ) = max(13) = 13 and 𝑢𝑢𝑢𝑢(⟨𝑏𝑏𝑏𝑏𝑑𝑑𝑑𝑑⟩, 𝑑𝑑𝑑𝑑4 , 𝑠𝑠𝑠𝑠3 ) =max(17,22) = 22, respectively.

Table 4: The remaining utility matrix of 𝑠𝑠𝑠𝑠3

item tid1 tid2 tid3 tid4
a

89

0

0

0

b

84

0

18

0

c

0

57

0

0

d

0

49

0

0

e

66

0

12

0

g

0

28

0

0

Definition 10 (Sequence utility)
The sequence utility of a sequence 𝑡𝑡𝑡𝑡 = ⟨𝑡𝑡𝑡𝑡1 𝑡𝑡𝑡𝑡2 … 𝑡𝑡𝑡𝑡𝑚𝑚𝑚𝑚 ⟩ in𝑠𝑠𝑠𝑠 = ⟨𝑋𝑋𝑋𝑋1 𝑋𝑋𝑋𝑋2 … 𝑋𝑋𝑋𝑋𝑛𝑛𝑛𝑛 ⟩ is denoted and defined as 𝑣𝑣𝑣𝑣(𝑡𝑡𝑡𝑡, 𝑠𝑠𝑠𝑠) =⋃𝑠𝑠𝑠𝑠′ ∼𝑡𝑡𝑡𝑡∧𝑠𝑠𝑠𝑠′ ⊆𝑠𝑠𝑠𝑠 𝑢𝑢𝑢𝑢(𝑠𝑠𝑠𝑠 ′ ). The utility of t in the dataset 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐵𝐵𝐵𝐵 isdenoted and defined as a utility set: 𝑣𝑣𝑣𝑣(𝑡𝑡𝑡𝑡) = ⋃𝑠𝑠𝑠𝑠∈𝑆𝑆𝑆𝑆 𝑣𝑣𝑣𝑣(𝑡𝑡𝑡𝑡, 𝑠𝑠𝑠𝑠).
For example, the utility of 𝑡𝑡𝑡𝑡 = ⟨𝑐𝑐𝑐𝑐𝑏𝑏𝑏𝑏⟩ in 𝑠𝑠𝑠𝑠1 is 𝑣𝑣𝑣𝑣(𝑡𝑡𝑡𝑡, 𝑠𝑠𝑠𝑠1 )= {𝑢𝑢𝑢𝑢(⟨(𝑐𝑐𝑐𝑐, 2)(𝑏𝑏𝑏𝑏, 1)⟩), 𝑢𝑢𝑢𝑢(⟨(𝑐𝑐𝑐𝑐, 2)(𝑏𝑏𝑏𝑏, 3)⟩), 𝑢𝑢𝑢𝑢(⟨(𝑐𝑐𝑐𝑐, 3)(𝑏𝑏𝑏𝑏, 3)⟩)}= {11, 21, 24} . The utility of 𝑡𝑡𝑡𝑡 in 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐵𝐵𝐵𝐵 is 𝑣𝑣𝑣𝑣(𝑡𝑡𝑡𝑡) ={11, 21, 24,{𝑣𝑣𝑣𝑣(𝑡𝑡𝑡𝑡, 𝑠𝑠𝑠𝑠1 ), 𝑣𝑣𝑣𝑣(𝑡𝑡𝑡𝑡, 𝑠𝑠𝑠𝑠2 ), 𝑣𝑣𝑣𝑣(𝑡𝑡𝑡𝑡, 𝑠𝑠𝑠𝑠3 ), 𝑣𝑣𝑣𝑣(𝑡𝑡𝑡𝑡, 𝑠𝑠𝑠𝑠4 )} =16, 16, 19, 13, 13}.

Definition 7 (Remaining utility matrix)
The remaining utility matrix of 𝑠𝑠𝑠𝑠 is 𝑚𝑚𝑚𝑚 × 𝑛𝑛𝑛𝑛 matrix,
where 𝑚𝑚𝑚𝑚 and 𝑛𝑛𝑛𝑛 are the number of q-items and qitemsets (transactions) in 𝑠𝑠𝑠𝑠 . The element at theposition (𝑘𝑘𝑘𝑘, 𝑗𝑗𝑗𝑗)(0 ≤ 𝑘𝑘𝑘𝑘 < 𝑚𝑚𝑚𝑚, 0 ≤ 𝑗𝑗𝑗𝑗 < 𝑛𝑛𝑛𝑛) of theremaining utility matrix stores the 𝑟𝑟𝑟𝑟𝑢𝑢𝑢𝑢(𝑖𝑖𝑖𝑖𝑘𝑘𝑘𝑘 , 𝑞𝑞𝑞𝑞) of q-item(𝑖𝑖𝑖𝑖𝑘𝑘𝑘𝑘 , 𝑞𝑞𝑞𝑞) in q-itemset j. For example, Table 4 shows theremaining utility matrix of 𝑠𝑠𝑠𝑠3 .

Definition 11 (Sequence maximum utility)
Given a sequence 𝑡𝑡𝑡𝑡, the maximum utility of 𝑡𝑡𝑡𝑡 in 𝑠𝑠𝑠𝑠 isdenotedanddefinedas𝑢𝑢𝑢𝑢𝑚𝑚𝑚𝑚𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚 (𝑡𝑡𝑡𝑡, 𝑠𝑠𝑠𝑠) =’’’max{ 𝑢𝑢𝑢𝑢(𝑡𝑡𝑡𝑡, 𝑖𝑖𝑖𝑖, 𝑠𝑠𝑠𝑠): ∀𝑖𝑖𝑖𝑖 ∈ 𝑠𝑠𝑠𝑠 ∧ 𝑠𝑠𝑠𝑠 ∼ 𝑡𝑡𝑡𝑡 ∧ 𝑠𝑠𝑠𝑠 ⊆ 𝑠𝑠𝑠𝑠}.
The maximum utility of a sequence 𝑡𝑡𝑡𝑡 in a q-sequence
dataset 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐵𝐵𝐵𝐵 is denoted and defined as 𝑢𝑢𝑢𝑢𝑚𝑚𝑚𝑚𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚 (𝑡𝑡𝑡𝑡) =∑ 𝑢𝑢𝑢𝑢𝑚𝑚𝑚𝑚𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚 (𝑡𝑡𝑡𝑡, 𝑠𝑠𝑠𝑠) : ∀𝑠𝑠𝑠𝑠 ∈ 𝑆𝑆𝑆𝑆.
For example, the maximum utility of the sequence 𝑡𝑡𝑡𝑡 =⟨𝑐𝑐𝑐𝑐𝑏𝑏𝑏𝑏⟩ in the sequence dataset 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐵𝐵𝐵𝐵 is 𝑢𝑢𝑢𝑢𝑚𝑚𝑚𝑚𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚 (𝑡𝑡𝑡𝑡) =𝑢𝑢𝑢𝑢𝑚𝑚𝑚𝑚𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚 (⟨𝑐𝑐𝑐𝑐𝑏𝑏𝑏𝑏⟩, 𝑠𝑠𝑠𝑠1 ) + 𝑢𝑢𝑢𝑢𝑚𝑚𝑚𝑚𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚 (⟨𝑐𝑐𝑐𝑐𝑏𝑏𝑏𝑏⟩, 𝑠𝑠𝑠𝑠2 ) + 𝑢𝑢𝑢𝑢𝑚𝑚𝑚𝑚𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚 (⟨𝑐𝑐𝑐𝑐𝑏𝑏𝑏𝑏⟩, 𝑠𝑠𝑠𝑠3 ) +𝑢𝑢𝑢𝑢𝑚𝑚𝑚𝑚𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚 (⟨𝑐𝑐𝑐𝑐𝑏𝑏𝑏𝑏⟩, 𝑠𝑠𝑠𝑠4 ) = 24 + 16 + 19 + 13 = 72.

Definition 8 (Matching)
Given 𝑠𝑠𝑠𝑠 = ⟨(𝑖𝑖𝑖𝑖1 , 𝑞𝑞𝑞𝑞1 )(𝑖𝑖𝑖𝑖2 , 𝑞𝑞𝑞𝑞2 ) … (𝑖𝑖𝑖𝑖𝑛𝑛𝑛𝑛 , 𝑞𝑞𝑞𝑞𝑛𝑛𝑛𝑛 )⟩ and a sequence𝑡𝑡𝑡𝑡 = ⟨𝑡𝑡𝑡𝑡1 𝑡𝑡𝑡𝑡2 … 𝑡𝑡𝑡𝑡𝑚𝑚𝑚𝑚 ⟩, 𝑠𝑠𝑠𝑠 is said to match 𝑡𝑡𝑡𝑡 if and only if 𝑛𝑛𝑛𝑛 =𝑚𝑚𝑚𝑚 and 𝑖𝑖𝑖𝑖𝑘𝑘𝑘𝑘 = 𝑡𝑡𝑡𝑡𝑘𝑘𝑘𝑘 for 1 ≤ 𝑘𝑘𝑘𝑘 ≤ 𝑛𝑛𝑛𝑛, denoted as t ∼ 𝑠𝑠𝑠𝑠.
For example, sequence ⟨(𝑎𝑎𝑎𝑎𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐)(𝑎𝑎𝑎𝑎𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏)(𝑏𝑏𝑏𝑏𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑)⟩ matches
𝑠𝑠𝑠𝑠1 . Note that because of quantities, two q-items may
be considered different, although they contain thesame item. Hence there could be multiple qsubsequences of a q-sequence matching a given

5

NAIS Journal

47

Definition 12 (High utility sequential pattern)
A sequence 𝑡𝑡𝑡𝑡 is said to be a high utility sequential
pattern if 𝑢𝑢𝑢𝑢𝑚𝑚𝑚𝑚𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚 (𝑡𝑡𝑡𝑡) ≥ 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 , where 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 is agiven user-specified minimum utility threshold. For
example, given 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 = 154 , the complete set of
HUSPs in the sequence dataset SDB is shown in Table5.

𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 =154, 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 =50%, the set of CHUSPs isshown in Table 6.
Table 6: CHUSP for 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 = 130, 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 = 50%

CHUSP

HUSP

utility

HUSP

utility⟨(𝑐𝑐𝑐𝑐𝑔𝑔𝑔𝑔)⟩

154⟨(𝑐𝑐𝑐𝑐𝑔𝑔𝑔𝑔)(𝑏𝑏𝑏𝑏𝑒𝑒𝑒𝑒)⟩

186⟨(𝑐𝑐𝑐𝑐𝑔𝑔𝑔𝑔)(𝑎𝑎𝑎𝑎𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏)(𝑏𝑏𝑏𝑏𝑒𝑒𝑒𝑒)⟩�(𝑐𝑐𝑐𝑐𝑔𝑔𝑔𝑔)(𝑎𝑎𝑎𝑎𝑏𝑏𝑏𝑏)(𝑏𝑏𝑏𝑏𝑒𝑒𝑒𝑒)�

159
155

⟨(𝑔𝑔𝑔𝑔)⟩⟨(𝑔𝑔𝑔𝑔)(𝑏𝑏𝑏𝑏𝑒𝑒𝑒𝑒)⟩2⟨(𝑐𝑐𝑐𝑐𝑔𝑔𝑔𝑔)⟩

154

4⟨(𝑐𝑐𝑐𝑐𝑔𝑔𝑔𝑔)(𝑎𝑎𝑎𝑎𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏)(𝑏𝑏𝑏𝑏𝑒𝑒𝑒𝑒)⟩⟨(𝑐𝑐𝑐𝑐𝑔𝑔𝑔𝑔)(𝑏𝑏𝑏𝑏𝑒𝑒𝑒𝑒)⟩203⟨(𝑐𝑐𝑐𝑐)(𝑎𝑎𝑎𝑎𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏)(𝑏𝑏𝑏𝑏𝑒𝑒𝑒𝑒)⟩168⟨(𝑐𝑐𝑐𝑐)(𝑏𝑏𝑏𝑏𝑒𝑒𝑒𝑒)⟩

147

4

134

2

159

2

186

3

148

3

138

4

Definition 16 (ULS: utility list structure)
Assume that a sequence 𝑡𝑡𝑡𝑡 has 𝑘𝑘𝑘𝑘(𝑘𝑘𝑘𝑘 > 0) ending qitems 𝑖𝑖𝑖𝑖 in a q-sequence 𝑠𝑠𝑠𝑠 where 𝑖𝑖𝑖𝑖1 < 𝑖𝑖𝑖𝑖2 < ⋯ < 𝑖𝑖𝑖𝑖𝑘𝑘𝑘𝑘 . The
ULS of 𝑡𝑡𝑡𝑡 in 𝑠𝑠𝑠𝑠 is a list of 𝑘𝑘𝑘𝑘 elements, where theα𝑡𝑡𝑡𝑡ℎ (1 ≤ α ≤ 𝑘𝑘𝑘𝑘) element in the ULS contains:
𝑡𝑡𝑡𝑡𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 : the itemset 𝐼𝐼𝐼𝐼𝑆𝑆𝑆𝑆 of 𝑖𝑖𝑖𝑖α of 𝑡𝑡𝑡𝑡 in 𝑠𝑠𝑠𝑠
⎧ 𝑎𝑎𝑎𝑎𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐: the maximum utility of 𝑖𝑖𝑖𝑖 in 𝑡𝑡𝑡𝑡
𝛼𝛼𝛼𝛼⎨𝑙𝑙𝑙𝑙𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖: a pointer pointing to either the(𝛼𝛼𝛼𝛼 + 1)𝑡𝑡𝑡𝑡ℎ element or null⎩

Definition 14 (Frequent high utility sequential
patterns)
Given a sequence 𝑡𝑡𝑡𝑡 and the dataset 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐵𝐵𝐵𝐵 ={𝑠𝑠𝑠𝑠1 , 𝑠𝑠𝑠𝑠2 , … , 𝑠𝑠𝑠𝑠𝑛𝑛𝑛𝑛 }, 𝑡𝑡𝑡𝑡 is said to be a frequent high utility
sequential pattern (FHUSP) if and only if 𝑡𝑡𝑡𝑡 is a HUSPand 𝑠𝑠𝑠𝑠𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢(𝑡𝑡𝑡𝑡) ≥ 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖, for a threshold 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 set by
the user.

Definition 17 (UCS: utility chain structure)
Given a sequence 𝑡𝑡𝑡𝑡 and q-sequence 𝑠𝑠𝑠𝑠. The 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚 of 𝑡𝑡𝑡𝑡 in𝑠𝑠𝑠𝑠 is denoted and defined as
𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚(𝑡𝑡𝑡𝑡, 𝑠𝑠𝑠𝑠)
𝑝𝑝𝑝𝑝𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒: is the prefix extension utility of 𝑡𝑡𝑡𝑡 in 𝑠𝑠𝑠𝑠
=�𝑚𝑚𝑚𝑚𝑈𝑈𝑈𝑈𝑆𝑆𝑆𝑆: is the 𝑚𝑚𝑚𝑚𝑈𝑈𝑈𝑈𝑆𝑆𝑆𝑆 of sequence 𝑡𝑡𝑡𝑡 in 𝑠𝑠𝑠𝑠

Definition 18 (CHUS: node structure))
Given a sequence 𝑡𝑡𝑡𝑡, the 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚 of 𝑡𝑡𝑡𝑡 in 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐵𝐵𝐵𝐵 is denotedand defined as
𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚(𝑡𝑡𝑡𝑡)
𝑠𝑠𝑠𝑠𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖: the set of sequence IDs containing 𝑡𝑡𝑡𝑡 in 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐵𝐵𝐵𝐵= � 𝑢𝑢𝑢𝑢𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 = �(𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚(𝑡𝑡𝑡𝑡, 𝑠𝑠𝑠𝑠))

Definition 15 (Closed frequent high utility sequential
patterns)
Given a sequence 𝑡𝑡𝑡𝑡 and the dataset 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐵𝐵𝐵𝐵 ={𝑠𝑠𝑠𝑠1 , 𝑠𝑠𝑠𝑠2 , … , 𝑠𝑠𝑠𝑠𝑛𝑛𝑛𝑛 }, 𝑡𝑡𝑡𝑡 is said to be a closed frequent highutility sequential pattern (CHUSP) if and only if 𝑡𝑡𝑡𝑡 is a
FHUSP and there exists no FHUSP that is a proper
super-sequence of 𝑡𝑡𝑡𝑡 and has the same support.
Mathematically, the set of all CHUSPs is defined by
𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝐶𝐶𝐶𝐶 = {𝑠𝑠𝑠𝑠 ∈ 𝐹𝐹𝐹𝐹𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶|𝑠𝑠𝑠𝑠′ ∉ 𝐹𝐹𝐹𝐹𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶: 𝑠𝑠𝑠𝑠
⊆ 𝑠𝑠𝑠𝑠′ ∧ 𝑠𝑠𝑠𝑠𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢(𝑠𝑠𝑠𝑠) = 𝑠𝑠𝑠𝑠𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢(𝑠𝑠𝑠𝑠′)}
The goal of CHUSPM is to discover the set of CHUSPs
that satisfies Definition 15. For example, given

𝑠𝑠𝑠𝑠∈𝑆𝑆𝑆𝑆

Definition 19 (Concatenation)
Given a sequence 𝑡𝑡𝑡𝑡 , there are two types ofconcatenation of 𝑡𝑡𝑡𝑡:
6

NAIS Journal

133⟨(𝑏𝑏𝑏𝑏𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐)⟩

Definition 13 (Support of a pattern)
Given a sequence 𝑡𝑡𝑡𝑡 and the dataset 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐵𝐵𝐵𝐵 ={𝑠𝑠𝑠𝑠1 , 𝑠𝑠𝑠𝑠2 , … , 𝑠𝑠𝑠𝑠𝑛𝑛𝑛𝑛 } , the support (or absolute support or
support.count) of the sequence 𝑡𝑡𝑡𝑡 in 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐵𝐵𝐵𝐵 is defined as
the number of q-sequences that contain 𝑡𝑡𝑡𝑡 and isdenoted by 𝑠𝑠𝑠𝑠𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢(𝑡𝑡𝑡𝑡). Mathematically, the support of 𝑡𝑡𝑡𝑡
is defined as 𝑠𝑠𝑠𝑠𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢(𝑡𝑡𝑡𝑡) = |{𝑠𝑠𝑠𝑠|𝑠𝑠𝑠𝑠 ∼ 𝑡𝑡𝑡𝑡 ∧ 𝑠𝑠𝑠𝑠 ∈ 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐵𝐵𝐵𝐵}|.
For example, 𝑠𝑠𝑠𝑠𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢(⟨(𝑐𝑐𝑐𝑐𝑔𝑔𝑔𝑔)⟩) = |{𝑠𝑠𝑠𝑠1 , 𝑠𝑠𝑠𝑠2 , 𝑠𝑠𝑠𝑠3 , 𝑠𝑠𝑠𝑠4 }| = 4
𝑠𝑠𝑠𝑠𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢(⟨(𝑐𝑐𝑐𝑐𝑔𝑔𝑔𝑔)(𝑏𝑏𝑏𝑏𝑒𝑒𝑒𝑒)⟩) = |{𝑠𝑠𝑠𝑠1 , 𝑠𝑠𝑠𝑠3 , 𝑠𝑠𝑠𝑠4 }| = 3.

48⟨(𝑎𝑎𝑎𝑎𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏)(𝑏𝑏𝑏𝑏𝑒𝑒𝑒𝑒)⟩⟨(𝑎𝑎𝑎𝑎𝑏𝑏𝑏𝑏)(𝑏𝑏𝑏𝑏𝑒𝑒𝑒𝑒)⟩

Table 5: The set of HUSPs for 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 = 154

utility support

Theorem 2 (Pruning strategy by PEU and RSU [2]))Given a pattern 𝑡𝑡𝑡𝑡, 𝐶𝐶𝐶𝐶𝑃𝑃𝑃𝑃𝑚𝑚𝑚𝑚(𝑡𝑡𝑡𝑡) and 𝑅𝑅𝑅𝑅𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆(𝑡𝑡𝑡𝑡) are considered
as upper bounds on the utility of 𝑡𝑡𝑡𝑡 and its descendants.
If 𝐶𝐶𝐶𝐶𝑃𝑃𝑃𝑃𝑚𝑚𝑚𝑚(𝑡𝑡𝑡𝑡) < 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 or 𝑅𝑅𝑅𝑅𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆(𝑡𝑡𝑡𝑡) < 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 , then 𝑡𝑡𝑡𝑡
and its descendants can be pruned from the search
space without affecting the result of the mining
process.

I − Extension: insert an item into the last itemset of 𝑡𝑡𝑡𝑡
�S − Extension: add a new 1 − itemset at the end of 𝑡𝑡𝑡𝑡
For example, ⟨(𝑎𝑎𝑎𝑎𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐)⟩ and ⟨(𝑎𝑎𝑎𝑎𝑐𝑐𝑐𝑐)(𝑎𝑎𝑎𝑎)⟩ is generated by
performing an I-Extension and an S-Extension of thesequence ⟨(𝑎𝑎𝑎𝑎𝑐𝑐𝑐𝑐)⟩, respectively.

Definition 20 (SWU: weighted sequence utilization)
SWU of a sequence 𝑡𝑡𝑡𝑡 in 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐵𝐵𝐵𝐵 is defined as
𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑚𝑚𝑚𝑚(𝑡𝑡𝑡𝑡) =�𝑠𝑠𝑠𝑠 ′ ∼𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 ′ ⊆𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆

Theorem 3 (MSP: minimum support-based pruning)
Given a sequence 𝑡𝑡𝑡𝑡 , if 𝑠𝑠𝑠𝑠𝑢𝑢𝑢𝑢𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝(𝑡𝑡𝑡𝑡) < 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 , then thesequence 𝑡𝑡𝑡𝑡 and its descendants are not CHUSP.

𝑢𝑢𝑢𝑢(𝑠𝑠𝑠𝑠)

For example, 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑚𝑚𝑚𝑚(⟨𝑎𝑎𝑎𝑎(𝑏𝑏𝑏𝑏𝑒𝑒𝑒𝑒)⟩) = 𝑢𝑢𝑢𝑢(𝑠𝑠𝑠𝑠1 ) + 𝑢𝑢𝑢𝑢(𝑠𝑠𝑠𝑠2 ) + 𝑢𝑢𝑢𝑢(𝑠𝑠𝑠𝑠3 ) +𝑢𝑢𝑢𝑢(𝑠𝑠𝑠𝑠4 )= 91 + 96 + 82 + 114 = 383.

4. Proposal Algorithm

Theorem 1 (Sequence weighted downward closure
property)
Given 𝑡𝑡𝑡𝑡1 and 𝑡𝑡𝑡𝑡2 , if 𝑡𝑡𝑡𝑡2 contains 𝑡𝑡𝑡𝑡1 , then 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑚𝑚𝑚𝑚(𝑡𝑡𝑡𝑡2 ) ≤𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑚𝑚𝑚𝑚(𝑡𝑡𝑡𝑡1 ). Theorem 1 can be used to evaluate whether
an item is promising [5, 11, 14]. The CHUSP algorithm
also uses this theorem to prune all items with an
𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑚𝑚𝑚𝑚 < 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 .

Definition 21 (PEU: prefix extension utility)
Given a sequence 𝑡𝑡𝑡𝑡 and 𝑠𝑠𝑠𝑠. The 𝐶𝐶𝐶𝐶𝑃𝑃𝑃𝑃𝑚𝑚𝑚𝑚 of 𝑡𝑡𝑡𝑡 in 𝑠𝑠𝑠𝑠 is denotedand defined as
𝐶𝐶𝐶𝐶𝑃𝑃𝑃𝑃𝑚𝑚𝑚𝑚(𝑡𝑡𝑡𝑡, 𝑠𝑠𝑠𝑠) = max{ 𝐶𝐶𝐶𝐶𝑃𝑃𝑃𝑃𝑚𝑚𝑚𝑚(𝑡𝑡𝑡𝑡, 𝑖𝑖𝑖𝑖𝑘𝑘𝑘𝑘 , 𝑠𝑠𝑠𝑠): ∀𝑖𝑖𝑖𝑖𝑘𝑘𝑘𝑘 that is an ending
q-item of 𝑡𝑡𝑡𝑡 in 𝑠𝑠𝑠𝑠}
𝑢𝑢𝑢𝑢(𝑡𝑡𝑡𝑡, 𝑖𝑖𝑖𝑖𝑘𝑘𝑘𝑘 , 𝑠𝑠𝑠𝑠) + 𝑟𝑟𝑟𝑟𝑢𝑢𝑢𝑢(𝑖𝑖𝑖𝑖𝑘𝑘𝑘𝑘 , 𝑠𝑠𝑠𝑠), 𝑖𝑖𝑖𝑖𝑓𝑓𝑓𝑓 𝑟𝑟𝑟𝑟𝑢𝑢𝑢𝑢(𝑖𝑖𝑖𝑖𝑘𝑘𝑘𝑘 , 𝑠𝑠𝑠𝑠) > 0
𝐶𝐶𝐶𝐶𝑃𝑃𝑃𝑃𝑚𝑚𝑚𝑚(𝑡𝑡𝑡𝑡, 𝑖𝑖𝑖𝑖𝑘𝑘𝑘𝑘 , 𝑠𝑠𝑠𝑠) = �
0, otherwise
The 𝐶𝐶𝐶𝐶𝑃𝑃𝑃𝑃𝑚𝑚𝑚𝑚 of 𝑡𝑡𝑡𝑡 in 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐵𝐵𝐵𝐵 is denoted and defined as:
𝐶𝐶𝐶𝐶𝑃𝑃𝑃𝑃𝑚𝑚𝑚𝑚(𝑡𝑡𝑡𝑡) = ∑𝑠𝑠𝑠𝑠′ ∼𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡′ ⊆𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝐶𝐶𝐶𝐶𝑃𝑃𝑃𝑃𝑚𝑚𝑚𝑚(𝑡𝑡𝑡𝑡, 𝑠𝑠𝑠𝑠)

Given 𝑡𝑡𝑡𝑡1 and 𝑡𝑡𝑡𝑡2 , if 𝑡𝑡𝑡𝑡2 contains 𝑡𝑡𝑡𝑡1 then 𝑢𝑢𝑢𝑢(𝑡𝑡𝑡𝑡2 ) ≤𝐶𝐶𝐶𝐶𝑃𝑃𝑃𝑃𝑚𝑚𝑚𝑚(𝑡𝑡𝑡𝑡1 ).

Definition 22 (RSU: reduced sequence utility)
Given a sequence 𝑡𝑡𝑡𝑡 and 𝑠𝑠𝑠𝑠. The 𝑅𝑅𝑅𝑅𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆 of 𝑡𝑡𝑡𝑡 in 𝑠𝑠𝑠𝑠 is denotedand defined as:
𝑅𝑅𝑅𝑅𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆(𝑡𝑡𝑡𝑡, 𝑠𝑠𝑠𝑠)

𝐶𝐶𝐶𝐶𝑃𝑃𝑃𝑃𝑚𝑚𝑚𝑚(𝑡𝑡𝑡𝑡′)| 𝑡𝑡𝑡𝑡′ ⊆ 𝑡𝑡𝑡𝑡 𝑡 𝑡𝑡𝑡𝑡1 ∼ 𝑡𝑡𝑡𝑡 𝑡 𝑡𝑡𝑡𝑡1 ⊆ 𝑠𝑠𝑠𝑠𝑠𝑠 𝑠𝑠𝑠𝑠2 ∼ 𝑡𝑡𝑡𝑡 𝑡 𝑡𝑡𝑡𝑡2 ⊆ 𝑠𝑠𝑠𝑠
0, otherwise
The RSU of the sequence 𝑡𝑡𝑡𝑡 in 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐵𝐵𝐵𝐵 is denoted anddefined as:=�

𝑅𝑅𝑅𝑅𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆(𝑡𝑡𝑡𝑡) =�𝑠𝑠𝑠𝑠 ′ ∼𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 ′ ⊆𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑅𝑅𝑅𝑅𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆(𝑡𝑡𝑡𝑡, 𝑠𝑠𝑠𝑠)

Given 𝑡𝑡𝑡𝑡1 and 𝑡𝑡𝑡𝑡2 , if 𝑡𝑡𝑡𝑡2 contains 𝑡𝑡𝑡𝑡1 then 𝑢𝑢𝑢𝑢(𝑡𝑡𝑡𝑡2 ) ≤𝑅𝑅𝑅𝑅𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆(𝑡𝑡𝑡𝑡1 ).

7

NAIS Journal

49

The pseudo-code of the CHUSP algorithm is shownin Algorithm 1. The input is a q-sequence dataset 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐵𝐵𝐵𝐵,
a sequence 𝑡𝑡𝑡𝑡 with its 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚 structure, and two
predefined parameters: 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑖𝑖𝑖𝑖𝑙𝑙𝑙𝑙 , 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛. First, a set
called 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝐶𝐶𝐶𝐶_𝑆𝑆𝑆𝑆𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 is initialized to keep all CHUSPs.
We also use the ¬𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝐶𝐶𝐶𝐶_𝑆𝑆𝑆𝑆𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 to track all but not
closed high utility sequential patterns. The algorithm
scans 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐵𝐵𝐵𝐵 to calculate the 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑚𝑚𝑚𝑚 of all items in 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐵𝐵𝐵𝐵(line 3). It then selects all items with an 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑚𝑚𝑚𝑚 ofgreater than 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 and builds the initial 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚
structure and the lexicographic tree required by themining process. It also removes all items with an 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑚𝑚𝑚𝑚
value less than 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 (line 4). The topmost node inthat tree is the root node, where its children are qsequences that contain a single item. Each node otherthan the root stores a sequence 𝑡𝑡𝑡𝑡, the 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚 structureof 𝑡𝑡𝑡𝑡, utility matrices, remaining utility matrices, andthe list that contains sequence IDs called 𝑠𝑠𝑠𝑠𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑠𝑠𝑠𝑠𝑡𝑡𝑡𝑡 of
1 q-items in q-sequences of 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐵𝐵𝐵𝐵.
If 𝐶𝐶𝐶𝐶𝑃𝑃𝑃𝑃𝑚𝑚𝑚𝑚(𝑡𝑡𝑡𝑡) is less than 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 , then the algorithm willconsider 𝑡𝑡𝑡𝑡 as a leaf and will not expand thelexicographic tree using node 𝑡𝑡𝑡𝑡, i.e., all its descendants
will be pruned (lines 5-6). In the next step, thealgorithm scans the projected dataset that includes
the 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑆𝑆𝑆𝑆 of 𝑡𝑡𝑡𝑡 in 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐵𝐵𝐵𝐵 to collect all items that can be
combined with 𝑡𝑡𝑡𝑡 to form a new sequence by IExtension or S-Extension (line 7). Each item with an
𝑅𝑅𝑅𝑅𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆 value lower than 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 is discarded from themining process (line 8). Then, the algorithm performs
a loop over all items in the iExts (lines 9-15) and sExts(lines 16-22). For each item 𝑖𝑖𝑖𝑖 in the iExts, thealgorithm performs an I-Extension with this item to
850

NAIS Journal

form a new sequence 𝑡𝑡𝑡𝑡 ′ by inserting 𝑖𝑖𝑖𝑖 in the lastitemset of 𝑡𝑡𝑡𝑡 . In addition, the 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚 structure,𝑠𝑠𝑠𝑠𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑠𝑠𝑠𝑠𝑡𝑡𝑡𝑡 , and the maximum utility of 𝑡𝑡𝑡𝑡 ′ areconstructed and calculated by extending the 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚 of𝑡𝑡𝑡𝑡 (lines 10-11). To reduce the search space and enhance
the mining process, CHUSP applies the MSP strategy(Theorem 3) to discard non-frequent patterns (line 12).
If the condition returns true, CHUSP stops
considering these patterns and backtracks to theprevious step. Otherwise, the algorithm checks if thepattern's utility value is greater than 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 . If yes,
the pattern is a high utility sequential pattern (line 13).
CHUSP calls the 𝑐𝑐𝑐𝑐𝑐𝑒𝑒𝑒𝑒𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑒𝑒𝑒𝑒𝑠𝑠𝑠𝑠𝑒𝑒𝑒𝑒𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑒𝑒𝑒𝑒𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟 procedure tocheck if that HUSP is closed (line 14).
The inputs of 𝑐𝑐𝑐𝑐𝑐𝑒𝑒𝑒𝑒𝑐𝑐𝑐𝑐𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑒𝑒𝑒𝑒𝑠𝑠𝑠𝑠𝑒𝑒𝑒𝑒𝑑𝑑𝑑𝑑𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑒𝑒𝑒𝑒𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑠𝑠𝑠𝑠 procedure are
two patterns 𝑡𝑡𝑡𝑡 , 𝑡𝑡𝑡𝑡 ′ , 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝐶𝐶𝐶𝐶_𝑆𝑆𝑆𝑆𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 and ¬𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝐶𝐶𝐶𝐶_𝑆𝑆𝑆𝑆𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 .
Note that the sequence 𝑡𝑡𝑡𝑡 ′ is a super-sequence of 𝑡𝑡𝑡𝑡 byperforming the I-Extension or S-Extension
concatenation. We consider 𝑡𝑡𝑡𝑡 and 𝑡𝑡𝑡𝑡 ′ as the previous
and current sequences since 𝑡𝑡𝑡𝑡 ′ is generated from 𝑡𝑡𝑡𝑡.
The procedure checks if the previous sequence 𝑡𝑡𝑡𝑡 is a
CHUSP by comparing its support count with thesupport count of the current sequence 𝑡𝑡𝑡𝑡 ′ . If the two
support values are equal, it means that 𝑡𝑡𝑡𝑡 is not a
CHUSP because it has a super-sequence with thesame support (break the Def. 15), then the procedurechecks if 𝑡𝑡𝑡𝑡 is in 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝐶𝐶𝐶𝐶_𝑆𝑆𝑆𝑆𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒, if yes then removes 𝑡𝑡𝑡𝑡 fromthis set (line 3). The procedure also checks if 𝑡𝑡𝑡𝑡 is in¬𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝐶𝐶𝐶𝐶_𝑆𝑆𝑆𝑆𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒; if No, add 𝑡𝑡𝑡𝑡 into this set (line 4). The
purpose of this action is to track all non-candidate
sequences. During mining, 𝑡𝑡𝑡𝑡 may be extended to other𝑡𝑡𝑡𝑡 ′ by doing other concatenations. In this case, 𝑡𝑡𝑡𝑡
involves in other checking procedures. The procedurethen inserts the current sequence 𝑡𝑡𝑡𝑡 ′ into the
𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝐶𝐶𝐶𝐶_𝑆𝑆𝑆𝑆𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 (line 5). It is worth noting that CHUSP isa recursive algorithm. Thus, the current sequence 𝑡𝑡𝑡𝑡 ′will be later called in other rounds of the algorithm toextend itself. In other words, the sequence 𝑡𝑡𝑡𝑡 ′ is thesuper-sequence of a sequence 𝑡𝑡𝑡𝑡 at this stage, but it willbe the sub-sequence of another sequence in anotherstage. Thus, any sequences in the 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝐶𝐶𝐶𝐶_𝑆𝑆𝑆𝑆𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 are
candidates and may be removed from the set when thealgorithm detects super-sequences having the same
support. If the supports of 𝑡𝑡𝑡𝑡 and 𝑡𝑡𝑡𝑡 ′ are different, thetwo patterns become candidates. The procedure adds
the current pattern 𝑡𝑡𝑡𝑡 ′ to the 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝐶𝐶𝐶𝐶_𝑆𝑆𝑆𝑆𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 as acandidate (line 8). Next, the procedure checks if theprevious sequence 𝑡𝑡𝑡𝑡 is in the ¬𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝐶𝐶𝐶𝐶_𝑆𝑆𝑆𝑆𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 . If yes,then it will not be a CHUSP candidate. Otherwise, 𝑡𝑡𝑡𝑡 isinserted into 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝐶𝐶𝐶𝐶_𝑆𝑆𝑆𝑆𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒.

Table 7: Characteristics of the datasets

DatasetThe CHUSP recursively calls itself to expand
𝑡𝑡𝑡𝑡 ′ (line 15). A similar process is performed for all items
in sExts. It passes a sequence and its projected dataset
to each recursive call as input parameters. The
sequence dataset 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐵𝐵𝐵𝐵 and lines 1-4 are used only for
initializing the algorithm and are not performed
during recursive calls. For each item in sExts, a newpattern is generated by performing an S-Extension(lines 16 to 22). When the algorithm completes
recursive calls, the algorithm traverses all patterns in
the 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝐶𝐶𝐶𝐶_𝑆𝑆𝑆𝑆𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 to remove non-CHUSPs from this list
(line 23). Finally, it returns all CHUSPs as the output.
5. Experimental Results
Experiments were performed to evaluate theperformance of CHUSP on a computer with a 64-bit
Intel(R) Xeon(R) Gold 6330 CPU @ 2.00GHz, 12 GB of
RAM, running Windows 10 Enterprise LTSC. The
source code is publicly available on GitHub. All thealgorithms were implemented in 𝐶𝐶𝐶𝐶#. Fig. 1 shows theuser interface of the CHUSP algorithm. The proposed
algorithm was compared with two algorithms. The
first algorithm is the HUS-Span algorithm [2] formining HUSPs. The second algorithm is FHUSP, an
extension of HUS-Span for mining FHUSPs. The
performance of the three algorithms has been
compared on six real datasets. The characteristics ofthese datasets are shown in Table 7. They are six reallife datasets. They have varied characteristics, suchas sparse and dense datasets, short and longsequences.
For each dataset, the 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 was decreased until
a clear winner was observed, or algorithms became toolong to execute. In some cases, a constraint on the
maximum length of CHUSP (𝑚𝑚𝑚𝑚𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚𝑈𝑈𝑈𝑈𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒ℎ) was used to
speed up the experiments. For 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 , a suitable
empirical value was chosen for each dataset to ensurethat the algorithms discovered a certain number of
CHUSPs. The 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 values for Sign, Kosarak10k,
BMSWebView1, BMSWebView2, Fifa and Bible were
set to 50%, 5%, 20%, 20%, 0.5%, 0.5%, respectively.

#Sequence#Item

Avg. seq
length
51.99

Sign

800

310

Kosarak10k

10,00010,094 8.14

BMSWebView1 59,601

497

2.51

BMSwebview2

77,512

3,340

4.62

Fifa

20,450

2,990

34.74

Bible

36,36913,905 21.64

Figure 1: The CHUSP application
First, the execution time of CHUSP is comparedwith HUS-Span and FHUSP. Fig. 2 shows that
CHUSP outperforms the compared algorithms on all
datasets. Each subfigure's vertical and horizontal axes
represent the execution time (milliseconds) andminimum utility threshold values, respectively. In
general, for all datasets, when the minimum utility
threshold is decreased or when datasets contain moresequences or longer sequences, the running time of thealgorithms increases. In that case, CHUSP can bemuch more efficient than the two algorithms,
especially on Sign, Bible, BMSWebview1, and FIFA
9NAIS Journal

51

datasets. On Sign (𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 = 50%) CHUSP is
respectively up to 295.7, 250.3, 222.7, 188.9, 156.6,
125.9, 116.2, 75.8, 50.9, and 37.5 times faster than
HUS-Span for 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 from 12,000 to 35,000 .
Compare with FHUSP, it is up to 292.72 , 245.01 ,215.88, 188.51, 154.50, 118.80, 111.47, 73.24, 50.24,
and 35.94. On BMSWebView2 (𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 = 50%)
CHUSP is respectively up to 12.2, 8.9, 7.6, 6.3, 4.7,
3.4, 3.2, 2.1, 1.9, and 1.7 times faster than HUS-Spanfor 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 from 10,000 to 100,000. It is respectively
up to 11.5, 8.0, 7.1, 5.8, 4.1, 3, 2.3, 1.8, 1.5, and 1.3
times faster than FHUSP. Similar results can beobserved for other datasets. The results indicate that
the MSP pruning strategy of CHUSP is effective andcan prune many non-frequent patterns. In addition,
the CHUS structure and pruning strategies are
suitable for mining CHUSPs. Thus, the algorithm canfacilitate the mining process and prune more noncandidates than HUS-Span and FHUSP algorithms.
Second, the algorithms have also been compared interms of memory performance for the six datasets forthe same 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 , 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖, and 𝑚𝑚𝑚𝑚𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈ℎ values asin the runtime experiment. Results are shown in Fig.
3 in terms of memory usage (vertical axes) for various
𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 values (horizontal axes). CHUSP consumes
less memory than HUS-Span in all cases. It meansthat the CHUSP structure is more effective than the
structure used by the HUS-Span algorithm. In
addition, the MSP strategy can filter many nonfrequent candidates. CHUSP is also better than
FHUSP in most cases, although they are very close insome cases. On FIFA and Bible, we can observe that
CHUSP performs much better than FHUSP. Except
for the BMSWebview1 dataset, FHUSP consumes lessmemory than CHUSP on large 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 values.
However, for low 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 values, when the algorithms
need more time to mine patterns, CHUSP
outperforms FHUSP. Generally, for each dataset, thememory usage increases when the 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 isdecreased, and it is also greater for larger datasets.
Finally, the number of patterns was measured forvarious 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 threshold values on each dataset. In

Fig. 4, vertical axes denote the number of patterns,
and horizontal axes indicate the corresponding
maximum threshold values. The number of patterns
generated by CHUSP is much less than that of HUSSpan and FHUSP for each dataset. On Sign
(𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 = 50%), for 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 from 12,000 to 35,000,
CHUSP found 62, 58, 51, 48, 41, 35, 31, 13, 5, and 3,
respectively. It can be observed that the number ofpatterns by CHUSP is respectively up to 169.1, 121.2,
93.7, 68.2, 37.7, 21.5, 16.5, 7.3, 3.4, and 1.3 times lessthan those found by HUS-Span. In addition, thenumber of patterns by CHUSP is respectively up to
1.13, 1.09, 1.1, 1.04, 1.02, 1.03, 1.03, 1.08, 1.00, and
1.00 times less than those found by FHUSP. On
Kosarak10k (𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 = 5%), the 𝑚𝑚𝑚𝑚𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑛𝑛𝑛𝑛𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔ℎ was set
to 3 for the 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 values of 10,000 and 20,000 for
HUS-Span and FHUSP; for CHUSP, this parameter
was set to full. For 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 from 10,000 to 100,000,
CHUSP found 21 , 14 , 10 , 5 , 3 , 2 , 2 , 2 , 1 , and 1
CHUSPs, respectively. It can be observed that the
number of patterns by CHUSP is respectively up to
3.9, 1.9, 1.4, 1.2, 1.3, 1.5, 1.5, 1.5, 2.0, and 2.0 times
less than those by HUS-Span. In addition, the numberof patterns by CHUSP is up to 1.4, 1.4, 1.2, 1.2, 1.3,
1.5 , 1.5 , 1.5 , 2.0 , and 2.0 times less than those by
FHUSP. On BMSwebview1 ( 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 = 0.5% ). The
𝑚𝑚𝑚𝑚𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈ℎ was set to 3 for HUS-Span and FHUSP;for CHUSP, this parameter was set to full. For
𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑚𝑚𝑚𝑚𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 from 5,000 to 35,000, CHUSP found 45, 42,
39, 38, 31, 18, 10, 3, 2, and 2 CHUSPs, respectively.
It can be observed that the number of patterns by
CHUSP is respectively up to 3.6, 3.5, 3.5, 3.2, 3.0, 3.3,
3.4, 6, 7, and 5.5 times less than those by HUS-Span.
In addition, the number of patterns by CHUSP is up
to 3.6, 3.5, 3.5, 3.2, 3.0, 3.3, 3.4, 6, 7, and 5.5 times
less than those by FHUSP. Similar results can beobserved for the BMSwebview1, FIFA, and BIBLE
datasets. These results indicate that the CHUSP
algorithm can eliminate many non-candidate patterns
from the search space and reduce the number ofpatterns from the mining process.

1052

NAIS JournalFigure 2: Runtimes for various minimum utility threshold values

Figure 3: Memory usage for various minimum utility threshold values
11

NAIS Journal

53

Figure 4: Number of patterns for various minimum utility threshold values
Proceedings of the 18th ACM SIGKDD international

6. Conclusion
This paper proposed an algorithm named CHUSP
for mining closed high utility sequential patterns. The
proposed algorithm uses the CHUS structure for
efficiently mining CHUSP. Experimental results
indicate that CHUSP outperforms HUS-Span and
FHUSP algorithms in terms of execution time andmemory usage. The number of patterns generated by
the three algorithms was also measured for various
minimum utility threshold values. The results showthat all the pruning strategies used in CHUSP caneliminate many non-CHUSP and thus speed up themining process. In future work, we will design aparallel framework that can enhance thecomputational cost of CHUSP and extend the patternmining framework for other tasks [14, 19, 25–27].

conference on Knowledge discovery and data mining. pp.
660–668 (2012).
2.

Wang, J.-Z., Huang, J.-L., Chen, Y.-C.: On efficiently
mining high utility sequential patterns. Knowl Inf Syst.
49, 597–627 (2016).

3.

Le, B., Huynh, U., Dinh, D.-T.: A pure array structure
and parallel strategy for high-utility sequential patternmining. Expert Syst Appl. 104, 107–120 (2018).

4.

Gan, W., Lin, J.C.-W., Zhang, J., Chao, H.-C., Fujita, H.,
Philip, S.Y.: ProUM: Projection-based utility mining onsequence data. Inf Sci (N Y). 513, 222–240 (2020).

5.

Dinh, T., Quang, M.N., Le, B.: A novel approach forhiding high utility sequential patterns. In: Proceedingsof the 6th International Symposium on Information andCommunication Technology. pp. 121–128 (2015).

6.

Le, B., Dinh, D.-T., Huynh, V.-N., Nguyen, Q.-M.,
Fournier-Viger, P.: An efficient algorithm for hiding highReferences

utility sequential patterns. International Journal of
Approximate Reasoning. 95, 77–92 (2018).

1.

Yin, J., Zheng, Z., Cao, L.: USpan: an efficient algorithm

7.

for mining high utility sequential patterns. In:

parallel algorithms for hiding high-utility sequential
1254

NAIS Journal

Huynh, U., Le, B., Dinh, D.-T., Fujita, H.: Multi-core8.

patterns. Knowl Based Syst. 237, 107793 (2022).

J.C.-W.: Discovering periodic high utility itemsets in a

Wang, J., Han, J.: BIDE: Efficient mining of frequent

discrete sequence. In: Periodic Pattern Mining. pp. 133–

closed sequences. In: Proceedings. 20th international

151. Springer (2021).

conference on data engineering. pp. 79–90 (2004).
9.

20.

Truong, T., Duong, H., Le, B., Fournier-Viger, P.:

Bac Le, H.: Mining correlated high-utility itemsets

FMaxCloHUSM: An efficient algorithm for mining

using various measures. Log J IGPL. 28, 19–32 (2020).

frequent closed and maximal high utility sequences.

21.

Eng Appl Artif Intell. 85, 1–20 (2019).
10.

Fournier-Viger, P., Lin, J.C.-W., Dinh, T., Le, H.B.:

Pattern Mining. pp. 97–129. Springer (2019).
22.

measure. In: International Conference on Hybrid
Artificial Intelligence Systems. pp. 53–65 (2016).

sequential pattern mining. IEEE Access. 8, 40714–

Dinh, T., Huynh, V.-N., Le, B.: Mining Periodic High

40722 (2020).
23.

14.

frequent time-interval sequential pattern mining from

545–555 (2017).

transactional databases. Int J Data Sci Anal. 13, 239–

Quang, M.N., Dinh, T., Huynh, U., Le, B.: MHHUSP:

250 (2022).
24.

Ni, X., Wang, M., Xiao, G., Wang, G.: Frequent high-Utility Sequential Patterns. In: Proceedings of the 8th

utility sequential pattern mining algorithm forInternational Conference on Knowledge and Systems

integrated architecture design of multi-platform

Engineering. pp. 13–18 (2016).

mission system. Aerospace Systems. 1–17 (2022).

Huynh, U., Le, B., Dinh, D.-T.: Hiding periodic high-25.

Dinh, D.-T., Fujinami, T., Huynh, V.-N.: Estimating theutility sequential patterns. In: Periodic Pattern Mining.

optimal number of clusters in categorical data

pp. 171–189. Springer (2021).

clustering by silhouette coefficient. In: International

Dinh, D.-T., Le, B., Fournier-Viger, P., Huynh, V.-N.: An

Symposium on Knowledge and Systems Sciences. pp.

efficient algorithm for mining periodic high-utility

1–17 (2019).

sequential patterns. Applied Intelligence. 48, 4694–

26.

4714 (2018).
15.

Gupta, S.K., others: HUFTI-SPM: high-utility andIntelligent Information and Database Systems. pp.

An integrated algorithm for mining and Hiding High

13.

Lin, J.C.-W., Li, Y., Fournier-Viger, P., Djenouri, Y.,
Zhang, J.: Efficient chain structure for high-utility

Utility Sequential Patterns. In: Asian Conference on

12.

Truong-Chi, T., Fournier-Viger, P.: A survey of highutility sequential pattern mining. In: High-Utility

Mining correlated high-utility itemsets using the bond

11.

Fournier-Viger, P., Zhang, Y., Lin, J.C.-W., Dinh, D.-T.,

Dinh, D.-T., Huynh, V.-N., Sriboonchitta, S.: Clustering
mixed numerical and categorical data with missing

Quang, M.N., Huynh, U., Dinh, T., Le, N.H., Le, B.: An

values. Inf Sci (N Y). 571, 418–442 (2021).

Approach to Decrease Execution Time and Difference

27.

Dinh, D.-T., Huynh, V.-N.: k-PbC: an improved cluster

for Hiding High Utility Sequential Patterns. In:

center initialization for categorical data clustering.

Proceedings of the 5th International Symposium on

Applied Intelligence. 1–23 (2020).

Integrated Uncertainty in Knowledge Modelling and
Decision Making. pp. 435–446 (2016).
16.

著者紹介
◆著者紹介

Dinh, D.-T., Huynh, V.-N., Le, B., Fournier-Viger, P.,

Dinh Duy Tai
Dinh
Duy Tai
Assistant
Professor, The Kyoto College ofGraduateProfessor,
Studies forThe
Informatics.
Assistant
Kyoto College of Graduate

Huynh, U., Nguyen, Q.-M.: A survey of privacy
preserving utility mining. In: High-Utility Pattern
Mining. pp. 207–232. Springer (2019).
17.

Studies for Informatics.

Huynh, U., Le, B., Dinh, D.-T., Huynh, V.-N.: Mining

Philippe Fournier-Viger

periodic high-utility sequential patterns with negative

Philippe
Professor, Fournier-Viger
College of Computer Science andunit profits. In: Periodic Pattern Mining. pp. 153–170.

Professor,
College of Computer
Scienceand Software
Software Engineering,
Shenzhen
University.
Engineering, Shenzhen University.

Springer (2021).
18.

Xie, S., Zhao, L.: An efficient algorithm for mining stable

Huynh Van Hongperiodic high-utility sequential patterns. Symmetry

Huynh
Van
Lecturer,
Ho Hong
Chi Minh University of Natural(Basel). 14, 2032 (2022).
19.

Lecturer,
Hoand
ChiEnvironment.
Minh University of Natural Resources
Resourcesand Environment.

Fournier-Viger, P., Wu, Y., Dinh, D.-T., Song, W., Lin,
13

NAIS Journal

55