arXiv CSopen access

Cross-level Privacy Preserving Utility Mining

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

databases, sql, data management, storage

Cross-level Privacy Preserving Utility Mining Jiahong Caia , Wensheng Gana,∗ and Philip S. Yub a College of Cyber Security, Jinan University, Guangzhou 510632, P.R. China

arXiv:2605.00036v1 [cs.DB] 28 Apr 2026

b Department of Computer Science, University of Illinois Chicago, Chicago IL 60607, USA.

ARTICLE INFO

ABSTRACT

Keywords: privacy-preserving cross-level itemsets sensitive pattern utility mining taxonomy

Privacy-preserving utility mining (PPUM) aims to hide sensitive high-utility patterns while preserving the utility of the sanitized database. In practice, however, many datasets are associated with taxonomic information, which makes the identification and processing of generalized items more challenging. To address this, we investigate the cross-level privacy-preserving utility mining (CLPPUM) problem and propose a method for protecting generalized items. Based on different victim item selection strategies, we develop three CLPPUM algorithms: minimum RGISU first (Min-RF), maximum RGISU first (Max-RF), and best NSC first (Best-NSCF). Furthermore, to enable efficient victim item identification, a novel dictionary structure named GI-dic is designed to accelerate the computation of required utility metrics. Experimental results on multiple datasets demonstrate that the proposed algorithms successfully hide all sensitive cross-level high-utility itemsets without introducing artificial itemsets. The results also show that our method performs well on sparse datasets, and both Min-RF and BestNSCF consistently outperform Max-RF. Overall, Min-RF achieves the best performance, particularly when the minimum utility threshold is low and the dataset is dense. Datasets and code are available at https://github.com/jhcai321/CLPPUM.

With the rapid growth of large-scale databases, the volume of data has increased significantly. Data mining [13, 15] has therefore become an important tool for extracting useful information from large-scale datasets. For example, enterprises analyze transaction records and user behavior to improve decision-making and enhance profitability. In this context, data mining has been expanded into different research directions. Frequent itemset mining (FIM) [1] focuses on the combination of goods that frequently appear in transaction records. However, in real life, low-frequency combinations of goods are still very likely to generate large profits. To overcome the limitations of frequency pattern mining, the concept of high-utility itemset mining (HUIM) [14, 41] was introduced. In HUIM, the utility of an item is determined by internal utility (quantity) and external utility (unit profit/importance). Therefore, it can be better used to analyze factors such as user preferences, importance, and profit in reality. A variety of HUIM algorithms have been developed [25, 28, 46]. Although HUIM has been widely used, it ignores the concept of hierarchical structure in the real world. As shown in Fig. 1, in computer peripherals, “keyboard” and “mouse” are the materialization of the abstract concept of “input device”. Therefore, to enable data mining to consider hierarchical information, the cross-level high-utility itemset mining (CLHUIM) [6, 10, 36] has been proposed. HUIM can assist decision-makers in analyzing massive real-world datasets and developing high-profit strategies from discovered itemsets. However, in data analysis in medical, government, and commercial organizations, data is ∗ Corresponding author

[email protected] (J. Cai); [email protected] (W. Gan); [email protected] (P.S. Yu) ORCID (s):

Jiahong Cai et al.: Preprint submitted to Elsevier

level 0

Peripherals

1. Introduction Input device

Keyboard

Mouse

level 1

Output device

Monitor

Headphones

level 2

Figure 1: A taxonomy tree of computer peripherals.

often transferred between data providers and data miners. Analyzing such data may lead to the leakage of sensitive information held by data providers. For example, in marketing scenarios, if the high-value discovered information reveals the consumption habits or behaviors of a particular gender, race, or group, then this information is likely to be sensitive, and its leakage may raise ethical concerns. Therefore, privacy-preserving data mining (PPDM) [2, 23] was proposed. PPDM minimizes the impact on non-sensitive information while hiding sensitive information, thereby preserving data availability. Privacy-preserving utility mining (PPUM) [12] is a branch of PPDM and can be divided into heuristic-based [21, 22, 42], border-based [27], and exact [20, 30] algorithms. Existing PPUM methods are effective for hiding sensitive high-utility patterns in conventional settings, but they do not explicitly consider hierarchical information. In real-world data, itemsets may involve generalized items, which increases the complexity of representation and processing. As a result, directly applying existing PPUM methods to the cross-level setting may not effectively hide sensitive cross-level high-utility itemsets. This limitation motivates the study of cross-level privacy-preserving utility mining (CLPPUM), which aims to handle sensitive itemsets that contain items from different levels. The specific contributions of this paper are as follows: Page 1 of 17

Cross-level Privacy Preserving Utility Mining

• This paper defines a new task, cross-level privacypreserving utility mining (CLPPUM), for identifying and hiding cross-level high-utility itemsets (CLHUIs). • Three indicators—sensitive count (SC), non-sensitive count (NSC), and real item sensitive utility (RISU)—are used to measure the relationship between items and sensitive/non-sensitive CLHUIs. These indicators are extended in the cross-level context, and a dictionary structure GI-dic is designed to accelerate the calculation of indicators and assist in the selection of victim items. • Three algorithms are designed to hide sensitive CLHUIs. The algorithms are named Minimum RGISU First (Min-RF), Maximum RGISU First (Max-RF), and Best NSC First (Best-NSCF). The study also compares the effects of different indicators on SCLHUIs. • Experiments are performed on several datasets to evaluate the performance of the proposed algorithms. The results indicate that the proposed algorithms perform well on sparse datasets, correctly hiding all sensitive CLHUIs without introducing any false CLHUIs into the database. As a result, both the hiding failure (HF) and the artificial cost (AC) are 0. Among the three proposed algorithms, Min-RF exhibits the optimal performance. The rest of this paper is arranged as follows: Section 2 presents and summarizes the research work related to PPUM. Section 3 introduces the basic knowledge of CLHUIM and PPUM. Section 4 provides a detailed exposition of the three CLPPUM algorithms proposed in this paper and analyzes their privacy-related properties. Section 5 conducts experiments and analyzes the results. Section 6 summarizes this paper and looks forward to future work.

2. Related Work 2.1. High-utility itemset mining To consider both the number of items and their unit profit/weight in the data mining process, frequent itemset mining (FIM) has been extended to high-utility itemset mining (HUIM) [14, 41]. However, since utility does not have anti-monotonicity with frequency, the HUIM task is more challenging [28]. To address this issue, many studies introduced the concept of upper bounds and proposed many efficient HUIM algorithms to improve mining efficiency. Early work proposed the Two-Phase algorithm [28], which relies on the transaction-weighted utility (TWU) upper bound. Based on the TWU, several tree-based twophase approaches were developed, including IHUP [3], UPGrowth [35], and UP-Growth+ [34]. Although these methods reduce the number of database scans, they still rely on the loose TWU upper bound and tend to generate a large number of candidate itemsets. To overcome this limitation, Liu et al. [25] proposed HUI-Miner, a one-phase algorithm based on the utility-list. By adopting a tighter remaining utility upper bound, it avoids candidate generation altogether. Subsequent methods, such as D2HUP [24], FHM Jiahong Cai et al.: Preprint submitted to Elsevier

[11], and EFIM [46], further improved efficiency through tighter upper bounds, more effective pruning strategies, and techniques such as high-utility database projection (HDP) and high-utility transaction merging (HTM). More recent studies have also explored memory reuse [9], bitwise acceleration [39], structural simplification [8], and approximate search [32, 40] to reduce both memory consumption and computational cost during utility-list construction and processing. Traditional HUIM cannot identify hierarchical information in reality. To address this limitation, taxonomy information has been incorporated into HUIM to support hierarchical structures. ML-HUI-Miner [6] introduced the concept of generalized HUIs. However, this algorithm can only mine items belonging to the same taxonomy level and cannot identify itemsets that span different levels. Subsequently, CLH-Miner [10] and FEACP [36] were proposed to support cross-level high-utility itemset mining (CLHUIM), using tighter upper bounds to reduce memory usage and runtime. Additionally, variants of CLHUIM algorithms have been proposed to discover top-k CLHUIs [17, 31, 33] and CLHUIs in databases with unstable and negative profits [37].

2.2. Privacy-preserving utility mining Utility pattern mining can assist in analyzing high-value information within data, bringing significant benefits to companies. However, when enterprises store, use, or share business and healthcare data, there is a high risk of disclosing sensitive or confidential information, which may lead to privacy concerns [38]. As a result, privacy-preserving data mining (PPDM) has been developed into privacy-preserving utility mining (PPUM). These algorithms can hide sensitive information in a database while balancing privacy protection and data sharing. PPUM algorithms can be divided into heuristic-based, border-based, and exact algorithms. Yeh and Hsu [42] first formalized the PPUM problem and proposed two classical heuristic-based algorithms, HHUIF and MSICF. To improve efficiency, a tree-based method called FPUTT [44] organizes the database to accelerate the identification and hiding of sensitive itemsets. Yin et al. [43] proposed FULD, which utilizes a novel utility dictionary structure to enhance performance. Subsequent studies have explored more sophisticated strategies for selecting victim items. Lin et al. [22] proposed the MSU-MAU and MSUMIU algorithms, incorporating multiple similarity measures to evaluate the side effects of data sanitization. Lin et al. [26] further considered non-sensitive itemsets in the victim selection process and introduced the IMSICF algorithm, effectively reducing the impact on non-sensitive patterns. The MinMax and Weighted algorithms [18] combine dual sorting strategies with different victim selection criteria to improve efficiency and reduce side effects. Ashraf et al. [5] introduced a new metric, real item sensitive utility (RISU), along with a refined sorting strategy to further optimize performance. In addition, boundary-based and exact approaches have been proposed to determine optimal sanitization strategies, Page 2 of 17

Cross-level Privacy Preserving Utility Mining Table 1 An example quantitative transaction database.

𝑇𝑖𝑑 𝑇1 𝑇2 𝑇3 𝑇4 𝑇5 𝑇6 𝑇7 𝑇8

Transaction (𝑎, 1), (𝑏, 1), (𝑑, 1) (𝑎, 2), (𝑑, 3), (𝑒, 1) (𝑎, 1), (𝑏, 2), (𝑐, 5), (𝑑, 1), (𝑒, 3) (𝑑, 4), (𝑒, 3) (𝑎, 1), (𝑏, 1), (𝑑, 1) (𝑑, 5), (𝑒, 2), (𝑓 , 2) (𝑎, 2), (𝑐, 1) (𝑎, 1), (𝑏, 4), (𝑒, 3)

Utility 9 21 26 18 9 21 13 15

such as using maximum boundary values [27] or formulating the problem as integer programming [20, 29, 30]. However, these methods often suffer from high computational complexity and long execution time [18]. Although heuristicbased algorithms cannot guarantee the best results, they are easy to understand and implement. In addition, heuristicbased privacy-preserving algorithms have also been extended to other related mining tasks, including frequent high average-utility itemset mining [19], periodic high-utility pattern mining [45], rare itemset mining [7, 16], and association rule mining [4]. Therefore, heuristic-based algorithms remain the focus of most current research. Although numerous algorithms have been developed for hiding HUIs, none of the existing privacy-preserving methods have taken real-world categorical hierarchical information into account. Therefore, this paper defines cross-level PPUM that aims to achieve the hiding of sensitive cross-level high-utility itemsets.

3. Preliminaries Let 𝐼 = {𝑖1 , 𝑖2 , ..., 𝑖𝑚 } be a set of items. A quantitative transaction database is a collection of transactions  = {𝑇1 , 𝑇2 , ..., 𝑇𝑛 }. For each transaction 𝑇𝑗 ∈ , 𝑇𝑗 ⊆ 𝐼, each 𝑇𝑗 has a unique identifier 𝑗. For each item 𝑣 ∈ 𝐼, the associated external utility (i.e., unit profit) is denoted as 𝑝(𝑣). For each item 𝑣 ∈ 𝑇𝑗 , its internal utility, referring to the quantity in transaction 𝑇𝑗 , is represented by 𝑞(𝑣, 𝑇𝑗 ). For example, Table 1 contains six items (𝐼 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓 }) and eight transactions ( = {𝑇1 , 𝑇2 , ..., 𝑇8 }). In the transaction 𝑇3 , the internal utility of items 𝑎, 𝑐, and 𝑑 is 1, 5, and 1, respectively. We set the external utility values of {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓 } to {5, 1, 3, 3, 2, 1}. Definition 1. (Taxonomy) [6, 10]. A taxonomy 𝜏 is a tree structure defined on the quantitative transaction database . In this structure, each leaf node corresponds to an item 𝑣 ∈ 𝐼. Each internal node denotes a category formed by aggregating all of its descendant leaf nodes, referred to as a generalized item (generalized items). The set of all generalized items is denoted as 𝐺𝐼, and the union of all generalized items and leaf items is denoted as 𝐴𝐼, i.e., 𝐴𝐼 = 𝐺𝐼 ∪ 𝐼. Let the relationship 𝐿𝑅 ⊆ 𝐺𝐼 × 𝐼, such that if there exists a path from 𝑔 to 𝑣, then (𝑔, 𝑣) ∈ 𝐿𝑅. Similarly, let the relationship 𝐺𝑅 ⊆ 𝐴𝐼 × 𝐴𝐼, such that if there exists a path from item 𝑑 to item 𝑓 , then (𝑑, 𝑓 ) ∈ 𝐺𝑅. Jiahong Cai et al.: Preprint submitted to Elsevier

Definition 2. (Descendant) [10]. In taxonomy 𝜏, the leaf items of a generalized item 𝑔 are all leaf nodes of 𝑔 in the tree structure that are reachable from 𝑔 along a path. This collection is formally defined as Leaf(𝑔, 𝜏) = {𝑣 ∣ (𝑔, 𝑣) ∈ 𝐿𝑅}. The descendant nodes of a (generalized) item 𝑑 are referred to as all nodes in the tree structure that are descendants of 𝑑, and are defined as: Desc(𝑑, 𝜏) = {𝑓 ∣ (𝑑, 𝑓 ) ∈ 𝐺𝑅}. level(𝑑) denotes the number of edges on the path from the root node to item 𝑑. A collection of items 𝑃 is considered an itemset, where 𝑃 ⊆ 𝐴𝐼 ∧∄ 𝑖, 𝑗 ∈ 𝑃 , 𝑖 ∈ Desc(𝑗, 𝜏). If ∃ 𝑔 ∈ 𝑃 where 𝑔 ∈ 𝐺𝐼, then 𝑃 is a generalized itemset.

∅ X c

Y a

Z d

Figure 2: A taxonomy of items.

Definition 3. (Utility of a generalized item/itemset) [10]. The utility of an item 𝑣 in a transaction 𝑇𝑗 is calculated as: 𝑢(𝑣, 𝑇𝑗 ) = 𝑞(𝑣, 𝑇𝑗 ) × 𝑝(𝑣). The utility of an itemset 𝑃 ∑ in 𝑇𝑗 is calculated as 𝑢(𝑃 , 𝑇𝑗 ) = 𝑣∈𝑃 𝑢(𝑣, 𝑇𝑗 ). The utility ∑ of an itemset 𝑃 in  is 𝑢(𝑃 ) = 𝑇𝑗 ∈𝑔(𝑃 ) 𝑢(𝑃 , 𝑇𝑗 ), where 𝑔(𝑃 ) is the set of transactions in  that contain 𝑃 . The utility of a generalized item 𝑔 in a transaction 𝑇𝑗 is denoted as 𝑢(𝑔, 𝑇𝑗 ), is calculated as the sum of the utilities of all ∑ its leaf items: 𝑣∈Leaf(𝑔,𝜏) 𝑝(𝑣) × 𝑞(𝑣, 𝑇𝑗 ). The utility of a generalized itemset GP in 𝑇𝑗 is determined as 𝑢(GP, 𝑇𝑗 ) = ∑ of a generalized itemset GP in  𝑑∈GP 𝑢(𝑑, 𝑇𝑗 ). The utility ∑ is calculated as 𝑢(GP) = 𝑇𝑗 ∈𝑔(GP) 𝑢(GP, 𝑇𝑗 ), where 𝑔(GP) is defined as 𝑔(GP) = {𝑇𝑗 ∈  ∣ 𝑣 ∈ 𝑇𝑗 ∧ ∀𝑔 ∈ GP ∧ ∃𝑣 ∈ Leaf(𝑔, 𝜏)}. Definition 4. (Cross-level high-utility itemset) [10]. A (generalized) itemset GP is considered a cross-level highutility itemset (CLHUI) if and only if the utility of the itemset GP is greater than or equal to the minimum utility threshold minutil: 𝑢(𝑃 ) ≥ minutil. The transaction utility (TU) of a transaction 𝑇𝑗 is defined as the sum of utilities of all items in 𝑇𝑗 , calculated as TU(𝑇𝑗 ) ∑ = 𝑥∈𝑇𝑗 𝑢(𝑥, 𝑇𝑗 ) [28]. For example, in Fig 2, the leaf items of the generalized item 𝑋 are Leaf({𝑋}, 𝜏) = {𝑎, 𝑏, 𝑐}, and its descendant items are Desc({𝑋}, 𝜏) = {𝑌 , 𝑎, 𝑏, 𝑐}. The level of item 𝑌 is level(𝑌 ) = 2. In Table 1, TU(𝑇8 ) = 𝑢(𝑎, 𝑇8 ) + 𝑢(𝑏, 𝑇8 ) + 𝑢(𝑒, 𝑇8 ) = 5 + 4 + 6 = 15. Assuming minutil = 50, according to the example in Table 1, 𝑢(𝑋, 𝑇5 ) = 𝑢(𝑎, 𝑇5 ) + 𝑢(𝑏, 𝑇5 ) = 1 × 5 + 1 × 1 = 6. 𝑢(𝑋) = 𝑢(𝑋, 𝑇1 ) + 𝑢(𝑋, 𝑇3 ) + 𝑢(𝑋, 𝑇5 ) + 𝑢(𝑋, 𝑇7 ) + 𝑢(𝑋, 𝑇8 ) = 6 + 10 + 22 + 6 + 13 + Page 3 of 17

Cross-level Privacy Preserving Utility Mining Table 2 Cross-level high-utility itemsets.

Itemset {𝑋} {𝑋, 𝑒} {𝑍} {𝑍, 𝑎}

Utility 66 55 69 62

Itemset {𝑋, 𝑍} {𝑋, 𝑑} {𝑍, 𝑌 } {𝑒, 𝑑}

Utility 85 62 70 57

Table 3 Sensitive cross-level high-utility itemsets and their transactions.

SCLHUI {𝑋, 𝑑} {𝑍, 𝑌 } {𝑒, 𝑑}

Transactions 𝑇1 , 𝑇2 , 𝑇3 , 𝑇5 𝑇1 , 𝑇2 , 𝑇3 , 𝑇5 , 𝑇8 𝑇2 , 𝑇3 , 𝑇4 , 𝑇6

Table 4 Sensitive counts, non-sensitive counts, and weights for transactions.

𝑆𝑇 SC NSC Wt

𝑇1 2 4 0.40

𝑇2 3 5 0.50

𝑇3 3 5 0.50

𝑇4 1 1 0.50

𝑇5 2 4 0.40

𝑇6 1 1 0.50

𝑇8 1 5 0.17

9 = 66. Since 𝑢(𝑋) = 66 > 50, 𝑋 is a CLHUI. Let itemset 𝑃 = {𝑍, 𝑏}, 𝑢(𝑃 , 𝑇5 ) = 𝑢(𝑏, 𝑇5 ) + 𝑢(𝑑, 𝑇5 ) = 1 + 3 = 4. 𝑢(𝑃 ) = 𝑢(𝑃 , 𝑇3 ) + 𝑢(𝑃 , 𝑇5 ) + 𝑢(𝑃 , 𝑇8 ) = 11 + 4 + 10 = 25. All CLHUIs are shown in Table 2. Definition 5. (Sensitive and non-sensitive cross-level highutility itemsets). The set of CLHUIs containing private or sensitive information that needs to be hidden is defined as sensitive CLHUIs (SCLHUIs). Let SCLHUIs = {𝑠𝐼1 , 𝑠𝐼2 , ..., 𝑠𝐼𝑚 }, this set represents the SCLHUIs that are hidden in the database. The set of CLHUIs that need to be preserved to ensure the data availability is defined as the non-sensitive CLHUIs (NSCLHUIs). Let NSCLHUIs = {𝑛𝑠𝐼1 , 𝑛𝑠𝐼2 , ..., 𝑛𝑠𝐼𝑘 }, where SCLHUIs ∪ NSCLHUIs = CLHUIs. Definition 6. (Sensitive count, non-sensitive count, and weight for transactions) [5, 18]. A transaction 𝑇𝑗 is a sensitive transaction 𝑆𝑇𝑗 if there exists an SCLHUI 𝑠𝑖 contained in the transaction 𝑇𝑗 , and the set of all sensitive transactions is the sensitive transaction set, denoted as 𝑆𝑇 . The number of SCLHUIs appearing in a transaction 𝑇𝑗 is denoted as SC(𝑇𝑗 ). The number of NSCLHUIs appearing in a transaction 𝑇𝑗 is denoted as NSC(𝑇𝑗 ). The sensitive weight SC(𝑇 )

of 𝑇𝑗 is calculated as follows: Wt(𝑇𝑗 ) = NSC(𝑇 𝑗)+1 . 𝑗

Let SCLHUIs = {{𝑋, 𝑑}, {𝑍, 𝑌 }, {𝑒, 𝑑}}. The transactions in which they appear are shown in Table 3. Therefore, the sensitive transaction 𝑆𝑇 = {𝑇1 , 𝑇2 , 𝑇3 , 𝑇4 , 𝑇5 , 𝑇6 , 𝑇8 }. Since there are {𝑋, 𝑑} and {𝑍, 𝑌 } in 𝑇1 , so SC(𝑇1 ) = 2. Additionally, because {𝑋}, {𝑍}, {𝑍, 𝑎} and {𝑋, 𝑍} are in 𝑇1 so NSC(𝑇1 ) = 2, Wt(𝑇1 ) = 2 / ( 4 + 1 ) = 0.4. SC, NSC, and Wt of 𝑆𝑇 are shown in Table 4. Jiahong Cai et al.: Preprint submitted to Elsevier

There may be no NSCLHUIs in some sensitive transactions; therefore, 1 is added to the denominator during Wt calculation. The higher SC of the transaction can affect more SCLHUIs when processing the transaction, speeding up the algorithm’s efficiency. The lower NSC of the transaction can reduce the impact on NSCLHUIs, minimizing the algorithm’s side effects. By sorting transactions based on their Wt, it is able to prioritize the more suitable transactions as victim transactions [5]. According to Table 4, the sample ordering of 𝑆𝑇 is 𝑇2 ≺ 𝑇3 ≺ 𝑇4 ≺ 𝑇6 ≺ 𝑇1 ≺ 𝑇5 ≺ 𝑇8 . Because generalized items are associated with taxonomy information, hiding them is more complicated than hiding ordinary items. When the utility of an ordinary itemset is reduced by deleting a leaf item from a transaction, that itemset will no longer appear in the transaction once one of its constituent items is removed. In contrast, for a generalized itemset, deleting a leaf item does not necessarily remove the generalized itemset from the transaction, because other leaf items of the same generalized item may still remain. Traditional PPUM algorithms do not distinguish between ordinary items and generalized items, and therefore cannot correctly handle this situation. For example, consider the database in Table 1 and the generalized itemset {𝑋, 𝑑}. If the item 𝑑 is removed from transaction 𝑇1 , then {𝑋, 𝑑} no longer appears in 𝑇1 , and its utility becomes 𝑢({𝑋, 𝑑}) = 𝑢({𝑋, 𝑑}) - 𝑢({𝑋, 𝑑}, 𝑇1 ) = 62 - 5 - 1 - 3 = 53. However, if the item 𝑎 is removed from 𝑇1 , the item 𝑏 still remains in the transaction. Since both 𝑎 and 𝑏 belong to the generalized item 𝑋, the itemset {𝑋, 𝑑} still appears in 𝑇1 , and its utility becomes𝑢({𝑋, 𝑑}) = 𝑢({𝑋, 𝑑}) - 𝑢(𝑎, 𝑇1 ) = 62 - 5 = 57. This difference shows that the hiding mechanism for generalized itemsets cannot be handled in the same way as that for ordinary itemsets. Problem statement: Given a database , a taxonomy 𝜏, a user-specified minimum utility threshold minutil, the set of all cross-level high-utility itemsets CLHUIs, and the set of all sensitive cross-level high-utility itemsets SCLHUIs, the task of the cross-level privacy-preserving utility mining (CLPPUM) is to hide all SCLHUIs in the database  and output the sanitized database ′ . Compared with the traditional PPUM, the key challenge of CLPPUM lies in identifying generalized items that do not explicitly exist in the database and applying reduction or deletion operations on them to achieve the hiding of generalized itemsets. Based on the definition of the CLPPUM, the framework of CLPPUM is illustrated in Fig. 3. The heuristic-based item deletion PPUM algorithm selects victim items and victim transactions related to SCLHUI. By modifying or deleting the victim items in the victim transaction, the algorithm reduces the utility of the SCLHUIs below the minutil. Common evaluation metrics for PPUM algorithms include hiding failure (HF), missing cost (MC), artificial cost (AC), itemset utility similarity (IUS), database utility similarity (DUS), and transaction modification ratio (TMR). Definition 7. (Hiding failure) [22, 42]. Hiding failure is defined as the ratio of SCLHUIs that remain unhidden after database sanitization to the total number of SCLHUIs. Page 4 of 17

Cross-level Privacy Preserving Utility Mining Yes Is transaction sensitive? For each SCLHUI

Sensitive cross-level HUIs

Original database (D)

Select SCLHUIs

Use a taxonomy τ, a minutil, and a CLHUIM algorithm

Sensitive database (D*)

Cross-level PPUM

For each SCLHUI Select victim item Ivic

Reduce or delete Ivic in D*, so that u(SCLHUI)< minutil

Cross-level HUIs Sanitized database (D’)

Figure 3: Algorithmic framework of CLPPUM.

Definition 10. (Similarity measures) [22]. Itemset utility similarity is defined as the sum of the utilities ∑ of all CLHUIs 𝑢(𝑃 ) to the sum of the utilities of CLHUIs: IUS = ∑𝑃 ∈CLHUIs’ 𝑢(𝑃 ) . 𝑃 ∈CLHUIs

It reflects the impact of database sanitization on CLHUIs. Database utility similarity is defined as the ratio of the database utility after sanitization to that before sanitization. It reflects the impact of the ∑sanitization process on the 𝑇 ∈′ 𝑇 𝑈 (𝑇𝑗 )

utility of the database: DUS = ∑ 𝑗

𝑇𝑗 ∈ 𝑇 𝑈 (𝑇𝑗 )

. The transaction

Definition 9. (Artificial cost) [22]. Artificial cost is defined as the ratio of false CLHUIs that are discovered after database sanitization to the total number of CLHUIs. This ratio is calculated by the following formula: AC = |CLHUIs’−CLHUIs| . |CLHUIs’|

modification ratio is defined as the ratio of the number of transactions modified during the database sanitization to the total number of all transactions in the database. It is #modified transactions . calculated as follows: TMR = ||

The relationship between the above three side effects and the CLHUIs is shown in Fig. 4. The upper circle (CLHUIs) and the lower circle (CLHUIs’) represent the sets of CLHUIs mined from the original database and the sanitized database, respectively. The yellow forward-slashed region denotes MC, the red backward-slashed region denotes HF, and the green forward-slashed region denotes AC.

4. Proposed Algorithms

CLHUIs MC

This section presents the proposed CLPPUM framework for hiding sensitive cross-level high-utility itemsets. We first describe the metrics used to evaluate the influence of generalized items on sensitive and non-sensitive itemsets, and then introduce the data structure used to support victim item selection. Based on these components, three algorithms, called Minimum RGISU-first (Min-RF), Maximum RGISU-first (Max-RF), and Best NSC-first (Best-NSCF), are developed. Their privacy-related properties are discussed in Section 4.5.

NSCLHUIs

SCLHUIs HF

AC CLHUIs’

Definition 11. (Sensitive and non-sensitive count of (generalized) items) [26]. Sensitive count SC(𝑔) of a (generalized) item 𝑔 refers to the number of SCLHUIs that contain the (generalized) item 𝑔, its ancestors, or its descendants. A non-sensitive count NSC(𝑔) of a (generalized) item 𝑔 refers to the number of NSCLHUIs that contain the (generalized) item 𝑔, its ancestors, or its descendants.

Figure 4: Relationship of the three side effects to the CLHUIs.

Jiahong Cai et al.: Preprint submitted to Elsevier

Page 5 of 17

Cross-level Privacy Preserving Utility Mining

Definition 12. (Real generalized item sensitive utility) [5]. Let 𝑔 be a sensitive (generalized) item. The real generalized item sensitive utility (RGISU) of 𝑔 is: RGISU(𝑔) = ∑ 𝑔∈𝑇𝑗 ∧𝑇𝑗 ∈𝑆𝑇 ∧𝑣∈Leaf(𝑔,𝜏) 𝑢(𝑣, 𝑇𝑗 ) When hiding sensitive itemsets, modifying different items may lead to substantially different side effects. This is mainly due to the fact that sensitive and non-sensitive itemsets often share common items or co-occur in the same transactions. As a result, the choice of victim item directly determines which itemsets will be affected during the sanitization process. In addition, a considerable number of transactions in the database do not contain any sensitive itemsets, and the utilities of items in such transactions are irrelevant to the hiding process. Therefore, selecting victim items solely based on utility computed over the entire database cannot accurately reflect their actual impact on sensitive and non-sensitive itemsets. To better capture this impact, we adopt RGISU as the primary criterion for victim item selection. Since RGISU is computed only from sensitive transactions, it more effectively reflects the contribution of a (generalized) item to the sensitive itemsets that need to be hidden. As generalized items do not explicitly appear in the database, operations on generalized items are transformed into operations on their corresponding leaf items. In this way, the proposed approach is able to preserve the hierarchical structure while effectively hiding SCLHUIs. According to Table 2 and Table 3, SC(𝑌 ) = 2 and NSC(𝑌 ) = 4. RGISU(𝑌 ) = 𝑢(𝑌 , 𝑇1 ) + 𝑢(𝑌 , 𝑇2 ) + 𝑢(𝑌 , 𝑇3 ) + 𝑢(𝑌 , 𝑇5 ) + 𝑢(𝑌 , 𝑇8 ) = 6 + 10 + 7 + 6 + 9 = 38. SC and NSC are used to select items that appear more frequently in sensitive itemsets and less frequently in non-sensitive itemsets, thereby reducing the impact on non-sensitive itemsets while speeding up the hiding of sensitive itemsets. Since items possess hierarchical information, operations on their descendants or ancestors are likely to impact them. Additionally, this counting method enables lower-level nodes to have higher NSC. This causes the algorithm to select higher-level nodes with fewer leaf nodes as victim items. These nodes generally have fewer leaf nodes, which reduces the number of deletion operations and speeds up the hiding process for generalized items. The RGISU is used to identify the items with the highest or lowest utility in the 𝑆𝑇 . By selecting such an item as the victim item, the algorithm can either accelerate the hiding process or minimize the impact on nonsensitive itemsets. To explain the algorithm more clearly, this section first introduces the proposed GI-dic dictionary structure, followed by a description of the three CLPPUM algorithms: Min-RF, Max-RF, and Best-NSCF.

4.1. Constructing GI-dic dictionary In order to efficiently calculate and use the assessment metrics to select the victim item 𝐼𝑣𝑖𝑐 , this paper constructs a generalized item-dictionary GI-dic, which can effectively reduce the traversal consumption of , SCLHUIs, and NSCLHUIs in the process of calculation. Jiahong Cai et al.: Preprint submitted to Elsevier

Definition 13. (Generalized item-dictionary). Let 𝑔 be a (generalized) item, and GI-dic stores the transactions 𝑇𝑗 in 𝑔 appears, along with the metrics used for selecting victim items. GI-dic takes 𝑔 as the key, and the values are SC, NSC, and RGISU of 𝑔 and the 𝑆𝑇 in which 𝑔 appears (GI-dic[𝐺𝑖 ] = {SC, NSC, RGISU, STs}). Since generalized items do not exist in the database, additional checks are required to identify whether an itemset is present in the current transaction. When computing the SC and NSC of a transaction, it is necessary to traverse and identify all SCLHUIs and NSCLHUIs while traversing the database , resulting in a time complexity of 𝑂(|| ∗ |NSCLHUIs| ∗ |NSCLHUI|). GI-dic enables fast identification of the transactions containing generalized itemsets through XOR operations. This optimization allows the algorithm to traverse the , SCLHUIs, and the NSCLHUIs once when calculating the SC and NSC of a transaction, reducing the time complexity to 𝑂(|NSCLHUIs| ∗ |NSCLHUI| ∗ |NSI |), where NSI denotes the set of transactions in which items of NSCLHUI appear. This optimization can improve the performance of the algorithm by 30-50%. In addition, GI-dic can store various metrics of (generalized) items, assisting in the selection of victim items. Based on the introduction of the above definition, the process of constructing GI-dic dictionary is shown in Algorithm 1. The construction process in Algorithm 1 is as follows. First, GI-dic is initialized for all items (lines 1–4). Next, scan the database once to compute RGISU for the (generalized) item 𝐺𝑖 in the sensitive transaction and record the TID of this transaction into GI-dic (lines 5-15). Specifically, the algorithm first determines whether the current transaction contains any SCLHUI, i.e., whether the transaction is a 𝑆𝑇 (lines 6–7). If so, the algorithm iterates through all (generalized) items appearing in the transaction, computes their RGISU, and records both the RGISU and the TIDs of the 𝑆𝑇 in GI-dic (lines 8–11). After that, the algorithm processes each SCLHUI 𝑆𝑘 in sequence (lines 16–26). It first traverses all (generalized) items 𝐺𝑖 in 𝑆𝑘 to compute their SC, and uses GI-dic to identify all transactions containing 𝑆𝑘 (lines 17–22). For each such transaction 𝑇𝑗 , the corresponding SC is increased (lines 23–25). The algorithm then processes the NSCLHUIs NS𝑘 (lines 27–37). For each NS𝑘 , all (generalized) items 𝐺𝑖 are traversed to compute their NSC, and GIdic is used to locate the transactions in which NS𝑘 appears (lines 28–33). The NSC of these transactions 𝑇𝑗 is then updated accordingly (lines 34–36). Finally, the weight Wt of each transaction is calculated, and all transactions are sorted in descending order of Wt (line 38). A sample GI-dic is shown in Table 5.

4.2. Min-RF algorithm This section introduces the proposed minimum RGISUfirst algorithm (Min-RF). The algorithm selects the (generalized) item 𝐼𝑖 with the smallest RGISU as the victim item, aiming to minimize the impact on NSCLHUIs. The pseudocode of the Min-RF algorithm is shown in Algorithm 2. Page 6 of 17

Cross-level Privacy Preserving Utility Mining

Algorithm 1: GI-dic construction algorithm Input: a quantitative database , a taxonomy 𝜏, sensitive cross-level high-utility itemsets SCLHUIs, non-sensitive cross-level high-utility itemsets NSCLHUIs. Output: generalized item-dictionary GI-dic. 1 GI-dic = ∅; 2 for each (generalized) item 𝐺𝑖 ∈ 𝐴𝐼 do 3 GI-dic[𝐺𝑖 ] = {0, 0, 0, ∅}; 4 end 5 for each transaction 𝑇𝑗 ∈  do 6 for each SCLHUI 𝑆𝑘 ∈ SCLHUIs do 7 if 𝑆𝑘 ⊆ 𝑇𝑗 then 8 for each (generalized) item 𝐺𝑖 ∈ 𝑇𝑗 do 9 GI-dic[𝐺𝑖 ].RGISU += 𝑢(𝐺𝑖 , 𝑇𝑗 ); 10 GI-dic[𝐺𝑖 ].STs.append(j); 11 end 12 break; 13 end 14 end 15 end 16 for each SCLHUI 𝑆𝑘 ∈ SCLHUIs do 17 Ts = GI-dic[𝐺𝑖 ].STs ∧ 𝐺𝑖 ∈ 𝑆𝑘 ; 18 for each (generalized) item 𝐺𝑖 ∈ 𝑆𝑘 do 19 GI-dic[𝐺𝑖 ].sc++; 20 Update the SC of descendants and ancestors of 𝐺𝑖 according to the taxonomy 𝜏; 21 Ts = Ts ∩ GI-dic[𝐺𝑖 ].STs; 22 end 23 for each transaction 𝑇𝑗 ∈ transactions do 24 𝑇𝑗 .sc++; 25 end 26 end 27 for each NSCLHUI NS𝑘 ∈ NSCLHUIs do 28 Ts = GI-dic[𝐺𝑖 ].STs ∧ 𝐺𝑖 ∈ NS𝑘 ; 29 for each (generalized) item 𝐺𝑖 ∈ NS𝑘 do 30 GI-dic[𝐺𝑖 ].nsc++; 31 Update the NSC of descendants and ancestors of 𝐺𝑖 according to the taxonomy 𝜏; 32 Ts = Ts ∩ GI-dic[𝐺𝑖 ].STs; 33 end 34 for each transaction 𝑇𝑗 ∈ transactions do 35 𝑇𝑗 .nsc++; 36 end 37 end 38 Sort transactions 𝑇𝑗 ∈  according to their Wt in descending order, where Wt = 𝑇𝑗 .𝑠𝑐 / (𝑇𝑗 .nsc + 1 ); 39 return generalized item-dictionary GI-dic;

First, the algorithm scans the database once and calculates and stores the utility of generalized items (line 1). Next, it calls GI-dic construction algorithm (Algorithm 1) to calculate various metrics for (generalized) item 𝐺𝑖 and transaction 𝑇𝑗 , and sorts transactions 𝑇𝑗 in descending order by weight (line 2). Then, it iterates over all SCLHUIs, selects the (generalized) item 𝐼𝑖 with the smallest RGISU as the victim item 𝐼𝑣𝑖𝑐 , and sorts all SCLHUIs 𝑆𝑖 in descending order based on the RGISU of its 𝐼𝑣𝑖𝑐 (lines 3–6). Finally, Jiahong Cai et al.: Preprint submitted to Elsevier

Table 5 GI-dic example.

Item 𝑎 𝑏 𝑐 𝑑 𝑒 𝑓 𝑋 𝑌 𝑍

SC 2 2 1 3 2 0 2 2 3

NSC 4 3 3 3 4 0 4 4 4

RGISU 30 8 15 45 24 2 53 38 69

Transactions 𝑇1 , 𝑇2 , 𝑇3 , 𝑇5 , 𝑇8 𝑇1 , 𝑇3 , 𝑇5 , 𝑇8 𝑇3 , 𝑇7 𝑇1 , 𝑇2 , 𝑇3 , 𝑇4 , 𝑇5 , 𝑇6 𝑇2 , 𝑇3 , 𝑇4 , 𝑇6 , 𝑇8 𝑇6 𝑇1 , 𝑇2 , 𝑇3 , 𝑇5 , 𝑇8 𝑇1 , 𝑇2 , 𝑇3 , 𝑇5 , 𝑇8 𝑇1 , 𝑇2 , 𝑇3 , 𝑇4 , 𝑇5 , 𝑇6 , 𝑇8

the algorithm iterates through all SCLHUI 𝑆𝑖 and hides them (lines 7–34). The algorithm first calculates the utility reduction diff required to hide 𝑆𝑖 , then obtains the leaf items 𝐼𝑣𝑖𝑐𝑠 of 𝐼𝑣𝑖𝑐 , and sorts 𝐼𝑣𝑖𝑐𝑠 in descending order based on their RGISU, transforming the processing of the (generalized) items into the processing of their leaf items (lines 8–9). Then, traverse 𝑇𝑗 contains the current SCLHUI 𝑆𝑖 , and processes the victim item 𝐼𝑣𝑖𝑐 in the transaction until diff ≤ 0 and 𝑆𝑖 is successfully hidden (lines 10-33). The algorithm traverses the leaf items. If diff ≥ 𝑢(𝐿𝐼, 𝑇𝑗 ), 𝐿𝐼 is removed from 𝑇𝑗 (lines 15–23). If 𝑢(𝐿𝐼, 𝑇𝑗 ) = 𝑢(𝐼𝑣𝑖𝑐 , 𝑇𝑗 ), it means that deleting 𝐿𝐼 will also remove 𝐼𝑣𝑖𝑐 from 𝑇𝑗 , and 𝑆𝑖 will no longer be in 𝑇𝑗 . In this case, diff reduces the utility of 𝑆𝑖 in 𝑇𝑗 . Otherwise, diff only reduces the utility of 𝐿𝐼 in 𝑇𝑗 (lines 16–20). The algorithm updates the impact of removing 𝐿𝐼 on all SCLHUI 𝑆𝑘 and removes 𝐿𝐼 from 𝑇𝑗 (lines 21–22). If diff ≤ 𝑢(𝐿𝐼, 𝑇𝑗 ), the internal utility of 𝐿𝐼 in 𝑇𝑗 is reduced. The algorithm calculates the required decrease in internal utility (diu), updates the database for all SCLHUI 𝑆𝑘 , setting diff to 0 (lines 24–28). Finally, the algorithm completes the hiding of SCLHUIs and returns the sanitized database ′ (line 35).

4.3. Max-RF algorithm The difference between the maximum RGISU-first algorithm (Max-RF) and Min-RF lies in the selection strategy: Max-RF selects the items with the highest RGISU as victim items, aiming to reduce the number of deletions involving victim items, thereby improving overall runtime efficiency (line 4). In addition, when sorting the leaf items of 𝐼𝑣𝑖𝑐 , the algorithm sorts them in descending order according to RGISU, also to minimize the number of operations and improve efficiency (line 6). The pseudocode of the Max-RF algorithm is shown in Algorithm 3.

4.4. Best-NSCF algorithm The difference between the Best NSC-first algorithm (Best-NSCF) and Min-RF is the selection strategy. BestNSCF aims to select the item that appears most frequently in SCLHUIs and occurs least in NSCLHUIs as the victim item 𝐼𝑣𝑖𝑐 . When no such optimal item exists, the algorithm selects the items with the lowest NSC and lowest RGISU as the victim items to minimize the impact on NSCLHUIs (line Page 7 of 17

Cross-level Privacy Preserving Utility Mining

Algorithm 2: The Min-RF algorithm

Algorithm 3: The Max-RF algorithm

Input: a quantitative database , a taxonomy 𝜏, minimum utility threshold minutil, sensitive cross-level high-utility itemsets SCLHUIs, cross-level high-utility itemsets CLHUIs. Output: A sanitized database ′ . 1 Scan the database  to compute and store the utility of generalized items; 2 Calls GI-dic construction algorithm to compute the SC, NSC, and RGISU of (generalized) items, and to compute the SC, NSC, and Wt of transactions to construct the GI-dic dictionary. 3 for each SCLHUI 𝑆𝑖 ∈ SCLHUIs do 4 𝐼𝑣𝑖𝑐 (𝑆𝑖 ) = 𝐼𝑖 , where 𝐼𝑖 ∈ 𝑆𝑖 ∧ ∀𝐼𝑗 ∈ 𝑆𝑖 , RGISU(𝐼𝑖 ) ≤ RGISU(𝐼𝑗 ); 5 end 6 Sort the SCLHUI 𝑆𝑖 ∈ SCLHUIs in descending order according to the RGISU of 𝐼𝑣𝑖𝑐 (𝑆𝑖 ); 7 for each SCLHUI 𝑆𝑖 ∈ SCLHUIs do 8 diff = 𝑢(𝑆𝑖 ) − minutil + 1; 9 Obtain all leaf items 𝐼𝑣𝑖𝑐𝑠 of 𝐼𝑣𝑖𝑐𝑠 , and sort 𝐼𝑣𝑖𝑐𝑠 in ascending order according to their RGISU; 10 for eachtransaction 𝑇𝑗 ∈  do 11 if diff > 0 ∧ 𝑆𝑖 ⊆ 𝑇𝑗 then 12 𝑇𝑣𝑖𝑐 (𝑆𝑖 ) = 𝑇𝑗 ; 13 for each leaf item 𝐿𝐼 ∈ 𝐼𝑣𝑖𝑐𝑠 do 14 if diff > 0 ∧ 𝐿𝐼 ∈ 𝑇𝑗 then 15 if diff ≥ 𝑢(𝐿𝐼, 𝑇𝑗 ) then 16 if 𝑢(𝐿𝐼, 𝑇𝑗 ) == 𝑢(𝐼𝑣𝑖𝑐 , 𝑇𝑗 ) then 17 diff -= 𝑢(𝑆𝑖 , 𝑇𝑗 ); 18 else 19 diff -= 𝑢(𝐿𝐼, 𝑇𝑗 ); 20 end 21 Update the SCLHUI 𝑆𝑘 ⊆ SCLHUIs, where 𝑆𝑘 ⊆ 𝑇𝑗 ∧ (𝐿𝐼 ∈ 𝑆𝑘 ∨ ∃𝑑 ∈ 𝑆𝑘 ∧ 𝐿𝐼 ∈ Desc(𝑑, 𝜏)); 22 Remove 𝐿𝐼 from 𝑇𝑗 ; 23 else 24 diu = ⌈diff∕𝑒𝑢(𝐼𝑣𝑖𝑐 )⌉; 25 iu(LI, 𝑇𝑗 ) -= diu; 26 Update the SCLHUI 𝑆𝑘 ⊆ SCLHUIs, where 𝑆𝑘 ⊆ 𝑇𝑗 ∧ (𝐿𝐼 ∈ 𝑆𝑘 ∨ ∃𝑑 ∈ 𝑆𝑘 ∧ 𝐿𝐼 ∈ Desc(𝑑, 𝜏)); 27 Update 𝑇𝑗 ; 28 diff = 0; 29 end 30 end 31 end 32 end 33 end 34 end ′ 35 return a sanitized database  ;

Input: a quantitative database , a taxonomy 𝜏, minimum utility threshold minutil, sensitive cross-level high-utility itemsets SCLHUIs, cross-level high-utility itemsets CLHUIs. Output: A sanitized database ′ . 1 Scan the database  to compute and store the utility of generalized items; 2 Calls GI-dic construction algorithm to compute the SC, NSC, and RGISU of (generalized) items, and to compute the SC, NSC, and Wt of transactions to construct the GI-dic dictionary. 3 for each SCLHUI 𝑆𝑖 ∈ SCLHUIs do 4 𝐼𝑣𝑖𝑐 (𝑆𝑖 ) = 𝐼𝑖 , where 𝐼𝑖 ∈ 𝑆𝑖 ∧ ∀𝐼𝑗 ∈ 𝑆𝑖 , RGISU(𝐼𝑖 ) ≥ RGISU(𝐼𝑗 ); 5 end 6 Sort the SCLHUI 𝑆𝑖 ∈ SCLHUIs in descending order according to the RGISU of 𝐼𝑣𝑖𝑐 (𝑆𝑖 ); 7 for each SCLHUI 𝑆𝑖 ∈ SCLHUIs do 8 diff = 𝑢(𝑆𝑖 ) − minutil + 1; 9 Obtain all leaf items 𝐼𝑣𝑖𝑐𝑠 of 𝐼𝑣𝑖𝑐𝑠 , and sort 𝐼𝑣𝑖𝑐𝑠 in descending order according to their RGISU; 10 for each transaction 𝑇𝑗 ∈  do 11 if diff > 0 ∧ 𝑆𝑖 ⊆ 𝑇𝑗 then 12 𝑇𝑣𝑖𝑐 (𝑆𝑖 ) = 𝑇𝑗 ; 13 for each leaf item 𝐿𝐼 ∈ 𝐼𝑣𝑖𝑐𝑠 do 14 if diff > 0 ∧ 𝐿𝐼 ∈ 𝑇𝑗 then 15 if diff ≥ 𝑢(𝐿𝐼, 𝑇𝑗 ) then 16 if 𝑢(𝐿𝐼, 𝑇𝑗 ) == 𝑢(𝐼𝑣𝑖𝑐 , 𝑇𝑗 ) then 17 diff -= 𝑢(𝑆𝑖 , 𝑇𝑗 ); 18 else 19 diff -= 𝑢(𝐿𝐼, 𝑇𝑗 ); 20 end 21 Update the SCLHUI 𝑆𝑘 ⊆ SCLHUIs, where 𝑆𝑘 ⊆ 𝑇𝑗 ∧ (𝐿𝐼 ∈ 𝑆𝑘 ∨ ∃𝑑 ∈ 𝑆𝑘 ∧ 𝐿𝐼 ∈ Desc(𝑑, 𝜏)); 22 Remove 𝐿𝐼 from 𝑇𝑗 ; 23 else 24 diu = ⌈diff∕𝑒𝑢(𝐼𝑣𝑖𝑐 )⌉; 25 iu(LI, 𝑇𝑗 ) -= diu; 26 Update the SCLHUI 𝑆𝑘 ⊆ SCLHUIs, where 𝑆𝑘 ⊆ 𝑇𝑗 ∧ (𝐿𝐼 ∈ 𝑆𝑘 ∨ ∃𝑑 ∈ 𝑆𝑘 ∧ 𝐿𝐼 ∈ Desc(𝑑, 𝜏)); 27 Update 𝑇𝑗 ; 28 diff = 0; 29 end 30 end 31 end 32 end 33 end 34 end ′ 35 return a sanitized database  ;

4). The pseudocode of the Best-NSCF algorithm is shown in Algorithm 4.

4.5. Security analysis

Jiahong Cai et al.: Preprint submitted to Elsevier

This section analyzes the privacy-related properties of the proposed CLPPUM algorithm from two aspects: the hiding of sensitive patterns and the difficulty of inferring Page 8 of 17

Cross-level Privacy Preserving Utility Mining

Algorithm 4: The Best-NSCF algorithm Input: a quantitative database , a taxonomy 𝜏, minimum utility threshold minutil, sensitive cross-level high-utility itemsets SCLHUIs, cross-level high-utility itemsets CLHUIs. Output: A sanitized database ′ . 1 Scan the database  to compute and store the utility of generalized items; 2 Calls GI-dic construction algorithm to compute the SC, NSC, and RGISU of (generalized) items, and to compute the SC, NSC, and Wt of transactions to construct the GI-dic dictionary. 3 for each SCLHUI 𝑆𝑖 ∈ SCLHUIs do 4 𝐼𝑣𝑖𝑐 (𝑆𝑖 ) = 𝐼𝑖 , where 𝐼𝑖 ∈ 𝑆𝑖 ∧ ∀𝐼𝑗 ∈ 𝑆𝑖 , NSC(𝐼𝑖 ) ≤ NSC(𝐼𝑗 ) ∧ SC(𝐼𝑖 ) ≥ SC(𝐼𝑗 ), if no such item exists, then select 𝐼𝑖 ∈ 𝑆𝑖 ∧ ∀𝐼𝑗 ∈ 𝑆𝑖 , NSC(𝐼𝑖 ) ≤ NSC(𝐼𝑗 ) ∧ RGISU(𝐼𝑖 ) ≤ RGISU(𝐼𝑗 ); 5 end 6 Sort the SCLHUI 𝑆𝑖 ∈ SCLHUIs in descending order according to the RGISU of 𝐼𝑣𝑖𝑐 (𝑆𝑖 ); 7 for each SCLHUI 𝑆𝑖 ∈ SCLHUIs do 8 diff = 𝑢(𝑆𝑖 ) − minutil + 1; 9 Obtain all leaf items 𝐼𝑣𝑖𝑐𝑠 of 𝐼𝑣𝑖𝑐𝑠 , and sort 𝐼𝑣𝑖𝑐𝑠 in ascending order according to their RGISU; 10 for each transaction 𝑇𝑗 ∈  do 11 if diff > 0 ∧ 𝑆𝑖 ⊆ 𝑇𝑗 then 12 𝑇𝑣𝑖𝑐 (𝑆𝑖 ) = 𝑇𝑗 ; 13 for each leaf item 𝐿𝐼 ∈ 𝐼𝑣𝑖𝑐𝑠 do 14 if diff > 0 ∧ 𝐿𝐼 ∈ 𝑇𝑗 then 15 if diff ≥ 𝑢(𝐿𝐼, 𝑇𝑗 ) then 16 if 𝑢(𝐿𝐼, 𝑇𝑗 ) == 𝑢(𝐼𝑣𝑖𝑐 , 𝑇𝑗 ) then 17 diff -= 𝑢(𝑆𝑖 , 𝑇𝑗 ); 18 else 19 diff -= 𝑢(𝐿𝐼, 𝑇𝑗 ); 20 end 21 Update the SCLHUI 𝑆𝑘 ⊆ SCLHUIs, where 𝑆𝑘 ⊆ 𝑇𝑗 ∧ (𝐿𝐼 ∈ 𝑆𝑘 ∨ ∃𝑑 ∈ 𝑆𝑘 ∧ 𝐿𝐼 ∈ Desc(𝑑, 𝜏)); 22 Remove 𝐿𝐼 from 𝑇𝑗 ; 23 else 24 diu = ⌈diff∕𝑒𝑢(𝐼𝑣𝑖𝑐 )⌉; 25 iu(LI, 𝑇𝑗 ) -= diu; 26 Update the SCLHUI 𝑆𝑘 ⊆ SCLHUIs, where 𝑆𝑘 ⊆ 𝑇𝑗 ∧ (𝐿𝐼 ∈ 𝑆𝑘 ∨ ∃𝑑 ∈ 𝑆𝑘 ∧ 𝐿𝐼 ∈ Desc(𝑑, 𝜏)); 27 Update 𝑇𝑗 ; 28 diff = 0; 29 end 30 end 31 end 32 end 33 end 34 end ′ 35 return a sanitized database  ;

original information from the sanitized database. We focus

Jiahong Cai et al.: Preprint submitted to Elsevier

on how the proposed modifications affect the observability of SCLHUIs and the inference process based on ′ . Definition 14. (Privacy Preservation Objective). The privacy objective of CLPPUM is defined as follows. In the sanitized database ′ , for any 𝑃 ∈ SCLHUIs, 𝑢(𝑃 , ′ ) < minutil, so that 𝑃 is no longer identified as a CLHUI. Meanwhile, given only the sanitized database ′ , minutil, and the publicly known algorithm, an attacker without access to the original database or additional background knowledge cannot uniquely determine the original sensitive itemsets. Theorem 1. (hiding property). For any 𝑃 ∈ SCLHUIs, CLPPUM reduces its utility in the sanitized database ′ such that 𝑢(𝑃 , ′ ) < minutil. Proof 1. Let 𝑃 be a SCLHUI in the original database , i.e., 𝑢(𝑃 , ) ≥ minutil. During the sanitization process, CLPPUM selects victim items and corresponding transactions, and then performs deletion or utility reduction operations. Each modification decreases the utility of 𝑃 . The process continues until the accumulated utility of 𝑃 falls below the threshold minutil. According to the definition of CLHUI, 𝑃 is no longer identified as a CLHUI in ′ . Moreover, this reduction is achieved through a sequence of modifications rather than a single deterministic change, which further affects how the modification process can be interpreted from the sanitized data. Theorem 2. (utility structure perturbation). The sanitization process alters the original utility relationships among items and transactions, making the relationship between observed modifications and original sensitive itemsets less direct. Proof 2. CLPPUM modifies selected items in victim transactions to reduce the utilities of sensitive itemsets. Since different itemsets may share items or co-occur in the same transactions, modifying a single item can affect multiple itemsets simultaneously. As a result, the mapping between item-level modifications and the affected itemsets is no longer one-to-one. The sanitized database ′ only reflects the final modified utilities, without indicating which sensitive itemset each modification was intended to hide. Therefore, multiple possible original configurations may lead to the same sanitized database ′ , making it difficult to uniquely determine the original sensitive itemsets. Theorem 3. (expansion of candidate inference space). After sanitization, sensitive itemsets are mixed with nonsensitive low-utility itemsets, increasing the number of candidates that need to be considered during inference. Proof 3. After sanitization, for any 𝑃 ∈ SCLHUIs, 𝑢(𝑃 , ′ ) < minutil. Therefore, they are no longer distinguishable from other low-utility itemsets based on the utility threshold. If an attacker attempts to recover hidden patterns by lowering minutil, the number of candidate itemsets increases significantly. In this enlarged candidate set, sensitive itemsets are Page 9 of 17

Cross-level Privacy Preserving Utility Mining Table 6 Characteristics of datasets. Dataset Foodmart Fruithut Chainstore Chess

|| 53,537 181,970 1,112,949 3,196

|𝐼| 1,560 1,265 40,086 75

|𝐺𝐼| 102 43 11,936 30

indistinguishable from many non-sensitive ones. As a result, the attacker examines a much larger set of candidates, which makes accurate identification more difficult in practice. In summary, CLPPUM reduces the utilities of sensitive itemsets so that they are no longer identifiable under the given threshold. The modifications introduce dependencies among itemsets and enlarge the set of potential candidates that could explain the observed data. These factors introduce ambiguity into the relationship between the sanitized database and the original sensitive itemsets. As a result, different original databases may correspond to the same sanitized outcome, which limits the ability to uniquely infer sensitive patterns from ′ without additional information.

5. Performance Evaluation To evaluate the performance of the CLPPUM algorithm, all experiments were conducted using Java on a computer equipped with an AMD Ryzen 9 5900HX processor (8 cores) and 16 GB of RAM. To identify a more effective victim item selection strategy, we conduct a comparative analysis of the three proposed algorithms: Min-RF, Max-RF, and Best-NSCF. Traditional PPUM methods cannot effectively analyze or identify generalized itemsets without introducing additional structures. Therefore, HHUIF and MSICF [42] were selected as baseline methods in our experiments. These two algorithms have relatively simple structures and can be readily extended to support the identification of generalized items. In the experiments, both the minimum utility threshold (minutil) and the number of sensitive itemsets were varied to assess their impact on algorithm performance. Furthermore, the algorithms were evaluated based on seven metrics: runtime, hiding failure (HF), missing cost (MC), artificial cost (AC), itemset utility similarity (IUS), dataset utility similarity (DUS), and transaction modification ratio (TMR).

5.1. Datasets We used four datasets containing the taxonomy 𝜏 to evaluate the performance of the algorithms. Foodmart is available in the FEACP repository on GitHub1 , while the Fruithut, Chainstore, and Chess datasets are obtained from the SPMF2 website. The internal and external utilities of the datasets are generated for the four datasets by taking the 1 Source:https://github.com/nguyenthanhtunghutechsg/ FEACP-Evaluation 2 Source:https://www.philippe-fournier-viger.com/spmf/index.php? link=datasets.php

Jiahong Cai et al.: Preprint submitted to Elsevier

Maxlevel 5 4 10 3

|𝑇MAX | 28 36 170 37

|𝑇AVE | 4.60 3.58 7.20 37.00

Density 0.29% 0.28% 0.02% 49.33%

largest common factor. Detailed dataset information is provided in Table 6. || denotes the number of transactions in the dataset . |𝐼| and |𝐺𝐼| represent the number of primitive and generalized items, respectively. Maxlevel indicates the maximum number of levels in the classification hierarchy. |𝑇MAX | and |𝑇AVE | denote the maximum and average number of items contained in each transaction, respectively. Density refers to the density of the dataset. Foodmart, Fruithut, and Chainstore are sparse datasets. Chainstore contains the most transactions, (generalized) items, and levels. Chess is the smallest but densest dataset; it has the longest average transaction length. On larger datasets, HHUIF and MSICF may fail to produce results [5]. This issue becomes more pronounced in datasets with taxonomy, since the algorithms must handle not only leaf items but also their corresponding generalized items. Therefore, two additional datasets were constructed by extracting the first 5,000 and 10,000 transactions from Foodmart for comparison with the baseline methods. Since all the proposed algorithms are based on item deletion and can successfully hide all SCLHUIs without introducing false CLHUIs, both the HF and AC of the proposed algorithms are zero. Therefore, this paper does not present the comparison results of these two metrics. When the number of sensitive itemsets is fixed, the number of sensitive itemsets for Chess, Foodmart, Foodmart_5000, Foodmart_10000, Fruithut, and Chainstore are: 100, 50, 50, 50, 50, and 2, respectively. When minutil is fixed, the minutil for Chess, Foodmart, Foodmart_5000, Foodmart_10000, Fruithut, and Chainstore are 1,560,000, 580,000, 30,000, 60,000, 3,600,000, and 800,000,000, respectively. Since SCLHUIs typically account for only a small portion of all CLHUIs in real-world scenarios, the proportion of SCLHUIs in the experiments was set to vary between 1% and 10% of the total CLHUIs. All sensitive itemsets were randomly selected.

5.2. Runtime This section evaluates and compares the runtime of the three algorithms. Fig. 5 and Fig. 6 respectively present the runtime of different algorithms when varying minutil and the number of sensitive itemsets. Fig. 5 illustrates the runtime performance of each algorithm under different minutil thresholds. As minutil increases, the runtime of the algorithms decreases. This is because a higher minutil results in a lower utility reduction required to hide SCLHUIs, thereby reducing the number of operations needed. On the five datasets other than Chainstore, the runtimes of Min-RF, Max-RF, and Best-NSCF are Page 10 of 17

Cross-level Privacy Preserving Utility Mining (a) Chess

(b) Foodmart

Min-RF Max-RF Best-NSCF HHUIF MSICF

15 10

Time (s)

15 10 5

0 1.48

0 1.52

1.56

1.6

1.64

minutil (d) Foodmart_10000

1.68 10

4.4

5.8

7.2

8.6

minutil (e) Fruithut

10 10

minutil

14 10

7 10 4

20 10

10 4

minutil (f) Chainstore

Time (s)

2.8

3.6

4.4

5.2

minutil

0 7.5

6 10

8.5

9.5

10 10 8

minutil

Figure 5: Comparison of runtime under different minimum utility thresholds. (a) Chess

10 5

120

8 6

176

244

312

2 20

380

Number of SCLHUIs (d) Foodmart_10000

116

0 20

140

Number of SCLHUIs (e) Fruithut

20 10

4 108

Min-RF Max-RF Best-NSCF HHUIF MSICF

Time (s)

0 40

(b) Foodmart

128

164

200

Number of SCLHUIs (f) Chainstore

50 40

60 40

Time (s)

100

30 20

20 0 20

10 10 56

128

164

200

Number of SCLHUIs

123

Number of SCLHUIs

150

Number of SCLHUIs

Figure 6: Comparison of runtime under different numbers of sensitive itemsets.

very similar. However, on the Chainstore dataset, the MaxRF algorithm, which is designed to improve efficiency, has a longer runtime than the other two algorithms, exceeding them by 56.2% to 130.0%. This is because, in CLPPUM, the algorithm transforms the processing of victim items into the processing of their leaf items. Although Max-RF reduces the number of operations on victim items by selecting those with the highest RGISU, the victim items with the largest RGISU often have a lower level and thus have a larger number of leaf items. This leads to a higher number of actual deletion operations compared to the other two algorithms. Additionally, the Chainstore dataset has the largest taxonomy, causing the runtime of Max-RF to increase significantly. For the smallest and densest dataset, Chess, the baseline method MSICF requires, on average 5 to 7 times more runtime than the proposed algorithms. This is mainly because MSICF needs to scan SC to select victim items and continuously update the SC of items during the hiding process. Moreover, the Jiahong Cai et al.: Preprint submitted to Elsevier

introduction of generalized items further enlarges the search space, which significantly increases the runtime. In contrast, Min-RF, Max-RF, and Best-NSCF benefit from the GI-dic dictionary, which reduces the computational complexity of related measures and thus improves efficiency. On the sparse datasets Foodmart_5000 and Foodmart_10000, the runtimes of HHUIF and MSICF are more than 10 times those of the proposed algorithms. Furthermore, the runtimes of these two baseline methods do not decrease as minutil increases. This is because HHUIF and MSICF must reselect victim items after processing each one, and the presence of generalized items further expands the search space, making their runtime largely dependent on the number of victim item selections. Consequently, their runtimes not only increase substantially but also do not exhibit a consistent decreasing trend with increasing minutil, instead varying according to the selected sensitive cross-level high-utility itemsets. For Foodmart,

Page 11 of 17

Cross-level Privacy Preserving Utility Mining (a) Chess

100

(b) Foodmart

100

MC (%)

80 95

60 Min-RF Max-RF Best-NSCF HHUIF MSICF

40 20

85 1.48

40 1.52

1.56

1.6

1.64

minutil (d) Foodmart_10000

100

1.68

4.4

5.8

10 6

7.2

8.6

100

10 5

minutil (e) Fruithut

7 10 4

minutil (f) Chainstore

MC (%)

60 80

40 6

minutil

14 10

40 30 20

40 4

2.8

3.6

4.4

5.2

minutil

10 7.5

6 10

8.5

9.5

10 10 8

minutil

Figure 7: Comparison of algorithm MC under different minimum utility thresholds. (a) Chess

100

(b) Foodmart

100

MC (%)

100

108

176

244

312

380

Number of SCLHUIs (d) Foodmart_10000

Min-RF Max-RF Best-NSCF HHUIF MSICF

40 40

60 40

100

116

140

Number of SCLHUIs (e) Fruithut

128

164

200

Number of SCLHUIs (f) Chainstore

70 60

80 60 40

MC (%)

100

50 40 30

40 20

20 20

128

164

200

Number of SCLHUIs

10 15

123

150

Number of SCLHUIs

Figure 8: Comparison of algorithm MC under different numbers of sensitive itemsets.

Fruithut, and Chainstore, HHUIF and MSICF fail to produce results within 10 minutes due to scalability limitations. Fig. 6 illustrates the impact of varying the number of sensitive itemsets on the runtime of each algorithm. As the number of sensitive itemsets increases, the runtime of the algorithms increases. Increasing the number of sensitive itemsets requires the algorithms to hide more sensitive itemsets, thereby increasing their runtime. On the Chess dataset, the runtime of MSICF is on average 2–3 times that of MinRF, Max-RF, and Best-NSCF. On the Foodmart and Fruithut datasets, the runtime of MSICF exceeds that of the three proposed algorithms by more than 30 times on average. On the Chainstore dataset, the runtime of Max-RF is 7.6%–92.5% higher than that of Min-RF and Best-NSCF. The differences among the five algorithms and their underlying reasons are largely consistent with those observed in Fig. 5.

Jiahong Cai et al.: Preprint submitted to Elsevier

5.3. Missing cost In this section, we evaluate the MC of the Min-RF, MaxRF, and Best-NSCF algorithms, with the results shown in Fig. 7 and Fig. 8. Due to the overlap between SCLHUIs and NSCLHUIs, algorithms based on item deletion cannot reduce the MC to 0. Fig. 7 shows the impact of changes in minutil on the MC of each algorithm. As shown, the missing cost increases with the rise of the minutil. This is because, as minutil increases, fewer itemsets are discovered by CLHUIM, while the proportion of sensitive itemsets increases, leading to a continuous increase in MC. Across all datasets, the proposed Min-RF and Best-NSCF algorithms achieve the best performance in reducing MC compared with the other methods. Moreover, the MC of these two algorithms are almost identical on sparse datasets. This is mainly because most of the datasets are sparse, making it difficult for BestNSCF to identify the optimal victim item simultaneously Page 12 of 17

Cross-level Privacy Preserving Utility Mining (a) Chess

(b) Foodmart

30 20

0 1.48

1.56

1.6

1.64

minutil (d) Foodmart_10000

1.68

10 3

4.4

5.8

10 6

7.2

8.6

10 5

minutil (e) Fruithut

7 10 4

minutil (f) Chainstore

50 40 30

IUS (%)

50 30

10 1.52

Min-RF Max-RF Best-NSCF HHUIF MSICF

IUS (%)

40 10

40 20

20 10 6

2.8

3.6

10 4

minutil

60 50 40 30 7.5

0 4

4.4

5.2

8.5

10 6

minutil

9.5

10 10 8

minutil

Figure 9: Comparison of IUS under different minimum utility thresholds. (a) Chess

(b) Foodmart

IUS (%)

15 10

108

176

244

312

0 20

380

Number of SCLHUIs (d) Foodmart_10000

116

0 20

140

Number of SCLHUIs (e) Fruithut

128

164

200

Number of SCLHUIs

0 15

128

164

200

Number of SCLHUIs (f) Chainstore

100

IUS (%)

0 20

IUS (%)

0 40

Min-RF Max-RF Best-NSCF HHUIF MSICF

60 40 20

123

Number of SCLHUIs

150

Number of SCLHUIs

Figure 10: Comparison of IUS under different numbers of sensitive itemsets.

with respect to SC and NSC. As a result, Best-NSCF often behaves similarly to Min-RF under these conditions and exhibits comparable performance. On the Foodmart_5000 dataset, the MC of Min-RF is on average 21.0% and 13.8% lower than that of HHUIF and MSICF, respectively. On Foodmart_10000, the reductions are 20.6% and 13.7%. On the Foodmart and Fruithut datasets, the MC of Min-RF is on average 14.81% and 25.7% lower than that of Max-RF, respectively. This advantage comes from the strategy adopted by Min-RF, which selects the item with the smallest RGISU as the victim item. Compared with utility alone, RGISU better reflects the impact of modifying a victim item on other sensitive itemsets. On the Chess dataset, when minutil is reduced to the range of 1,480,000 to 1,560,000, Min-RF achieves a 0.6% to 3.4% lower MC compared to Best-NSCF. This is because Chess is a dense dataset, where Best-NSCF is better able to select victim items that are optimal in terms Jiahong Cai et al.: Preprint submitted to Elsevier

of NSC. However, in CLHUIM, quantity (i.e., SC and NSC) provides less information than utility. Even if a (generalized) item has the fewest NSC and the largest SC, it may still affect a large number of NSCLHUIs due to its numerous leaf items and high utility. Conversely, RGISU reflects not only the utility of a (generalized) item in sensitive transactions but also suggests, when lower, that the item resides at a lower level in the taxonomy and has fewer leaf items. Therefore, selecting the (generalized) items with the lowest RGISU as the victim item can minimize the impact on database utility while accelerating the hiding process. This explains why Min-RF achieves both lower runtime and lower MC in the experiments. Fig. 8 shows the impact of changes in the number of sensitive itemsets on the MC of each algorithm. As the number of sensitive itemsets increases, the MC continues to rise. This is because the increase in SCLHUIs requires the Page 13 of 17

Cross-level Privacy Preserving Utility Mining (a) Chess

100

(b) Foodmart

100

DUS (%)

90 95

80 70

80 Min-RF Max-RF Best-NSCF HHUIF MSICF

60 85 1.48

50 1.52

1.56

1.6

1.64

minutil (d) Foodmart_10000

100

4.4

5.8

10 6

7.2

8.6

80 70

60 6

minutil

14 10

7 10 4

96 94 92

60 4

DUS (%)

minutil (f) Chainstore

100

10 5

minutil (e) Fruithut

100

DUS (%)

40 3

1.68

2.8

3.6

4.4

5.2

minutil

90 7.5

6 10

8.5

9.5

10 10 8

minutil

Figure 11: Comparison of DUS under different minimum utility thresholds. (a) Chess

100

60 40

100

108

176

244

312

380

100

116

140

Number of SCLHUIs (e) Fruithut

128

164

200

Number of SCLHUIs (f) Chainstore

100 98

80 70 60

DUS (%)

60 20

Number of SCLHUIs (d) Foodmart_10000

Min-RF Max-RF Best-NSCF HHUIF MSICF

DUS (%)

100

DUS (%)

(b) Foodmart

100

96 94 92

90 20

128

164

200

Number of SCLHUIs

123

Number of SCLHUIs

150

Number of SCLHUIs

Figure 12: Comparison of DUS under different numbers of sensitive itemsets.

algorithm to conceal more items, thereby leading to higher MC. On the five sparse datasets, the MC values of Min-RF and Best-NSCF are almost identical. On the Chess dataset, when the number of sensitive itemsets varies from 40 to 312, Min-RF achieves an MC that is 0.8%–3.3% lower than that of Best-NSCF. The differences among the five algorithms and the reasons for these differences are essentially the same as those shown in Fig. 7.

5.4. Itemset utility similarity This section presents an evaluation of IUS for the MinRF, Max-RF, and Best-NSCF algorithms, with the results shown in Fig. 9 and Fig. 10. Unlike MC, which focuses on the difference in the number of CLHUIs before and after hiding, IUS focuses on the change in the utility of CLHUIs. These two metrics exhibit an inverse relationship: as the MC increases, the IUS decreases accordingly.

Jiahong Cai et al.: Preprint submitted to Elsevier

Fig. 9 shows the impact of changing minutil on the IUS of each algorithm. As minutil increases, the IUS consistently decreases. This is because a higher minutil results in fewer CLHUIs being discovered, increasing the proportion of sensitive itemsets among them. Consequently, the utility difference between the itemsets before and after sanitization becomes larger. Across all six datasets, Min-RF and BestNSCF achieve the best IUS. On the Chess dataset, when minutil falls within the range of 1,480,000–1,560,000, the IUS of Min-RF is 0.6%–3.4% higher than that of Best-NSCF. The differences in IUS among the five algorithms further support the conclusions drawn from MC: Min-RF and BestNSCF perform best on sparse datasets, while on Chess, MinRF achieves a slightly lower MC than Best-NSCF, leading to a higher IUS. Fig. 10 shows the impact of changes in the number of sensitive itemsets on IUS of each algorithm. As the number of sensitive itemsets increases, the IUS continues Page 14 of 17

Cross-level Privacy Preserving Utility Mining (a) Chess

(b) Foodmart

TMR (%)

Min-RF Max-RF Best-NSCF HHUIF MSICF

60 50

50 40

50 40 30

30 10 1.48

20 1.52

1.56

1.6

1.64

minutil (d) Foodmart_10000

1.68

5.8

10 6

7.2

8.6

10 5

minutil (e) Fruithut

7 10 4

minutil (f) Chainstore

40 30

TMR (%)

4.4

0 4

minutil

14 10

2.8

3.6

4.4

5.2

minutil

0 7.5

6 10

8.5

9.5

10 10 8

minutil

Figure 13: Comparison of TMR under different minimum utility thresholds. (a) Chess

(b) Foodmart

TMR (%)

60 50

50 40

108

176

244

312

380

Number of SCLHUIs (d) Foodmart_10000

40 20 0 20

116

0 20

140

Number of SCLHUIs (e) Fruithut

128

164

200

Number of SCLHUIs

0 15

128

164

200

Number of SCLHUIs (f) Chainstore

Min-RF Max-RF Best-NSCF HHUIF MSICF

TMR (%)

40 20

30 10

10 5 0

123

Number of SCLHUIs

150

Number of SCLHUIs

Figure 14: Comparison of TMR under different numbers of sensitive itemsets.

to decrease. This is because the more sensitive itemsets the algorithm needs to hide, the fewer CLHUIs can be discovered from the sanitized database, resulting in lower IUS. On the sparse datasets, Min-RF and Best-NSCF achieve the best performance in terms of IUS. On the Chess dataset, the difference in IUS between Min-RF and Best-NSCF is similar to the difference observed in their MC values. The differences among the five algorithms and their underlying causes are largely consistent with those observed in Fig. 9.

5.5. Database utility similarity In this section, we evaluated the DUS of the Min-RF, Max-RF, and Best-NSCF algorithms. The results are shown in Fig. 11 and Fig. 12. The results from the two experimental approaches show a high degree of consistency. As minutil increases, the utility of the selected SCLHUIs also increases. These itemsets often contain more generalized items with Jiahong Cai et al.: Preprint submitted to Elsevier

lower levels, which leads to an increase in deletion operations and consequently a decline in DUS. As the number of SCLHUIs increases, the algorithm also needs to delete more itemsets, resulting in a continuous decrease in DUS. Across the six datasets, Min-RF and Best-NSCF achieve the best performance. On the Chess dataset, when minutil is 1,480,000, and the number of sensitive itemsets is 312, although Min-RF achieves better MC and IUS than BestNSCF, the DUS of Best-NSCF is 1.4% and 0.9% higher than that of Min-RF, respectively. This is due to the randomness in selecting SCLHUIs, which means that although Min-RF only seeks the (generalized) items with the smallest RGISU as victim items, in certain cases, this strategy tends to favor generalized items with lower SC, which may require the deletion of more victim items to successfully hide the sensitive itemsets. On dense datasets, Best-NSCF can relatively

Page 15 of 17

Cross-level Privacy Preserving Utility Mining

more easily identify items with optimal SC and NSC. BestNSCF selects the (generalized) items with the smallest NSC values, minimizing their impact on NSCLHUIs, resulting in a higher DUS compared to the Min-RF algorithm.

5.6. Transaction modification ratio Finally, we evaluated the TMR of the Min-RF, Max-RF, and Best-NSCF algorithms, with the results shown in Fig. 13 and Fig. 14. It can be observed that, on all datasets except Chainstore, the TMR of Min-RF, Max-RF, and Best-NSCF remain relatively similar and relatively low. This is because these algorithms process transactions in a fixed order, which reduces scanning overhead and tends to concentrate modifications on transactions that have already been modified. On the Chess dataset when minutil = 1,640,000, and on the Chainstore dataset when the number of sensitive itemsets is 4 or 5, Max-RF achieves a lower TMR than the other two algorithms. This is because Max-RF selects the (generalized) item with the largest RGISU as the victim item. Although Max-RF performs more deletion operations on leaf items than the other two algorithms, it requires fewer operations on the victim items themselves and affects fewer transactions containing those items, resulting in a lower TMR. Among the five algorithms, HHUIF produces the lowest TMR. This is because it selects transactions for modification based on utility, causing the modified transactions to be concentrated among those with higher TU. In contrast, MSICF exhibits a relatively high TMR on the dense Chess dataset. On dense datasets, strong correlations exist among sensitive itemsets, leading to very similar SC values across items. As a result, selecting victim items solely based on SC provides limited guidance. Moreover, since MSICF does not process transactions in a fixed order, it often modifies previously untouched transactions while repeatedly handling victim items, which further increases the TMR.

6. Conclusion Existing PPUM methods often overlook the hierarchical information inherent in real-world data. To address this gap, this paper formulates the novel task of CLPPUM and designs three new algorithms called Min-RF, Max-RF, and BestNSCF to hide SCLHUIs. To effectively evaluate the impact of sanitization operations involving generalized items, key metrics (SC, NSC, and RISU) are extended into the crosslevel context. Additionally, a dedicated GI-dic structure is designed to accelerate metric computation and assist in victim item selection, thereby improving the overall efficiency of the algorithms. Experiments on multiple datasets show that all three proposed algorithms can successfully hide all SCLHUIs without generating false itemsets. Among them, Min-RF demonstrates the best overall performance. However, the proposed method has certain limitations on dense datasets: due to strong correlations among items, the deletion-based strategy affects a large number of nonsensitive itemsets, leading to higher side effects (measured by MC). Therefore, achieving a better balance among mining Jiahong Cai et al.: Preprint submitted to Elsevier

efficiency, privacy preservation, and side-effect minimization remains an unresolved challenge. Future work will focus on developing more flexible victim item selection and database modification strategies to further reduce side effects and improve performance on dense datasets. Promising directions include integrating multi-objective optimization frameworks to explicitly trade off different metrics, as well as exploring parallel or distributed computing paradigms to enhance scalability.

Acknowledgment This research was supported in part by the National Natural Science Foundation of China (No. 62272196), and Guangzhou Basic and Applied Basic Research Foundation (No. 2024A04J9971).

Data Availability Datasets and code are available at https://github.com/

jhcai321/CLPPUM.

CRediT Authorship Contribution Statement Jiahong Cai: Methodology, Writing original draft. Wensheng Gan: Review and editing, Supervision. Philip S. Yu: Review and editing.

References [1] Agrawal, R., Imieliński, T., Swami, A., 1993. Mining association rules between sets of items in large databases, in: The ACM SIGMOD International Conference on Management of Data, pp. 207–216. [2] Agrawal, R., Srikant, R., 2000. Privacy-preserving data mining, in: The ACM SIGMOD International Conference on Management of Data, pp. 439–450. [3] Ahmed, C.F., Tanbeer, S.K., Jeong, B.S., Lee, Y.K., 2009. Efficient tree structures for high utility pattern mining in incremental databases. IEEE Transactions on Knowledge and Data Engineering 21, 1708– 1721. [4] Aljehani, S., Alotaibi, Y., 2025. Preserving privacy in association rule mining using multi-threshold particle swarm optimization. Information Sciences 692, 121673. [5] Ashraf, M., Rady, S., Abdelkader, T., Gharib, T.F., 2023. Efficient privacy preserving algorithms for hiding sensitive high utility itemsets. Computers & Security 132, 103360. [6] Cagliero, L., Chiusano, S., Garza, P., Ricupero, G., 2017. Discovering high-utility itemsets at multiple abstraction levels, in: New Trends in Databases and Information Systems, Springer. pp. 224–234. [7] Chen, C.M., Li, W., Lv, J., Kumari, S., 2025. Rare yet critical: Algorithms for privacy preserving rare itemset mining. Information Sciences , 122572. [8] Cheng, Z., Fang, W., Shen, W., Lin, J.C.W., Yuan, B., 2023. An efficient utility-list based high-utility itemset mining algorithm. Applied Intelligence 53, 6992–7006. [9] Duong, Q.H., Fournier-Viger, P., Ramampiaro, H., Nørvåg, K., Dam, T.L., 2018. Efficient high utility itemset mining using buffered utilitylists. Applied Intelligence 48, 1859–1877. [10] Fournier-Viger, P., Wang, Y., Lin, J.C.W., Luna, J.M., Ventura, S., 2020. Mining cross-level high utility itemsets, in: 33rd International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, Springer. pp. 858–871.

Page 16 of 17

Cross-level Privacy Preserving Utility Mining [11] Fournier-Viger, P., Wu, C.W., Zida, S., Tseng, V.S., 2014. FHM: Faster high-utility itemset mining using estimated utility cooccurrence pruning, in: Foundations of Intelligent Systems: 21st International Symposium, Springer. pp. 83–92. [12] Gan, W., Lin, J.C.W., Chao, H.C., Wang, S.L., Yu, P.S., 2018. Privacy preserving utility mining: a survey, in: IEEE International Conference on Big Data, IEEE. pp. 2617–2626. [13] Gan, W., Lin, J.C.W., Chao, H.C., Zhan, J., 2017. Data mining in distributed environment: a survey. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 7, e1216. [14] Gan, W., Lin, J.C.W., Fournier-Viger, P., Chao, H.C., Tseng, V.S., Yu, P.S., 2021. A survey of utility-oriented pattern mining. IEEE Transactions on Knowledge and Data Engineering 33, 1306–1327. [15] Gan, W., Lin, J.C.W., Fournier-Viger, P., Chao, H.C., Yu, P.S., 2020. HUOPM: High-utility occupancy pattern mining. IEEE Transactions on Cybernetics 50, 1195–1208. [16] Gui, Y., Gan, W., Wu, Y., Yu, P.S., 2024. Privacy preserving rare itemset mining. Information Sciences 662, 120262. [17] Han, M., Liu, S., Gao, Z., Mu, D., Li, A., 2024. Mining topk constrained cross-level high-utility itemsets over data streams. Knowledge and Information Systems 66, 2885–2924. [18] Jangra, S., Toshniwal, D., 2022. Efficient algorithms for victim item selection in privacy-preserving utility mining. Future Generation Computer Systems 128, 219–234. [19] Le, B., Truong, T., Duong, H., Fournier-Viger, P., Fujita, H., 2022. H-FHAUI: Hiding frequent high average utility itemsets. Information Sciences 611, 408–431. [20] Li, S., Mu, N., Le, J., Liao, X., 2019. A novel algorithm for privacy preserving utility mining based on integer linear programming. Engineering Applications of Artificial Intelligence 81, 300–312. [21] Lin, J.C.W., Hong, T.P., Fournier-Viger, P., Liu, Q., Wong, J.W., Zhan, J., 2017. Efficient hiding of confidential high-utility itemsets with minimal side effects. Journal of Experimental & Theoretical Artificial Intelligence 29, 1225–1245. [22] Lin, J.C.W., Wu, T.Y., Fournier-Viger, P., Lin, G., Zhan, J., Voznak, M., 2016. Fast algorithms for hiding sensitive high-utility itemsets in privacy-preserving utility mining. Engineering Applications of Artificial Intelligence 55, 269–284. [23] Lindell, Y., Pinkas, B., 2000. Privacy preserving data mining, in: Annual international cryptology conference, Springer. pp. 36–54. [24] Liu, J., Wang, K., Fung, B.C., 2015. Mining high utility patterns in one phase without generating candidates. IEEE Transactions on Knowledge and Data Engineering 28, 1245–1257. [25] Liu, M., Qu, J., 2012. Mining high utility itemsets without candidate generation, in: The 21st ACM International Conference on Information and Knowledge Management, pp. 55–64. [26] Liu, X., Chen, G., Wen, S., Song, G., 2020. An improved sanitization algorithm in privacy-preserving utility mining. Mathematical Problems in Engineering 2020, 7489045. [27] Liu, X., Xu, F., Lv, X., 2018. A novel approach for hiding sensitive utility and frequent itemsets. Intelligent Data Analysis 22, 1259– 1278. [28] Liu, Y., Liao, W.k., Choudhary, A., 2005. A two-phase algorithm for fast discovery of high utility itemsets, in: Advances in Knowledge Discovery and Data Mining: 9th Pacific-Asia Conference, Springer. pp. 689–695. [29] Nguyen, D., Le, B., 2024. Novel stochastic algorithms for privacypreserving utility mining. Applied Intelligence 54, 12725–12741. [30] Nguyen, D., Tran, M.T., Le, B., 2023. A new algorithm using integer programming relaxation for privacy-preserving in utility mining. Applied Intelligence 53, 25106–25118. [31] Nouioua, M., Wang, Y., Fournier-Viger, P., Lin, J.C.W., Wu, J.M.T., 2020. TKC: Mining top-k cross-level high utility itemsets, in: International Conference on Data Mining Workshops, IEEE. pp. 673– 682. [32] Qu, J.F., Fournier-Viger, P., Liu, M., Hang, B., Hu, C., 2023. Mining high utility itemsets using prefix trees and utility vectors. IEEE Transactions on Knowledge and Data Engineering 35, 10224–10236.

Jiahong Cai et al.: Preprint submitted to Elsevier

[33] Truong, N.T., Tue, N.K., Chinh, N.D., Huynh, L.D., Diep, V.T., Hung, P.D., 2023. Efficient mining of top-k cross-level high utility itemsets, in: International Conference on Future Data and Security Engineering, Springer. pp. 118–131. [34] Tseng, V.S., Shie, B.E., Wu, C.W., Yu, P.S., 2012. Efficient algorithms for mining high utility itemsets from transactional databases. IEEE Transactions on Knowledge and Data Engineering 25, 1772–1786. [35] Tseng, V.S., Wu, C.W., Shie, B.E., Yu, P.S., 2010. UP-Growth: an efficient algorithm for high utility itemset mining, in: The 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 253–262. [36] Tung, N., Nguyen, L.T., Nguyen, T.D., Fourier-Viger, P., Nguyen, N.T., Vo, B., 2022. Efficient mining of cross-level high-utility itemsets in taxonomy quantitative databases. Information Sciences 587, 41– 62. [37] Tung, N., Nguyen, T.D., Nguyen, L.T., Vu, D.L., Fournier-Viger, P., Vo, B., 2025. Mining cross-level high utility itemsets in unstable and negative profit databases. IEEE Transactions on Knowledge and Data Engineering 37, 5420–5435. [38] Wu, J.M.T., Srivastava, G., Jolfaei, A., Fournier-Viger, P., Lin, J.C.W., 2021. Hiding sensitive information in ehealth datasets. Future Generation Computer Systems 117, 169–180. [39] Wu, P., Niu, X., Fournier-Viger, P., Huang, C., Wang, B., 2022. UBPMiner: An efficient bit-based high utility itemset mining algorithm. Knowledge-Based Systems 248, 108865. [40] Yan, Y., Niu, X., Zhang, Z., Fournier-Viger, P., Ye, L., Min, F., 2024. Efficient high utility itemset mining without the join operation. Information Sciences 681, 121218. [41] Yao, H., Hamilton, H.J., Butz, C.J., 2004. A foundational approach to mining itemset utilities from databases, in: The SIAM International Conference on Data Mining, SIAM. pp. 482–486. [42] Yeh, J.S., Hsu, P.C., 2010. HHUIF and MSICF: Novel algorithms for privacy preserving utility mining. Expert Systems with Applications 37, 4779–4786. [43] Yin, C., Li, Y., 2023. Fast privacy-preserving utility mining algorithm based on utility-list dictionary. Applied Intelligence 53, 29363– 29377. [44] Yun, U., Kim, J., 2015. A fast perturbation algorithm using tree structure for privacy preserving utility mining. Expert Systems with Applications 42, 1149–1165. [45] Zhou, Q., Gan, W., Qi, Z., Yu, P.S., 2025. Utility-based privacypreserving data mining. IEEE Internet of Things Journal 13, 2067– 2084. [46] Zida, S., Fournier-Viger, P., Lin, J.C.W., Wu, C.W., Tseng, V.S., 2017. Efim: a fast and memory efficient algorithm for high-utility itemset mining. Knowledge and Information Systems 51, 595–625.

Page 17 of 17

Cross-level Privacy Preserving Utility Mining

Related documents