Abstract

Pattern mining is an important task of data mining and involves the extraction of interesting associations from large transactional databases. Typically, a given transactional database D gets updated due to the addition and deletion of transactions. Consequently, some of the previously discovered patterns may become invalid, while some new patterns may emerge. This has motivated significant research efforts in the area of incremental mining. The goal of incremental mining is to efficiently mine patterns when D gets updated with additions and/or deletions of transactions as opposed to mining all of the patterns from scratch. Incidentally, active research efforts are being made to develop incremental pattern mining algorithms for extracting frequent patterns, sequential patterns and utility patterns. Another important type of pattern is the coverage pattern (CP), which has significant applications in areas such as banner advertising, search engine advertising and visibility mining. However, none of the existing works address the issue of incremental mining for extracting CPs. In this regard, the main contributions of this work are twofold. First, we introduce the problem of incremental mining of CPs. Second, we propose an approach, designated as Comprehensive Coverage Pattern Mining, for efficiently extracting CPs under the incremental paradigm. We have also performed extensive experiments using two real click-stream datasets and one synthetic dataset to demonstrate the overall effectiveness of our proposed approach.

Abstract

Billboard advertisement is one of the dominant modes of traditional outdoor advertisements. Given a set of billboards, there is an opportunity to improve the revenue of the billboard operator by satisfying the advertising demands of an increased number of clients by exploiting the user trajectory data. Our main contributions are three-fold. First, we introduce the problem of billboard advertisement allocation for improving the billboard operator revenue. Second, we propose an efficient user trajectory-based transactional framework using coverage pattern mining for addressing the billboard advertisement allocation problem. Third, we conduct a performance study with a real dataset to show the effectiveness of the proposed framework.

Abstract

Placement of items on the shelf space of retail stores significantly impacts the revenue of the retailer. Given the prevalence and popularity of medium-to-large-size retail stores, several research efforts have been made towards facilitating item/itemset placement in retail stores for improving retailer revenue. However, they do not consider the issue of urgency of sale of individual items. Hence, they cannot efficiently index, retrieve and place high-revenue itemsets in retail store slots in an urgency-aware manner. Our key contributions are two-fold. First, we introduce the notion of urgency for retail itemset placement. Second, we propose the urgency-aware URI index for efficiently retrieving high-revenue and urgent itemsets of different sizes. We discuss the URIP itemset placement scheme, which exploits URI for improving retailer revenue. We also conduct a performance evaluation with two real datasets to demonstrate that URIP is indeed effective in improving retailer revenue w.r.t. existing schemes.

Abstract

Mining of coverage patterns from transactional databases is one of the data mining tasks. It has applications in banner advertising, search engine advertising and visibility computation. In general, most real-world transactional databases are typically large. Mining of coverage patterns from large transactional databases such as query log transactions on a single computer is challenging and time-consuming. In this paper, we propose Distributed Coverage Pattern Mining (DCPM) approach. In this approach, we employ a notion of the summarized form of Inverse Transactional Database (ITD) and replicate it at every node. We also employ an efficient clustering-based method to distribute the computational load of extracting coverage patterns among the Worker nodes. We performed extensive experiments using two real-world datasets and one synthetic dataset. The results show that the proposed approach significantly improves the performance over the state-of-the-art approaches in terms of execution time and data shuffled.

Abstract

Facilitating the discovery of drugs by combining diverse compounds is becoming prevalent, especially for treating complex diseases like cancers and HIV. A drug is a chemi- cal compound structure and any sub-structure of a chemical compound is designated as a fragment. A chemical compound or a fragment can be modeled as a graph structure. Given a set of chemical compounds and their corresponding large set of fragments modeled as graph structures, we address the problem of identifying potential combinations of diverse chemical compounds, which cover a certain percentage of the set of fragments. In this regard, the key contributions of this work are three-fold: First, we introduce the notion of Graph Transactional Coverage Patterns (GTCPs) for any given graph transactional dataset. Second, we propose an efficient model and framework for extracting GTCPs from a given graph transactional dataset. Third, we conduct an extensive performance study using three real datasets to demonstrate that it is indeed feasible to efficiently extract GTCPs using our proposed GTCP-extraction framework. We also demonstrate the effectiveness of the GTCP-extraction framework through a case study in computer-aided drug design. Index Terms—Graph mining, Graph transactions, Coverage patterns, Drug discovery

Abstract

High utility itemset mining is an important model in data mining. It involves discovering all itemsets in a quantitative transactional database that satisfy a user-specified minimum utility (minUtil) constraint. MinUtil controls the minimum value that an itemset must maintain in a database. Since the model evaluates an itemset’s interestingness using only the minUtil constraint, it implicitly assumes that all items in the database have similar utility values. However, some items have high utility, while others may have relatively low utility in a database. If minUtil is set too high, the user will miss all itemsets containing low utility items. To find itemsets that involve both high and low utility items, minUtil has to be set very low. However, this may cause a combinatorial explosion as the items with high utility may combine with others in all possible ways. This dilemma is called the low utility item problem. This paper proposes a flexible …

Abstract

Spatial High Utility Itemset Mining (SHUIM) is an important knowledge discovery technique with many real-world applications. It involves discovering all itemsets that satisfy the user-specified m inimum u tility (minUtil) i n a q uantitative spatiotemporal database. The popular adoption and the successful industrial application of this technique have been hindered by the following two limitations: (i) Since the rationale of SHUIM is to find all itemsets that satisfy the minUtil constraint, it often produces too many patterns, most of which may be redundant or uninteresting to the user. (ii) Specifying a right minUtil value is an open research problem in SHUIM. This paper tackles these two problems by proposing a novel model of top-k spatial high utility itemsets that may exist in a database. A new constraint, called dynamic minimum utility (dMinUtil), was explored to reduce the search space effectively. This constraint is based on …

Abstract

Facilitating the discovery of drugs by combining diverse compounds is becoming prevalent, especially for treating complex diseases like cancers and HIV. A drug is a chemical compound structure and any sub-structure of a chemical compound is designated as a fragment. A chemical compound or a fragment can be modeled as a graph structure. Given a set of chemical compounds and their corresponding large set of fragments modeled as graph structures, we address the problem of identifying potential combinations of diverse chemical compounds, which cover a certain percentage of the set of fragments. In this regard, the key contributions of this work are three-fold: First, we introduce the notion of Graph Transactional Coverage Patterns (GTCPs) for any given graph transactional dataset. Second, we propose an efficient model and framework for extracting GTCPs from a given graph transactional dataset. Third, we conduct an extensive performance study using three real datasets to demonstrate that it is indeed feasible to efficiently extract GTCPs using our proposed GTCP-extraction framework. We also demonstrate the effectiveness of the GTCP-extraction framework through a case study in computer-aided drug design. Index Terms—Graph mining, Graph transactions, Coverage patterns, Drug discovery

Abstract

Pattern mining from graph transactional data (GTD) is an active area of research with applications in the domains of bioinformatics, chemical informatics and social networks. Existing works address the problem of mining frequent subgraphs from GTD. However, the knowledge concerning the coverage aspect of a set of subgraphs is also valuable for improving the performance of several applications. In this regard, we introduce the notion of subgraph coverage patterns (SCPs). Given a GTD, a subgraph coverage pattern is a set of subgraphs subject to relative frequency, coverage and overlap constraints provided by the user. We propose the Subgraph ID-based Flat Transactional (SIFT) framework for the efficient extraction of SCPs from a given GTD. Our performance evaluation using three real datasets demonstrates that our proposed SIFT framework is indeed capable of efficiently extracting SCPs from GTD. Furthermore, we demonstrate the effectiveness of SIFT through a case study in computer-aided drug design.

Abstract

Location-based services (LBS), which provide personalized and timely information, entail privacy concerns such as unwanted leak of current user locations to potential stalkers. Existing works have proposed dummy generation techniques by creating a cloaking region (CR) such that the user’s location is at a fixed distance from the center of CR. Hence, if the adversary somehow knows the location of the center of CR, the user’s location would be vulnerable to attack. We propose an improved dummy generation approach for facilitating improved location privacy for mobile users. Our performance study demonstrates that our proposed approach is indeed effective in improving user location privacy.