OpenRaiser/Intern-Atlas huggingface dataset:
The Multi-shop Ski Rental Problem
Venue: arXiv cs.GT 2014
Year: 2014

We consider the {\em multi-shop ski rental} problem. This problem generalizes the classic ski rental problem to a multi-shop setting, in which each shop has different prices for renting and purchasing a pair of skis, and a \emph{consumer} has to make decisions on when and where to buy. We are interested in the {\em optimal online (competitive-ratio minimizing) mixed strategy} from the consumer's perspective. For our problem in its basic form, we obtain exciting closed-form solutions and a linear time algorithm for computing them. We further demonstrate the generality of our approach by investigating three extensions of our basic problem, namely ones that consider costs incurred by entering a shop or switching to another shop. Our solutions to these problems suggest that the consumer must assign positive probability in \emph{exactly one} shop at any buying time. Our results apply to many real-world applications, ranging from cost management in \texttt{IaaS} cloud to scheduling in distributed computing.
Transaction Handling in COM, EJB and .NET
Venue: arXiv cs.SE 2014
Year: 2014

The technology evolution has shown a very impressive performance in the last years by introducing several technologies that are based on the concept of component. As time passes, new versions of Component- Based technologies are released in order to improve services provided by previous ones. One important issue that regards these technologies is transactional activity. Transactions are important because they consist in sending different small amounts of information collected properly in a single combined unit which makes the process simpler, less expensive and also improves the reliability of the whole system, reducing its chances to go through possible failures. Different Component-Based technologies offer different ways of handling transactions. In this paper, we will review and discuss how transactions are handled in three of them: COM, EJB and .NET. It can be expected that .NET offers more efficient mechanisms due to the fact of being released later than the other two technologies. Nevertheless, COM and EJB are still present in the market and their services are still widely used. Comparing transaction handling in these technologies will be helpful to analyze the advantages and disadvantages of each of them. This comparison and evaluation will be seen in two main perspectives: performance and security.
Multiprocessor Scheduling of Dependent Tasks to Minimize Makespan and Reliability Cost Using NSGA-II
Venue: arXiv cs.DC 2014
Year: 2014

Algorithms developed for scheduling applications on heterogeneous multiprocessor system focus on asingle objective such as execution time, cost or total data transmission time. However, if more than oneobjective (e.g. execution cost and time, which may be in conflict) are considered, then the problem becomes more challenging. This project is proposed to develop a multiobjective scheduling algorithm using Evolutionary techniques for scheduling a set of dependent tasks on available resources in a multiprocessor environment which will minimize the makespan and reliability cost. A Non-dominated sorting Genetic Algorithm-II procedure has been developed to get the pareto- optimal solutions. NSGA-II is a Elitist Evolutionary algorithm, and it takes the initial parental solution without any changes, in all iteration to eliminate the problem of loss of some pareto-optimal solutions.NSGA-II uses crowding distance concept to create a diversity of the solutions.
Algorithm For Multi-Hand Finger Counting: An Easy Approach
Venue: arXiv cs.HC 2014
Year: 2014

In this paper we propose an easy algorithm for real time hand finger counting involving one or more than one hand. Hand finger counting is a simple medium for Human-Computer Interface which can prove to be a convenient input method for driving interactive menus, small applications and interactive games. Here, we also calculate the orientation of the hand which can be used to provide inputs for the direction and/or speed control of a robot, controlling mouse cursor or slide-show presentations. If being used by a single person, with his or her two hands, the person can trigger ten different commands with fingers in addition to the orientation of the hand. We tried to use very simple algorithm using very basic mathematics of 2D coordinate geometry and avoided the conventional use of calculus, contours and convex hull. Anyone seeking for an easy to implement hand finger counting algorithm can refer to it.
Approximate controllability and lack of controllability to zero of the heat equation with memory
Venue: arXiv cs.SY 2014
Year: 2014

In this paper we consider the heat equation with memory in a bounded region $Ω\subset\mathbb{R}^d$, $d\geq 1$, in the case that the propagation speed of the signal is infinite (i.e. the Colemann-Gurtin model). The memory kernel is of class $C^1$. We examine its controllability properties both under the action of boundary controls or when the controls are distributed in a subregion of $Ω$. We prove approximate controllability of the system and, in contrast with this, we prove the existence of initial conditions which cannot be steered to hit the target $0$ in a certain time $T$, of course when the memory kernel is not identically zero. In both the cases we derive our results from well known properties of the heat equation.
Decoding of Quasi-Cyclic Codes up to A New Lower Bound on the Minimum Distance
Venue: arXiv cs.IT 2014
Year: 2014

A new lower bound on the minimum Hamming distance of linear quasi-cyclic codes over finite fields is proposed. It is based on spectral analysis and generalizes the Semenov- Trifonov bound in a similar way as the Hartmann-Tzeng bound extends the BCH approach for cyclic codes. Furthermore, a syndrome-based algebraic decoding algorithm is given.
A Joint Optimization of Operational Cost and Performance Interference in Cloud Data Centers
Venue: arXiv cs.DC 2014
Year: 2014

Virtual machine (VM) scheduling is an important technique to efficiently operate the computing resources in a data center. Previous work has mainly focused on consolidating VMs to improve resource utilization and thus to optimize energy consumption. However, the interference between collocated VMs is usually ignored, which can result in very worse performance degradation to the applications running in those VMs due to the contention of the shared resources. Based on this observation, we aim at designing efficient VM assignment and scheduling strategies where we consider optimizing both the operational cost of the data center and the performance degradation of running applications and then, we propose a general model which captures the inherent tradeoff between the two contradictory objectives. We present offline and online solutions for this problem by exploiting the spatial and temporal information of VMs where VM scheduling is done by jointly consider the combinations and the life-cycle overlapping of the VMs. Evaluation results show that the proposed methods can generate efficient schedules for VMs, achieving low operational cost while significantly reducing the performance degradation of applications in cloud data centers.
Overview of Stemming Algorithms for Indian and Non-Indian Languages
Venue: arXiv cs.CL 2014
Year: 2014

Stemming is a pre-processing step in Text Mining applications as well as a very common requirement of Natural Language processing functions. Stemming is the process for reducing inflected words to their stem. The main purpose of stemming is to reduce different grammatical forms / word forms of a word like its noun, adjective, verb, adverb etc. to its root form. Stemming is widely uses in Information Retrieval system and reduces the size of index files. We can say that the goal of stemming is to reduce inflectional forms and sometimes derivationally related forms of a word to a common base form. In this paper we have discussed different stemming algorithm for non-Indian and Indian language, methods of stemming, accuracy and errors.
Substrate integrated waveguide power divider, circulator and coupler in [10-15] GHz band
Venue: arXiv cs.OH 2014
Year: 2014

The Substrate Integrated Waveguide (SIW) technology is an attractive approach for the design of high performance microwave and millimeter wave components, as it combines the advantages of planar technology, such as low fabrication costs, with the low loss inherent to the waveguide solution. In this study, a substrate integrated waveguide power divider, circulator and coupler are conceived and optimized in [10-15] GHz band by Ansoft HFSS code. Thus, results of this modeling are presented, discussed and allow to integrate these devices in planar circuits.
Thoughts on a Recursive Classifier Graph: a Multiclass Network for Deep Object Recognition
Venue: arXiv cs.CV 2014
Year: 2014

We propose a general multi-class visual recognition model, termed the Classifier Graph, which aims to generalize and integrate ideas from many of today's successful hierarchical recognition approaches. Our graph-based model has the advantage of enabling rich interactions between classes from different levels of interpretation and abstraction. The proposed multi-class system is efficiently learned using step by step updates. The structure consists of simple logistic linear layers with inputs from features that are automatically selected from a large pool. Each newly learned classifier becomes a potential new feature. Thus, our feature pool can consist both of initial manually designed features as well as learned classifiers from previous steps (graph nodes), each copied many times at different scales and locations. In this manner we can learn and grow both a deep, complex graph of classifiers and a rich pool of features at different levels of abstraction and interpretation. Our proposed graph of classifiers becomes a multi-class system with a recursive structure, suitable for deep detection and recognition of several classes simultaneously.
Algorithms for Packet Routing in Switching Networks with Reconfiguration Overhead
Venue: arXiv cs.NI 2014
Year: 2014

Given a set of messages to be transmitted in packages from a set of sending stations to a set of receiving stations, we are required to schedule the packages so as to achieve the minimum possible time from the moment the 1st transmission initiates to the concluding of the last. Preempting packets in order to reroute message remains, as part of some other packet to be transmitted at a later time would be a great means to achieve our goal, if not for the fact that each preemption will come with a reconfiguration cost that will delay our entire effort. The problem has been extensively studied in the past and various algorithms have been proposed to handle many variations of the problem. In this paper we propose an improved algorithm that we call the Split-Graph Algorithm (SGA). To establish its efficiency we compare it, to two of the algorithms developed in the past. These two are the best presented in bibliography so far, one in terms of approximation ratio and one in terms of experimental results.
On the Energy-Spectral Efficiency Trade-off of the MRC Receiver in Massive MIMO Systems with Transceiver Power Consumption
Venue: arXiv cs.IT 2014
Year: 2014

We consider the uplink of a multiuser massive MIMO system wherein a base station (BS) having $M$ antennas communicates coherently with $K$ single antenna user terminals (UTs). We study the energy efficiency of this system while taking the transceiver power consumption at the UTs and the BS into consideration. For a given spectral efficiency $R$ and fixed transceiver power consumption parameters, we propose and analyze the problem of maximizing the energy efficiency as a function of $(M,K)$. For the maximum ratio combining (MRC) detector at the BS we show that with increasing $R$, $(M,K)$ can be adaptively increased in such a way that the energy efficiency converges to a positive constant as $R \rightarrow \infty$ ($(M,K)$ is increased in such a way that a constant per-user spectral efficiency $R/K$ is maintained). This is in contrast to the fixed $(M,K)$ scenario where the energy efficiency is known to converge to zero as $R \rightarrow \infty$. We also observe that for large $R$, the optimal $(M,K)$ maximizing the energy efficiency is such that, the total power consumed by the power amplifiers (PA) in all the $K$ UTs is a small fraction of the total system power consumption.
Practical LDPC coded modulation schemes for the fading broadcast channel with confidential messages
Venue: arXiv cs.IT 2014
Year: 2014

The broadcast channel with confidential messages is a well studied scenario from the theoretical standpoint, but there is still lack of practical schemes able to achieve some fixed level of reliability and security over such a channel. In this paper, we consider a quasi-static fading channel in which both public and private messages must be sent from the transmitter to the receivers, and we aim at designing suitable coding and modulation schemes to achieve such a target. For this purpose, we adopt the error rate as a metric, by considering that reliability (security) is achieved when a sufficiently low (high) error rate is experienced at the receiving side. We show that some conditions exist on the system feasibility, and that some outage probability must be tolerated to cope with the fading nature of the channel. The proposed solution exploits low-density parity-check codes with unequal error protection, which are able to guarantee two different levels of protection against noise for the public and the private information, in conjunction with different modulation schemes for the public and the private message bits.
Distributed Local Linear Parameter Estimation using Gaussian SPAWN
Venue: arXiv cs.MA 2014
Year: 2014

We consider the problem of estimating local sensor parameters, where the local parameters and sensor observations are related through linear stochastic models. Sensors exchange messages and cooperate with each other to estimate their own local parameters iteratively. We study the Gaussian Sum-Product Algorithm over a Wireless Network (gSPAWN) procedure, which is based on belief propagation, but uses fixed size broadcast messages at each sensor instead. Compared with the popular diffusion strategies for performing network parameter estimation, whose communication cost at each sensor increases with increasing network density, the gSPAWN algorithm allows sensors to broadcast a message whose size does not depend on the network size or density, making it more suitable for applications in wireless sensor networks. We show that the gSPAWN algorithm converges in mean and has mean-square stability under some technical sufficient conditions, and we describe an application of the gSPAWN algorithm to a network localization problem in non-line-of-sight environments. Numerical results suggest that gSPAWN converges much faster in general than the diffusion method, and has lower communication costs, with comparable root mean square errors.
A Signal Processor for Gaussian Message Passing
Venue: arXiv cs.AR 2014
Year: 2014

In this paper, we present a novel signal processing unit built upon the theory of factor graphs, which is able to address a wide range of signal processing algorithms. More specifically, the demonstrated factor graph processor (FGP) is tailored to Gaussian message passing algorithms. We show how to use a highly configurable systolic array to solve the message update equations of nodes in a factor graph efficiently. A proper instruction set and compilation procedure is presented. In a recursive least squares channel estimation example we show that the FGP can compute a message update faster than a state-ofthe- art DSP. The results demonstrate the usabilty of the FGP architecture as a flexible HW accelerator for signal-processing and communication systems.
Pagination: It's what you say, not how long it takes to say it
Venue: arXiv cs.CL 2014
Year: 2014

Pagination - the process of determining where to break an article across pages in a multi-article layout is a common layout challenge for most commercially printed newspapers and magazines. To date, no one has created an algorithm that determines a minimal pagination break point based on the content of the article. Existing approaches for automatic multi-article layout focus exclusively on maximizing content (number of articles) and optimizing aesthetic presentation (e.g., spacing between articles). However, disregarding the semantic information within the article can lead to overly aggressive cutting, thereby eliminating key content and potentially confusing the reader, or setting too generous of a break point, thereby leaving in superfluous content and making automatic layout more difficult. This is one of the remaining challenges on the path from manual layouts to fully automated processes that still ensure article content quality. In this work, we present a new approach to calculating a document minimal break point for the task of pagination. Our approach uses a statistical language model to predict minimal break points based on the semantic content of an article. We then compare 4 novel candidate approaches, and 4 baselines (currently in use by layout algorithms). Results from this experiment show that one of our approaches strongly outperforms the baselines and alternatives. Results from a second study suggest that humans are not able to agree on a single "best" break point. Therefore, this work shows that a semantic-based lower bound break point prediction is necessary for ideal automated document synthesis within a real-world context.
Optimal Rendezvous Strategies for Different Environments in Cognitive Radio Networks
Venue: arXiv cs.NI 2014
Year: 2014

In Cognitive Radio Networks (CRNs), the secondary users (SUs) are allowed to access the licensed channels opportunistically. A fundamental and essential operation for SUs is to establish communication through choosing a common channel at the same time slot, which is referred to as rendezvous problem. In this paper, we study strategies to achieve fast rendezvous for two secondary users. The channel availability for secondary nodes is subject to temporal and spatial variation. Moreover, in a distributed system, one user is oblivious of the other user's channel status. Therefore, a fast rendezvous is not trivial. Recently, a number of rendezvous strategies have been proposed for different system settings, but rarely have they taken the temporal variation of the channels into account. In this work, we first derive a time-adaptive strategy with optimal expected time-to-rendezvous (TTR) for synchronous systems in stable environments, where channel availability is assumed to be static over time. Next, in dynamic environments, which better represent temporally dynamic channel availability in CRNs, we first derive optimal strategies for two special cases, and then prove that our strategy is still asymptotically optimal in general dynamic cases. Numerous simulations are conducted to demonstrate the performance of our strategies, and validate the theoretical analysis. The impacts of different parameters on the TTR are also investigated, such as the number of channels, the channel open possibilities, the extent of the environment being dynamic, and the existence of an intruder.
An Ontology Oriented Architecture for Context Aware Services Adaptation
Venue: arXiv cs.SE 2014
Year: 2014

In the field of ubiquitous computing, a class of applications called context-aware services attracted great interest especially since the emergence of wireless technologies and mobile devices. Context-aware application can dynamically capture a range of information from its environment and this information represents a context, the application adapts its execution according to this context. An important challenge in ubiquitous computing is dealing with context. Ontologies presents the most promising instrument for context modeling and managing due to their high and formal expressiveness and the possibilities for applying ontology reasoning techniques. In this paper, we present an ontology based approach for the development of context aware services.
Efficient Inference and Learning in a Large Knowledge Base: Reasoning with Extracted Information using a Locally Groundable First-Order Probabilistic Logic
Venue: arXiv cs.AI 2014
Year: 2014

One important challenge for probabilistic logics is reasoning with very large knowledge bases (KBs) of imperfect information, such as those produced by modern web-scale information extraction systems. One scalability problem shared by many probabilistic logics is that answering queries involves "grounding" the query---i.e., mapping it to a propositional representation---and the size of a "grounding" grows with database size. To address this bottleneck, we present a first-order probabilistic language called ProPPR in which that approximate "local groundings" can be constructed in time independent of database size. Technically, ProPPR is an extension to stochastic logic programs (SLPs) that is biased towards short derivations; it is also closely related to an earlier relational learning algorithm called the path ranking algorithm (PRA). We show that the problem of constructing proofs for this logic is related to computation of personalized PageRank (PPR) on a linearized version of the proof space, and using on this connection, we develop a proveably-correct approximate grounding scheme, based on the PageRank-Nibble algorithm. Building on this, we develop a fast and easily-parallelized weight-learning algorithm for ProPPR. In experiments, we show that learning for ProPPR is orders magnitude faster than learning for Markov logic networks; that allowing mutual recursion (joint learning) in KB inference leads to improvements in performance; and that ProPPR can learn weights for a mutually recursive program with hundreds of clauses, which define scores of interrelated predicates, over a KB containing one million entities.
An Approach for Computing Dynamic Slice of Concurrent Aspect-Oriented Programs
Venue: arXiv cs.SE 2014
Year: 2014

We propose a dynamic slicing algorithm to compute the slice of concurrent aspect-oriented programs. We use a dependence based intermediate program representation called Concurrent Aspect-oriented System Dependence Graph (CASDG) to represent a concurrent aspect-oriented program. The CASDG of an aspect-oriented program consists of a system dependence graph (SDG) for the non-aspect code, a group of dependence graphs for aspect code and some additional dependence edges used to connect the system dependence graph for the non-aspect code to dependence graph for aspect code. The proposed dynamic slicing al-gorithm is an extended version of NMDS algorithm for concurrent object-oriented programs, which is based on marking and unmarking of the executed nodes in CASDG appropriately during run-time.
Annotated imports
Venue: arXiv cs.PL 2014
Year: 2014

Presented simple extensions to scala language related to import statements: exported imports, which provide ability to reuse sequence of import clauses in composable form and default rewriters, which provide mechanism for pluggable macro-based AST transformation of overall compilation unit, activated by import of library object. Using these facilities not only allows more compact code, it prevents application programmer from producing certain type of errors too and allows to implement local language extension as libraries on top of standard compiler. Part of discussed extensions is submitted to scala language committee as pre-sip \cite{ai-presip} and can be used as first step for refining imports semantics in the future version of scala language.