Itemset mining is a crucial technology for extracting interesting patterns that meet predefined thresholds from transaction databases, such as frequent itemset mining (FIM) and high-utility itemset mining (HUIM). Despite their significance, few studies have explored the simultaneous consideration of both support and utility. This gap arises from the theoretical complexity of integrating these dimensions and the practical difficulty of setting appropriate thresholds for both. To overcome this limitation, we introduce Skyline frequent-utility itemset mining (SFUIM), a method that examines frequent and high-utility itemsets without requiring predefined thresholds. Nevertheless, SFUIM faces significant challenges due to its expansive search space and intensive computational requirements. In this paper, we propose a PSI algorithm and its enhanced version PSI*, which confines calculations to specific partitions by prefix-based partitioning. Experiments demonstrate that PSI*outperforms state-of-the-art methods, especially on large-scale datasets.

Abstract In many practical applications, skyline query is an important operation to return the pareto optimal tuples, which provides a candidate set for the optimum. On massive data, skyline often reports too many results, the users will be overwhelmed and be difficult to find the desired information easily. This paper devises P-skyline to reduce the size of the returned results. Given the approximation factor, P-skyline only generates the prominent skyline results by the definition of p-dominance. To the best of our knowledge, this paper is the first work to study P-skyline problem. This paper first proposes a baseline algorithm, which requires one full table scan to compute the results. It is found that baseline algorithm incurs a relatively high execution cost on massive data. Then, PSTP algorithm is proposed, which consists of two stages: candidate acquisition and refinement. On the presorted table, PSTP utilizes selective retrieval and selective checking to process P-skyline with much lower I/O cost and computation cost. The extensive experimental results, conducted on synthetic and real-life data sets, show that PSTP can compute P-skyline on massive data efficiently.

Computing strongly connected components (SCC) is a key operation for many applications on directed graphs. Specifically, a SCC of a directed graph$G$is one of its maximal subgraphs, in which any two nodes are reachable to each other.

Functional dependencies (FDs) are the most common constraints in the design theory for relational databases, generalizing the concept of a key for a relation. Given an attribute subset$X$and an attribute$A$in relation schema, a functional dependency (FD)$X\rightarrow A$means that the value of$A$is uniquely determined by the values of$X$. An FD$X\rightarrow A$is minimal if$A$is not determined by any proper subset of$X$, and is nontrivial if$A$is not contained in$X$The FD discovery problem is to determine all minimal nontrivial functional dependencies over a given relation instance.

Abstract Top-k frequent itemset mining (top-k FIM) plays an important role in many practical applications. It reports the k itemsets with the highest supports. Rather than the subtle minimum support threshold specified in FIM, top-k FIM only needs the more understandable parameter of the result number. The existing algorithms require at least two passes of scan on the table, and incur high execution cost on massive data. This paper develops a prefix-partitioning-based PTF algorithm to mine top-k frequent itemsets efficiently, where each prefix-based partition keeps the transactions sharing the same prefix item. PTF can skip most of the partitions directly which cannot generate any top-k frequent itemsets. Vertical mining is developed to process the partitions of vertical representation with the high-support-first principle, and only a small fraction of the items are involved in the processing of the partitions. Two improvements are proposed to reduce execution cost further. Hybrid vertical storage mode maintains the prefix-based partitions adaptively and the candidate pruning reduces the number of the explored candidates. The extensive experimental results show that, on massive data, PTF can achieve up to 1348.53 times speedup ratio and involve up to 355.31 times less I/O cost compared with the state-of-the-art algorithms.

Frequent itemset mining (FIM) and high-utility itemset mining (HUIM) are two important branches of itemset mining which is a key technology of knowledge discovery in many applications. Nowadays, there have been extensive algorithms on FIM and HUIM, but few studies consider frequency and utility together, so skyline frequent-utility itemset mining (SFUIM) is proposed to find useful itemsets with both frequency and utility measurements. Nevertheless, SFUIM is more challenging than FIM and HUIM since the search space is large and the calculation cost is expensive without any threshold, especially on large-scale databases. To address it, this paper proposes a novel prefix-based algorithm PSI* to mine skyline frequent-utility itemsets on massive data. PSI* divides the huge database by prefix-based partitioning, so that the calculation of itemsets with a specific prefix-item only involves a partition instead of the database. A multilevel-index based list is presented to compactly maintain the maximal utility under the frequency constraint, and a novel grid-based structure is devised to organize partitions or items by a designed order. Moreover, four efficient pruning strategies are proposed to prune itemsets as early as possible. Substantial experiments show that the PSI* algorithm has better performance than the state-of-the-art algorithms, obviously on large-scale databases.

Functional dependencies are the most common constraints in the design theory for relational databases, which have very important practical applications in many areas. Different kinds of algorithms are proposed to discover the functional dependencies. However, it is found in this paper that the existing algorithms cannot deal well with massive data which cannot be held entirely in memory due to high memory consumption and high computation cost. In this paper, a novel algorithm FSC is presented to compute functional dependencies on massive data. The two-step execution of FSC relies on a pre-computed update-friendly assistant structure of comparable pairs which reflect the identifier pairs for tuples with at least one equal attribute. In step 1, FSC determines the violated functional dependencies and introduces the selective comparison by comparable pairs to reduce the required pairwise comparison significantly. The direct value-combination compression strategy is devised to process attributes of small cardinality. In step 2, FSC induces the required functional dependencies by the results in step 1. The extensive experimental results, conducted on synthetic and real-life data sets, show that FSC can discover functional dependencies on massive data efficiently.

Since knowledge graphs (KGs) describe and model the relationships between entities and concepts in the real world, reasoning on KGs often corresponds to the r eachability queries with l abel and s ubstructure c onstraints (LSCR queries). Specifically, for a search path p , LSCR queries not only require that the labels of the edges passed by p are in a label set, but also claim that a vertex in p could satisfy a substructure constraint.

In literature, many algorithms are proposed to find strongly connected components (SCC) for directed graphs. Specifically, a SCC of a directed graph$G$is one of its maximal subgraphs, in which any two nodes are reachable to each other. Existing in-memory algorithms are efficient, and can find all the SCCs of$G$in a linear time, with respect to the size of$G$. Nevertheless, as the sizes of graphs grow rapidly in real applications, current efforts have been focused on semi-external algorithms. Existing semi-external algorithms maintain an in-memory sketch$\mathcal {A}$of$G$, and gradually restructure$\mathcal {A}$with their in-memory processes (IMP) until all the SCCs can be computed based on$\mathcal {A}$. However, the I/O and CPU costs of existing algorithms are still high when$G$is relatively large. Thus, this paper proposes a new semi-external algorithmEP-SCCwith a novel IMPEP-Reductionfor finding all the SCCs of$G$efficiently. Extensive experiments are conducted on both synthetic and real graphs, in which WDC-2014 contains 1.7 billion nodes, and eu-2015 has over 91 billion edges. Experimental results confirm that EP-SCC significantly outperforms existing semi-external SCC algorithms.

Since knowledge graphs (KGs) describe and model the relationships between entities and concepts in the real world, reasoning on KGs often correspond to the reachability queries with label and substructure constraints (LSCR queries). Specifically, for a search path p, LSCR queries not only require that the labels of the edges passed by p are in a certain label set, but also claim that a vertex in p could satisfy a certain substructure constraint. They are much more complex than existing label-constraint reachability (LCR) queries. LSCR queries on KGs can be addressed by two natural ways (EA-1) an online search algorithm and (EA-2) a combined search strategy, to the best of our knowledge. This paper presents two optimized algorithms for EA-1 and EA-2, but the optimized algorithms are still inefficient, since their efficiencies are highly dominated by their search directions as analyzed in this paper. Motivated by that, this paper presents an efficient informed search strategy on KGs, named INSK, with a lightweight index, named local index. An extensive experimental evaluation, on both synthetic and real KGs, illustrates that our INSK can efficiently process LSCR queries on KGs.