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.

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.

Maximizing Range Sum (MaxRS) query is a basic operation in computational geometry and database communities. Given a set of weighted objects in 2-dimensional space and a rectangle, MaxRS query aims to find an optimal position of the rectangle to maximize the total weight of covered objects (i.e., Range Sum). All the existing literature for MaxRS query commonly assumes that every object is associated with a unique point. In real applications, however, every object (e.g., GPS-enabled moving vehicle) is related to a trajectory including a sequence of points, which goes beyond this restrictive assumption. How to tackle the problem of MaxRS query in trajectory data (MaxRST) is important and challenging. In this paper, we propose the definition of MaxRST query where a trajectory is covered by a rectangle if at least one of points in the trajectory is enclosed by the rectangle. We propose a novel method to solve MaxRST query by converting it to rectilinear polygon intersection problem. Then, an interval-tree-based partitioning technique is developed to efficiently settle rectilinear polygon intersection problem. To further shorten the response time, we present ($\epsilon, \delta$) -approximate MaxRST query, which returns an approximate answer having the relative error$\epsilon$to the optimal covered weight with probability at least$\delta$. Furthermore, two complementary sampling-based ($\epsilon, \delta$) -approximate MaxRST algorithms are proposed. One performs random sampling with replacements on rectilinear polygons and the sample size is irrelevant to the number of trajectories. The other employs grid shifting technique to reduce sample size yet requires an extra cost for grid construction. The theoretical analysis and experimental results show that our proposed algorithms have high performance in terms of efficiency and accuracy.

Abstract Incomplete skyline query is an important operation to filter out pareto-optimal tuples on incomplete data. It is harder than skyline due to intransitivity and cyclic dominance. It is analyzed that the existing algorithms cannot process incomplete skyline on massive data efficiently. This paper proposes a novel table-scan-based TSI algorithm to deal with incomplete skyline on massive data with high efficiency. TSI algorithm solves the issues of intransitivity and cyclic dominance by two separate stages. In stage 1, TSI computes the candidates by a sequential scan on the table. The tuples dominated by others are discarded directly in stage 1. In stage 2, TSI refines the candidates by another sequential scan. The pruning operation is devised in this paper to reduce the execution cost of TSI. By the assistant structures, TSI can skip majority of the tuples in phase 1 without retrieving it actually. The extensive experimental results, which are conducted on synthetic and real-life data sets, show that TSI can compute skyline on massive incomplete data efficiently.

The skyline query is important in the database community. In recent years, the researches on incomplete data have been increasingly considered, especially for the skyline query. However, the existing skyline definition on incomplete data cannot provide users with valuable references. In this paper, we propose a novel skyline definition utilizing probabilistic model on incomplete data where each point has a probability to be in the skyline. In particular, it returns K points with the highest skyline probabilities. In addition, we propose incomplete models and estimate probability density functions of missing values on independent, correlated, and anti-correlated distributions, respectively. Meanwhile, it is a big challenge to compute probabilistic skyline on incomplete data. We propose three efficient algorithms SPISkyline, SPCSkyline, and SPASkyline for probabilistic skyline computation on incomplete data complying with independent, correlated, and anti-correlated distributions, respectively. They employ pruning strategy, optimization of the process of probability computation, and sorting technique to improve the efficiency of probabilistic skyline computation on incomplete data. Our experimental results demonstrate that our proposed concept of probabilistic skyline is an effective method to tackle skyline query on incomplete data and our algorithms are tens of times faster than the naive algorithm on both synthetic and real datasets.

Top-k dominating query is an important operation to return a set of interesting points from a potentially huge data space. For any tuple, its domination score is defined as the number of tuples dominated by the tuple. Top-k dominating query returns the k tuples with the highest domination scores. This paper proposes a novel table-scan-based TDTS algorithm to compute the top-k dominating results on massive data efficiently. TDTS presorts table T to generate PT, whose tuples are arranged in the order of round-robin retrieval on the sorted lists. TDTS performs sequential scan on PT to obtain query results. It is proved that TDTS has the characteristic of early termination. This paper devises efficient pruning operation to reduce the number of candidate tuples and the number of assistant tuples significantly. The experimental results show that, TDTS has a markedly superior performance compared with the existing algorithms.

The skyline query is important in database community. In recent years, the researches on incomplete data have been increasingly considered, especially for the skyline query. However, the existing skyline definition on incomplete data cannot provide users with valuable references. In this paper, we propose a novel skyline definition utilizing probabilistic model on incomplete data where each point has a probability to be in the skyline. In particular, it returnsK points with the highest skyline probabilities. Meanwhile, it is a big challenge to compute probabilistic skyline on incomplete data. We propose an efficient algorithm PISkyline, which utilizes two pruning strategies to reduce the number of points and adopts two optimizations to accelerate probability computation for each point. Nevertheless, PISkyline is susceptible to the order of input data and there is still a great deal of room for optimization. We develop a point-level sorting technique by adjusting the order of accessing points to further improve the efficiency of PISkyline. Our experimental results demonstrate that our algorithms are tens of times faster than the naive algorithm on both synthetic and real datasets.

In many applications, top-k dominating query is an important operation to return k tuples with the highest domination scores in a potentially huge data space. It is analyzed that the existing algorithms have their performance problems when performed on massive data. This paper proposes a novel table-scan-based TDTS algorithm to efficiently compute top-k dominating results. TDTS first presorts the table for early termination. The early termination checking is proposed in this paper, along with the theoretical analysis of scan depth. The pruning operation for tuples is devised in this paper. The theoretical pruning effect shows that the number of tuples maintained in TDTS can be reduced substantially. The extensive experimental results, conducted on synthetic and real-life data sets, show that TDTS outperforms the existing algorithms significantly.

Top-k query is an important operation to return a set of interesting points from a potentially huge data space. In top-k query, a ranking function is provided to determine the score of each tuple and k tuples with the largest scores are returned.

In many applications, top-k query is an important operation to return a set of interesting points in a potentially huge data space. It is analyzed in this paper that the existing algorithms cannot process top-k query on massive data efficiently. This paper proposes a novel table-scan-based T2S algorithm to efficiently compute top-k results on massive data. T2S first constructs the presorted table, whose tuples are arranged in the order of the round-robin retrieval on the sorted lists. T2S maintains only fixed number of tuples to compute results. The early termination checking for T2S is presented in this paper, along with the analysis of scan depth. The selective retrieval is devised to skip the tuples in the presorted table which are not top-k results. The theoretical analysis proves that selective retrieval can reduce the number of the retrieved tuples significantly. The construction and incremental-update/batchprocessing methods for the used structures are proposed in this paper. The extensive experimental results, conducted on synthetic and real-life data sets, show that T2S has a significant advantage over the existing algorithms.

Skyline is an important operation in many applications to return a set of interesting points from a potentially huge data space. Given a table, the operation finds all tuples that are not dominated by any other tuples. It is found that the existing algorithms cannot process skyline on big data efficiently. This paper presents a novel skyline algorithm SSPL on big data. SSPL utilizes sorted positional index lists which require low space overhead to reduce I/O cost significantly. The sorted positional index list Ljis constructed for each attribute Ajand is arranged in ascending order of Aj. SSPL consists of two phases. In phase 1, SSPL computes scan depth of the involved sorted positional index lists. During retrieving the lists in a round-robin fashion, SSPL performs pruning on any candidate positional index to discard the candidate whose corresponding tuple is not skyline result. Phase 1 ends when there is a candidate positional index seen in all of the involved lists. In phase 2, SSPL exploits the obtained candidate positional indexes to get skyline results by a selective and sequential scan on the table. The experimental results on synthetic and real data sets show that SSPL has a significant advantage over the existing skyline algorithms.