A digital herbarium for the flora of Karnataka

A herbarium-based database (virtual herbarium) is a referral system for plants that maximizes the usefulness of the collections. The information content of such a database is essentially built on the voucher specimens that the herbarium has in its care. The present article reports on the construction of a `virtual herbarium' for the state-wide collection of flowering plants in the Herbarium JCB housed at the Centre for Ecological Sciences, Indian Institute of Science, Bangalore, that is expected to be launched soon. The taxonomic data on each species include all information presented on the herbarium specimen label, namely species name, author citation, sub-species if any, variety if any, family, subfamily, collection number, locations, date of collection, habitat and the collector's name. The data further comprise `flora' in which the species are described. Additional information includes the nomenclature update according to `The Plant List', a detailed description, phenology, species distribution, threat status and comments on any special features of the taxon. The live images of the species provided in the database form an information synergy on the species. This initiative is the first of its kind for herbaria in peninsular India.

Incentive Compatible Influence Maximization in Social Networks with Application to Viral Marketing

Information diffusion and influence maximization are important and extensively studied problems in social networks. Various models and algorithms have been proposed in the literature in the context of the influence maximization problem. A crucial assumption in all these studies is that the influence probabilities are known to the social planner. This assumption is unrealistic since the influence probabilities are usually private information of the individual agents and strategic agents may not reveal them truthfully. Moreover, the influence probabilities could vary significantly with the type of the information flowing in the network and the time at which the information is propagating in the network. In this paper, we use a mechanism design approach to elicit influence probabilities truthfully from the agents. Our main contribution is to design a scoring rule based mechanism in the context of the influencer-influencee model. In particular, we show the incentive compatibility of the mechanisms and propose a reverse weighted scoring rule based mechanism as an appropriate mechanism to use.

Efficient Regular Expression Pattern Matching for Network Intrusion Detection Systems using Modified Word-based Automata

Network Intrusion Detection Systems (NIDS) intercept the traffic at an organization's network periphery to thwart intrusion attempts. Signature-based NIDS compares the intercepted packets against its database of known vulnerabilities and malware signatures to detect such cyber attacks. These signatures are represented using Regular Expressions (REs) and strings. Regular Expressions, because of their higher expressive power, are preferred over simple strings to write these signatures. We present Cascaded Automata Architecture to perform memory efficient Regular Expression pattern matching using existing string matching solutions. The proposed architecture performs two stage Regular Expression pattern matching. We replace the substring and character class components of the Regular Expression with new symbols. We address the challenges involved in this approach. We augment the Word-based Automata, obtained from the re-written Regular Expressions, with counter-based states and length bound transitions to perform Regular Expression pattern matching. We evaluated our architecture on Regular Expressions taken from Snort rulesets. We were able to reduce the number of automata states between 50% to 85%. Additionally, we could reduce the number of transitions by a factor of 3 leading to further reduction in the memory requirements.

Predicting the lithospheric stress field and plate motions by joint modeling of lithosphere and mantle dynamics

The way in which basal tractions, associated with mantle convection, couples with the lithosphere is a fundamental problem in geodynamics. A successful lithosphere-mantle coupling model for the Earth will satisfy observations of plate motions, intraplate stresses, and the plate boundary zone deformation. We solve the depth integrated three-dimensional force balance equations in a global finite element model that takes into account effects of both topography and shallow lithosphere structure as well as tractions originating from deeper mantle convection. The contribution from topography and lithosphere structure is estimated by calculating gravitational potential energy differences. The basal tractions are derived from a fully dynamic flow model with both radial and lateral viscosity variations. We simultaneously fit stresses and plate motions in order to delineate a best-fit lithosphere-mantle coupling model. We use both the World Stress Map and the Global Strain Rate Model to constrain the models. We find that a strongly coupled model with a stiff lithosphere and 3-4 orders of lateral viscosity variations in the lithosphere are best able to match the observational constraints. Our predicted deviatoric stresses, which are dominated by contribution from mantle tractions, range between 20-70 MPa. The best-fitting coupled models predict strain rates that are consistent with observations. That is, the intraplate areas are nearly rigid whereas plate boundaries and some other continental deformation zones display high strain rates. Comparison of mantle tractions and surface velocities indicate that in most areas tractions are driving, although in a few regions, including western North America, tractions are resistive. Citation: Ghosh, A., W. E. Holt, and L. M. Wen (2013), Predicting the lithospheric stress field and plate motions by joint modeling of lithosphere and mantle dynamics.

Tiling stencil computations to maximize parallelism

Most stencil computations allow tile-wise concurrent start, i.e., there always exists a face of the iteration space and a set of tiling hyperplanes such that all tiles along that face can be started concurrently. This provides load balance and maximizes parallelism. However, existing automatic tiling frameworks often choose hyperplanes that lead to pipelined start-up and load imbalance. We address this issue with a new tiling technique that ensures concurrent start-up as well as perfect load-balance whenever possible. We first provide necessary and sufficient conditions on tiling hyperplanes to enable concurrent start for programs with affine data accesses. We then provide an approach to find such hyperplanes. Experimental evaluation on a 12-core Intel Westmere shows that our code is able to outperform a tuned domain-specific stencil code generator by 4% to 27%, and previous compiler techniques by a factor of 2x to 10.14x.

The dynamics between forward citations and price of singleton patents

In recent years, business practitioners are seen valuing patents on the basis of the market price that the patent can attract. Researchers have also looked into various patent latent variables and firm variables that influence the price of a patent. Forward citations of a patent are shown to play a role in determining price. Using patent auction price data (of Ocean Tomo now ICAP patent brokerage), we delve deeper into of the role of forward citations. The successfully sold 167 singleton patents form the sample of our study. We found that, it is mainly the right tail of the citation distribution that explains the high prices of the patents falling on the right tail of the price distribution. There is consistency in the literature on the positive correlation between patent prices and forward citations. In this paper, we go deeper to understand this linear relationship through case studies. Case studies of patents with high and low citations are described in this paper to understand why some patents attracted high prices. We look into the role of additional patent latent variables like age, technology discipline, class and breadth of the patent in influencing citations that a patent receives.

Optimal incentive timing strategies for product marketing on social networks

We consider the problem of devising incentive strategies for viral marketing of a product. In particular, we assume that the seller can influence penetration of the product by offering two incentive programs: a) direct incentives to potential buyers (influence) and b) referral rewards for customers who influence potential buyers to make the purchase (exploit connections). The problem is to determine the optimal timing of these programs over a finite time horizon. In contrast to algorithmic perspective popular in the literature, we take a mean-field approach and formulate the problem as a continuous-time deterministic optimal control problem. We show that the optimal strategy for the seller has a simple structure and can take both forms, namely, influence-and-exploit and exploit-and-influence. We also show that in some cases it may optimal for the seller to deploy incentive programs mostly for low degree nodes. We support our theoretical results through numerical studies and provide practical insights by analyzing various scenarios.

Sustaining cooperation on networks: an analytical study based on evolutionary game theory

We analytically study the role played by the network topology in sustaining cooperation in a society of myopic agents in an evolutionary setting. In our model, each agent plays the Prisoner's Dilemma (PD) game with its neighbors, as specified by a network. Cooperation is the incumbent strategy, whereas defectors are the mutants. Starting with a population of cooperators, some agents are switched to defection. The agents then play the PD game with their neighbors and compute their fitness. After this, an evolutionary rule, or imitation dynamic is used to update the agent strategy. A defector switches back to cooperation if it has a cooperator neighbor with higher fitness. The network is said to sustain cooperation if almost all defectors switch to cooperation. Earlier work on the sustenance of cooperation has largely consisted of simulation studies, and we seek to complement this body of work by providing analytical insight for the same. We find that in order to sustain cooperation, a network should satisfy some properties such as small average diameter, densification, and irregularity. Real-world networks have been empirically shown to exhibit these properties, and are thus candidates for the sustenance of cooperation. We also analyze some specific graphs to determine whether or not they sustain cooperation. In particular, we find that scale-free graphs belonging to a certain family sustain cooperation, whereas Erdos-Renyi random graphs do not. To the best of our knowledge, ours is the first analytical attempt to determine which networks sustain cooperation in a population of myopic agents in an evolutionary setting.

Generating Efficient Data Movement Code for Heterogeneous Architectures with Distributed-Memory

Programming for parallel architectures that do not have a shared address space is extremely difficult due to the need for explicit communication between memories of different compute devices. A heterogeneous system with CPUs and multiple GPUs, or a distributed-memory cluster are examples of such systems. Past works that try to automate data movement for distributed-memory architectures can lead to excessive redundant communication. In this paper, we propose an automatic data movement scheme that minimizes the volume of communication between compute devices in heterogeneous and distributed-memory systems. We show that by partitioning data dependences in a particular non-trivial way, one can generate data movement code that results in the minimum volume for a vast majority of cases. The techniques are applicable to any sequence of affine loop nests and works on top of any choice of loop transformations, parallelization, and computation placement. The data movement code generated minimizes the volume of communication for a particular configuration of these. We use a combination of powerful static analyses relying on the polyhedral compiler framework and lightweight runtime routines they generate, to build a source-to-source transformation tool that automatically generates communication code. We demonstrate that the tool is scalable and leads to substantial gains in efficiency. On a heterogeneous system, the communication volume is reduced by a factor of 11X to 83X over state-of-the-art, translating into a mean execution time speedup of 1.53X. On a distributed-memory cluster, our scheme reduces the communication volume by a factor of 1.4X to 63.5X over state-of-the-art, resulting in a mean speedup of 1.55X. In addition, our scheme yields a mean speedup of 2.19X over hand-optimized UPC codes.

Parallel Flow-Sensitive Pointer Analysis by Graph-Rewriting

Precise pointer analysis is a problem of interest to both the compiler and the program verification community. Flow-sensitivity is an important dimension of pointer analysis that affects the precision of the final result computed. Scaling flow-sensitive pointer analysis to millions of lines of code is a major challenge. Recently, staged flow-sensitive pointer analysis has been proposed, which exploits a sparse representation of program code created by staged analysis. In this paper we formulate the staged flow-sensitive pointer analysis as a graph-rewriting problem. Graph-rewriting has already been used for flow-insensitive analysis. However, formulating flow-sensitive pointer analysis as a graph-rewriting problem adds additional challenges due to the nature of flow-sensitivity. We implement our parallel algorithm using Intel Threading Building Blocks and demonstrate considerable scaling (upto 2.6x) for 8 threads on a set of 10 benchmarks. Compared to the sequential implementation of staged flow-sensitive analysis, a single threaded execution of our implementation performs better in 8 of the benchmarks.