Abstract

Matroidal networks were introduced by Doughert yet al.and have been well studied in the recent past. It was shown that a network has a scalar linear network coding solution if and only if it is matroidal associated with a representable matroid. A particularly interesting feature of this development is the ability to construct (scalar and vector)linearly solvable networks using certain classes of matroids.Furthermore, it was shown through the connection between network coding and matroid theory that linear network coding is not always sufficient for general network coding scenarios.The current work attempts to establish a connection between matroid theory and network-error correcting and detecting codes. In a similar vein to the theory connecting matroids and network coding, we abstract the essential aspects of linear network-error detecting codes to arrive at the definition of a matroidal error detecting network(and similarly, a matroidal error correcting networkabstracting from network-error correcting codes). An acyclic network (with arbitrary sink demands) is then shown to possess a scalar linear error detecting (correcting)network code if and only if it is a matroidal error detecting(correcting) network associated with a representable matroid.Therefore, constructing such network-error correcting and detecting codes implies the construction of certain representable matroids that satisfy some special conditions, and vice versa.We then present algorithms that enable the construction of matroidal error detecting and correcting networks with a specified capability of network-error correction. Using these construction algorithms, a large class of hitherto unknown scalar linearly solvable networks with multi source, multicast,and multiple- unicast network-error correcting codes is made available for theoretical use and practical implementation,with parameters, such as number of information symbols,number of sinks, number of coding nodes, error correcting capability, and so on, being arbitrary but for computing power(for the execution of the algorithms). The complexity of the construction of these networks is shown to be comparable with the complexity of existing algorithms that design multi cast scalar linear network-error correcting codes. Finally, we also show that linear network coding is not sufficient for the general network-error correction (detection) problem with arbitrary demands. In particular, for the same number of network errors,we show a network for which there is a nonlinear network-error detecting code satisfying the demands at the sinks, where as there are no linear network-error detecting codes that do the same.

Abstract

A code is said to be data-local maximally recoverable if (i) all the information symbols have locality and (ii) any erasure pattern which can be potentially recovered (i.e., the number of equations is equal to the number of unknowns) is recovered by the code. A code is said to be local maximally recoverable if(i) all the symbols of the code have locality and (ii) from the above holds. In this paper, we establish the matroid structures corresponding to data-local and local maximally recoverable codes (MRC). The matroid structures of these codes can be used to determine the associated Tutte polynomial. Greene proved that the weight enumerators of any code can be determined from its associated Tutte polynomial. We will use this result to derive explicit expressions for the weight enumerators of data-local MRC. Also, Britz proved that the higher support weights of any code can be determined from its associated Tutte polynomial.We will use this result to derive expressions for the higher support weights of data-local and local MRC with two local codes.

Abstract

Image based reconstruction of urban environments is a challenging problem that deals with optimization of large number of variables, and has several sources of errors like the presence of dynamic objects. Since most large scale approaches make the assumption of observing static scenes, dynamic objects are relegated to the noise modelling section of such systems. This is an approach of convenience since the RANSAC based framework used to compute most multiview geometric quantities for static scenes naturally confine dynamic objects to the class of outlier measurements. However, reconstructing dynamic objects along with the static environment helps us get a complete picture of an urban environment. Such understanding can then be used for important robotic tasks like path planning for autonomous navigation, obstacle tracking and avoidance, and other areas. In this paper, we propose a system for robust SLAM that works in both static and dynamic environments. To overcome the challenge of dynamic objects in the scene, we propose a new model to incorporate semantic constraints into the reconstruction algorithm. While some of these constraints are based on multi-layered dense CRFs trained over appearance as well as motion cues, other proposed constraints can be expressed as additional terms in the bundle adjustment optimization process that does iterative refinement of 3D structure and camera / object motion trajectories. We show results on the challenging KITTI urban dataset for accuracy of motion segmentation and reconstruction of the trajectory and shape of moving objects relative to ground truth. We are able to show average relative error reduction by 41 % for moving object trajectory reconstruction relative to state-of-the-art methods like TriTrack[16], as well as on standard bundle adjustment algorithms with motion segmentation.

Abstract

We propose a novel collision avoidance formulation in the intent space, suitable for navigation of non-holonomic robots in human centered environments. The intent space is characterized by various bands of trajectories wherein each band can be thought to be a representation of a possible human intended motion and the uncertainty associated with it. We ascribe probabilities to human intentions and characterize the uncertainty around it through Gaussian state transition and its concomitant Gaussian parametric distribution. Given an intent space we design avoidance maneuvers based on our recent works on time scaled collision cone concept which provides analytical characterization of collision free velocities in dynamic environments. In this paper, we present a probabilistic variant of the time scaled collision cone which allows us to relate space of collision free velocities to an associated confidence measure. We also develop an optimization framework which extract such specific solutions from the entire solution space that achieves an elegant balance between the objective of minimizing risk and ease of avoidance maneuver. We further show that by accounting for possible intents in human motion, the method transcends the realm of reactive avoidance to proactive anticipation of collisions and its effective avoidance, thereby increasing the overall safety of navigation.

Abstract

Protein-protein interaction (PPI) networks are valuable biological data source which contain rich information useful for protein function prediction. The PPI network data obtained from high-throughput experiments is known to be noisy and incomplete. In the literature, common neighbor, clustering, and classification-based approaches have been proposed to improve the performance of protein function prediction by modeling PPI data as a graph. These approaches exploit the fact that protein shares function with other proteins directly interacting with it. In this paper we have experimented an alternative approach by exploiting the notion that two proteins share a function if they have a well defined group of directly or indirectly connected common neighbors. The experiments conducted on variety of PPI network datasets show that the proposed approach improves protein function prediction accuracy over existing approaches

Abstract

The system of advertising on web search engines is more popularly known as Adwords. In Adwords, advertisers bid on relevant search keywords for displaying their advertisement when a query containing any of those keywords is fired. During keyword auction, there is very high competition for the frequent keywords while little to no competition for the less frequent ones. In this paper, we have proposed an approach to utilize the eye balls related to infrequent keywords to meet the demands of more advertisers by employing the notions of coverage and concept taxonomy. We employed the notion of coverage to form the multiple distinct groups of infrequent keywords. We also employed concept taxonomy to ensure that each group of keywords is semantically related. We have conducted experiments on the search queries dataset of AOL search engine. The results show that the proposed approach has a potential to meet the advertising demands of more number of advertisers over the existing approach.

Abstract

Protein-protein interaction (PPI) networks are valuable biological data source which contain rich information useful for protein function prediction. The PPI network data set obtained from high-throughput experiments is known to be noisy and incomplete. By modeling PPI data as a graph, research efforts are being made in the literature to improve the performance of protein function prediction by extending common neighbor, clustering, and classification based approaches. These approaches exploit the fact that protein shares function with other proteins which are connected through common neighbours. As PPI data is modeled as a graph, it contains prominent nodes which establish relatively high connectivity with other modes. In this paper we propose an improved approach for protein function prediction by exploiting the connectivity properties of prominent proteins. Experimental results on real-world data sets demonstrate the effectiveness of proposed approach.

Abstract

We propose a model of coverage patterns (CPs) and approaches for extracting CPs from transactional databases. The model is motivated by the problem of banner advertisement placement in e-commerce web sites. Normally, an advertiser expects that the banner advertisement should be displayed to a certain percentage of web site visitors. On the other hand, to generate more revenue for a given web site, the publisher makes efforts to meet the coverage demands of multiple advertisers. Informally, a CP is a set of non overlapping items covered by certain percentage of transactions in a transactional database.The CPs do not satisfy the downward closure property. Efforts are being made in the literature to extract CPs using level-wise pruning approach. In this paper, we propose CP extraction approaches based on pattern growth techniques. Experimental results show that the proposed pattern growth approaches improve the performance over the level-wise pruning approach. The results also show that CPs could be used in meeting the demands of multiple advertisers.

Abstract

Online advertising provides an opportunity for product sellers and service providers to reach customers and has become a key factor in the growth of economy. It is a major source of revenue for the major search engine and social networking sites. Search engine, context-specific and banner advertising are the major modes of online advertising. The banner advertisement mode has certain advantages over other modes of advertising. Currently, the number of websites registered comes to a billion. Each day, a typical website receives the number of visitors ranging from hundreds to millions. In a few years, the entire population of the globe is going to be connected to Internet and browse websites. It is possible for a product seller or service provider to reach every potential customer through banner advertising. In this paper, a framework is proposed to harvest the pages views of web by forming the clusters of similar websites. Rather than managing a single website, the publisher manages the aggregated advertising space of a collection of websites. As a result, the advertisement space could be expanded significantly and it will provide the opportunity for increased number of publishers to market the aggregated advertisement space of millions of websites to advertisers for reaching potential customers. It will also help in balancing the management of banner advertising market.

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.