Abstract

Interactive visualization and analysis of the class boundaries is important because it tells us how and why the classes differ. However, the problem of modeling the boundary of classes of arbitrary size, shape and density is challenging. The boundary of a class should not be limited to the points/shape which encloses the points within the class but it should be, the points/shape which encloses the region of influence of a class. The "region of influence" refers to the space around the class where any point lying within the region is likely to be classified to the class based on a nearest neighbor classifier. We have developed interactive boundary visualization toolkit for classified datasets which provides insights about the classifier model used on the dataset. Our algorithm first generates a candidate boundary set for each class based on reverse k-nearest neighbors approach and extends this boundary iteratively through the region of influence of the class. Further, we present these boundary points enclosing the region of influence as a linear approximated shape using triangulation techniques. We show experimental results on 2D and 3D datasets.

Abstract

Robots playing games that humans are adept in is a challenge. We studied robotic agents playing Chain Catch game as a Multi-Agent System (MAS). Our game starts with a traditional Catch game similar to Pursuit evasion, and further extends it to form a growing chain of predator agents to chase remaining preys. Hence Chain Catch is a combination of two challenges-pursuit domain and robotic chain formation. These are games that require team of robotic agents to cooperate among themselves and to compete with other group of agents through quick decision making. In this paper, we present a Chain Catch simulator that allows us to incorporate game rules, design strategies and simulate the game play. We developed cost model driven strategies for each of Escapee, Catcher and Chain. Our results show that Sliding slope strategy is the best strategy for Escapees whereas Tagging method is the best method for chain s movement in Chain Catch. We also use production quality robots to implement the game play in a physical environment and analyze game strategies on real robots. Our real robots implementation in different scenarios shows that game strategies work as expected and a complete chain formation takes place successfully in each game.

Abstract

We investigate the automatic generation of Wikipedia articles as an alternative to its manual creation. We propose a framework for creating a Wikipedia article for a named entity which not only looks similar to other Wikipedia articles in its category but also aggregates the diverse aspects related to that named entity from the Web. In particular, a semi-supervised method is used for determining the headings and identifying the content for each heading in the Wikipedia article generated. Evaluations show that articles created by our system for categories like actors are more reliable and informative compared to those generated by previous approaches of Wikipedia article automation.

Abstract

A method, non-transitory computer readable medium, and apparatus for receiving data from a cloud database. One or more queries requesting data from the cloud database are received. The one or more queries are converted from a row-store database query into a column-store database query. An optimal join plan is identified for the one or more queries using a cost based optimizer based on metadata for one or more relations in the cloud database. The optimal join plan is executed using a cloud application programming interface.

Abstract

In a traditional ER model, once we specify a subclass or superclass relationship, any changes to that relationship are treated as schema evolution. Further, ER models are rigid in the sense that once a relationship type is specified across a set of entity types, an instance of relationship type occur when one instance of all participating entity types are specified. Therefore, it is difficult to introduce in a simplified manner all relationship types across subsets of given set of entity types. In this paper, we provide mechanisms to model in our extended ER model: (i) specification of dynamic relationship types across subsets of instances of entity types, (ii) a simplified specification of relationships across subsets of given set of entity types, and (iii) mapping our extended ER model to relational database schema. We also show through an e-contract example the utility of our extended ER model.

Abstract

The subset sum problem, also referred as SSP, is a NP-Hard computational problem. SSP has its applications in broad domains like cryptography, number theory, operation research and complexity theory. The most famous algorithm for solving SSP is Backtracking Algorithm which has exponential time complexity. Therefore, our goal is to design and develop better alternate enumeration techniques for faster generation of SSP solutions. Given the set of first n natural numbers which is denoted by Xn and a target sum S, we propose various alternate enumeration techniques which find all the subsets of Xn that add up to sum S. In this paper, we present the mathematics behind this exponential problem. We analyze the distribution of power set of Xn and present formulas which show definite patterns and relations among these subsets. We introduce three major distributions for power set of Xn: Sum Distribution, Length-Sum Distribution and Element Distribution. These distributions are prepossessing procedures for various alternate enumeration techniques for solving SSP. We propose novel algorithms: Subset Generation using Sum Distribution, Subset Generation using Length-Sum Distribution, Basic Bucket Algorithm, Maximum and Minimum Frequency Driven Bucket Algorithms and Local Search using Maximal and Minimal Subsets for enumerating SSP.

Abstract

Crowd management is a complex, challenging and crucial task. Lack of appropriate management of crowd has, in past, led to many unfortunate stampedes with significant loss of life. To increase the crowd management efficiency, we deploy automated real time detection of stampede prone areas. Then, we use robotic agents to aid the crowd management police in controlling the crowd in these stampede prone areas. While doing so, we aim for minimum interference by robotic agents in our environment. Thereby not disturbing the ambiance and aesthetics of the place. We evaluate the effectiveness of our model in dealing with difficult scenarios like emergency evacuation and presence of localized congestion. Lastly, we simulate a multi agent system based on our model and use it to illustrate the utility of robotic agents for detecting and reducing congestion.

Abstract

Preventing traffic congestion by forecasting near time traffic flows is an important problem as it leads to effective use of transport resources. Social network provides information about activities of humans and social events. Thus, with the help of social network, we can extract which humans will attend a particular event (in near time) and can estimate flow of traffic based on it. This opens up a wide area of research which poses need to have a framework for traffic management that can capture essential parameters of real-life behaviour and provide a way to iterate upon and evaluate new ideas. In this paper, we present building blocks of a framework and a system to simulate a city with its transport system, humans and their social network. We emphasize on relevant parameters selected and modular design of the framework. Our framework defines metrics to evaluate congestion avoidance strategies. To show utility of the framework, we present experimental studies of few strategies on a public transport system.

Abstract

A queue is required when a service provider is not able to handle jobs arriving over the time. In a highly flexible and dynamic environment, some jobs might demand for faster execution at run-time especially when the resources are limited and the jobs are competing for acquiring resources. A user might demand for speed up (reduced wait time) for some of the jobs present in the queue at run time. In such cases, it is required to accelerate (directly sending the job to the server) urgent jobs (requesting for speed up) ahead of other jobs present in the queue for an earlier completion of urgent jobs. Under the assumption of no additional resources, such acceleration of jobs would result in slowing down of other jobs present in the queue. In this paper, we formulate the problem of Speed Up Scheduling without acquiring any additional resources for the scheduling of on-line speed up requests posed by a user at run-time and present algorithms for the same. We apply the idea of Speed Up Scheduling to two different domains-Web Scheduling and CPU Scheduling. We demonstrate our results with a simulation based model using trace driven workload and synthetic datasets to show the usefulness of Speed Up scheduling. Speed Up provides a new way of addressing urgent jobs, provides a different evaluation criteria for comparing scheduling algorithms and has practical applications.

Abstract

Preventing traffic congestion by forecasting near time traffic flows is an important problem as it leads to effective use of transport resources. Social network provides information about activities of humans and social events. Thus, with the help of social network, we can extract which humans will attend a particular event (in near time) and can estimate flow of traffic based on it. This opens research area to build a framework for traffic management that can capture essential parameters of real-life behavior and provide a way to iterate upon and evaluate new ideas. In this paper, we present building blocks of such framework and a system to simulate a city with its transport system, humans and their social network. We emphasize on relevant parameters selected and modular design of the framework. To show the utility of the framework, we present experimental studies of few strategies on a public transport system.