Abstract

High utility itemset mining is an important model with many real-world applications. But the popular adoption and successful industrial application of this model has been hindered by the following two limitations: (i) computational expensiveness of the model and (ii) infrequent itemsets may be output as high utility itemsets. This paper makes an effort to address these two limitations. A generic high utility-frequent itemset model is introduced to find all itemsets in the data that satisfy user-specified minimum support and minimum utility constraints. Two new pruning measures, named cutoff utility and suffix utility, are introduced to reduce the computational cost of finding the desired itemsets. A single phase fast algorithm, called High Utility Frequent Itemset Miner (HU-FIMi), is introduced to discover the itemsets efficiently. Experimental results demonstrate that the proposed algorithm is efficient.

Abstract

Honking in traffic is an auditory warning to indicate: driver’s actions, alert pedestrians and to convey an emergency situation requiring right of way. Though studies have shown the importance of honking in maintaining traffic flow, there have been cases where irrational use leads to an increase in stress/irritation with effects on driver decision making. Most drivers are unaware of the adverse health effects of high decibel honking. In this report, we looked at the effects of honking on driving behavior in a lab-developed VR driving simulator and anxiety/stress as indicated by changes in skin conductance /pulse rate measured using sensors.

Abstract

In real-world databases, high utility itemset (HUI) is an important class of regularities. Most previous studies have focused on mining HUIs in transactional databases and did not consider the spatiotemporal characteristics of items. In this study, a more flexible model of spatial HUIs (SHUIs) that exist in spatiotemporal databases is proposed. In a spatiotemporal database (STD), an itemset is said to be an SHUI if its utility is not less than a user-specified minimum utility and the distance between any two of its items is not more than a user-specified maximum distance. Identifying SHUIs is very challenging because the generated itemsets do not satisfy the anti-monotonic property. In this study, we present two novel pruning techniques for reducing computational costs. Moreover, a fast single scan algorithm is presented for effectively evaluating all SHUIs in a STD. Furthermore, two case studies are presented, in which the proposed model is used to identify useful information in traffic congestion data and air pollution data.

Abstract

In retail stores, the placement of items on the shelf space significantly impacts the sales of items. In particular, the probability of sales of a given item is typically considerably higher when it is placed in a premium (i.e., highly visible/easily accessible) slot as opposed to a non-premium slot. In this paper, we address the problem of maximizing the revenue for the retailer by determining the placement of the itemsets in different types of slots with varied premiumness such that each item is placed at least once in any of the slots. We first propose the notion of premiumness of slots in a given retail store. Then we discuss a framework for efficiently identifying itemsets from a transactional database and placing these itemsets by mapping itemsets with different revenue to slots with varied premiumness for maximizing retailer revenue. Our performance evaluation on both synthetic and real datasets demonstrate that the proposed scheme indeed improves the retailer revenue by up to 45% w.r.t. a recent existing scheme.

Abstract

While the problems of finding 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 reflects such user preferences. Moreover, users typically prefer diverse paths over similar paths for gaining flexibility in path selection. Given a set of user traversals in a road network and a set of paths between a given source and destination pair, we propose a scheme based on transactional modeling and pattern mining for performing top-k ranking of these paths based on both path popularity and path diversity. Our performance evaluation with a real dataset demonstrates the effectiveness of the proposed scheme.

Abstract

High Utility Itemset Mining (HUIM) is an important model with many real-world applications. Given a (non-binary) transactional database and an external utility database, the aim of HUIM is to discover all itemsets within the data that satisfy the user-specified minimum utility (minUtil) constraint. The popular adoption and successful industrial application of HUIM has been hindered by the following two limitations: (i) HUIM does not allow external utilities of items to vary over time and (ii) HUIM algorithms are inadequate to find recurring customer purchase behavior. This paper introduces a flexible model of Partial Periodic High Utility Itemset Mining (PPHUIM) to address these two problems. The goal of PPHUIM is to discover only those interesting high utility itemsets that are occurring at regular intervals in a given temporal database. An efficient depth-first search algorithm, called PPHUI-Miner (Partial Periodic High Utility Itemset-Miner), has been proposed to enumerate all partial periodic high-utility itemsets in temporal databases. Experimental results show that the proposed algorithm is efficient.

Abstract

Sponsored search has emerged as one of the most dominant forms for advertising on the Web. In sponsored search, advertisers create ad campaigns and bid on the keywords of potential search queries related to a given product or service. It has been observed that search queries follow a long-tail distribution of a small yet fat head of frequent queries and a long and thin tail of infrequent queries. Normally, the advertisers tend to bid on frequent keywords related to search queries. As a result, the ad space of the tail portion of search queries is harder to exploit. In this paper, we have proposed an improved allocation approach to utilize the ad space of the tail keywords related to search queries based on the knowledge of coverage patterns extracted from the transactions formed from search query logs. The advertisers bid on potential concepts represented by coverage patterns which consist of a combination of head and tail keywords. By facilitating the advertisers to bid on the concepts, the proposed approach improves the ad space utilization of tail queries. Experiments on the real-world dataset of search query logs demonstrate that the proposed approach indeed improves the performance of search engine advertising by improving ad space utilization of tail queries.

Abstract

Literary novels are a mine of information stored in a narrative. Information Extraction (IE) on these novels can be directed by a specific aim to derive knowledge of interest. In this paper, we explore the problem of extracting evidence summaries for all characters in a detective novel. But in this domain, there is no standard annotated text which provides the ground truth for evidence and there exists no fixed metric of evaluation. For extracting summaries, we explore unsupervised methods of learning. We first assume that all characters are equally likely to be culprits and build evidence against each character. Given this evidence, we assess the likelihood of each character being the culprit, eventually arriving at the true culprit(s). Our contribution is the formulation of evidence summaries for characters in determining the culprit. Our experiments are based on a corpus of detective novels spanning the last hundred years. We evaluate these summaries for comprehension with the help of human readers and broadly categorize novels into three groups.

Abstract

In this work, we present an algorithm for robot replacement to increase the operational time of a multi-robot payload transport system. Our system comprises a group of non-holonomic wheeled mobile robots traversing on a known trajectory. We design a multi-robot system with loosely coupled robots that ensures the system lasts much longer than the battery life of an individual robot. A system level optimization is presented, to decide on the operational state (charging or discharging) of each robot in the system. The charging state implies that the robot is not in a formation and is kept on charge whereas the discharging state implies that the robot is a part of the formation. Robot battery recharge hubs are present along the trajectory. Robots in the formation can be replaced at these hub locations with charged robots using a replacement mechanism. We showcase the efficacy of the proposed scheduling framework through simulations and experiments with real robots.

Abstract

Visibility computation is critical in spatial databases for realizing various interesting and diverse applications such as defence-related surveillance, identifying interesting spots in tourist places and online warcraft games. Existing works address the problem of identifying individual locations for maximizing the visibility of a given target object. However, in case of many applications, a set of locations may be more effective than just individual locations towards maximizing the visibility of the given target object. In this paper, we introduce the Multi-Location Visibility (MLV) query. An MLV query determines the top-k query locations from which the visibility of a given target object can be maximized. We propose a portion-based transactional framework and coverage pattern mining based algorithm to process MLV queries. Our performance evaluation with real datasets demonstrates the effectiveness of the proposed scheme in terms of query processing time, pruning efficiency and target object visibility w.r.t. a recent existing scheme.