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.

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

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

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

Retailer revenue is significantly impacted by item placement in retail stores. Notably, placement of items in the premium slots (i.e., slots with increased visibility/accessibility) improves the probability of sale w.r.t. item placement in non-premium slots. Moreover, customers often tend to buy sets of items (i.e., itemsets) instead of individual purchases. In this paper, we address the problem of maximizing retailer revenue by determining the placement of itemsets in different types of slots with varied premiumness. Our key contributions are as follows. First, we introduce the notion of premiumness of retail slots and discuss the issue of itemset placement in slots with varied premiumness. Second, we propose two efficient schemes, namely Premiumness and Revenue-based Itemset Placement (PRIP) and Premiumness and Average Revenue-based Itemset Placement (PARIP), for placing itemsets with varying revenue in slots with varied premiumness. Third, we perform a detailed performance analysis using both real and synthetic datasets to showcase the effectiveness of our proposed schemes. We also perform a comprehensive mathematical analysis of our proposed schemes w.r.t. the complexity analysis.

Abstract

Product placement in retail stores has a significant impact on the revenue of the retailer. Hence, research efforts are being made to propose approaches for improving item placement in retail stores based on the knowledge of utility patterns extracted from the log of customer purchase transactions. Another strategy to make any retail store interesting from a customer perspective is to cater to the varied requirements and preferences of customers. This can be achieved by placing a wider variety of items in the shelves of the retail store, thereby increasing the diversity of the items that are available for purchase. In this regard, the key contributions of our work are three-fold. First, we introduce the problem of concept hierarchy based diverse itemset placement in retail stores. Second, we present a framework and schemes for facilitating efficient retrieval of the diverse top-revenue itemsets based on a concept hierarchy. Third, we conducted a performance evaluation with a real dataset to demonstrate the overall effectiveness of our proposed schemes.

Abstract

Partial Periodic itemsets are an important class of regularities that exist in a temporal database. A Partial Periodic itemset is something persistent and predictable that appears in the data. Past studies on Partial Periodic itemsets have been primarily focused on centralized databases and are not scalable for Big Data environments. One cannot ignore the advantage of scalability by using more resources. This is because we deal with large databases in a real-time environment and using more resources can increase the performance. To address the issue we have proposed a parallel algorithm by including the step of distributing transactional identifiers among the machines and mining the identical itemsets independently over the different machines. Experiments on Apache Spark’s distributed environment show that the proposed approach speeds up with the increase in a number of machines.

Abstract

Product placement in retail has a significant impact on the sales revenue of retailers. Hence, research efforts are being made to improve retailer revenue using high-utility pattern mining based product placement approaches. However, none of these existing approaches has explored generalized high-utility itemset mining for determining product placement in retail. The knowledge of generalized high-utility itemsets extracted from user purchase transactional database in conjunction with a product taxonomy can provide new insights about customer purchase behaviour. This work proposes the generalized utility itemset (GUI) index for retrieving generalized high-utility (revenue) itemsets. We also present a framework, which leverages the GUI index towards retail product placement to improve revenue. Our performance study using real datasets shows the effectiveness of our proposed scheme w.r.t. two existing …