OpenRaiser/Intern-Atlas huggingface dataset:
Homomorphic Hashing for Sparse Coefficient Extraction
Venue: arXiv cs.CC 2012
Year: 2012

We study classes of Dynamic Programming (DP) algorithms which, due to their algebraic definitions, are closely related to coefficient extraction methods. DP algorithms can easily be modified to exploit sparseness in the DP table through memorization. Coefficient extraction techniques on the other hand are both space-efficient and parallelisable, but no tools have been available to exploit sparseness. We investigate the systematic use of homomorphic hash functions to combine the best of these methods and obtain improved space-efficient algorithms for problems including LINEAR SAT, SET PARTITION, and SUBSET SUM. Our algorithms run in time proportional to the number of nonzero entries of the last segment of the DP table, which presents a strict improvement over sparse DP. The last property also gives an improved algorithm for CNF SAT with sparse projections.
An ADMM Algorithm for Solving l_1 Regularized MPC
Venue: arXiv cs.SY 2012
Year: 2012

We present an Alternating Direction Method of Multipliers (ADMM) algorithm for solving optimization problems with an l_1 regularized least-squares cost function subject to recursive equality constraints. The considered optimization problem has applications in control, for example in l_1 regularized MPC. The ADMM algorithm is easy to implement, converges fast to a solution of moderate accuracy, and enables separation of the optimization problem into sub-problems that may be solved in parallel. We show that the most costly step of the proposed ADMM algorithm is equivalent to solving an LQ regulator problem with an extra linear term in the cost function, a problem that can be solved efficiently using a Riccati recursion. We apply the ADMM algorithm to an example of l_1 regularized MPC. The numerical examples confirm fast convergence to moderate accuracy and a linear complexity in the MPC prediction horizon.
Metadata Management in Scientific Computing
Venue: arXiv cs.DL 2012
Year: 2012

Complex scientific codes and the datasets they generate are in need of a sophisticated categorization environment that allows the community to store, search, and enhance metadata in an open, dynamic system. Currently, data is often presented in a read-only format, distilled and curated by a select group of researchers. We envision a more open and dynamic system, where authors can publish their data in a writeable format, allowing users to annotate the datasets with their own comments and data. This would enable the scientific community to collaborate on a higher level than before, where researchers could for example annotate a published dataset with their citations. Such a system would require a complete set of permissions to ensure that any individual's data cannot be altered by others unless they specifically allow it. For this reason datasets and codes are generally presented read-only, to protect the author's data; however, this also prevents the type of social revolutions that the private sector has seen with Facebook and Twitter. In this paper, we present an alternative method of publishing codes and datasets, based on Fluidinfo, which is an openly writeable and social metadata engine. We will use the specific example of the Einstein Toolkit, a shared scientific code built using the Cactus Framework, to illustrate how the code's metadata may be published in writeable form via Fluidinfo.
Outlier Detection Techniques for SQL and ETL Tuning
Venue: arXiv cs.DB 2012
Year: 2012

RDBMS is the heart for both OLTP and OLAP types of applications. For both types of applications thousands of queries expressed in terms of SQL are executed on daily basis. All the commercial DBMS engines capture various attributes in system tables about these executed queries. These queries need to conform to best practices and need to be tuned to ensure optimal performance. While we use checklists, often tools to enforce the same, a black box technique on the queries for profiling, outlier detection is not employed for a summary level understanding. This is the motivation of the paper, as this not only points out to inefficiencies built in the system, but also has the potential to point evolving best practices and inappropriate usage. Certainly this can reduce latency in information flow and optimal utilization of hardware and software capacity. In this paper we start with formulating the problem. We explore four outlier detection techniques. We apply these techniques over rich corpora of production queries and analyze the results. We also explore benefit of an ensemble approach. We conclude with future courses of action. The same philosophy we have used for optimization of extraction, transform, load (ETL) jobs in one of our previous work. We give a brief introduction of the same in section four.
Parameter Learning in PRISM Programs with Continuous Random Variables
Venue: arXiv cs.AI 2012
Year: 2012

Probabilistic Logic Programming (PLP), exemplified by Sato and Kameya's PRISM, Poole's ICL, De Raedt et al's ProbLog and Vennekens et al's LPAD, combines statistical and logical knowledge representation and inference. Inference in these languages is based on enumerative construction of proofs over logic programs. Consequently, these languages permit very limited use of random variables with continuous distributions. In this paper, we extend PRISM with Gaussian random variables and linear equality constraints, and consider the problem of parameter learning in the extended language. Many statistical models such as finite mixture models and Kalman filter can be encoded in extended PRISM. Our EM-based learning algorithm uses a symbolic inference procedure that represents sets of derivations without enumeration. This permits us to learn the distribution parameters of extended PRISM programs with discrete as well as Gaussian variables. The learning algorithm naturally generalizes the ones used for PRISM and Hybrid Bayesian Networks.
Thesis Report: Resource Utilization Provisioning in MapReduce
Venue: arXiv cs.DC 2012
Year: 2012

In this thesis report, we have a survey on state-of-the-art methods for modelling resource utilization of MapReduce applications regard to its configuration parameters. After implementation of one of the algorithms in literature, we tried to find that if CPU usage modelling of a MapReduce application can be used to predict CPU usage of another MapReduce application.
Extended Report: The Implicit Calculus
Venue: arXiv cs.PL 2012
Year: 2012

Generic programming (GP) is an increasingly important trend in programming languages. Well-known GP mechanisms, such as type classes and the C++0x concepts proposal, usually combine two features: 1) a special type of interfaces; and 2) implicit instantiation of implementations of those interfaces. Scala implicits are a GP language mechanism, inspired by type classes, that break with the tradition of coupling implicit instantiation with a special type of interface. Instead, implicits provide only implicit instantiation, which is generalized to work for any types. This turns out to be quite powerful and useful to address many limitations that show up in other GP mechanisms. This paper synthesizes the key ideas of implicits formally in a minimal and general core calculus called the implicit calculus, and it shows how to build source languages supporting implicit instantiation on top of it. A novelty of the calculus is its support for partial resolution and higher-order rules (a feature that has been proposed before, but was never formalized or implemented). Ultimately, the implicit calculus provides a formal model of implicits, which can be used by language designers to study and inform implementations of similar mechanisms in their own languages.
Adaptive Mixture Methods Based on Bregman Divergences
Venue: arXiv cs.LG 2012
Year: 2012

We investigate adaptive mixture methods that linearly combine outputs of $m$ constituent filters running in parallel to model a desired signal. We use "Bregman divergences" and obtain certain multiplicative updates to train the linear combination weights under an affine constraint or without any constraints. We use unnormalized relative entropy and relative entropy to define two different Bregman divergences that produce an unnormalized exponentiated gradient update and a normalized exponentiated gradient update on the mixture weights, respectively. We then carry out the mean and the mean-square transient analysis of these adaptive algorithms when they are used to combine outputs of $m$ constituent filters. We illustrate the accuracy of our results and demonstrate the effectiveness of these updates for sparse mixture systems.
On the Stability of Contention Resolution Diversity Slotted ALOHA
Venue: arXiv cs.IT 2012
Year: 2012

In this paper a Time Division Multiple Access (TDMA) based Random Access (RA) channel with Successive Interference Cancellation (SIC) is considered for a finite user population and reliable retransmission mechanism on the basis of Contention Resolution Diversity Slotted ALOHA (CRDSA). A general mathematical model based on Markov Chains is derived which makes it possible to predict the stability regions of SIC-RA channels, the expected delays in equilibrium and the selection of parameters for a stable channel configuration. Furthermore the model enables the estimation of the average time before reaching instability. The presented model is verified against simulations and numerical results are provided for comparison of the stability of CRDSA versus the stability of traditional Slotted ALOHA (SA). The presented results show that CRDSA has not only a high gain over SA in terms of throughput but also in its stability.
Optimizing the Replay Protection at the Link Layer Security Framework in Wireless Sensor Networks
Venue: arXiv cs.CR 2012
Year: 2012

Ensuring communications security in Wireless Sensor Networks (WSNs) is very vital because the security protocols therein, should be devised to work at the link layer. Theoretically, any link layer security protocol must support three vital security attributes viz. Confidentiality, Message Integrity and Replay protection. However, in order to ensure lesser overhead, replay protection is often not incorporated as part of the link layer security framework. We argue here, that it is essential to implement replay protection at the link layer only and devise a simple scheme to do so. We first survey the common approaches to ensuring replay protection in conventional networks. We also implement the conventional algorithms for replay protection using the link layer framework for WSNs viz. TinySec as the underlying platform. Subsequently analyzing their limitations, we propose a novel Bloom-filter based replay protection algorithm for unicast communications. We show that our algorithm is better than the other contemporary approaches for ensuring replay protection in unicast communications in the WSNs.
FlexiSec: A Configurable Link Layer Security Architecture for Wireless Sensor Networks
Venue: arXiv cs.CR 2012
Year: 2012

Ensuring communications security in Wireless Sensor Networks (WSNs) indeed is critical; due to the criticality of the resources in the sensor nodes as well as due to their ubiquitous and pervasive deployment, with varying attributes and degrees of security required. The proliferation of the next generation sensor nodes, has not solved this problem, because of the greater emphasis on low-cost deployment. In addition, the WSNs use data-centric multi-hop communication that in turn, necessitates the security support to be devised at the link layer (increasing the cost of security related operations), instead of being at the application layer, as in general networks. Therefore, an energy-efficient link layer security framework is necessitated. There do exists a number of link layer security architectures that offer some combinations of the security attributes desired by different WSN applications. However, as we show in this paper, none of them is responsive to the actual security demands of the applications. Therefore, we believe that there is a need for investigating the feasibility of a configurable software-based link layer security architecture wherein an application can be compiled flexibly, with respect to its actual security demands. In this paper, we analyze, propose and experiment with the basic design of such configurable link layer security architecture for WSNs. We also experimentally evaluate various aspects related to our scheme viz. configurable block ciphers, configurable block cipher modes of operations, configurable MAC sizes and configurable replay protection. The architecture proposed is aimed to offer the optimal level of security at the minimal overhead, thus saving the precious resources in the WSNs.
A survey of proof nets and matrices for substructural logics
Venue: arXiv cs.LO 2012
Year: 2012

This paper is a survey of two kinds of "compressed" proof schemes, the \emph{matrix method} and \emph{proof nets}, as applied to a variety of logics ranging along the substructural hierarchy from classical all the way down to the nonassociative Lambek system. A novel treatment of proof nets for the latter is provided. Descriptions of proof nets and matrices are given in a uniform notation based on sequents, so that the properties of the schemes for the various logics can be easily compared.
Combined Channel Aggregation and Fragmentation Strategy in Cognitive Radio Networks
Venue: arXiv cs.NI 2012
Year: 2012

In cognitive radio networks, channel aggregation (CA) and channel fragmentation (CF) techniques have been proposed to enhance the spectrum utilization. While most of the literature studies CA and CF independently, in this paper we combine CA and CF innovatively and present a new spectrum sharing strategy named CAF (Channel Aggregation and Fragmentation). We elaborate on the proposed CAF strategy and derive the balance equation by a continuous time Markov chain (CTMC) model. Then various system performance metrics including blocking probability, dropping probability, spectrum utilization and throughput of the secondary network are evaluated. Both analytical and simulation results show that our strategy lowers the blocking and dropping probabilities and enhances the spectrum utilization and throughput effectively. Moreover, by tuning the bandwidth requirement of each secondary user, different system performance can be achieved.
Reduplicated MWE (RMWE) helps in improving the CRF based Manipuri POS Tagger
Venue: arXiv cs.CL 2012
Year: 2012

This paper gives a detail overview about the modified features selection in CRF (Conditional Random Field) based Manipuri POS (Part of Speech) tagging. Selection of features is so important in CRF that the better are the features then the better are the outputs. This work is an attempt or an experiment to make the previous work more efficient. Multiple new features are tried to run the CRF and again tried with the Reduplicated Multiword Expression (RMWE) as another feature. The CRF run with RMWE because Manipuri is rich of RMWE and identification of RMWE becomes one of the necessities to bring up the result of POS tagging. The new CRF system shows a Recall of 78.22%, Precision of 73.15% and F-measure of 75.60%. With the identification of RMWE and considering it as a feature makes an improvement to a Recall of 80.20%, Precision of 74.31% and F-measure of 77.14%.
A tour about Isaac Newton's life
Venue: arXiv cs.OH 2012
Year: 2012

Here we propose a tour about the life of Isaac Newton, using a georeferenced method, based on the free satellite maps. Our tour is modelled on the time-line of the great scientist's life, as an ancient "itinerarium" was modelled on the Roman roads, providing a listing of places and intervening distances, sometimes with short description or symbols concerning the places. KML language and Google Earth, with its Street View and 3D images are powerful tools to create this virtual tour.
Using Signals to Improve Automatic Classification of Temporal Relations
Venue: arXiv cs.CL 2012
Year: 2012

Temporal information conveyed by language describes how the world around us changes through time. Events, durations and times are all temporal elements that can be viewed as intervals. These intervals are sometimes temporally related in text. Automatically determining the nature of such relations is a complex and unsolved problem. Some words can act as "signals" which suggest a temporal ordering between intervals. In this paper, we use these signal words to improve the accuracy of a recent approach to classification of temporal links.
Coteries, Social Circles and Hamlets Close Communities: A Study of Acquaintance Networks
Venue: arXiv cs.SI 2012
Year: 2012

In the analysis of social networks many relatively loose and heuristic definitions of 'community' abound. In this paper the concept of closely knit communities is studied as defined by the property that every pair of its members are neighbors or has at least one common neighbor, where the neighboring relationship is based on some more or less durable and stable acquaintance or contact relation. In this paper these are studied in the form of graphs or networks of diameter two (2-clubs). Their structure can be characterized by investigating shortest spanning trees and girth leading to a typology containing just three or, in combination, six types of close communities.
LOCKE Detailed Specification Tables
Venue: arXiv cs.AR 2012
Year: 2012

This document shows the detailed specification of LOCKE coherence protocol for each cache controller, using a table-based technique. This representation provides clear, concise visual information yet includes sufficient detail (e.g., transient states) arguably lacking in the traditional, graphical form of state diagrams.
Throughput Optimal Scheduling with Dynamic Channel Feedback
Venue: arXiv cs.NI 2012
Year: 2012

It is well known that opportunistic scheduling algorithms are throughput optimal under full knowledge of channel and network conditions. However, these algorithms achieve a hypothetical achievable rate region which does not take into account the overhead associated with channel probing and feedback required to obtain the full channel state information at every slot. We adopt a channel probing model where $β$ fraction of time slot is consumed for acquiring the channel state information (CSI) of a single channel. In this work, we design a joint scheduling and channel probing algorithm named SDF by considering the overhead of obtaining the channel state information. We first analytically prove SDF algorithm can support $1+ε$ fraction of of the full rate region achieved when all users are probed where $ε$ depends on the expected number of users which are not probed. Then, for homogenous channel, we show that when the number of users in the network is greater than 3, $ε> 0$, i.e., we guarantee to expand the rate region. In addition, for heterogenous channels, we prove the conditions under which SDF guarantees to increase the rate region. We also demonstrate numerically in a realistic simulation setting that this rate region can be achieved by probing only less than 50% of all channels in a CDMA based cellular network utilizing high data rate protocol under normal channel conditions.
Agent-time Epistemics and Coordination
Venue: arXiv cs.MA 2012
Year: 2012

A minor change to the standard epistemic logical language, replacing $K_{i}$ with $K_{\node{i,t}}$ where $t$ is a time instance, gives rise to a generalized and more expressive form of knowledge and common knowledge operators. We investigate the communication structures that are necessary for such generalized epistemic states to arise, and the inter-agent coordination tasks that require such knowledge. Previous work has established a relation between linear event ordering and nested knowledge, and between simultaneous event occurrences and common knowledge. In the new, extended, formalism, epistemic necessity is decoupled from temporal necessity. Nested knowledge and event ordering are shown to be related even when the nesting order does not match the temporal order of occurrence. The generalized form of common knowledge does {\em not} correspond to simultaneity. Rather, it corresponds to a notion of tight coordination, of which simultaneity is an instance.
Modeling of Mixed Decision Making Process
Venue: arXiv cs.AI 2012
Year: 2012

Decision making whenever and wherever it is happened is key to organizations success. In order to make correct decision, individuals, teams and organizations need both knowledge management (to manage content) and collaboration (to manage group processes) to make that more effective and efficient. In this paper, we explain the knowledge management and collaboration convergence. Then, we propose a formal description of mixed and multimodal decision making (MDM) process where decision may be made by three possible modes: individual, collective or hybrid. Finally, we explicit the MDM process based on UML-G profile.
A Novel Fault Detection Approach combining Adaptive Thresholding and Fuzzy Reasoning
Venue: arXiv cs.SY 2012
Year: 2012

Fault detection methods have their pros and cons. Thus, it is possible that some methods can complement each other and offer consequently better diagnostic systems. The integration of various characteristics is a way to develop "hybrid" systems to overcome the limitations of individual strategies of each method. In this paper a novel detection module combining the use of adaptive threshold and fuzzy logic reasoning inspired by the Evsukoff's approach is proposed in order to reduce the rate of false alarms, guarantee more robustness to disturbances and assist the operator in making decisions. The proposed approach can be used in case of multiple faults detection. This approach is applied to a benchmark in diagnosis domain: the three-tank system. The results of the proposed detection module are then presented through a gradual palette of colors in the graphical interface of the system.
Achieving Consensus with Individual Centrality Approach
Venue: arXiv cs.SI 2012
Year: 2012

This paper proposes a new consensus model in participatory decision making. The model employs advice centrality approach by electing a leader and recommender named as Supra Decision Maker (SDM). A SDM has a role as a decision bench-marker to other decision makers in evaluating each alternative with respect to given criteria. The weighting value for each alternative can be obtained by considering consensus level and preferences' distances between SDM and other Decision Makers. A social function using Social Judgment Scheme (SJS) concept is employed when a decision does not achieve the required consensus level. A simple example is presented here to illustrate our model. Keywords: Consensus, Group decision making, Centrality, Supra Decision Maker, Social Judgment Scheme
Self-Healing by Means of Runtime Execution Profiling
Venue: arXiv cs.SE 2012
Year: 2012

A self-healing application brings itself into a stable state after a failure put the software into an unstable state. For such self-healing software application, finding fix for a previously unseen fault is a grand challenge. Asking the user to provide fixes for every fault is bad for productivity, especially when the users are non-savvy in technical aspect of computing. If failure scenarios come into existence, the user wants the runtime environment to handle those situations autonomically. This paper presents a new technique of finding self-healing actions by matching a fault scenario to already established fault models. By profiling and capturing runtime parameters and execution pathWays, stable execution models are established and later are used to match with an unstable execution scenario. Experimentation and results are presented that showed that even with additional overheads; this technique can prove beneficial for autonomically healing faults and reliving system administrators from mundane troubleshooting situations.