Search

Clustering is increasingly being used to select the appropriate test suites. In this paper, we apply this approach to regression testing. Regression testing is the practice of verifying the robustness and reliability of software by retesting after changes have been made. Creating and maintaining functional regression tests is a laborious and costly activity. To be effective, these tests must represent the actual user journeys of the application. In addition, an optimal number of test cases is critical for the rapid execution of the regression test suite to stay within the time and computational resource budget as it is re‐run at each major iteration of the software development. Therefore, the selection and maintenance of functional regression tests based on the analysis of application logs has gained popularity in recent years. This paper presents a novel approach to improve regression testing by automating the creation of test suites using user traces fed into clustering pipelines. Our methodology introduces a new metric based on pattern mining to quantify the statistical coverage of prevalent user paths. This metric helps to determine the optimal number of clusters within a clustering pipeline, thus addressing the challenge of suboptimal test suite sizes. Additionally, we introduce two criteria, to systematically evaluate and rank clustering pipelines. Experimentation involving 33 variations of clustering pipelines across four datasets demonstrates the potential effectiveness of our automated approach compared with manually crafted test suites. (All the experiments and data on Scanner, Spree and Booked Scheduler are available at https://github.com/frederictamagnan/STVR2024.) Then, we analyse the semantics of the clusters based on their principal composing patterns. [ABSTRACT FROM AUTHOR]

Dynamic networks are ubiquitous in many domains for modelling evolving graph-structured data and detecting changes allows us to understand the dynamic of the domain represented. A category of computational solutions is represented by the pattern-based change detectors (PBCDs), which are non-parametric unsupervised change detection methods based on observed changes in sets of frequent patterns over time. Patterns have the ability to depict the structural information of the sub-graphs, becoming a useful tool in the interpretation of the changes. Existing PBCDs often rely on exhaustive mining, which corresponds to the worst-case exponential time complexity, making this category of algorithms inefficient in practice. In fact, in such a case, the pattern mining process is even more time-consuming and inefficient due to the combinatorial explosion of the sub-graph pattern space caused by the inherent complexity of the graph structure. Non-exhaustive search strategies can represent a possible approach to this problem, also because not all the possible frequent patterns contribute to changes in the time-evolving data. In this paper, we investigate the viability of different heuristic approaches which prevent the complete exploration of the search space, by returning a concise set of sub-graph patterns (compared to the exhaustive case). The heuristics differ on the criterion used to select representative patterns. The results obtained on real-world and synthetic dynamic networks show that these solutions are effective, when mining patterns, and even more accurate when detecting changes. [ABSTRACT FROM AUTHOR]

Static code analysis tools (SATs) are widely used to detect potential defects in software projects. However, the usability of SATs is seriously hindered by a large number of unactionable warnings. Currently, many warning prioritization approaches are proposed to improve the usability of SATs. These approaches mainly extract different warning features to capture the statistical or historical information of warnings, thereby ranking actionable warnings in front of unactionable warnings. Such features are extracted by extremely relying on domain knowledge. However, the precise domain knowledge is difficult to be acquired. Also, the domain knowledge obtained in a project cannot be directly applied to other projects due to different application scenarios among different projects. To address the above problem, we propose a pattern mining-based warning prioritization approach based on the warning-related Abstract Syntax Tree (AST). To automatically mine actionable warning patterns, our approach leverages an advanced technique to collect actionable warnings, designs an algorithm to extract the warning-related AST, and mines patterns from ASTs of all actionable warnings. To prioritize the newly reported warnings, our approach combines exact and fuzzing matching techniques to calculate the similarity score between patterns of the newly reported warnings and the mined actionable warning patterns. We compare our approach with four typical baselines on five open-source and large-scale Java projects. The results show that our approach outperforms four baselines and achieves the maximum MAP (0.76) and MRR (2.19). Besides, a case study on Defect4J dataset demonstrates that our approach can discover 83% of true defects in the top 10 warnings. [ABSTRACT FROM AUTHOR]

In pattern mining, high-utility itemset mining (HUIM) is useful for discovering high-utility patterns. The study of HUIM using heuristic techniques reflects issues in producing better offspring. It is ineffective in terms of search space organization, population diversity, and utility calculation, which impact runtime and accuracy. It is observed that very few researchers have experimented with genetic algorithm (GA) and are still facing the same issues as mentioned before. To overcome these problems, a novel approach is proposed for HUIM using modified GA and optimized local search (HUIM-MGALS) with six potential contributions. First is linking the utility with the Bitmap dataset to reduce utility access time, leading to effective search space organization. Second, HUIM-MGALS employs a fitness scaling strategy to avoid redundancy. Third, a high-utility itemset (HUI) revision strategy is employed to explore significant HUIs. Modified population diversity maintenance strategy and iterative crossover help to preserve significant HUIs and improve search capability as fourth and fifth contributions. Sixth, the use of multiple mutations refines the wasted individuals to boost accuracy. Extensive experimentation showed that HUIM-MGALS significantly outperforms the presented algorithms, up to 8.6 times faster. It also demonstrates superior HUI discovery capabilities for both sparse and dense datasets. This is supported by the modified population diversity maintenance strategy, which is proved to be the most impactful modification for HUI discovery in HUIM-MGALS. [ABSTRACT FROM AUTHOR]

Time series motif discovery (TSMD) refers to the task of identifying patterns that occur multiple times (possibly with minor variations) in a time series. All existing methods for TSMD have one or more of the following limitations: they only look for the two most similar occurrences of a pattern; they only look for patterns of a pre-specified, fixed length; they cannot handle variability along the time axis; and they only handle univariate time series. In this paper, we present a new method, LoCoMotif, that has none of these limitations. The method is motivated by a concrete use case from physiotherapy. We demonstrate the value of the proposed method on this use case. We also introduce a new quantitative evaluation metric for motif discovery, and benchmark data for comparing TSMD methods. LoCoMotif substantially outperforms the existing methods, on top of being more broadly applicable. [ABSTRACT FROM AUTHOR]

In recent years, pattern mining has evolved from a slow-moving, repetitive three-step process to a much more agile and iterative/user-centric mining model. A crucial element of this framework is the capability to rapidly provide a set of diverse patterns to the user. This paper proposes a pattern mining approach based on constraint programming that incorporates a non-redundancy/diversity constraint into closed pattern enumeration. The level of diversity is controlled through a threshold on the maximum pairwise Jaccard similarity of pattern occurrences. We show that the Jaccard measure does not have nice (anti-)monotonicity properties w.r.t. the general-to-specific enumeration. To address this limitation, we propose anti-monotonic lower and upper-bound relaxations of the Jaccard similarity with nice pruning-enabling properties, and connect the final results to the original Jaccard Index. To evaluate the effectiveness of our relaxations, we conduct a comprehensive comparison against several existing pattern mining techniques designed to control redundancy. Experimental results illustrate that our approach provides an effective solution for mining diverse itemsets, showing competitive performance in both runtime and flexibility. [ABSTRACT FROM AUTHOR]

We present updates to the Cray Graph Engine, a high performance in‐memory semantic graph database, which enable performant execution across multiple architectures as well as deployment in a container to support cloud and as‐a‐service graph analytics. This paper discusses the changes required to port and optimize CGE to target multiple architectures, including Cray Shasta systems, large shared‐memory machines such as SuperDome Flex (SDF), and cluster environments such as Apollo systems. The porting effort focused primarily on removing dependences on XPMEM and Cray PGAS and replacing these with a simplified PGAS library based upon POSIX shared memory and one‐sided MPI, while preserving the existing Coarray‐C++ CGE code base. We also discuss the containerization of CGE using Singularity and the techniques required to enable container performance matching native execution. We present early benchmarking results for running CGE on the SDF, Infiniband clusters and Slingshot interconnect‐based Shasta systems. [ABSTRACT FROM AUTHOR]

Periodic high-utility itemset (PHUI) mining can extend beyond the conventional approach of high-utility itemset mining by uncovering recurring customer purchase behaviors common in real-life scenarios (e.g., buying apples and oranges every three days or weekly). Such behaviors, particularly in market basket databases, signify stable patterns that ensure long-term profitability. Existing PHUI mining algorithms assume a static database and incur significant costs when handling incremental databases, as each batch of new transactions necessitates reprocessing the entire dataset. To overcome this challenge, we introduce the Incremental Periodic High-Utility Itemset Miner (IPHM), a method for efficiently extracting periodic high-utility itemsets in incremental database environments. We propose an innovative incremental utility-list structure tailored for incremental database scenarios. Effective pruning strategies are employed to expedite the construction and update of incremental utility-lists and to discard unpromising candidates. As demonstrated by the experimental results, the algorithm is efficacious and efficient, highlighting its practical applicability in dynamic data environments. The algorithm shows a remarkable ability to quickly adapt to database changes, making it highly suitable for applications in market basket analysis where frequent updates are common.

This study addresses the crucial challenge of monitoring the State of Health (SOH) of Lithium-Ion Batteries (LIBs) in response to the escalating demand for renewable energy systems and the imperative to reduce CO2 emissions. The research introduces deep learning (DL) models, namely Encoder-Long Short-Term Memory (E-LSTM) and Convolutional Neural Network-LSTM (CNN–LSTM), each designed to forecast battery SOH. E-LSTM integrates an encoder for dimensionality reduction and an LSTM model to capture data dependencies. CNN–LSTM, on the other hand, employs CNN layers for encoding followed by LSTM layers for precise SOH estimation. Significantly, we prioritize model explainability by employing a game-theoretic approach known as SHapley Additive exPlanations (SHAP) to elucidate the output of our models. Furthermore, a method based on pattern mining was developed, synergizing with the model, to identify patterns contributing to abnormal SOH decrease. These insights are presented through informative plots. The proposed approach relies on the battery dataset from the Massachusetts Institute of Technology (MIT) and showcases promising results in accurately estimating SOH values, in which the E-LSTM model outperformed the CNN–LSTM model with a Mean Absolute Error (MAE) of less than 1%.

Abstract The High Average Utility Itemset Mining (HAUIM) technique, a variation of High Utility Itemset Mining (HUIM), uses the average utility of the itemsets. Historically, most HAUIM algorithms were designed for static databases. However, practical applications like market basket analysis and business decision-making necessitate regular updates of the database with new transactions. As a result, researchers have developed incremental HAUIM (iHAUIM) algorithms to identify HAUIs in a dynamically updated database. Contrary to conventional methods that begin from scratch, the iHAUIM algorithm facilitates incremental changes and outputs, thereby reducing the cost of discovery. This paper provides a comprehensive review of the state-of-the-art iHAUIM algorithms, analyzing their unique characteristics and advantages. First, we explain the concept of iHAUIM, providing formulas and real-world examples for a more in-depth understanding. Subsequently, we categorize and discuss the key technologies used by varying types of iHAUIM algorithms, encompassing Apriori-based, Tree-based, and Utility-list-based techniques. Moreover, we conduct a critical analysis of each mining method's advantages and disadvantages. In conclusion, we explore potential future directions, research opportunities, and various extensions of the iHAUIM algorithm.

Episode mining is a research area in data mining, where the aim is to discover interesting episodes, that is, subsequences of events, in an event sequence. The most popular episode-mining task is frequent episode mining (FEM), which consists of identifying episodes that appear frequently in an event sequence, but this task has also been extended in various ways. It was shown that episode mining can reveal insightful patterns for numerous applications such as web stream analysis, network fault management, and cybersecurity, and that episodes can be useful for prediction. Episode mining is an active research area, and there have been numerous advances in the field over the last 25 years. However, due to the rapid evolution of the pattern mining field, there is no prior study that summarizes and gives a detailed overview of this field. The contribution of this article is to fill this gap by presenting an up-to-date survey that provides an introduction to episode mining and an overview of recent developments and research opportunities. This advanced review first gives an introduction to the field of episode mining and the first algorithms. Then, the main concepts used in these algorithms are explained. After that, several recent studies are reviewed that have addressed some limitations of these algorithms and proposed novel solutions to overcome them. Finally, the paper lists some possible extensions of the existing frameworks to mine more meaningful patterns and presents some possible orientations for future work that may contribute to the evolution of the episode mining field. [ABSTRACT FROM AUTHOR]

To represent complex inter-relationships among entities, weighted graphs are more useful than their unweighted counterparts. In a transactional graph setting, researchers have made several attempts to mine weighted frequent subgraphs from a collection of edge-weighted graphs, which will serve as the representative feature of the underlying graph database and can be further used for analysis. As weighted support of any pattern does not hold downward closure property, a property that is often used in frequent pattern mining to control search space, has made weighted frequent substructure mining a tremendously difficult task. This article proposes an efficient weighted frequent subgraph mining framework called WFSM-MaxPWS for graphs with static edge weights. We introduce a new pruning technique called MaxPWS pruning along with canonical labeling of subgraphs, which helps reduce the search space significantly without compromising completeness. Extending the WFSM-MaxPWS framework, we propose another framework called DewgSpan that is capable of mining graphs with dynamic edge weight. DewgSpan utilizes a summarized edge-weight distribution table to overcome the new challenges of dynamic edge-weight settings. Evaluation results show that WFSM-MaxPWS and DewgSpan are significantly faster than the existing MaxW pruning technique of weighted pattern mining. [ABSTRACT FROM AUTHOR]

This paper proposes the sky-signature model, an extension of the signature model Gautrais et al. (in: Proceedings of the Pacific-Asia conference on knowledge discovery and data mining (PAKDD), Springer, 2017b) to multi-objective optimization. The signature approach considers a sequence of itemsets, and given a number k it returns a segmentation of the sequence in k segments such that the number of items occuring in all segments is maximized. The limitation of this approach is that it requires to manually set k, and thus fixes the temporal granularity at which the data is analyzed. The sky-signature model proposed in this paper removes this requirement, and allows to examine the results at multiple levels of granularity, while keeping a compact output. This paper also proposes efficient algorithms to mine sky-signatures, as well as an experimental validation both real data both from the retail domain and from natural language processing (political speeches). [ABSTRACT FROM AUTHOR]

Due to the development of computing technology, various data are collected and analyzed to extract meaningful information and are utilized in various industries. In particular, in the manufacturing industry, collected data are analyzed and used for process management, monitoring, quality prediction, etc., to establish smart factories and Reconfigurable Smart Factories. To continuously manage the processes of a Reconfigurable Smart Factory, it is necessary to derive a process model that includes factors affecting the process and to compare the actual execution process with the designed process and make improvements. The conventional methods for deriving process model are methods that apply to processes with a fixed start and end and are difficult to apply directly to the processes of a Reconfigurable Smart Factory. Furthermore, the conventional methods are sequential control flow-oriented, and a process derivation method that includes factors affecting the process is required. Therefore, it is necessary to consider various factors (e.g., time attributes, task time) that affect the process, not just the sequence, to solve this. In this study, we propose a novel method to derive a process that includes sequential flow and time conditions. The proposed methodology focuses on the execution time and order of instances to derive the process. Experiments were conducted by changing the conditions of the methodology and measuring the execution time to validate the proposed methodology. [ABSTRACT FROM AUTHOR]

Due to the increased size of data, there is a need for retrieving the right document for the user efficiently, which finds various applications in the research community. In this work, we propose Hybrid Global Search Optimization with Density based clustering (HGSODC) that extend the current state of the art, which is mostly based on searching a document from closed frequent terms to bring efficient result by alleviating convergence problem. Firstly, the documents are preprocessed by removing stop words, stemming, and then grouped using hierarchical density-based spatial clustering of applications with noise (HDBSCAN) clustering, and then closed frequent patterns mining is performed at each document. Secondly, the search is done using the HGSOA algorithm, and the documents are retrieved. We determine the effectiveness of the HGSODC approach through a set of experiments under the NPL, LISA, and CACM corpus. Compared to some existing related work, a wide range of evaluations are provided to show the strength of the proposed method in terms of precision, recall, MAP, F-score, accuracy, and convergence rate by running multiple experiments to compare our approaches with different baselines. The results indicate that the proposed HGSODC approach outperforms the traditional document information retrieval methods based on returned document quality and running time. [ABSTRACT FROM AUTHOR]

A Dockerfile defines a set of instructions to build Docker images, which can then be instantiated to support containerized applications. Recent studies have revealed a considerable amount of quality issues with Dockerfiles. In this article, we propose a novel approach, Dockerfiles Rule mIning and Violation dEtection (DRIVE), to mine implicit rules and detect potential violations of such rules in Dockerfiles. DRIVE first parses Dockerfiles and transforms them to an intermediate representation. It then leverages an efficient sequential pattern mining algorithm to extract potential patterns. With heuristic-based reduction and moderate human intervention, potential rules are identified, which can then be utilized to detect potential violations of Dockerfiles. DRIVE identifies 34 semantic rules and 19 syntactic rules including 9 new semantic rules that have not been reported elsewhere. Extensive experiments on real-world Dockerfiles demonstrate the efficacy of our approach. [ABSTRACT FROM AUTHOR]

Abstract Background Healthcare, as with other sectors, has undergone progressive digitalization, generating an ever-increasing wealth of data that enables research and the analysis of patient movement. This can help to evaluate treatment processes and outcomes, and in turn improve the quality of care. This scoping review provides an overview of the algorithms and methods that have been used to identify care pathways from healthcare utilization data. Method This review was conducted according to the methodology of the Joanna Briggs Institute and the Preferred Reporting Items for Systematic Reviews Extension for Scoping Reviews (PRISMA-ScR) Checklist. The PubMed, Web of Science, Scopus, and EconLit databases were searched and studies published in English between 2000 and 2021 considered. The search strategy used keywords divided into three categories: the method of data analysis, the requirement profile for the data, and the intended presentation of results. Criteria for inclusion were that health data were analyzed, the methodology used was described and that the chronology of care events was considered. In a two-stage review process, records were reviewed by two researchers independently for inclusion. Results were synthesized narratively. Results The literature search yielded 2,865 entries; 51 studies met the inclusion criteria. Health data from different countries ( $$n=12$$ n = 12 ) and of different types of disease ( $$n=26$$ n = 26 ) were analyzed with respect to different care events. Applied methods can be divided into those identifying subsequences of care and those describing full care trajectories. Variants of pattern mining or Markov models were mostly used to extract subsequences, with clustering often applied to find care trajectories. Statistical algorithms such as rule mining, probability-based machine learning algorithms or a combination of methods were also applied. Clustering methods were sometimes used for data preparation or result compression. Further characteristics of the included studies are presented. Conclusion Various data mining methods are already being applied to gain insight from health data. The great heterogeneity of the methods used shows the need for a scoping review. We performed a narrative review and found that clustering methods currently dominate the literature for identifying complete care trajectories, while variants of pattern mining dominate for identifying subsequences of limited length.

Competitive bidding is a popular technique State Highway Agencies use for selecting contractors for public construction work. It intends to ensure that construction projects are awarded at the lowest price. However, public owners may award contracts at high prices due to collusive bid arrangements among bidders. The current practices and state-of-the-art methods of bid collusion detection are ineffective because they greatly rely on engineers' estimates, which can be inaccurate, and the similarity in the cost structure of the bids, which experienced collusive bidders can manipulate. This study contributes to the body of knowledge with a novel data-driven collusion red-flag detection framework (CRFD) that utilizes pattern mining techniques and statistical tests for detecting contractors with a red-flag pattern, which refers to a significant difference in the winning rates of a contractor with and without the co-occurrence of other particular contractors. A mechanism is also proposed to incorporate potential, influential factors into the CRFD to increase the detection power or examine possible collusion between different scenarios. The proposed method is expected to assist project owners in detecting early signs of bid collusion and eventually help them significantly enhance their award decision-making. [ABSTRACT FROM AUTHOR]

Partial periodic pattern (3P) mining is a vital data mining technique that aims to discover all interesting patterns that have exhibited partial periodic behavior in temporal databases. Previous studies have primarily focused on identifying 3Ps only in row temporal databases. One can not ignore the existence of 3Ps in columnar temporal databases as many real-world applications, such as Facebook and Adobe, employ them to store their big data. This paper proposes an efficient single database scan algorithm, Partial Periodic Pattern-Equivalence Class Transformation (3P-ECLAT), to identify all 3Ps in a columnar temporal database. The proposed algorithm compresses the given database into a novel list-based data structure and mines it recursively to find all 3Ps. The 3P-ECLAT leverages the "downward closure property" and "depth-first search technique" to reduce the search space and the computational cost. Extensive experiments have been conducted on synthetic and real-world databases to demonstrate the efficiency of the 3P-ECLAT algorithm. The memory and runtime results show that 3P-ECLAT outperforms its competitor considerably. Furthermore, 3P-ECLAT is highly scalable and is superior to the previous approach in handling large databases. Finally, to demonstrate the practical utility of our algorithm, we provide two real-world case studies, one on analyzing traffic congestion during disasters and another on identifying the highly polluted areas in Japan. [ABSTRACT FROM AUTHOR]

Whatever malware protection is upcoming, still the data are prone to cyber-attacks. The most threatening Structured Query Language Injection Attack (SQLIA) happens at the database layer of web applications leading to unlimited and unauthorized access to confidential information through malicious code injection. Since feature extraction accuracy significantly influences detection results, extracting the features of a query that predominantly contributes to SQL Injection (SQLI) is the most challenging task for the researchers. So, the proposed work primarily focuses on that using modified parse-tree representation. Some existing techniques used graph representation to identify characteristics of the query based on a predefined fixed list of SQL keywords. As the complete graph representation requires high time complexity for traversals due to the unnecessary links, a modified parse tree of tokens is proposed here with restricted links between operators (internal nodes) and operands (leaf nodes) of the WHERE clause. Tree siblings from the leaf nodes comprise the WHERE clause operands, where the attackers try to manipulate the conditions to be true for all the cases. A novelty of this work is identifying patterns of legitimate and injected queries from the proposed modified parse tree and applying a pattern-based neural network (NN) model for detecting attacks. The proposed approach is applied in various machine learning (ML) models and a neural network model, Multi-Layer Perceptron (MLP). With the scrupulously extracted patterns and their importance (weights) in legitimate and injected queries, the MLP model provides better results in terms of accuracy (97.85%), precision (93.8%), F1-Score (96%), and AUC (97.8%). [ABSTRACT FROM AUTHOR]

In database marketing, recency, frequency, and monetary (RFM) analysis is an important tool to segment customers based on their recent purchase behaviors. By combining the RFM model with frequent pattern mining algorithms such as RFMP-Growth and fuzzy-RFU-tree, RFM-patterns can be mined. RFMP-Growth and fuzzy-RFU-tree use a tree-based structure; however, patterns found by RFMP-Growth do not contain qualitative information among items. By applying the fuzzification method, patterns mined by fuzzy-RFU-tree contain qualitative information about items. However, this algorithm consumes considerable memory and time. Therefore, to discover valuable fuzzy-RFM-patterns efficiently, we first introduce a list structure and propose the F-RFM-Miner algorithm. Consequently, we design two new pruning strategies to reduce the number of candidate patterns. Moreover, we conduct experiments on dense and sparse datasets to compare our algorithm with state-of-the-art algorithm and test the efficiency of the new pruning strategies. The experiment results show that F-RFM-Miner performs better than fuzzy-RFU-tree. [ABSTRACT FROM AUTHOR]

Mining high utility itemsets are the basic task in the area of frequent itemset mining (FIM) that has various applications in diverse domains, including market basket analysis, web mining, cross-marketing, and e-commerce. In recent years, many efficient high utility itemsets mining (HUIM) algorithms are proposed to discover the high utility itemsets (HUIs). This survey presents a comprehensive summary of the current state-of-the-art HUIM approaches for transactional databases. This paper categorises the state-of-the-art approaches as level-wise, tree-based, utility-list-based, projection-based and miscellaneous. It provides the pros and cons of each category of mining approaches in detail. A taxonomy of the HUIM for transactional databases is presented. The survey also summarises and discusses approaches for other types of databases, including on-shelf, dynamic and uncertain. The paper explores the applications of HUIM in diverse domains and discusses the challenges and limitations of the approach. It presents an overview of 16 real-world which are utilized by various state-of-the-art HUIM approaches for transactional databases. Overall, this survey provides a valuable resource for researchers in the field of HUIM and offers insights into future directions for research and development in this area. [ABSTRACT FROM AUTHOR]

High-utility sequential pattern mining (HUSPM) helps researchers find all subsequences that have high utility in a quantitative sequential database. The HUSPM approach appears to be well suited for resource transformation in DIKWP graphs. However, all the extensions of a high-utility sequential pattern (HUSP) also have a high utility that increases with its length. Therefore, it is difficult to obtain diverse patterns of resources. The patterns that consist of many low-utility items can also be a HUSP. In practice, such a long pattern is difficult to analyze. In addition, the low-utility items do not always reflect the interestingness of association rules. High average-utility pattern mining is considered a solution to extract more significant patterns by considering the lengths of patterns. In this paper, we formulate the problem of top-k high average-utility sequential pattern mining (HAUSPM) and propose a novel algorithm for resource transformation. We adopt a projection mechanism to improve efficiency. We also adopt the sequence average-utility-raising strategy to increase thresholds. We design the prefix extension average utility and the reduced sequence average utility by incorporating the average utility into the utility upper bounds. The results of our comparative experiments demonstrate that the proposed algorithm can achieve sufficiently good performance. [ABSTRACT FROM AUTHOR]