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.

Abstract

Automatic extraction of information from text and its transformation into a structured format is an important goal in both Semantic Web Research and computational linguistics. Knowledge Graphs (KG) serve as an intuitive way to provide structure to unstructured text. A fact in a KG is expressed in the form of a triple which captures entities and their interrelationships (predicates). Multiple triples extracted from text can be semantically identical but they may have a vocabulary gap which could lead to an explosion in the number of redundant triples. Hence, to get rid of this vocabulary gap, there is a need to map triples to a homogeneous namespace. In this work, we present an end-to-end KG construction system, which identifies and extracts entities and relationships from text and maps them to the homogenous DBpedia namespace. For Predicate Mapping, we propose a Deep Learning architecture to model semantic similarity. This mapping step is computation heavy, owing to the large number of triples in DBpedia. We identify and prune unnecessary comparisons to make this step scalable. Our experiments show that the proposed approach is able to construct a richer KG at a significantly lower computation cost with respect to previous work.

Abstract

In this paper, we simulated a distributed, cooperative path planning technique for multiple drones (∼200) to explore an unknown region (∼10,000 connected units) in the presence of obstacles. The map of an unknown region is dynamically created based on the information obtained from sensors and other drones. The unknown area is considered a connected region made up of hexagonal unit cells. These cells are grouped to form larger cells called sub-areas. We use long range and short range communication. The short-range communication within drones in smaller proximity helps avoid re-exploration of cells already explored by companion drones located in the same subarea. The long-range communication helps drones identify next subarea to be targeted based on weighted RNN (Reverse nearest neighbor). Simulation results show that weighted RNN in a hexagonal representation makes exploration more efficient, scalable and resilient to communication failures

Abstract

Pattern mining is an important task of data mining and involves the extraction of interesting associations from large databases. Typically, pattern mining is carried out from huge databases, which tend to get updated several times. Consequently, as a given database is updated, some of the patterns discovered 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 and incrementally mine patterns when a database is updated as opposed to mining all of the patterns from scratch from the complete database. Incidentally, research efforts are being made to develop incremental pattern mining algorithms for extracting different kinds of patterns such as frequent patterns, sequential patterns and utility patterns. However, none of the existing works addresses incremental mining in the context of coverage patterns, which has important applications in areas such as banner advertising, search engine advertising and graph mining. In this regard, the main contributions of this work are three-fold. First, we introduce the problem of incremental mining in the context of coverage patterns. Second, we propose the IncCMine algorithm for efficiently extracting the knowledge of coverage patterns when incremental database is added to the existing database. Third, we performed extensive experiments using two real-world click stream datasets and one synthetic dataset. The results of our performance evaluation demonstrate that our proposed IncCMine algorithm indeed improves the performance significantly w.r.t. the existing CMine algorithm. Index Terms—Data mining, Coverage patterns, Incremental mining, Knowledge discovery

Abstract

We present a novel robotic front-end for autonomous aerial motion-capture (mocap) in outdoor environments. In previous work, we presented an approach for cooperative detection and tracking (CDT) of a subject using multiple micro-aerial vehicles (MAVs). However, it did not ensure optimal view-point configurations of the MAVs to minimize the uncertainty in the person’s cooperatively tracked 3D position estimate. In this article, we introduce an active approach for CDT. In contrast to cooperatively tracking only the 3D positions of the person, the MAVs can actively compute optimal local motion plans, resulting in optimal view-point configurations, which minimize the uncertainty in the tracked estimate. We achieve this by decoupling the goal of active tracking into a quadratic objective and non-convex constraints corresponding to angular configurations of the MAVs w.r.t. the person. We derive this decoupling using Gaussian observation model assumptions within the CDT algorithm. We preserve convexity in optimization by embedding all the non-convex constraints, including those for dynamic obstacle avoidance, as external control inputs in the MPC dynamics. Multiple real robot experiments and comparisons involving 3 MAVs in several challenging scenarios are presented.