OpenRaiser/Intern-Atlas huggingface dataset:
Low power-area designs of 1bit full adder in cadence virtuoso platform
Venue: arXiv cs.AR 2013
Year: 2013

Power consumption has emerged as a primary design constraint for integrated circuits (ICs). In the Nano meter technology regime, leakage power has become a major component of total power. Full adder is the basic functional unit of an ALU. The power consumption of a processor is lowered by lowering the power consumption of an ALU, and the power consumption of an ALU can be lowered by lowering the power consumption of Full adder. So the full adder designs with low power characteristics are becoming more popular these days. This proposed work illustrates the design of the low-power less transistor full adder designs using cadence tool and virtuoso platform, the entire simulations have been done on 180nm single n-well CMOS bulk technology, in virtuoso platform of cadence tool with the supply voltage 1.8V and frequency of 100MHz. These circuits consume less power with maximum (6T design)of 93.1% power saving compare to conventional 28T design and 80.2% power saving compare to SERF design without much delay degradation. The proposed circuit exploits the advantage of GDI technique and pass transistor logic
Implementation of nlization framework for verbs, pronouns and determiners with eugene
Venue: arXiv cs.CL 2013
Year: 2013

UNL system is designed and implemented by a nonprofit organization, UNDL Foundation at Geneva in 1999. UNL applications are application softwares that allow end users to accomplish natural language tasks, such as translating, summarizing, retrieving or extracting information, etc. Two major web based application softwares are Interactive ANalyzer (IAN), which is a natural language analysis system. It represents natural language sentences as semantic networks in the UNL format. Other application software is dEep-to-sUrface GENErator (EUGENE), which is an open-source interactive NLizer. It generates natural language sentences out of semantic networks represented in the UNL format. In this paper, NLization framework with EUGENE is focused, while using UNL system for accomplishing the task of machine translation. In whole NLization process, EUGENE takes a UNL input and delivers an output in natural language without any human intervention. It is language-independent and has to be parametrized to the natural language input through a dictionary and a grammar, provided as separate interpretable files. In this paper, it is explained that how UNL input is syntactically and semantically analyzed with the UNL-NL T-Grammar for NLization of UNL sentences involving verbs, pronouns and determiners for Punjabi natural language.
Interference Alignment with Diversity for the $2 \times 2$ $X$-Network with three antennas
Venue: arXiv cs.IT 2013
Year: 2013

Interference alignment is known to achieve the maximum sum DoF of $\frac{4M}{3}$ in the $2 \times 2$ $X$-Network (i.e., two-transmitter (Tx) two-receiver (Rx) $X$-Network) with $M$ antennas at each node, as demonstrated by Jafar and Shamai. Recently, an Alamouti code based transmission scheme, which we call the Li-Jafarkhani-Jafar (LJJ) scheme, was proposed for the $2 \times 2$ $X$-Network with two antennas at each node. This scheme achieves a sum degrees of freedom (DoF) of $\frac{8}{3}$ and also a diversity gain of two when fixed finite constellations are employed at each Tx. In the LJJ scheme, each Tx required the knowledge of only its own channel unlike the Jafar-Shamai scheme which required global CSIT to achieve the maximum possible sum DoF of $\frac{8}{3}$. Bit error rate (BER) is an important performance metric when the coding length is finite. This work first proposes a new STBC for a three transmit antenna single user MIMO system. Building on this STBC, we extend the LJJ scheme to the $2 \times 2$ $X$-Network with three antennas at each node. Local channel knowledge is assumed at each Tx. It is shown that the proposed scheme achieves the maximum possible sum DoF of 4. A diversity gain of 3 is also guaranteed when fixed finite constellation inputs are used.
Distributed Maximum Likelihood Sensor Network Localization
Venue: arXiv cs.IT 2013
Year: 2013

We propose a class of convex relaxations to solve the sensor network localization problem, based on a maximum likelihood (ML) formulation. This class, as well as the tightness of the relaxations, depends on the noise probability density function (PDF) of the collected measurements. We derive a computational efficient edge-based version of this ML convex relaxation class and we design a distributed algorithm that enables the sensor nodes to solve these edge-based convex programs locally by communicating only with their close neighbors. This algorithm relies on the alternating direction method of multipliers (ADMM), it converges to the centralized solution, it can run asynchronously, and it is computation error-resilient. Finally, we compare our proposed distributed scheme with other available methods, both analytically and numerically, and we argue the added value of ADMM, especially for large-scale networks.
A Brief Study of Open Source Graph Databases
Venue: arXiv cs.DB 2013
Year: 2013

With the proliferation of large irregular sparse relational datasets, new storage and analysis platforms have arisen to fill gaps in performance and capability left by conventional approaches built on traditional database technologies and query languages. Many of these platforms apply graph structures and analysis techniques to enable users to ingest, update, query and compute on the topological structure of these relationships represented as set(s) of edges between set(s) of vertices. To store and process Facebook-scale datasets, they must be able to support data sources with billions of edges, update rates of millions of updates per second, and complex analysis kernels. These platforms must provide intuitive interfaces that enable graph experts and novice programmers to write implementations of common graph algorithms. In this paper, we explore a variety of graph analysis and storage platforms. We compare their capabil- ities, interfaces, and performance by implementing and computing a set of real-world graph algorithms on synthetic graphs with up to 256 million edges. In the spirit of full disclosure, several authors are affiliated with the development of STINGER.
A Conflict-Based Path-Generation Heuristic for Evacuation Planning
Venue: arXiv cs.AI 2013
Year: 2013

Evacuation planning and scheduling is a critical aspect of disaster management and national security applications. This paper proposes a conflict-based path-generation approach for evacuation planning. Its key idea is to generate evacuation routes lazily for evacuated areas and to optimize the evacuation over these routes in a master problem. Each new path is generated to remedy conflicts in the evacuation and adds new columns and a new row in the master problem. The algorithm is applied to massive flood scenarios in the Hawkesbury-Nepean river (West Sydney, Australia) which require evacuating in the order of 70,000 persons. The proposed approach reduces the number of variables from 4,500,000 in a Mixed Integer Programming (MIP) formulation to 30,000 in the case study. With this approach, realistic evacuations scenarios can be solved near-optimally in real time, supporting both evacuation planning in strategic, tactical, and operational environments.
Robust Periocular Recognition By Fusing Sparse Representations of Color and Geometry Information
Venue: arXiv cs.CV 2013
Year: 2013

In this paper, we propose a re-weighted elastic net (REN) model for biometric recognition. The new model is applied to data separated into geometric and color spatial components. The geometric information is extracted using a fast cartoon - texture decomposition model based on a dual formulation of the total variation norm allowing us to carry information about the overall geometry of images. Color components are defined using linear and nonlinear color spaces, namely the red-green-blue (RGB), chromaticity-brightness (CB) and hue-saturation-value (HSV). Next, according to a Bayesian fusion-scheme, sparse representations for classification purposes are obtained. The scheme is numerically solved using a gradient projection (GP) algorithm. In the empirical validation of the proposed model, we have chosen the periocular region, which is an emerging trait known for its robustness against low quality data. Our results were obtained in the publicly available UBIRIS.v2 data set and show consistent improvements in recognition effectiveness when compared to related state-of-the-art techniques.
Training in Data Curation as Service in a Federated Data Infrastructure - the FrontOffice-BackOffice Model
Venue: arXiv cs.DL 2013
Year: 2013

The increasing volume and importance of research data leads to the emergence of research data infrastructures in which data management plays an important role. As a consequence, practices at digital archives and libraries change. In this paper, we focus on a possible alliance between archives and libraries around training activities in data curation. We introduce a so-called \emph{FrontOffice--BackOffice model} and discuss experiences of its implementation in the Netherlands. In this model, an efficient division of tasks relies on a distributed infrastructure in which research institutions (i.e., universities) use centralized storage and data curation services provided by national research data archives. The training activities are aimed at information professionals working at those research institutions, for instance as digital librarians. We describe our experiences with the course \emph{DataIntelligence4Librarians}. Eventually, we reflect about the international dimension of education and training around data curation and stewardship.
ACTORS: A Goal-driven Approach for Capturing and Managing Consent in e-Health Systems
Venue: arXiv cs.CY 2013
Year: 2013

The notion of patient's consent plays a major role in granting access to medical data. In typical healthcare systems, consent is captured by a form that the patient has to fill in and sign. In e-Health systems, the paper-form consent is being replaced by the integration of the notion of consent in the mechanisms that regulate the access to the medical data. This helps in empowering the patient with the capability of granting and revoking consent in a more effective manner. However, the process of granting and revoking consent greatly varies according to the situation in which the patient is. Our main argument is that such a level of detail is very difficult and error-prone to capture as a set of authorisation policies. In this paper, we present ACTORS, a goal-driven approach to manage consent. The main idea behind ACTORS is to leverage the goal-driven approach of Teleo-Reactive (TR) programming for managing consent that takes into account changes regarding the domains and contexts in which the patient is providing her consent.
Analytical Framework of LDGM-based Iterative Quantization with Decimation
Venue: arXiv cs.IT 2013
Year: 2013

While iterative quantizers based on low-density generator-matrix (LDGM) codes have been shown to be able to achieve near-ideal distortion performance with comparatively moderate block length and computational complexity requirements, their analysis remains difficult due to the presence of decimation steps. In this paper, considering the use of LDGM-based quantizers in a class of symmetric source coding problems, with the alphabet being either binary or non-binary, it is proved rigorously that, as long as the degree distribution satisfies certain conditions that can be evaluated with density evolution (DE), the belief propagation (BP) marginals used in the decimation step have vanishing mean-square error compared to the exact marginals when the block length and iteration count goes to infinity, which potentially allows near-ideal distortion performances to be achieved. This provides a sound theoretical basis for the degree distribution optimization methods previously proposed in the literature and already found to be effective in practice.
On SAT representations of XOR constraints
Venue: arXiv cs.CC 2013
Year: 2013

We study the representation of systems S of linear equations over the two-element field (aka xor- or parity-constraints) via conjunctive normal forms F (boolean clause-sets). First we consider the problem of finding an "arc-consistent" representation ("AC"), meaning that unit-clause propagation will fix all forced assignments for all possible instantiations of the xor-variables. Our main negative result is that there is no polysize AC-representation in general. On the positive side we show that finding such an AC-representation is fixed-parameter tractable (fpt) in the number of equations. Then we turn to a stronger criterion of representation, namely propagation completeness ("PC") --- while AC only covers the variables of S, now all the variables in F (the variables in S plus auxiliary variables) are considered for PC. We show that the standard translation actually yields a PC representation for one equation, but fails so for two equations (in fact arbitrarily badly). We show that with a more intelligent translation we can also easily compute a translation to PC for two equations. We conjecture that computing a representation in PC is fpt in the number of equations.
Low Complexity List Successive Cancellation Decoding of Polar Codes
Venue: arXiv cs.IT 2013
Year: 2013

We propose a low complexity list successive cancellation (LCLSC) decoding algorithm to reduce complexity of traditional list successive cancellation (LSC) decoding of polar codes while trying to maintain the LSC decoding performance at the same time. By defining two thresholds, namely "likelihood ratio (LR) threshold" and "Bhattacharyya parameter threshold", we classify the reliability of each received information bit and the quality of each bit channel. Based on this classification, we implement successive cancellation (SC) decoding instead of LSC decoding when the information bits from "bad" subchannels are received reliably and further attempt to skip LSC decoding for the rest information bits in order to achieve a lower complexity compared to full LSC decoding. Simulation results show that the complexity of LCLSC decoding is much lower than LSC decoding and can be close to that of SC decoding, especially in low code rate regions.
OBST: A Self-Adjusting Peer-to-Peer Overlay Based on Multiple BSTs
Venue: arXiv cs.NI 2013
Year: 2013

The design of scalable and robust overlay topologies has been a main research subject since the very origins of peer-to-peer (p2p) computing. Today, the corresponding optimization tradeoffs are fairly well-understood, at least in the static case and from a worst-case perspective. This paper revisits the peer-to-peer topology design problem from a self-organization perspective. We initiate the study of topologies which are optimized to serve the communication demand, or even self-adjusting as demand changes. The appeal of this new paradigm lies in the opportunity to be able to go beyond the lower bounds and limitations imposed by a static, communication-oblivious, topology. For example, the goal of having short routing paths (in terms of hop count) does no longer conflict with the requirement of having low peer degrees. We propose a simple overlay topology Obst(k) which is composed of k (rooted and directed) Binary Search Trees (BSTs), where k is a parameter. We first prove some fundamental bounds on what can and cannot be achieved optimizing a topology towards a static communication pattern (a static Obst(k)). In particular, we show that the number of BSTs that constitute the overlay can have a large impact on the routing costs, and that a single additional BST may reduce the amortized communication costs from Omega(log(n)) to O(1), where n is the number of peers. Subsequently, we discuss a natural self-adjusting extension of Obst(k), in which frequently communicating partners are "splayed together".
Mapping Mutable Genres in Structurally Complex Volumes
Venue: arXiv cs.CL 2013
Year: 2013

To mine large digital libraries in humanistically meaningful ways, scholars need to divide them by genre. This is a task that classification algorithms are well suited to assist, but they need adjustment to address the specific challenges of this domain. Digital libraries pose two problems of scale not usually found in the article datasets used to test these algorithms. 1) Because libraries span several centuries, the genres being identified may change gradually across the time axis. 2) Because volumes are much longer than articles, they tend to be internally heterogeneous, and the classification task needs to begin with segmentation. We describe a multi-layered solution that trains hidden Markov models to segment volumes, and uses ensembles of overlapping classifiers to address historical change. We test this approach on a collection of 469,200 volumes drawn from HathiTrust Digital Library. To demonstrate the humanistic value of these methods, we extract 32,209 volumes of fiction from the digital library, and trace the changing proportions of first- and third-person narration in the corpus. We note that narrative points of view seem to have strong associations with particular themes and genres.
Multihop Routing in Ad Hoc Networks
Venue: arXiv cs.IT 2013
Year: 2013

This paper presents a dual method of closed-form analysis and lightweight simulation that enables an evaluation of the performance of mobile ad hoc networks that is more realistic, efficient, and accurate than those found in existing publications. Some features accommodated by the new analysis are shadowing, exclusion and guard zones, and distance-dependent fading. Three routing protocols are examined: least-delay, nearest-neighbor, and maximum-progress routing. The tradeoffs among the path reliabilities, average conditional delays, average conditional number of hops, and area spectral efficiencies are examined.
SEEDS: Superpixels Extracted via Energy-Driven Sampling
Venue: arXiv cs.CV 2013
Year: 2013

Superpixel algorithms aim to over-segment the image by grouping pixels that belong to the same object. Many state-of-the-art superpixel algorithms rely on minimizing objective functions to enforce color ho- mogeneity. The optimization is accomplished by sophis- ticated methods that progressively build the superpix- els, typically by adding cuts or growing superpixels. As a result, they are computationally too expensive for real-time applications. We introduce a new approach based on a simple hill-climbing optimization. Starting from an initial superpixel partitioning, it continuously refines the superpixels by modifying the boundaries. We define a robust and fast to evaluate energy function, based on enforcing color similarity between the bound- aries and the superpixel color histogram. In a series of experiments, we show that we achieve an excellent com- promise between accuracy and efficiency. We are able to achieve a performance comparable to the state-of- the-art, but in real-time on a single Intel i7 CPU at 2.8GHz.
Trajectory-Based Dynamic Map Labeling
Venue: arXiv cs.CG 2013
Year: 2013

In this paper we introduce trajectory-based labeling, a new variant of dynamic map labeling, where a movement trajectory for the map viewport is given. We define a general labeling model and study the active range maximization problem in this model. The problem is NP-complete and W[1]-hard. In the restricted, yet practically relevant case that no more than k labels can be active at any time, we give polynomial-time algorithms. For the general case we present a practical ILP formulation with an experimental evaluation as well as approximation algorithms.
Stochastic Optimization of Service Provision with Selfish Users
Venue: arXiv cs.GT 2013
Year: 2013

We develop a computationally efficient technique to solve a fairly general distributed service provision problem with selfish users and imperfect information. In particular, in a context in which the service capacity of the existing infrastructure can be partially adapted to the user load by activating just some of the service units, we aim at finding the configuration of active service units that achieves the best trade-off between maintenance (e.g.\ energetic) costs for the provider and user satisfaction. The core of our technique resides in the implementation of a belief-propagation (BP) algorithm to evaluate the cost configurations. Numerical results confirm the effectiveness of our approach.
The complexity of parity graph homomorphism: an initial investigation
Venue: arXiv cs.CC 2013
Year: 2013

Given a graph G, we investigate the question of determining the parity of the number of homomorphisms from G to some other fixed graph H. We conjecture that this problem exhibits a complexity dichotomy, such that all parity graph homomorphism problems are either polynomial-time solvable or parityP-complete, and provide a conjectured characterisation of the easy cases. We show that the conjecture is true for the restricted case in which the graph H is a tree, and provide some tools that may be useful in further investigation into the parity graph homomorphism problem, and the problem of counting homomorphisms for other moduli.
Searching of gapped repeats and subrepetitions in a word
Venue: arXiv cs.FL 2013
Year: 2013

A gapped repeat is a factor of the form $uvu$ where $u$ and $v$ are nonempty words. The period of the gapped repeat is defined as $|u|+|v|$. The gapped repeat is maximal if it cannot be extended to the left or to the right by at least one letter with preserving its period. The gapped repeat is called $α$-gapped if its period is not greater than $α|v|$. A $δ$-subrepetition is a factor which exponent is less than 2 but is not less than $1+δ$ (the exponent of the factor is the quotient of the length and the minimal period of the factor). The $δ$-subrepetition is maximal if it cannot be extended to the left or to the right by at least one letter with preserving its minimal period. We reveal a close relation between maximal gapped repeats and maximal subrepetitions. Moreover, we show that in a word of length $n$ the number of maximal $α$-gapped repeats is bounded by $O(α^2n)$ and the number of maximal $δ$-subrepetitions is bounded by $O(n/δ^2)$. Using the obtained upper bounds, we propose algorithms for finding all maximal $α$-gapped repeats and all maximal $δ$-subrepetitions in a word of length $n$. The algorithm for finding all maximal $α$-gapped repeats has $O(α^2n)$ time complexity for the case of constant alphabet size and $O(n\log n + α^2n)$ time complexity for the general case. For finding all maximal $δ$-subrepetitions we propose two algorithms. The first algorithm has $O(\frac{n\log\log n}{δ^2})$ time complexity for the case of constant alphabet size and $O(n\log n +\frac{n\log\log n}{δ^2})$ time complexity for the general case. The second algorithm has $O(n\log n+\frac{n}{δ^2}\log \frac{1}δ)$ expected time complexity.
Why SOV might be initially preferred and then lost or recovered? A theoretical framework
Venue: arXiv cs.CL 2013
Year: 2013

Little is known about why SOV order is initially preferred and then discarded or recovered. Here we present a framework for understanding these and many related word order phenomena: the diversity of dominant orders, the existence of free words orders, the need of alternative word orders and word order reversions and cycles in evolution. Under that framework, word order is regarded as a multiconstraint satisfaction problem in which at least two constraints are in conflict: online memory minimization and maximum predictability.