OpenRaiser/Intern-Atlas huggingface dataset:
When Do Redundant Requests Reduce Latency ?
Venue: arXiv cs.NI 2013
Year: 2013

Several systems possess the flexibility to serve requests in more than one way. For instance, a distributed storage system storing multiple replicas of the data can serve a request from any of the multiple servers that store the requested data, or a computational task may be performed in a compute-cluster by any one of multiple processors. In such systems, the latency of serving the requests may potentially be reduced by sending "redundant requests": a request may be sent to more servers than needed, and it is deemed served when the requisite number of servers complete service. Such a mechanism trades off the possibility of faster execution of at least one copy of the request with the increase in the delay due to an increased load on the system. Due to this tradeoff, it is unclear when redundant requests may actually help. Several recent works empirically evaluate the latency performance of redundant requests in diverse settings. This work aims at an analytical study of the latency performance of redundant requests, with the primary goals of characterizing under what scenarios sending redundant requests will help (and under what scenarios they will not help), as well as designing optimal redundant-requesting policies. We first present a model that captures the key features of such systems. We show that when service times are i.i.d. memoryless or "heavier", and when the additional copies of already-completed jobs can be removed instantly, redundant requests reduce the average latency. On the other hand, when service times are "lighter" or when service times are memoryless and removal of jobs is not instantaneous, then not having any redundancy in the requests is optimal under high loads. Our results hold for arbitrary arrival processes.
Common Due-Date Problem: Exact Polynomial Algorithms for a Given Job Sequence
Venue: arXiv cs.DS 2013
Year: 2013

This paper considers the problem of scheduling jobs on single and parallel machines where all the jobs possess different processing times but a common due date. There is a penalty involved with each job if it is processed earlier or later than the due date. The objective of the problem is to find the assignment of jobs to machines, the processing sequence of jobs and the time at which they are processed, which minimizes the total penalty incurred due to tardiness or earliness of the jobs. This work presents exact polynomial algorithms for optimizing a given job sequence or single and parallel machines with the run-time complexities of $O(n \log n)$ and $O(mn^2 \log n)$ respectively, where $n$ is the number of jobs and $m$ the number of machines. The algorithms take a sequence consisting of all the jobs $(J_i, i=1,2,\dots,n)$ as input and distribute the jobs to machines (for $m>1$) along with their best completion times so as to get the least possible total penalty for this sequence. We prove the optimality for the single machine case and the runtime complexities of both. Henceforth, we present the results for the benchmark instances and compare with previous work for single and parallel machine cases, up to $200$ jobs.
Aircraft Landing Problem: Efficient Algorithm for a Given Landing Sequence
Venue: arXiv cs.DS 2013
Year: 2013

In this paper, we investigate a special case of the static aircraft landing problem (ALP) with the objective to optimize landing sequences and landing times for a set of air planes. The problem is to land the planes on one or multiple runways within a time window as close as possible to the preferable target landing time, maintaining a safety distance constraint. The objective of this well-known NP-hard optimization problem is to minimize the sum of the total penalty incurred by all the aircraft for arriving earlier or later than their preferred landing times. For a problem variant that optimizes a given feasible landing sequence for the single runway case, we present an exact polynomial algorithm and prove the run-time complexity to lie in $O(N^3)$, where $N$ is the number of aircraft. The proposed algorithm returns the optimal solution for the ALP for a given feasible landing sequence on a single runway for a common practical case of the ALP described in the paper. Furthermore, we propose a strategy for the ALP with multiple runways and present our results for all the benchmark instances with single and multiple runways, while comparing them to previous results in the literature.
Reinforcement Learning for Matrix Computations: PageRank as an Example
Venue: arXiv cs.LG 2013
Year: 2013

Reinforcement learning has gained wide popularity as a technique for simulation-driven approximate dynamic programming. A less known aspect is that the very reasons that make it effective in dynamic programming can also be leveraged for using it for distributed schemes for certain matrix computations involving non-negative matrices. In this spirit, we propose a reinforcement learning algorithm for PageRank computation that is fashioned after analogous schemes for approximate dynamic programming. The algorithm has the advantage of ease of distributed implementation and more importantly, of being model-free, i.e., not dependent on any specific assumptions about the transition probabilities in the random web-surfer model. We analyze its convergence and finite time behavior and present some supporting numerical experiments.
Exponential Stability of Homogeneous Positive Systems of Degree One With Time-Varying Delays
Venue: arXiv cs.SY 2013
Year: 2013

While the asymptotic stability of positive linear systems in the presence of bounded time delays has been thoroughly investigated, the theory for nonlinear positive systems is considerably less well-developed. This paper presents a set of conditions for establishing delay-independent stability and bounding the decay rate of a significant class of nonlinear positive systems which includes positive linear systems as a special case. Specifically, when the time delays have a known upper bound, we derive necessary and sufficient conditions for exponential stability of (a) continuous-time positive systems whose vector fields are homogeneous and cooperative, and (b) discrete-time positive systems whose vector fields are homogeneous and order preserving. We then present explicit expressions that allow us to quantify the impact of delays on the decay rate and show that the best decay rate of positive linear systems that our bounds provide can be found via convex optimization. Finally, we extend the results to general linear systems with time-varying delays.
A Misanthropic Reinterpretation of the Chinese Room Problem
Venue: arXiv cs.AI 2013
Year: 2013

The chinese room problem asks if computers can think; I ask here if most humans can.
A novel local search based on variable-focusing for random K-SAT
Venue: arXiv cs.AI 2013
Year: 2013

We introduce a new local search algorithm for satisfiability problems. Usual approaches focus uniformly on unsatisfied clauses. The new method works by picking uniformly random variables in unsatisfied clauses. A Variable-based Focused Metropolis Search (V-FMS) is then applied to random 3-SAT. We show that it is quite comparable in performance to the clause-based FMS. Consequences for algorithmic design are discussed.
Locality and applications to subsumption testing and interpolation in $\mathcal{EL}$ and some of its extensions
Venue: arXiv cs.LO 2013
Year: 2013

In this paper we show that subsumption problems in lightweight description logics (such as $\mathcal{EL}$ and $\mathcal{EL}^+$) can be expressed as uniform word problems in classes of semilattices with monotone operators. We use possibilities of efficient local reasoning in such classes of algebras, to obtain uniform PTIME decision procedures for CBox subsumption in $\mathcal{EL}$, $\mathcal{EL}^+$ and extensions thereof. These locality considerations allow us to present a new family of (possibly many-sorted) logics which extend $\mathcal{EL}$ and $\mathcal{EL}^+$ with $n$-ary roles and/or numerical domains. As a by-product, this allows us to show that the algebraic models of ${\cal EL}$ and ${\cal EL}^+$ have ground interpolation and thus that ${\cal EL}$, ${\cal EL}^+$, and their extensions studied in this paper have interpolation. We also show how these ideas can be used for the description logic $\mathcal{EL}^{++}$.
Learning Input and Recurrent Weight Matrices in Echo State Networks
Venue: arXiv cs.LG 2013
Year: 2013

Echo State Networks (ESNs) are a special type of the temporally deep network model, the Recurrent Neural Network (RNN), where the recurrent matrix is carefully designed and both the recurrent and input matrices are fixed. An ESN uses the linearity of the activation function of the output units to simplify the learning of the output matrix. In this paper, we devise a special technique that take advantage of this linearity in the output units of an ESN, to learn the input and recurrent matrices. This has not been done in earlier ESNs due to their well known difficulty in learning those matrices. Compared to the technique of BackPropagation Through Time (BPTT) in learning general RNNs, our proposed method exploits linearity of activation function in the output units to formulate the relationships amongst the various matrices in an RNN. These relationships results in the gradient of the cost function having an analytical form and being more accurate. This would enable us to compute the gradients instead of obtaining them by recursion as in BPTT. Experimental results on phone state classification show that learning one or both the input and recurrent matrices in an ESN yields superior results compared to traditional ESNs that do not learn these matrices, especially when longer time steps are used.
The Distributed Computing Paradigms: P2P, Grid, Cluster, Cloud, and Jungle
Venue: arXiv cs.DC 2013
Year: 2013

The distributed computing is done on many systems to solve a large scale problem. The growing of high-speed broadband networks in developed and developing countries, the continual increase in computing power, and the rapid growth of the Internet have changed the way. In it the society manages information and information services. Historically, the state of computing has gone through a series of platform and environmental changes. Distributed computing holds great assurance for using computer systems effectively. As a result, supercomputer sites and data centers have changed from providing high performance floating point computing capabilities to concurrently servicing huge number of requests from billions of users. The distributed computing system uses multiple computers to solve large-scale problems over the Internet. It becomes data-intensive and network-centric. The applications of distributed computing have become increasingly wide-spread. In distributed computing, the main stress is on the large scale resource sharing and always goes for the best performance. In this article, we have reviewed the work done in the area of distributed computing paradigms. The main stress is on the evolving area of cloud computing.
Java File Security System (JFSS)
Venue: arXiv cs.CR 2013
Year: 2013

Nowadays, storage systems are increasingly subject to attacks. So the security system is quickly becoming mendatory feature of the data storage systems. For the security purpose we are always dependent on the cryptography techniques. These techniques take the performance costs for the complete system. So we have proposed the Java File Security System(JFSS). It is based on the on-demand computing system concept, because of the performance issues. It is a greate comback for the system performance. The concept is used because, we are not always in need the secure the files, but the selected one only. In this paper, we have designed a file security system on Windows XP. When we use the operating system, we have to secure some important data. The date is always stored in the files, so we secure the important files well. To check the proposed functionality, we experiment the above said system on the Windows operating system. With these experiments, we have found that the proposed system is working properly, according to the needs of the users.
Smart: Semantically mashup rest web services
Venue: arXiv cs.OH 2013
Year: 2013

A mashup is a combination of information from more than one source, mixed up in a way to create something new, or at least useful. Anyone can find mashups on the internet, but these are always specifically designed for a predefined purpose. To change that fact, we implemented a new platform we called the SMART platform. SMART enables the user to make his own choices as for the REST web services he needs to call in order to build an intelligent personalized mashup, from a Google-like simple search interface, without needing any programming skills. In order to achieve this goal, we defined an ontology that can hold REST web services descriptions. These descriptions encapsulate mainly, the input type needed for a service, its output type, and the kind of relation that ties the input to the output. Then, by matching the user input query keywords, with the REST web services definitions in our ontology, we can find registered services individuals in this ontology, and construct the raw REST query for each service found. The wrap up from the keywords, into semantic definitions, in order to find the matching service individual, then the wrap down from the semantic service description of the found individual, to the raw REST call, and finally the wrap up of the result again into semantic individuals, is done for two main purposes: the first to let the user use simple keywords in order to build complex mashups, and the second to benefit from the ontology inference engine in a way, where services instances can be tied together into an intelligent mashup, simply by making each service output individuals, stand as the next service input.
Community detection thresholds and the weak Ramanujan property
Venue: arXiv cs.SI 2013
Year: 2013

Decelle et al.\cite{Decelle11} conjectured the existence of a sharp threshold for community detection in sparse random graphs drawn from the stochastic block model. Mossel et al.\cite{Mossel12} established the negative part of the conjecture, proving impossibility of meaningful detection below the threshold. However the positive part of the conjecture remained elusive so far. Here we solve the positive part of the conjecture. We introduce a modified adjacency matrix $B$ that counts self-avoiding paths of a given length $\ell$ between pairs of nodes and prove that for logarithmic $\ell$, the leading eigenvectors of this modified matrix provide non-trivial detection, thereby settling the conjecture. A key step in the proof consists in establishing a {\em weak Ramanujan property} of matrix $B$. Namely, the spectrum of $B$ consists in two leading eigenvalues $ρ(B)$, $λ_2$ and $n-2$ eigenvalues of a lower order $O(n^ε\sqrt{ρ(B)})$ for all $ε>0$, $ρ(B)$ denoting $B$'s spectral radius. $d$-regular graphs are Ramanujan when their second eigenvalue verifies $|λ|\le 2 \sqrt{d-1}$. Random $d$-regular graphs have a second largest eigenvalue $λ$ of $2\sqrt{d-1}+o(1)$ (see Friedman\cite{friedman08}), thus being {\em almost} Ramanujan. Erdős-Rényi graphs with average degree $d$ at least logarithmic ($d=Ω(\log n)$) have a second eigenvalue of $O(\sqrt{d})$ (see Feige and Ofek\cite{Feige05}), a slightly weaker version of the Ramanujan property. However this spectrum separation property fails for sparse ($d=O(1)$) Erdős-Rényi graphs. Our result thus shows that by constructing matrix $B$ through neighborhood expansion, we regularize the original adjacency matrix to eventually recover a weak form of the Ramanujan property.
Cryptanalysis of An Advanced Temporal Credential-Based Security Scheme with Mutual Authentication and Key Agreement for Wireless Sensor Networks
Venue: arXiv cs.CR 2013
Year: 2013

With the rapid advancement of wireless network technology, usage of WSN in real time applications like military, forest monitoring etc. found increasing. Generally WSN operate in an unattended environment and handles critical data. Authenticating the user trying to access the sensor memory is one of the critical requirements. Many researchers have proposed remote user authentication schemes focusing on various parameters. In 2013, Li et al. proposed a temporal-credential-based mutual authentication and key agreement scheme for WSNs. Li et al. claimed that their scheme is secure against all major cryptographic attacks and requires less computation cost due to usage of hash function instead encryption operations. Unfortunately, in this paper we will show that their scheme is vulnerable to offline password guessing attack, stolen smart card attack, leakage of password etc. and failure to provide data privacy.
Impact of Indentation in Programming
Venue: arXiv cs.PL 2013
Year: 2013

In computer programming languages, indentation formats program source code to improve readability. Programming languages make use of indentation to define program structure .Programmers use indentation to understand the structure of their programs to human readers. Especially, indentation is the better way to represent the relationship between control flow constructs such as selection statements or loops and code contained within and outside them. This paper describes about different indentation styles used in Programming and also describes context of each indentation style. It also describes indentation styles used for various programming constructs and the best practice for a particular programming construct. This paper helps the beginners to understand various indentation styles used in programming and also to choose suitable indentation style.
Comparative Study of Various VOIP Applications in 802.11a Wireless Network Scenario
Venue: arXiv cs.NI 2013
Year: 2013

Today, Voice over Wireless Local Area Network (VOWLAN) is the most accepted Internet application. There are a large number of literatures regarding the performance of various WLAN networks. Most of them focus on simulations and modeling, but there are also some experiments with real networks. This paper explains the comparison of performance of two different VOIP (Voice over Internet Protocol) applications over the same IEEE 802.11a wireless network. Radio link standard 802.11a have maximum transmission rate of 54Mbps. First protocol is session initiation protocol (SIP) and second is H.323 protocol. First one has an agent called SIP proxy. Second have a gateway reflects the characteristics of a Switched Circuit Network (SCN). With this comparison we have required to obtain a better understanding of wireless network suitability for voice communication in IP network.
Abstraction Level Taxonomy of Programming Language Frameworks
Venue: arXiv cs.PL 2013
Year: 2013

The main purpose of this article is to describe the taxonomy of computer languages according to the levels of abstraction. There exists so many computer languages because of so many reasons like the evolution of better computer languages over the time; the socio-economic factors as the proprietary interests, commercial advantages; expressive power; ease of use of novice; orientation toward special purposes; orientation toward special hardware; and diverse ideas about most suitability. Moreover, the important common properties of most of these languages are discussed here. No programming language is designed in a vacuity, but it solves some specific kinds of problems. There is a different framework for each problem and best suitable framework for each problem. A single framework is not best for all types of problems. So, it is important to select vigilantly the frameworks supported by the language. The five generation of the computer programming languages are explored in this paper to some extent.
Synthetic Data Generation using Benerator Tool
Venue: arXiv cs.DB 2013
Year: 2013

Datasets of different characteristics are needed by the research community for experimental purposes. However, real data may be difficult to obtain due to privacy concerns. Moreover, real data may not meet specific characteristics which are needed to verify new approaches under certain conditions. Given these limitations, the use of synthetic data is a viable alternative to complement the real data. In this report, we describe the process followed to generate synthetic data using Benerator, a publicly available tool. The results show that the synthetic data preserves a high level of accuracy compared to the original data. The generated datasets correspond to microdata containing records with social, economic and demographic data which mimics the distribution of aggregated statistics from the 2011 Irish Census data.
HINO: a BFO-aligned ontology representing human molecular interactions and pathways
Venue: arXiv cs.AI 2013
Year: 2013

Many database resources, such as Reactome, collect manually annotated reactions, interactions, and pathways from peer-reviewed publications. The interactors (e.g., a protein), interactions, and pathways in these data resources are often represented as instances in using BioPAX, a standard pathway data exchange format. However, these interactions are better represented as classes (or universals) since they always occur given appropriate conditions. This study aims to represent various human interaction pathways and networks as classes via a formal ontology aligned with the Basic Formal Ontology (BFO). Towards this goal, the Human Interaction Network Ontology (HINO) was generated by extending the BFO-aligned Interaction Network Ontology (INO). All human pathways and associated processes and interactors listed in Reactome and represented in BioPAX were first converted to ontology classes by aligning them under INO. Related terms and associated relations and hierarchies from external ontologies (e.g., CHEBI and GO) were also retrieved and imported into HINO. HINO ontology terms were resolved in the linked ontology data server Ontobee. The RDF triples stored in the RDF triple store are queryable through a SPARQL program. Such an ontology system supports advanced pathway data integration and applications.
Demographic and Structural Characteristics to Rationalize Link Formation in Online Social Networks
Venue: arXiv cs.SI 2013
Year: 2013

Recent years have seen tremendous growth of many online social networks such as Facebook, LinkedIn and MySpace. People connect to each other through these networks forming large social communities providing researchers rich datasets to understand, model and predict social interactions and behaviors. New contacts in these networks can be formed either due to an individual's demographic profile such as age group, gender, geographic location or due to network's structural dynamics such as triadic closure and preferential attachment, or a combination of both demographic and structural characteristics. A number of network generation models have been proposed in the last decade to explain the structure, evolution and processes taking place in different types of networks, and notably social networks. Network generation models studied in the literature primarily consider structural properties, and in some cases an individual's demographic profile in the formation of new social contacts. These models do not present a mechanism to combine both structural and demographic characteristics for the formation of new links. In this paper, we propose a new network generation algorithm which incorporates both these characteristics to model growth of a network.We use different publicly available Facebook datasets as benchmarks to demonstrate the correctness of the proposed network generation model.
Intuitionistic Neutrosophic Soft Set
Venue: arXiv cs.OH 2013
Year: 2013

In this paper we study the concept of intuitionistic neutrosophic set of Bhowmik and Pal. We have introduced this concept in soft sets and defined intuitionistic neutrosophic soft set. Some definitions and operations have been introduced on intuitionistic neutrosophic soft set. Some properties of this concept have been established.