A survey of high utility sequential patterns mining methods

3.1.1 Serial algorithms

Serial algorithms can be divided into tree-based, matrix-based, list-based, array-based, chain-based, projection-based and other structure-based algorithms according to the data representation. This section summarizes the algorithms of different representation forms respectively.

(1) The tree-based algorithm scans the database once to establish a tree structure, and then finds high utility sequences based on the tree structure. Compared with the two-phase algorithm, the space-time efficiency is better improved [24]. Shie [25] proposed two tree-based methods, UMSP_DFG and UMSP_BFG, in order to mine high utility mobile sequence patterns in the mobile commerce environment. The main difference between the two algorithms is the different methods used to generate patterns of length 2 during the mining process and UMSP_DFG uses a depth-first approach to generate candidate sequences, while UMSP_BFG uses a breadth-first generation strategy to generate candidate sequences. The same point of the two algorithms is that they scan the database once to generate a mapping table and build a tree structure MTS-tree (Mobile Transaction Sequence Tree) to summarize information such as location, item, path and utility in the mobile transaction database. Zihayat [23] proposed an efficient algorithm HUSP-Miner, and used a utility model called Sequence Suffix utility to effectively prune the search space in HUSP mining. It reduces the number of candidate items in the mining process through the tree chain mode, and the algorithm has a great improvement in time and space efficiency. In 2021, Huynh [26] et al. proposed a new utility function to calculate the utility of sequences. FHNewUSM uses three pruning strategies to prune the search space, namely: width pruning based on SWU, compact pruning based on UBs, depth pruning based on AMF_SUB. However, the new utility function is time-consuming to calculate the utility. The high utility sequence based on time intervals reflects the scene of events with unequal time intervals. Mirbagheri [27] et al. designed an algorithm HUIPMiner based on time interval sequences. This algorithm introduces two new pruning strategies DUC and ICE into two phase to mine high utility sequential patterns based on intervals. In two-phase, each iteration generates a specific type of candidate of a certain length. However, the algorithm produces too many candidates’ sequence itemsets, which has a great impact on the space-time efficiency of the algorithm. In order to solve the problem of high computational complexity of the HUSPM algorithm, Tang [13] et al. proposed a new algorithm for mining sequential patterns with high utility named HUSP-FP. The algorithm adopts the method of pattern growth to mine high utility sequence patterns, and all high utility sequence itemsets can be obtained from the tree without scanning the original data set. The algorithm establishes a global tree to store the sequence, the leaf node stores the utility value of the sequence, and mines all high utility sequences at one time based on the pattern growth method, without generating candidates. Figure 4 shows the tree structure corresponding to S₂ in Table 1 established by the HUSP-FP algorithm. Taking the sample database as an example, set the minimum utility threshold to 100, and the process of building a global tree is as follows: the first step is scanning the data set once, counting the utility value and sequence weighted utility value (SWU) of each item, and establishing the header table structure, as shown in Fig. 4 shown in the table. The second step is to delete items in the header table that are less than the minimum utility threshold (the SWU of e is less than 100, so delete them), and update the header table structure. The third step is to scan the original data set again, and build a tree structure according to the order in which the original items appear. In Table 1, S₁ is < [(a, 2) (f, 2)] , [(a, 1) (b, 1)] , [(c, 2) (d, 4)] , [(e, 4) (f, 1) (g, 1)]>, added to the tree structure as shown in Fig. 4, the left branch of the tree is S₁, the right branch is S₂, and the right leaf node stores the utility values of all items in S₁, List ={a = 9, f = 18, b = 9, c = 4, d = 4, g = 10}.

OPEN IN VIEWER

Fig. 4

Transaction tree corresponding to S₂ in Table 1.

(2) Since high utility sequential pattern mining considers the order and utility of the sequence at the same time, an item may appear multiple times in the sequence, so there will be a combinatorial explosion problem. Therefore, a new and more compact data structure called the utility matrix structure is proposed to store the utility information of sequence data, including sequence position, utility value, remaining utility, time order, etc. The utility matrix consists of items and q-itemsets, each element consists of a tuple, the first value represents the utility of the quantized item, and the second value represents the remaining utility of the quantized item. Table 3 shows the utility matrix information of S₄ in Table 1.

The USpan [28] algorithm uses a Lexicographic Q-sequence tree (LQS-tree) and a utility matrix. The LQS-tree structure is shown in Fig. 5. The LQS-tree expands the sequence through I-concatenation and S-concatenation. The authors construct sequence utility by considering the value and quantity associated with each item, and define the problem of mining high utility sequence patterns; USpan uses a full lexicographically quantified sequence tree to construct a sequence based on utility, LQS-tree Each node in is associated with the q-sequence and the utility value of the sequence, and its root node is empty, except for the root node of the LQS-tree, all nodes are prefix-based extensions of their parent nodes and all children of any node in the tree are listed in increasing order. Two cascading mechanisms, I-concatena-tion and S-concatenation, are used to generate new concatenated sequences. In addition, two pruning methods (width pruning and depth pruning) are defined, which greatly reduce the search space in the LQS-tree. However, it needs to compress the dataset into an LQS-tree, which requires high memory consumption for large-scale datasets.

OPEN IN VIEWER

Fig. 5

Lexicographic Q-sequence Tree.

In 2014, Wang [12] et al. proposed an algorithm HUS-Span for efficiently mining high utility sequential patterns, which traverses in a depth-first manner based on LQS-tree. In order to solve the problem that SWU is too loose, two new quantitative indicators, namely Reduced Sequence Utility (RSU) and Projected-Database Utility (PDU), are proposed to prune low-utility sequences. However, since the utility matrix is used to store the utility values, when the data is sparse, the utility matrix will waste more storage space, so the algorithm is not efficient enough when dealing with sparse data. Alkan [29] et al. propose efficient data structures and pruning techniques based on Cumulated Rest of Match (CRoM). CRoM allows stricter pruning before generating candidate patterns by defining a stricter upper bound on candidate utility. Furthermore, they developed an efficient algorithm called HuspExt, which is based on Lexicographic pattern tree, and it computes the utility of child pattern based on the utility of parent pattern. For each sequence in the database, a new structure called data matrix is used for storage. However, this algorithm requires a large amount of memory to store sequences, and is not suitable for processing large data. Furthermore, the set of sequences generated based on the upper bound of CRoM is not a complete set of HUSPs. In order to solve the problem of the irrationality of a single threshold, in 2018, Xu [30] proposed a multi-threshold high utility sequential pattern mining method HUSpan-MMU, which traverses the LQS-tree in a depth-first manner and uses two the pruning strategies SPU (Sequence-projected utility) and SWU prune the LQS-tree to output the entire high utility sequence. This algorithm solves the problem of how to establish multiple minimum utilities of sequences. Literature [31] proposed a new high utility sequential pattern mining algorithm based on maximum remaining utility (HUSP-MRU). In HUSP-MRU, the Maximum Remaining Utility (MRU) is defined as a candidate more compact upper bound. The search space is built with a Lexicographic sequence pattern tree, and the Lexicographic pattern tree is traversed in a depth-first manner. The utility matrix structure is used for MRU storage, and pruning is performed based on MRU to improve mining efficiency.

(3) The utility list structure stores the original database information and some basic information that needs to be calculated. It consists of UP Information (storage of item name, utility value, remaining utility value and the next occurrence position) and Header Table (storage of quantization sequence and the first occurrence position). The utility list is a data structure designed based on the idea of “space for time”. It is formed by the transformation and expansion of transactions in the original database. Table 4 shows the utility list structure of S₁ in Table 1.

Yin [32] et al. proposed TUS, an efficient algorithm for mining top-k high utility sequence patterns, and developed a new sequence boundary and corresponding pruning strategy to effectively filter out unpromising candidates. In addition, pre-insertion and sorting strategies are also introduced to improve the minimum utility threshold, and the proposed strategy effectively reduces the search space and the number of candidates, so the mining performance is significantly improved. In 2017, Lin [33] et al. introduced the concept of multi-threshold high utility sequential pattern mining algorithm. The article designed a high utility sequential pattern algorithm with multiple minimum utility thresholds, LS-tree and UL-list structures. The algorithm first searches the entire LS-tree in a depth-first manner, and then uses the UL-list structure to store the utility value of the sequence. A large number of experiments on real data sets show that the algorithm proposed by the author can effectively mine complete HUSP collections with multiple minimum utility thresholds. The HUSP-Miner [20] algorithm searches in a depth-first manner, and generates and searches new sequences in a pattern-growing manner. The role of UL-list is to speed up the generation of new sequences, improve the calculation speed of sequence utility upper bounds and utility values, and avoid multiple scans of the original database. Compared with the HUS-SPan and HuspExt algorithms, the HUSP-Miner algorithm has obvious advantages in the running time, the number of candidate sequences and the scalability of the algorithm. Buffett [34] proposed a new method to solve the problem of establishing a more compact upper bound on the candidate pattern set to reduce the search space required to identify the complete pattern set, which maintains a list of possible candidate connection items, this list specifies the only candidates that need to be considered possible for concatenating with the sequential pattern being considered or any future sequential patterns that occur as descendants in the search tree. The article uses two list structures RUL (removed-utilities list) and RUPL (removed-utility-positions list) storage utility, compared with the SWU used by Uspan and the RSU used by HUS-Span, the two new upper-bound MCU and RCU are more compact and have smaller search spaces. Reference [35] proposes an efficient algorithm for the HUSP mining task, called HUSP-ULL. It utilizes a LQS-tree and a utility linked list (UL-list) structure to store the utility information of each sequence. HUSP-ULL has a good performance on large sequence data mining, especially datasets with large average number of elements per sequence or large average number of items per element. However, the UL-list structure proposed in the literature is a complex structure that is not easy to implement.

(4) Compared with the matrix structure, the array structure consumes less memory and can effectively improve the mining efficiency. In the array structure, each column stores the itemset ID, item, actual utility, remaining utility, and item in the sequence s respectively. The next position and the position of the first element in the next item set, Table 5 shows the utility array structure of S₃ in Table 1.

PAS (Pure Array Structure) is a compact structure that maintains the full utility information of the sequence in a one-dimensional array structure. Therefore, it is purer and simpler than the two-dimensional array structure used in the utility matrix. In 2018, Le [36] introduced a pure array structure to solve the problem that the utility matrix consumes a large amount of main memory, and proposed a new algorithm AHUS-P based on the pure array structure to effectively solve the HUSPM problem. The AHUS-P algorithm uses breadth-first search (BFS) to traverse the LQS-tree. The article argues that when AHUS-P evaluates nodes in an LQS-tree, the mining order on each node does not depend on its sibling nodes. Therefore, all child nodes of any node in the LQS-tree can be processed simultaneously without affecting the mining results. Compared with the HUS-Span algorithm, this algorithm has a good performance in terms of running time, memory and scalability. In 2019, Gan [37] et al. proposed an efficient projection-based utility mining method, called ProUM, to discover high utility sequences by using upper bounds (Sequence Extended Utility (SEU) and utility array structures). Based on the projection mechanism, this algorithm proposes a new structure for processing time series data called Utility-Array. The utility array can calculate the utility and remaining utility of the sequence without scanning the database, and can filter out hopeless candidates as early as possible, it greatly saves search time.

(5) The chain structure scans the database once to establish a utility chain. The chain structure consists of SID, TID, sequence utility, remaining utility and the next position of the sequence. Its structure is shown in the Fig. 6.

OPEN IN VIEWER

Fig. 6

Utility chain of sequence <a> in Table 1.

In 2016, HUSP-Span [38] proposed by Wang traversed the LQS-tree in a depth-first manner and used two more compact upper bounds PEU (prefix extension utility) and RSU (reduced sequence utility) to prune the search space, using the utility chain structure speeds up the calculation of upper bounds and sequence utility values. Although HUSP-Span can effectively mine high utility sequential patterns, it is usually difficult for users who do not have sufficient knowledge of QSDB to set an appropriate utility threshold. In view of this, the author proposes the TKHUSP-Span algorithm to mine former k-item high utility sequence. The TKHUSP-Span algorithm uses three search strategies: guided depth-first search (GDFS), best-first search (BFS), and a hybrid search of BFS and GDFS. Experimental results show that TKUSP-Span Hybrid is superior to TUS algorithm both in terms of time and memory. Mining high utility sequential patterns in uncertain data has always been a relatively complicated problem. HEUSPs [39] algorithm was proposed to mine uncertain data sets. HEUSPs is based on the PUL-chain (probability utility list-Chain) of each item. The structure searches the database once to calculate the upper bound value of PSWU and calculates the total estimated utility of expected utility eu(D). During the mining process, the algorithm traverses the entire search space in a depth-first manner, and prunes unpromising sequences according to the pruning strategy PPEU. Compared with the general HUS-Span model, the constructed algorithm can effectively deal with uncertain datasets to mine the desired HEUSP (high-expected utility sequential patterns) and extract them efficiently. In 2020, Lin [40] et al. designed a new efficient data structure SU-chain to store utility information. Several pruning strategies are used in the SU-chain structure to identify information that is irrelevant to the early pruning process, so it can be obtained from the projection database, and also reduce the search space. Traditional high utility sequential pattern mining aims to discover the complete set of patterns that satisfy a user-defined minimum utility threshold in the database; However, they do not allow the user to execute the target query. In order to meet the needs of users, a series of frequency-based methods for searching specific target items are proposed. So far, the goal-oriented frequent itemset query, association rule query, and sequential pattern query (SPQ) have played an important role in the query in the database, and these three goal-oriented techniques can effectively mine patterns and rules, and have shown great potential in some real-life applications [41]. Based on this, TUSQ [42] was designed for high utility sequence mode query. The algorithm is based on two new upper bounds, suffix remaining utility and terminated descendants’ utility, and a vertical Last Instance Table structure. To further improve efficiency, TUSQ relies on a projection technique that relies on a compact data structure called a targeted chain.

(6) Some known algorithms have problems such as multi-pass data set scanning, generation of a large number of candidate item sets, and low timeliness. The algorithm based on the projection mechanism does not need to scan the database multiple times, which can greatly improve the efficiency of the algorithm. The general idea of projection-based methods is to recursively project the processed database into some smaller projected sub databases, and then grow itemsets or subsequence fragments in each projected subdatabase [43]. In order to effectively deal with the problem of high utility sequential pattern mining, Lan [44] et al. proposed a high-efficiency projection-based algorithm (PHUS) to achieve this goal, which uses a maximum utility measure and sequence utility upper bound (SUUB). Especially, in mining, an effective projection-based pruning strategy is used to further obtain a more precise utility upper bound of subsequences, and then a large number of unpromising candidate subsequences can be avoided. Furthermore, an efficient index structure is designed to quickly find the relevant quantization sequences of prefixes to be processed in the recursive process. Two baseline algorithms, U-HUSPM and P-HUSPM [45], are used to efficiently mine High Utility Probabilistic Sequential Patterns (HUPSP) in uncertain databases. Both algorithms first perform a breadth-first search to prune all patterns with SWU values smaller than the minimum utility threshold or probability values smaller than the minimum expected support. In the second stage, they identify actual HUPSPs from the candidates obtained in the first stage. The U-HUSPM algorithm mines HUPSPs using a hierarchical approach and applies three pruning strategies to reduce the number of unpromising candidates in the search space. The P-HUSPM algorithm uses a projection mechanism to create a small projection database for each processed sequence, which speeds up the mining process. In order to effectively mine the top-k high utility sequences, the TKUS [46] algorithm adopts projection and local search mechanisms, and follows a variety of strategies, including SUR (Sequence Utility Raising strategy), TDE (Terminate Descendants Early strategy) and EUI (Eliminate Unpromising Items strategy), these strategies can greatly reduce the search space and speed up the mining process. The TKUS algorithm traverses the entire LQS-tree in a depth-first manner, which can quickly increase the minimum utility threshold and effectively extract the first k HUSPs.

(7) In addition to the algorithms based on the above structures, there are several other new data structure algorithms. The UTMing [47] algorithm is the first algorithm used to process time-interval sequence data. It uses the minutil for Unit pruning strategy to cut off all unpromising items, and uses the time-interval tables structure to store the utility information of the sequence during the search process. In the real-world, some goods are only placed on the shelf for a specific short period of time; traditional utility mining methods are biased towards items with a longer shelf life because they have a higher probability of generating high utility. In order to eliminate this bias, Zhang [48] proposed the problem of on-shelf utility mining (OSUM). The algorithm uses a PLS-Forest structure to store utility, in which the database is divided into multiple partitions according to the time period, and each item is associated with multiple partitions. associated with a shelf time period. Incorporating the information on the shelf (utility) into raw measures is crucial to discover interesting and informative time-dependent patterns. Gupta [49] et al. proposed a hybrid pattern growth algorithm HUFTI-SPM based on the three constraints of frequency, time interval and utility. This algorithm uses two data structures: the modified time series table and the supporting utility table, and the time series table stores support and utility information about subsequences, and the support utility table is used to capture support and utility corresponding to different time intervals.

Parallel algorithms can be divided into Hadoop-based and Spark-based algorithms according to the different big data processing platforms used. This section summarizes the algorithms and their advantages and disadvantages of the two different platform technologies.

(1) Hadoop is composed of distributed file system HDFS and MapReduce. HDFS can store data in a distributed manner and replicate data with high reliability in multiple nodes [50]. The MapReduce framework is designed to execute tasks across multiple nodes with key-value pairs as input and output. MapReduce highly abstracts the complex parallel computing process running on large-scale clusters into two functions——Map function and Reduce function. Through the Map function, the data is mapped to different blocks and then distributed to computer clusters for distributed processing. For calculation, reduce uses the output of Map as input, gathers the same key into the same Reduce, and obtains the final result through processing. This method well embodies the “divide and conquer” strategy [51]. The operating principle of MapReduce is shown in the Fig. 7. Hadoop uses the MRv1 version of the MapReduce programming model, which is a disk-based architecture, in which MapReduce needs to be stored on the disk.

OPEN IN VIEWER

Fig. 7

Working principle of MapReduce.

In 2022, Saleti [52] et al. used a MapReduce-based approach to mine high utility time-interval sequences. A multi-threshold algorithm called MRHUTSP-MMU is proposed in the literature, which is based on the Hadoop platform for mining in three stages. The algorithm uses MMU to store utility values, which greatly improves mining efficiency.

In 2022, Wu [53] and others proposed an algorithm MR-HUPSP for mining high utility sequences in large-scale uncertain data. This algorithm is an extension of the U-HUSPM [40] algorithm, based on the MapReduce framework in the Hadoop platform. The raw database is scanned by MR-HUPSP created by running multiple MapReduce jobs. The developed MR-HUPSP is able to segment the database and transfer these segments to multiple nodes for parallel processing, which can collect all the required information in one scan, which greatly reduces the running time of the database.

(2) Unlike the Hadoop framework, Spark has improved the MRv1 version of MapReduce. It is a memory architecture that stores the results in the main memory and can greatly reduce I/O operations. For the Spark framework, it is called Resilient Distributed Dataset (RDD) structure can manage memory data distributed in the cluster through fault recovery to maintain high scalability.

In 2015, Cheng [54] et al. proposed a high utility sequential pattern mining algorithm HusMaR based on the MapReduce framework. This algorithm uses a utility matrix to filter useless single-item sequences, generates sequence candidates, and uses a random mapping strategy to balance the amount of computation. This algorithm was used by Zhao et al. [56] to deal with catenary fault sequence database. In the literature, for the slotted busbar components used in the catenary rigid-flexible transition, CAD is used to analyze the moment of inertia of each slot, and compared with the moment of inertia of a single contact wire and a single contact wire with a positioning wire clamp, the obtained the position of the flexible anchor point is obtained, and the specific height of the flexible anchor point is obtained through the analysis and calculation of the contact line uplift. This scheme has been applied in the rigid-flexible transition of the depot of Metro Line 2 in Guiyang City, China, and achieved good results.

The BigHUSP [14] algorithm defines a parallel distributed computing framework based on Apache Spark. The algorithm implements distributed parallel computing tasks based on MapReduce, which is divided into initialization phase and mining phase. In the initialization phase, the MapReduce step is first performed to calculate the Global Sequence-Weighted Utility (GSWU) of each item, and items whose GSWU is less than the minimum utility threshold are pruned to reduce the search space. In the mining phase, BigHUSP uses existing HUSP mining algorithms (such as the USpan algorithm) on each partition to mine local HUSP. After that, G-HUSP (Global High Utility Sequential Pattern) can be found by calculating the utility of L-HUSP (Local High Utility Sequential Pattern) on all partitions.

In order to solve the shortcoming of low efficiency of the serial algorithm, Zhang [56] et al. proposed an efficient HUSPM distributed algorithm PHUSP. The algorithm makes full use of the advantages of multi-machines and multi-core processors, and can quickly complete mining tasks. The algorithm first forms n partitions (D₁-D_n) through the partition strategy SLST (similar length, similar time) and transfers them to related machines, and then each machine executes a multi-threaded algorithm based on HUS-Span to obtain from the corresponding D_i find all local HUSPs in. All local HUSPs will be merged into global candidates for D. Afterwards, to discover the global HUSP of D, it sends the global candidates to each computer to compute the utility, and filters the HUSP according to the returned results.

HUSP-Spark [50] is a HUSPM algorithm based on the iterative four-stage MapReduce framework of the Apache Spark platform. It consists of four phases that execute the MapReduce framework. These phases can be summarized as: initialization process, mining process, update process, and generation process. The initialization process screens out all 1-sequences for subsequent use; the mining process constructs SU-Chain to mine k-HUSP and all potential candidate sequences; the update process prunes through the constraint PEU [34] to reduce the search space; A fourth MapReduce framework performs partitioning of the database during generation to find potential (k + 1)-HUSPs.

In 2020, Sumalatha [15] et al. proposed a distributed mining algorithm based on DHUTISP of three-stage MapReduce to discover high utility time-interval sequential patterns (HUTISP). The algorithm considers the time interval between consecutive sequences, so it is more complex than general high utility sequence mining algorithms.

In the same year, Zeng [57] et al. proposed a distributed high utility sequential pattern mining algorithm based on multiple utility thresholds, called SHEMA, to solve the problems of large search space and high computational complexity in the process of mining high utility patterns of sequential patterns algorithm. The algorithm uses a pure array structure to maintain utility information and a prefix tree trie-tree to maintain sequence patterns. These two data structures can effectively improve the time-space efficiency of the mining process. In the process of evaluating the prefix tree nodes, the mining order of each node is independent of other peer nodes, so all child nodes in the prefix tree can be processed in parallel without affecting the results. Based on this, the distributed implementation scheme of this algorithm is given, which can realize parallel computing on platforms such as cloud computing, GPU (graphics processing unit), multi-core processors, etc., so as to realize fast mining processing.

Algorithm DHUTISP-MMU [59] is used to mine high utility sequential patterns with time intervals in big data environments. A new data structure TIUL (Time Interval Utility Linked List) is used to store sequence utility information. MMU-table (minimum utility threshold table) structure to store multiple threshold information.

Srivastava [58] proposed a four-stage MapReduce algorithm HUSP-Spark based on the Spark platform. The processing of large data sets is divided into four stages: initialization, mining, updating and generation. Experiments show that the designed model can handle very large dataset, while state-of-the-art algorithms can only achieve good performance on small datasets.

ML-HUSPM [16] is a scalable mining algorithm for high utility sequential patterns based on a three-layer MapReduce model. Two new data structures are used in the literature, called sidset and Utility-Linked List respectively, and these two data structures are used to store the necessary information that needs to be stored in the mining process. Sidset is used to reduce the utility computation of the patterns computed in each node mining during the second phase. At the same time, the Utility-Linked List is converted and expanded by the sequences in the original database, and records information about the original database and the required utility information.

This section describes the high utility sequential pattern mining algorithms in static databases from the serial and parallel perspectives. Figure 8 summarizes the proposed algorithms in terms of comparison algorithms, key technologies, pruning strategies, and advantages and disadvantages of the algorithms.

OPEN IN VIEWER

Fig. 8

High utility sequential pattern mining algorithms.

Among serial algorithms, there are many algorithms using tree structure, list structure and matrix structure. The algorithm based on the tree structure only needs to scan the database once to establish the tree structure, and then find out the high utility sequence according to the tree structure. However, the establishment and maintenance of the tree structure is time-consuming. For example, the HUSP-Miner [23] algorithm based on the tree structure uses the depth-first method to search the tree, and its time complexity is O (M × Lavg + NumPot × NumOcavg), where M is the size of the data set, and Lavg is the average of these transactions’ length, NumPot is the number of potentially high utility patterns, and NumOcavg is the average number of occurrences of potentially high utility sequential patterns. The list structure is a data structure designed based on the idea of “space for time”, which is relatively easy to implement, but the list itself requires additional storage space, and its connection operation will take a lot of time, resulting in a decrease in the space-time efficiency of the algorithm. For example, based on the list structure The HUSP-ULL [35] algorithm needs O (M × L)time to scan the database, and O (2M)time to calculate the utility and remaining utility of the sequence in the data set, where M is the number of sequences in the database, and L is the average length of the sequence. The algorithm based on the matrix structure uses the utility matrix to store the utility information of the sequence data, including the sequence position, utility value, remaining utility, time order, etc. However, when the data is sparse, the matrix will waste more storage space, therefore, the matrix structure not suitable for storing sparse datasets. For example, the HuspExt [29] algorithm only needs the time complexity of O (1)to access the data matrix, but the space complexity in the worst case is O (n × k !), where n is the number of sequences and k is each the largest set of k items contained in a sequence. Most of the existing high utility sequential pattern mining algorithms focus on how to improve the mining efficiency of HUSPM, such as USpan algorithm, HuspExt algorithm, PHUS algorithm, and HUS-Span algorithm. Among them, the USpan algorithm, HuspExt algorithm, and HUS-Span algorithm are all based on the LQS-tree using two node expansion mechanisms, and different sequence utility upper bounds.

Parallel algorithms are mainly used to process massive data. Faced with the problem of huge data sets and the “combination explosion” of sequence data, a single machine cannot handle very large data sets, and parallel distributed processing of data is particularly important. The BigHUSP [14] algorithm first defines a parallel distributed computing framework on large datasets based on Apache Spark, and lays the foundation for parallel distributed mining of high utility sequential patterns. The HUSP-Spark algorithm proposed by Lin takes 2759 seconds to mine high utility sequences on one machine, but only 777 seconds to mine high utility sequences on five machines, and the performance of the algorithm is better as the number of machines increases. Therefore, HUSP-Spark [50] is well suited for distributed mining of large datasets. The HUSP-Spark algorithm proposed by Srivastava [58] shows that when the size of the dataset is very small, traditional algorithms such as USpan, HUS-Span and HUSP-ULL outperform the designed HUSP-Spark in all datasets. In the experiment, the running time of USpan, HUS-Span and HUSP-ULL are 117.9 seconds, 43.7 seconds and 14.56 seconds respectively, while HUSP-Spark needs 2262.16 seconds. This is reasonable because initializing the MapReduce framework requires a higher computational cost compared to traditional algorithms. However, when the size of the database increases, these traditional algorithms cannot produce results due to the out-of-memory problem, while the HUSP-Spark algorithm can perform mining well.

In general, there are still some serious challenges in HUSPM mining, which are as follows: First, in pattern mining, the utility-based computation mechanism is different from the frequency-based computation mechanism. The former is more complicated, and the utility value of the sequence does not have the property of downward closure. This means that support-based pattern mining techniques and models cannot be directly applied to mine interesting patterns driven by utility. In addition, pruning the search space of HUSPM is more difficult. Second, the HUSPM problem is inherently more complex than HUIM and FPM. Due to the inherent temporal order implied in sequence data, HUSPM may easily face the problem of combinatorial explosion of the search space if it lacks a pruning strategy based on a compact upper bound on utility overestimation. Third, a common approach to identify high utility sequential patterns is to recursively generate projection-based sub-databases, and then scan these sub-databases to calculate specific utility values for each sequential pattern. However, when the number of sequences in the processed database is very large, these operations can lead to excessively long running times and prohibitively high memory consumption costs. Therefore, how to effectively reduce the size of the database that needs to be projected and scanned is crucial for efficiently mining high utility sequential patterns. Fourth, most of the current algorithms only focus on improving the efficiency of the algorithm, while ignoring the object-oriented effectiveness issues, for example, only mining the top-k items that users are interested in, mining high utility sequences in uncertain or multi-source heterogeneous data Various situations will be encountered in real life, such as mining highly correlated high utility sequences. Therefore, how to solve the problem of algorithm effectiveness so that it can be used in more application scenarios is an urgent problem to be solved. Finally, in HUSPM, how to speed up the running time and reduce memory consumption while ensuring that HUSP is not missed is crucial. How to improve the efficiency of utility mining for sequence data is still an open key issue.

The purpose of hiding is to find a way to hide all high utility sequential patterns so that adversaries cannot mine them from sanitized databases. High utility sequence hiding algorithms can be classified into array-based, chain-based and matrix-based algorithms according to key technologies. This subsection summarizes algorithms for hiding high utility sequential patterns.

(1) Algorithm based on matrix structure

The matrix structure is widely used to store the utility and remaining utility of the sequence. Dinh [61] et al. extended the USpan algorithm to mine all high utility sequence patterns, and then proposed two hidden algorithms (Hiding High Utility Sequential Pattern) HHUSP and (Maximum Sequential Patterns Conflict First) MSPCF, the algorithm achieves the purpose of “hiding” by reducing the utility value of some high utility sequences to be hidden. The HHUSP algorithm first mining the high utility sequence patterns, then screens out the high utility sequences that need to be hidden, and finally outputs the sanitized database. The MSPCF algorithm is the same as the HHUSP algorithm, first scans the original database and extends the USpan algorithm to mine all high utility sequences. Unlike the HHUSP algorithm, the main purpose of the MSPCF algorithm is to find the item with the highest number of occurrences, or another way to find the item with the largest number of conflicts between items in the high utility sequence pattern set, and then preferentially hide the item containing the high utility sequence pattern. The advantage of Dinh’s method is that the database is only scanned during the mining step, avoiding multiple scans, and thus, it will be very efficient when performed on large databases. However, the computation time and memory usage of these two algorithms are similar to those of USpan [28], which is easily plagued by computational problems. Also, they did not consider the difference between the original database and the sanitized database after the hidden stage. HUSP-D [62] and HUSP-A [62] algorithms, hide high utility sequential patterns by descending and ascending order of utility to reduce variance and reduce execution time. The general process of this algorithm to hide HUSPs includes three steps: 1) mining step: use the HUSPM algorithm to mine all HUSPs from the original sequence database; 2) sorting step: sort the HUSP set using a specific order; 3) hiding step: modify the original sequence database, and returns the final sanitized database. These two algorithms are the HHUSP [61] algorithm with an additional step added to rearrange the hidden order of HUSP. Experimental results show that the proposed improvements lead to better performance of the HHUSP-D algorithm in terms of running time, memory usage, and loss cost compared to the HHUSP algorithm. The previous algorithm is to mining all high utility sequences first and then hide them. A new mining and hiding method are to hide while mining. Quang [63] et al. integrate the ideas of HHUSP [61] into USpan [28] to form MHHUSP algorithm, which is an integrated method combining mining and hiding. Actually, the key idea of MHHUSP is to first find the high utility mode, and then modify its utility to be lower than minutil. Every time MHHUSP algorithm finds a HUSP, it immediately invokes the hidden algorithm to reduce the utility value of the sequence. It is not necessary to modify the database after finding all high utility sequences. This algorithm can greatly reduce the number of candidate sequences. Therefore, it can run faster and more efficiently than other systems.

(2) Algorithm based on chain structure

The chain structure is flexible and efficient. In 2018, Le [64] et al. proposed an efficient and high utility sequence hiding algorithm HUS-Hiding. HUS-Hiding relies on a new structure called UCH (Utility-chain for Hiding) to facilitate the hiding process. The UCH structure adopts the idea of exchanging space for time, and records the previously appeared location information in the table in advance to avoid repeated lookups. HUS-Hiding uses an existing mining algorithm to find HUSPs, and for each HUSP found, the database is immediately modified (making its utility value less than minutil) to achieve the purpose of hiding. Repeating the process until no HUSP is found, the algorithm then returns the sanitized database.

(3) Algorithms based on array structure

The compact structure of the array structure can greatly improve memory utilization. In 2019, Zhang [65] et al. proposed an efficient algorithm FH-HUSP for HUSPH. The algorithm uses a new structure IUA (index-based utility array) to store all the utility information in the extraction process, which speeds up the utility calculation speed, adopts the separation and integration strategy to reduce the search space, and uses the dynamic programming method to find q item to be modified, so all high utility sequential patterns can be quickly hidden at a certain minimum utility with relatively fast speed. In 2022, Huynh et al. [66] introduced a multi-core parallel method for hiding all high utility sequential patterns. Three algorithms, USHPA, USHP and USHR, are proposed in the literature to effectively hide all HUSPs from quantitative sequence datasets. The proposed algorithm relies on a structure named pattern utility set for hiding (push) to hide all patterns. This structure holds the basic information needed for modification. In addition, a metric called Privacy Factor (PF) is introduced to evaluate the quality of the hidden results, and the proposed algorithm applies a separate hidden pattern that first collects HUSP sets using a mining algorithm and then modifies them, until their utility falls below a minimum threshold. USHPA is a serial algorithm, while USHP and USHR are parallel algorithms. The USHPA algorithm is for those who only consider hidden results. The USHR algorithm is for companies that consider privacy rather than utility of data. In general, USHP is the algorithm with the best performance, while USHR is the algorithm with the best privacy among the proposed algorithms.

3.2.2 Metrics

In addition to running time and memory consumption, there are several other evaluation metrics for evaluating the quality of high utility sequential pattern hiding algorithms. Bertino et al. [67] proposed a framework for evaluating the performance of privacy-preserving data mining. The evaluation indicators of PPUM are proposed, including hidden failure (HF), loss cost (MC) and artificial cost (AC). Concealment failure means that some information was not fully concealed after the sanitization process. Attackers may still be able to extract sensitive information from the final sanitized database. Missing itemsets means that some insensitive but frequent itemsets become infrequent after purification. Thus, the missing cost is the ratio of missing itemsets, and a lower missing cost is better for PPDM. Dinh [66] et al. mentioned database modification rate (DMR) and data integrity (DI) in addition to the above three evaluation indicators. In addition, Lin [68] et al. proposed another performance evaluation criterion, namely database structure similarity (DSS), database utility similarity (DUS) and itemset utility similarity (IUS). Huynh et al. proposed the Privacy Factor (PF) metric [66]. Rajalaxmi and Natarajan [69] also proposed a similar concept, namely the utility difference of DUS. The details of the relevant metrics are shown below.

Criterion 1 Hiding Failure (HF) [70] is one of the evaluation indicators to evaluate whether sensitive information is successfully hidden before and after sanitization. Calculated as follows:

H F = | H U S ( D B ' ) | |HUS ( DB ) |(8)

where | HUS(DB’) | is the number of sensitive HUSP after sanitization, and | HUS(DB) | is the number of sensitive HUSP before sanitization.

Usage: HF represents the proportion of HUSPs that can be discovered by utility pattern mining after the database is updated. Therefore, if the result of equation 1 converges to 0%, all HUSPs are hidden. That is, the smaller the HF value, the better the hiding performance.

Criterion 2 Miss Cost (MC) [70] is the ratio of non-sensitive HUSP missing after sanitization. The missing cost is calculated as follows: MC = u ( SDB ) - u ( SDB ′ )(9) where the MC value is obtained by subtracting the total utility of the purified database from the total utility of the original database.

Usage: The lower the value of MC, the better the performance of the hidden algorithm, because it means that the cleaned database is more similar to the original database.

Criterion 3 Artificial Cost (AC) [70] is the rate of becoming HUSPs due to decontamination. Its measurement method is as follows: AC = | ∼ HUS ( DB ′ ) - ∼ HUS ( DB ) | | ∼ HUS ( DB ) |(10) where | ∼ HUS (DB’) | is the number of non-sensitive HUS after sanitization, | ∼ HUS (DB) | is the number of non-sensitive HUS before sanitization.

Usage: The AC metric is usually used by heuristic-based algorithms to evaluate their performance, the lower its value, the better the performance of the hidden algorithm.

Criterion 4 Database Modification Ratio (DMR) [70] is the difference ratio between the original database DB and the sanitized database DB. Its measurement method is as follows: DMR = U ( SDB ) - U ( SDB ′ ) U ( SDB )(11) where U(SDB) and U(SDB') are the total utility of the original database and the sanitized database, respectively.

Usage: The higher the DMR, the greater the difference between DB and DB'. The lower the DMR, the more similar DB and DB' are to each other. A DMR of 0% means DB' is the same as DB. The smaller the database modification ratio, the better.

Criterion 5 The database integrity measure (Data integrity, DI) [70] shows the impact of transaction deletion on the original database, which can be used to verify the similarity with the original database. Calculated as follows: DI = | SDB ′ | | SDB |(12) where |SDB'| is the size of the sanitized database and |SDB| is the size of the original database.

Usage: The smaller the DI value, the more deleted transactions and the greater the modification to the database. Therefore, the higher the DI value, the better.

Criterion 6 The utility integrity measure (Utility integrity, UI) [70] is used to evaluate the difference in total utility before and after sanitization. Also known as Database Utility Similarity (DUS), its measurement method is as follows: DUS = UI = U ( SDB ′ ) U ( SDB )(13) where U(SDB') is the total utility of the database after sanitization, and U(SDB) is the total utility of the database before sanitization.

Usage: For UI, the higher the value, the better. Because it means that before and after modification, not only the similarity of database utility is guaranteed, but also sensitive sequences are hidden.

Criterion 7 The database structure similarity (DSS) [70] metric is used to evaluate the structural similarity before and after sanitization. DSS only considers the existence of an item or itemset in a transaction. Therefore, it evaluates the similarity between the original database and the sanitized database. Its measurement method is as follows: DSS = ∑ k = 1 | tp k DB ∪ tp k DB ′ | ( freq ( tp k DB ) - freq ( tp k DB ′ ) ) 2(14) where freq ( tp k DB ) is the frequency of the pattern in the original database and freq ( tp k DB ′ ) is the frequency of the pattern in the sanitized database.

Usage: For DSS, the higher the value, the better the performance of the algorithm.

Criterion 8 Itemset utility similarity (IUS) [70] was used to evaluate the utility loss of HUS found before and after the PPUM sanitization process. IUS provides a more practical evaluation for the PPUM algorithm, especially when the gap between the utility of the discovered HUS and the minimum utility threshold is large. Its measurement method is as follows: IUS = ∑ x ∈ HUSPs DB ′ u ( X ) ∑ x ∈ HUSPs DB u ( X )(15) where HUSPs^DB′ and HUSPs ^DB are the HUSPs in the sanitized database and the original database, respectively.

Usage: For this value, the smaller the value, the smaller the gap between the modified sequence utility and the minimum utility threshold, and the better the performance of the hidden algorithm.

This section describes the high utility sequential pattern algorithm and its hiding strategy and evaluation index. Table 6 compares the hiding strategy, key technology and metrics of hiding high utility sequential pattern algorithm.

The hidden pattern algorithm is generally divided into three steps. Firstly, the existing mining algorithm is used to mine high utility sequences; secondly, according to the requirements, the hidden pattern algorithm is used to modify the utility value of the sequence to be hidden so that it is lower than the minimum utility threshold; finally, the modified database is returned. Therefore, there are two different modes of hidden mining: one is to mine all high utility sequences and select the sequence to be hidden; the other is to mine a high utility sequence to determine whether to hide the sequence. Hiding means hiding directly, that is, hiding while digging, which is a dynamic hiding process. The former is usually time-consuming and takes up a lot of memory, while the latter algorithm design is more difficult.

To judge the performance of a hidden algorithm, in addition to the traditional comparison of time and memory consumption, there are many other evaluation indicators, such as HF, MC, AC, etc. A good hiding algorithm should have a good distortion rate, that is, all sensitive sequences are hidden after cleaning. For the information storage of the sequence to be hidden, the algorithms proposed so far mainly have three structures: matrix structure, chain structure and array structure. The algorithm based on the matrix structure can fully store sequence information and is easy to expand, but it will waste a lot of storage space when the data is sparse; on the kosarak10k data set, minutil is set from 35000 to 12000, and MHHUSP [63] is better than USpan+HHUSP combination 2.78, 1.87, 2.51, 3.89, 3.13, 2.55, 2.4, 2.6, 3 and 3.7 times faster. The chain structure is a new structure. The algorithm based on the chain structure is more flexible in deletion and insertion, but the access can only start from scratch; let n be the number of sequences in the original database, L is the average length of the sequence, and n₁ is the number of potential HUSPs, L₁ is the average number of occurrences of potential HUSPs, HUS-Hiding [64] scans the database and calculates SWU time-consuming O (n × L), constructs LQS-tree time-consuming O (n₁ × L₁), and modifies the utility value of HUSPs time-consuming O (n₁), the time complexity of the HUS-Hiding algorithm is O (n × L + n₁ × L₁ + n₁). The array structure can handle a large amount of data, but its insertion, deletion and other operations perform poorly and are not suitable for dynamic access. Let n_s be the number of sequences, n_i the average length of the sequence, n_p the number of potential HUSPs, n₀ the average number of occurrences of potential HUSPs, n_h the number of HUSPs, n_j the average number of items per HUSP, n_c the number of items per HUSP the average number of sequences, n_r is the time required to reduce the utility of all HUSPs by θ, φ is the number of processors, USHPA [66] is divided into two parts: mining and hiding, and mining takes O (n _s  × n _i  + n _p  × n₀/φ + n _p ), hiding time-consuming O (n _h  × n _c  × n _j ), then the average time complexity of the USHPA algorithm is O (n _s  × n _i  + n _p  × n₀/φ + n _p  + n _h  × n _c  × n _j ). The USHP [66] algorithm simultaneously hides n_h HUSPs of φ processors and takes O(n_h) time to synchronize the processors, then the average time complexity is O (n_s × n_i + (n_p × n₀)/φ + n_p + (n_h × n_c × n_j)/φ + n_h), USHR needs to use random utility θ to reduce the utility value of HUSPs, then the average time complexity is O (n _s  × n _i  + (n _p  × n₀)/φ + (n _p  + n _h  × n _c  × n _j )/φ + n _h  + n _r ). USHPA, USHP and USHR are composed of mining and hiding. They use the pure array structure PAS to store sequence utility. PAS is composed of three one-dimensional arrays which contain sequence, sequence utility and residual utility. Mining consumes space O (n _s  × n _i  × 3 + n _p  × n₀ × 3 + n _h  × n _c  × (n _j  + 2)).

On the whole, hidden high utility sequential pattern mining is still in its infancy, and there are few related algorithms. Therefore, how to use biological heuristic algorithms to solve high utility sequential pattern mining still needs to be innovatively explored.