Abstract

Placement of items on the shelf space of retail stores significantly impacts the revenue of the retailer. Since customers typically tend to buy sets of items (i.e., itemsets) together, several research efforts have been undertaken towards facilitating itemset placement in retail stores for improving retailer revenue. However, they fail to consider that the time-period of expiry can vary across items i.e., some items expire sooner than others. This leads to loss of opportunity towards improving retailer revenue. Hence, we propose PEAR, which is a Product Expiry-Aware and Revenue-conscious itemset placement scheme for improving retailer revenue. Our key contributions are three-fold. First, we introduce the problem of addressing retail itemset placement when the items can be associated with different time-periods of expiry. Second, we propose the expiry-aware PEAR scheme for efficiently identifying and placing high …

Abstract

While the problems of fnding the shortest path and k-shortest paths have been extensively researched, the research community has been shifting its focus towards discovering and identifying paths based on user preferences. Since users naturally follow some of the paths more than other paths, the popularity of a given path often refects such user preferences. Given a set of user traversals in a road network and a set of paths between a given source and destination pair, we address the problem of performing top-k ranking of the paths in that set based on path popularity. In this paper, we introduce a new model for computing the popularity scores of paths. Our main contributions are threefold. First, we propose a framework for modeling user traversals in a road network as transactions. Second, we present an approach for efciently computing the popularity score of any path based on the itemsets extracted from the transactions using pattern mining techniques. Third, we conducted an extensive performance evaluation with two real datasets to demonstrate the efectiveness of the proposed scheme.

Abstract

Time series classification is an important model in data mining. It involves assigning a class label to a test instance based on the training data with known class labels. Most previous studies developed time series classifiers by disregarding the fuzzy nature of events (i.e., events with similar values may belong to different classes) within the data. Consequently, these studies suffered from performance issues, including decreased accuracy and increased memory, runtime, and energy requirements. With this motivation, this paper proposes a novel fuzzy nearest neighbor classifier for time series data. The basic idea of our classifier is to transform the very large training data into a relatively small representative training data and use it to label a test instance by employing a new fuzzy distance measure known as Ravi. Experimental results on real world benchmark datasets demonstrate that the proposed classifier …

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.

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

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

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

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

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

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.