OpenRaiser/Intern-Atlas huggingface dataset:
Performance Evaluation of Edge-Directed Interpolation Methods for Images
Venue: arXiv cs.CV 2013
Year: 2013

Many interpolation methods have been developed for high visual quality, but fail for inability to preserve image structures. Edges carry heavy structural information for detection, determination and classification. Edge-adaptive interpolation approaches become a center of focus. In this paper, performance of four edge-directed interpolation methods comparing with two traditional methods is evaluated on two groups of images. These methods include new edge-directed interpolation (NEDI), edge-guided image interpolation (EGII), iterative curvature-based interpolation (ICBI), directional cubic convolution interpolation (DCCI) and two traditional approaches, bi-linear and bi-cubic. Meanwhile, no parameters are mentioned to measure edge-preserving ability of edge-adaptive interpolation approaches and we proposed two. One evaluates accuracy and the other measures robustness of edge-preservation ability. Performance evaluation is based on six parameters. Objective assessment and visual analysis are illustrated and conclusions are drawn from theoretical backgrounds and practical results.
Web Service Interface for Data Collection
Venue: arXiv cs.CY 2013
Year: 2013

Data collection is a key component of an information system. The widespread penetration of ICT tools in organizations and institutions has resulted in a shift in the way the data is collected. Data may be collected in printed-form, by e-mails, on a compact disk, or, by direct upload on the management information system. Since web services are platform-independent, it can access data stored in the XML format from any platform. In this paper, we present an interface which uses web services for data collection. It requires interaction between a web service deployed for the purposes of data collection, and the web address where the data is stored. Our interface requires that the web service has pre-knowledge of the address from where the data is to be collected. Also, the data to be accessed must be stored in XML format. Since our interface uses computer-supported interaction on both sides, it eases the task of regular and ongoing data collection. We apply our framework to the Education Management Information System, which collects data from schools spread across the country.
Exploiting Opportunistic Physical Design in Large-scale Data Analytics
Venue: arXiv cs.DB 2013
Year: 2013

Large-scale systems, such as MapReduce and Hadoop, perform aggressive materialization of intermediate job results in order to support fault tolerance. When jobs correspond to exploratory queries submitted by data analysts, these materializations yield a large set of materialized views that typically capture common computation among successive queries from the same analyst, or even across queries of different analysts who test similar hypotheses. We propose to treat these views as an opportunistic physical design and use them for the purpose of query optimization. We develop a novel query-rewrite algorithm that addresses the two main challenges in this context: how to search the large space of rewrites, and how to reason about views that contain UDFs (a common feature in large-scale data analytics). The algorithm, which provably finds the minimum-cost rewrite, is inspired by nearest-neighbor searches in non-metric spaces. We present an extensive experimental study on real-world datasets with a prototype data-analytics system based on Hive. The results demonstrate that our approach can result in dramatic performance improvements on complex data-analysis queries, reducing total execution time by an average of 61% and up to two orders of magnitude.
Dynamic Provisioning in Next-Generation Data Centers with On-site Power Production
Venue: arXiv cs.DS 2013
Year: 2013

The critical need for clean and economical sources of energy is transforming data centers that are primarily energy consumers to also energy producers. We focus on minimizing the operating costs of next-generation data centers that can jointly optimize the energy supply from on-site generators and the power grid, and the energy demand from servers as well as power conditioning and cooling systems. We formulate the cost minimization problem and present an offline optimal algorithm. For "on-grid" data centers that use only the grid, we devise a deterministic online algorithm that achieves the best possible competitive ratio of $2-α_{s}$, where $α_{s}$ is a normalized look-ahead window size. For "hybrid" data centers that have on-site power generation in addition to the grid, we develop an online algorithm that achieves a competitive ratio of at most \textmd{\normalsize {\small $\frac{P_{\max} (2-α_{s})}{c_{o}+c_{m}/L} [1+2\frac{P_{\max}-c_{o}}{P_{\max}(1+α_{g})}]$}}, where $α_{s}$ and $α_{g}$ are normalized look-ahead window sizes, $P_{\max}$ is the maximum grid power price, and $L$, $c_{o}$, and $c_{m}$ are parameters of an on-site generator. Using extensive workload traces from Akamai with the corresponding grid power prices, we simulate our offline and online algorithms in a realistic setting. Our offline (resp., online) algorithm achieves a cost reduction of 25.8% (resp., 20.7%) for a hybrid data center and 12.3% (resp., 7.3%) for an on-grid data center. The cost reductions are quite significant and make a strong case for a joint optimization of energy supply and energy demand in a data center. A hybrid data center provides about 13% additional cost reduction over an on-grid data center representing the additional cost benefits that on-site power generation provides over using the grid alone.
Enumerating Some Fractional Repetition Codes
Venue: arXiv cs.IT 2013
Year: 2013

In a distributed storage systems (DSS), regenerating codes are used to optimize bandwidth in the repair process of a failed node. To optimize other DSS parameters such as computation and disk I/O, Distributed Replication-based Simple Storage (Dress) Codes consisting of an inner Fractional Repetition (FR) code and an outer MDS code are commonly used. Thus constructing FR codes is an important research problem, and several constructions using graphs and designs have been proposed. In this paper, we present an algorithm for constructing the node-packet distribution matrix of FR codes and thus enumerate some FR codes up to a given number of nodes n. We also present algorithms for constructing regular graphs which give rise to FR codes.
The performance of locality-aware topologies for peer-to-peer live streaming
Venue: arXiv cs.NI 2013
Year: 2013

This paper is concerned with the effect of overlay network topology on the performance of live streaming peer-to-peer systems. The paper focuses on the evaluation of topologies which are aware of the delays experienced between different peers on the network. Metrics are defined which assess the topologies in terms of delay, bandwidth usage and resilience to peer drop-out. Several topology creation algorithms are tested and the metrics are measured in a simple simulation testbed. This gives an assessment of the type of gains which might be expected from locality awareness in peer-to-peer networks.
Deterministic and Stochastic Approaches to Supervisory Control Design for Networked Systems with Time-Varying Communication Delays
Venue: arXiv cs.SY 2013
Year: 2013

This paper proposes a supervisory control structure for networked systems with time-varying delays. The control structure, in which a supervisor triggers the most appropriate controller from a multi-controller unit, aims at improving the closed-loop performance relative to what can be obtained using a single robust controller. Our analysis considers average dwell-time switching and is based on a novel multiple Lyapunov-Krasovskii functional. We develop stability conditions that can be verified by semi-definite programming, and show that the associated state feedback synthesis problem also can be solved using convex optimization tools. Extensions of the analysis and synthesis procedures to the case when the evolution of the delay mode is described by a Markov chain are also developed. Simulations on small and large-scale networked control systems are used to illustrate the effectiveness of our approach.
Minimum Energy Source Coding for Asymmetric Modulation with Application to RFID
Venue: arXiv cs.IT 2013
Year: 2013

Minimum energy (ME) source coding is an effective technique for efficient communication with energy-constrained devices, such as sensor network nodes. In this paper, the principles of generalized ME source coding is developed that is broadly applicable. Two scenarios - fixed and variable length codewords - are analyzed. The application of this technique to RFID systems where ME source coding is particularly advantageous due to the asymmetric nature of data communications is demonstrated, a first to the best of our knowledge.
Wireless Broadcast with Physical-Layer Network Coding
Venue: arXiv cs.IT 2013
Year: 2013

This work investigates the maximum broadcast throughput and its achievability in multi-hop wireless networks with half-duplex node constraint. We allow the use of physical-layer network coding (PNC). Although the use of PNC for unicast has been extensively studied, there has been little prior work on PNC for broadcast. Our specific results are as follows: 1) For single-source broadcast, the theoretical throughput upper bound is n/(n+1), where n is the "min vertex-cut" size of the network. 2) In general, the throughput upper bound is not always achievable. 3) For grid and many other networks, the throughput upper bound n/(n+1) is achievable. Our work can be considered as an attempt to understand the relationship between max-flow and min-cut in half-duplex broadcast networks with cycles (there has been prior work on networks with cycles, but not half-duplex broadcast networks).
#Bigbirds Never Die: Understanding Social Dynamics of Emergent Hashtag
Venue: arXiv cs.SI 2013
Year: 2013

We examine the growth, survival, and context of 256 novel hashtags during the 2012 U.S. presidential debates. Our analysis reveals the trajectories of hashtag use fall into two distinct classes: "winners" that emerge more quickly and are sustained for longer periods of time than other "also-rans" hashtags. We propose a "conversational vibrancy" framework to capture dynamics of hashtags based on their topicality, interactivity, diversity, and prominence. Statistical analyses of the growth and persistence of hashtags reveal novel relationships between features of this framework and the relative success of hashtags. Specifically, retweets always contribute to faster hashtag adoption, replies extend the life of "winners" while having no effect on "also-rans." This is the first study on the lifecycle of hashtag adoption and use in response to purely exogenous shocks. We draw on theories of uses and gratification, organizational ecology, and language evolution to discuss these findings and their implications for understanding social influence and collective action in social media more generally.
Usage-based vs. Citation-based Methods for Recommending Scholarly Research Articles
Venue: arXiv cs.DL 2013
Year: 2013

There are two principal data sources for collaborative filtering recommenders in scholarly digital libraries: usage data obtained from harvesting a large, distributed collection of Open URL web logs and citation data obtained from the journal articles. This study explores the characteristics of recommendations generated by implementations of these two methods: the 'bX' system by ExLibris and an experimental citation-based recommender, Sarkanto. Recommendations from each system were compared according to their semantic similarity to the seed article that was used to generate them. Since the full text of the articles was not available for all the recommendations in both systems, the semantic similarity between the seed article and the recommended articles was deemed to be the semantic distance between the journals in which the articles were published. The semantic distance between journals was computed from the "semantic vectors" distance between all the terms in the full-text of the available articles in that journal and this study shows that citation-based recommendations are more semantically diverse than usage-based ones. These recommenders are complementary since most of the time, when one recommender produces recommendations the other does not.
Upper-bounding $\ell_1$-optimization weak thresholds
Venue: arXiv cs.IT 2013
Year: 2013

In our recent work \cite{StojnicCSetam09} we considered solving under-determined systems of linear equations with sparse solutions. In a large dimensional and statistical context we proved that if the number of equations in the system is proportional to the length of the unknown vector then there is a sparsity (number of non-zero elements of the unknown vector) also proportional to the length of the unknown vector such that a polynomial $\ell_1$-optimization technique succeeds in solving the system. We provided lower bounds on the proportionality constants that are in a solid numerical agreement with what one can observe through numerical experiments. Here we create a mechanism that can be used to derive the upper bounds on the proportionality constants. Moreover, the upper bounds obtained through such a mechanism match the lower bounds from \cite{StojnicCSetam09} and ultimately make the latter ones optimal.
Symmetries in Modal Logics
Venue: arXiv cs.LO 2013
Year: 2013

We generalize the notion of symmetries of propositional formulas in conjunctive normal form to modal formulas. Our framework uses the coinductive models and, hence, the results apply to a wide class of modal logics including, for example, hybrid logics. Our main result shows that the symmetries of a modal formula preserve entailment.
A weak HOAS approach to the POPLmark Challenge
Venue: arXiv cs.LO 2013
Year: 2013

Capitalizing on previous encodings and formal developments about nominal calculi and type systems, we propose a weak Higher-Order Abstract Syntax formalization of the type language of pure System F<: within Coq, a proof assistant based on the Calculus of Inductive Constructions. Our encoding allows us to accomplish the proof of the transitivity property of algorithmic subtyping, which is in fact the first of the three tasks stated by the POPLmark Challenge, a set of problems that capture the most critical issues in formalizing programming language metatheory.
Sequent Calculi for the classical fragment of Bochvar and Halldén's Nonsense Logics
Venue: arXiv cs.LO 2013
Year: 2013

In this paper sequent calculi for the classical fragment (that is, the conjunction-disjunction-implication-negation fragment) of the nonsense logics B3, introduced by Bochvar, and H3, introduced by Halldén, are presented. These calculi are obtained by restricting in an appropriate way the application of the rules of a sequent calculus for classical propositional logic CPL. The nice symmetry between the provisos in the rules reveal the semantical relationship between these logics. The Soundness and Completeness theorems for both calculi are obtained, as well as the respective Cut elimination theorems.
A Graph Calculus for Predicate Logic
Venue: arXiv cs.LO 2013
Year: 2013

We introduce a refutation graph calculus for classical first-order predicate logic, which is an extension of previous ones for binary relations. One reduces logical consequence to establishing that a constructed graph has empty extension, i. e. it represents bottom. Our calculus establishes that a graph has empty extension by converting it to a normal form, which is expanded to other graphs until we can recognize conflicting situations (equivalent to a formula and its negation).
Holographaic Alogorithms on Bases of Rank 2
Venue: arXiv cs.CC 2013
Year: 2013

An essential problem in the design of holographic algorithms is to decide whether the required signatures can be realized by matchgates under a suitable basis transformation (SRP). For holographic algorithms on domain size 2, [1, 2, 4, 5] have built a systematical theory. In this paper, we reduce SRP on domain size k>2 to SRP on domain size 2 for holographic algorithms on bases of rank 2. Furthermore, we generalize the collapse theorem of [3] to domain size k>2.
Some results related to the conjecture by Belfiore and Solé
Venue: arXiv cs.IT 2013
Year: 2013

In the first part of the paper, we consider the relation between kissing number and the secrecy gain. We show that on an $n=24m+8k$-dimensional even unimodular lattice, if the shortest vector length is $\geq 2m$, then as the number of vectors of length $2m$ decreases, the secrecy gain increases. We will also prove a similar result on general unimodular lattices. We will also consider the situations with shorter vectors. Furthermore, assuming the conjecture by Belfiore and Solé, we will calculate the difference between inverses of secrecy gains as the number of vectors varies. We will show by an example that there exist two lattices in the same dimension with the same shortest vector length and the same kissing number, but different secrecy gains. Finally, we consider some cases of a question by Elkies by providing an answer for a special class of lattices assuming the conjecture of Belfiore and Solé. We will also get a conditional improvement on some Gaulter's results concerning the conjecture.
Optimality of $\ell_2/\ell_1$-optimization block-length dependent thresholds
Venue: arXiv cs.IT 2013
Year: 2013

The recent work of \cite{CRT,DonohoPol} rigorously proved (in a large dimensional and statistical context) that if the number of equations (measurements in the compressed sensing terminology) in the system is proportional to the length of the unknown vector then there is a sparsity (number of non-zero elements of the unknown vector) also proportional to the length of the unknown vector such that $\ell_1$-optimization algorithm succeeds in solving the system. In more recent papers \cite{StojnicCSetamBlock09,StojnicICASSP09block,StojnicJSTSP09} we considered under-determined systems with the so-called \textbf{block}-sparse solutions. In a large dimensional and statistical context in \cite{StojnicCSetamBlock09} we determined lower bounds on the values of allowable sparsity for any given number (proportional to the length of the unknown vector) of equations such that an $\ell_2/\ell_1$-optimization algorithm succeeds in solving the system. These lower bounds happened to be in a solid numerical agreement with what one can observe through numerical experiments. Here we derive the corresponding upper bounds. Moreover, the upper bounds that we obtain in this paper match the lower bounds from \cite{StojnicCSetamBlock09} and ultimately make them optimal.
Faster Algorithms for Markov Decision Processes with Low Treewidth
Venue: arXiv cs.DS 2013
Year: 2013

We consider two core algorithmic problems for probabilistic verification: the maximal end-component decomposition and the almost-sure reachability set computation for Markov decision processes (MDPs). For MDPs with treewidth $k$, we present two improved static algorithms for both the problems that run in time $O(n \cdot k^{2.38} \cdot 2^k)$ and $O(m \cdot \log n \cdot k)$, respectively, where $n$ is the number of states and $m$ is the number of edges, significantly improving the previous known $O(n\cdot k \cdot \sqrt{n\cdot k})$ bound for low treewidth. We also present decremental algorithms for both problems for MDPs with constant treewidth that run in amortized logarithmic time, which is a huge improvement over the previously known algorithms that require amortized linear time.
Development of a Device for Remote Monitoring of Heart Rate and Body Temperature
Venue: arXiv cs.OH 2013
Year: 2013

We present a new integrated, portable device to provide a convenient solution for remote monitoring heart rate at the fingertip and body temperature using Ethernet technology and widely spreading internet. Now a days, heart related disease is rising. Most of the times in these cases, patients may not realize their actual conditions and even it is a common fact that there are no doctors by their side, especially in rural areas, but now a days most of the diseases are curable if detected in time. We have tried to make a system which may give information about one's physical condition and help him or her to detect these deadly but curable diseases. The system gives information of heart rate and body temperature simultaneously acquired on the portable side in real time and transmits results to web. In this system, the condition of heart and body temperature can be monitored from remote places. Eventually, this device provides a low cost, easily accessible human health monitor solution bridging the gaps between patients and doctors.
Parallel Computation Is ESS
Venue: arXiv cs.LG 2013
Year: 2013

There are enormous amount of examples of Computation in nature, exemplified across multiple species in biology. One crucial aim for these computations across all life forms their ability to learn and thereby increase the chance of their survival. In the current paper a formal definition of autonomous learning is proposed. From that definition we establish a Turing Machine model for learning, where rule tables can be added or deleted, but can not be modified. Sequential and parallel implementations of this model are discussed. It is found that for general purpose learning based on this model, the implementations capable of parallel execution would be evolutionarily stable. This is proposed to be of the reasons why in Nature parallelism in computation is found in abundance.
Coauthorship and citation in scientific publishing
Venue: arXiv cs.DL 2013
Year: 2013

A large number of published studies have examined the properties of either networks of citation among scientific papers or networks of coauthorship among scientists. Here, using an extensive data set covering more than a century of physics papers published in the Physical Review, we study a hybrid coauthorship/citation network that combines the two, which we analyze to gain insight into the correlations and interactions between authorship and citation. Among other things, we investigate the extent to which individuals tend to cite themselves or their collaborators more than others, the extent to which they cite themselves or their collaborators more quickly after publication, and the extent to which they tend to return the favor of a citation from another scientist.
Event management for large scale event-driven digital hardware spiking neural networks
Venue: arXiv cs.NE 2013
Year: 2013

The interest in brain-like computation has led to the design of a plethora of innovative neuromorphic systems. Individually, spiking neural networks (SNNs), event-driven simulation and digital hardware neuromorphic systems get a lot of attention. Despite the popularity of event-driven SNNs in software, very few digital hardware architectures are found. This is because existing hardware solutions for event management scale badly with the number of events. This paper introduces the structured heap queue, a pipelined digital hardware data structure, and demonstrates its suitability for event management. The structured heap queue scales gracefully with the number of events, allowing the efficient implementation of large scale digital hardware event-driven SNNs. The scaling is linear for memory, logarithmic for logic resources and constant for processing time. The use of the structured heap queue is demonstrated on field-programmable gate array (FPGA) with an image segmentation experiment and a SNN of 65~536 neurons and 513~184 synapses. Events can be processed at the rate of 1 every 7 clock cycles and a 406$\times$158 pixel image is segmented in 200 ms.