OpenRaiser/Intern-Atlas huggingface dataset:
Analysis of Branch Misses in Quicksort
Venue: arXiv cs.DS 2014
Year: 2014

The analysis of algorithms mostly relies on counting classic elementary operations like additions, multiplications, comparisons, swaps etc. This approach is often sufficient to quantify an algorithm's efficiency. In some cases, however, features of modern processor architectures like pipelined execution and memory hierarchies have significant impact on running time and need to be taken into account to get a reliable picture. One such example is Quicksort: It has been demonstrated experimentally that under certain conditions on the hardware the classically optimal balanced choice of the pivot as median of a sample gets harmful. The reason lies in mispredicted branches whose rollback costs become dominating. In this paper, we give the first precise analytical investigation of the influence of pipelining and the resulting branch mispredictions on the efficiency of (classic) Quicksort and Yaroslavskiy's dual-pivot Quicksort as implemented in Oracle's Java 7 library. For the latter it is still not fully understood why experiments prove it 10% faster than a highly engineered implementation of a classic single-pivot version. For different branch prediction strategies, we give precise asymptotics for the expected number of branch misses caused by the aforementioned Quicksort variants when their pivots are chosen from a sample of the input. We conclude that the difference in branch misses is too small to explain the superiority of the dual-pivot algorithm.
Energy Efficient Full Adder Cell Design With Using Carbon Nanotube Field Effect Transistors In 32 Nanometer Technology
Venue: arXiv cs.AR 2014
Year: 2014

Full Adder is one of the critical parts of logical and arithmetic units. So, presenting a low power full adder cell reduces the power consumption of the entire circuit. Also, using Nano-scale transistors, because of their unique characteristics will save energy consumption and decrease the chip area. In this paper we presented a low power full adder cell by using carbon nanotube field effect transistors (CNTFETs). Simulation results were carried out using HSPICE based on the CNTFET model in 32 nanometer technology in Different values of temperature and VDD.
Parallax Effect Free Mosaicing of Underwater Video Sequence Based on Texture Features
Venue: arXiv cs.CV 2014
Year: 2014

In this paper, we present feature-based technique for construction of mosaic image from underwater video sequence, which suffers from parallax distortion due to propagation properties of light in the underwater environment. The most of the available mosaic tools and underwater image mosaicing techniques yields final result with some artifacts such as blurring, ghosting and seam due to presence of parallax in the input images. The removal of parallax from input images may not reduce its effects instead it must be corrected in successive steps of mosaicing. Thus, our approach minimizes the parallax effects by adopting an efficient local alignment technique after global registration. We extract texture features using Centre Symmetric Local Binary Pattern (CS-LBP) descriptor in order to find feature correspondences, which are used further for estimation of homography through RANSAC. In order to increase the accuracy of global registration, we perform preprocessing such as colour alignment between two selected frames based on colour distribution adjustment. Because of existence of 100% overlap in consecutive frames of underwater video, we select frames with minimum overlap based on mutual offset in order to reduce the computation cost during mosaicing. Our approach minimizes the parallax effects considerably in final mosaic constructed using our own underwater video sequences.
Macro with Pico Cells (HetNets) System Behavior Using Well-known scheduling Algorithms
Venue: arXiv cs.NI 2014
Year: 2014

This paper demonstrates the concept of using Heterogeneous networks (HetNets) to improve Long Term Evolution (LTE) system by introducing the LTE Advance (LTE-A). The type of HetNets that has been chosen for this study is Macro with Pico cells. Comparing the system performance with and without Pico cells has clearly illustrated using three well-known scheduling algorithms (Proportional Fair PF, Maximum Largest Weighted Delay First MLWDF and Exponential/Proportional Fair EXP/PF). The system is judged based on throughput, Packet Loss Ratio PLR, delay and fairness.A simulation platform called LTE-Sim has been used to collect the data and produce the paper outcomes and graphs. The results prove that adding Pico cells enhances the overall system performance. From the simulation outcomes, the overall system performance is as follows: throughput is duplicated or tripled based on the number of users, the PLR is almost quartered, the delay is nearly reduced ten times (PF case) and changed to be a half (MLWDF/EXP cases), and the fairness stays closer to value of 1. It is considered an efficient and cost effective way to increase the throughput, coverage and reduce the latency.
Evolving intraday foreign exchange trading strategies utilizing multiple instruments price series
Venue: arXiv cs.NE 2014
Year: 2014

We propose a Genetic Programming architecture for the generation of foreign exchange trading strategies. The system's principal features are the evolution of free-form strategies which do not rely on any prior models and the utilization of price series from multiple instruments as input data. This latter feature constitutes an innovation with respect to previous works documented in literature. In this article we utilize Open, High, Low, Close bar data at a 5 minutes frequency for the AUD.USD, EUR.USD, GBP.USD and USD.JPY currency pairs. We will test the implementation analyzing the in-sample and out-of-sample performance of strategies for trading the USD.JPY obtained across multiple algorithm runs. We will also evaluate the differences between strategies selected according to two different criteria: one relies on the fitness obtained on the training set only, the second one makes use of an additional validation dataset. Strategy activity and trade accuracy are remarkably stable between in and out of sample results. From a profitability aspect, the two criteria both result in strategies successful on out-of-sample data but exhibiting different characteristics. The overall best performing out-of-sample strategy achieves a yearly return of 19%.
It's the Human that Matters: Accurate User Orientation Estimation for Mobile Computing Applications
Venue: arXiv cs.CY 2014
Year: 2014

Ubiquity of Internet-connected and sensor-equipped portable devices sparked a new set of mobile computing applications that leverage the proliferating sensing capabilities of smart-phones. For many of these applications, accurate estimation of the user heading, as compared to the phone heading, is of paramount importance. This is of special importance for many crowd-sensing applications, where the phone can be carried in arbitrary positions and orientations relative to the user body. Current state-of-the-art focus mainly on estimating the phone orientation, require the phone to be placed in a particular position, require user intervention, and/or do not work accurately indoors; which limits their ubiquitous usability in different applications. In this paper we present Humaine, a novel system to reliably and accurately estimate the user orientation relative to the Earth coordinate system. Humaine requires no prior-configuration nor user intervention and works accurately indoors and outdoors for arbitrary cell phone positions and orientations relative to the user body. The system applies statistical analysis techniques to the inertial sensors widely available on today's cell phones to estimate both the phone and user orientation. Implementation of the system on different Android devices with 170 experiments performed at different indoor and outdoor testbeds shows that Humaine significantly outperforms the state-of-the-art in diverse scenarios, achieving a median accuracy of $15^\circ$ averaged over a wide variety of phone positions. This is $558\%$ better than the-state-of-the-art. The accuracy is bounded by the error in the inertial sensors readings and can be enhanced with more accurate sensors and sensor fusion.
Two maximum entropy based algorithms for running quantile estimation in non-stationary data streams
Venue: arXiv cs.DS 2014
Year: 2014

The need to estimate a particular quantile of a distribution is an important problem which frequently arises in many computer vision and signal processing applications. For example, our work was motivated by the requirements of many semi-automatic surveillance analytics systems which detect abnormalities in close-circuit television (CCTV) footage using statistical models of low-level motion features. In this paper we specifically address the problem of estimating the running quantile of a data stream when the memory for storing observations is limited. We make several major contributions: (i) we highlight the limitations of approaches previously described in the literature which make them unsuitable for non-stationary streams, (ii) we describe a novel principle for the utilization of the available storage space, (iii) we introduce two novel algorithms which exploit the proposed principle in different ways, and (iv) we present a comprehensive evaluation and analysis of the proposed algorithms and the existing methods in the literature on both synthetic data sets and three large real-world streams acquired in the course of operation of an existing commercial surveillance system. Our findings convincingly demonstrate that both of the proposed methods are highly successful and vastly outperform the existing alternatives. We show that the better of the two algorithms (data-aligned histogram) exhibits far superior performance in comparison with the previously described methods, achieving more than 10 times lower estimate errors on real-world data, even when its available working memory is an order of magnitude smaller.
An explicit sparse recovery scheme in the L1-norm
Venue: arXiv cs.DS 2014
Year: 2014

Consider the approximate sparse recovery problem: given Ax, where A is a known m-by-n dimensional matrix and x is an unknown (approximately) sparse n-dimensional vector, recover an approximation to x. The goal is to design the matrix A such that m is small and recovery is efficient. Moreover, it is often desirable for A to have other nice properties, such as explicitness, sparsity, and discreteness. In this work, we show that we can use spectral expander graphs to explicitly design binary matrices A for which the column sparsity is optimal and for which there is an efficient recovery algorithm (l1-minimization). In order to recover x that is close to δn-sparse (where δ is a constant), we design an explicit binary matrix A that has m = O(sqrt{δ} log(1/δ) * n) rows and has O(log(1/δ)) ones in each column. Previous such constructions were based on unbalanced bipartite graphs with high vertex expansion, for which we currently do not have explicit constructions. In particular, ours is the first explicit non-trivial construction of a measurement matrix A such that Ax can be computed in O(n log(1/δ)) time.
SCULPT: A Schema Language for Tabular Data on the Web
Venue: arXiv cs.DB 2014
Year: 2014

Inspired by the recent working effort towards a recommendation by the World Wide Web Consortium (W3C) for tabular data and metadata on the Web, we present in this paper a concept for a schema language for tabular web data called SCULPT. The language consists of rules constraining and defining the structure of regions in the table. These regions are defined through the novel formalism of region selection expressions. We present a formal model for SCULPT and obtain a linear time combined complexity evaluation algorithm. In addition, we consider weak and strong streaming evaluation for SCULPT and present a fragment for each of these streaming variants. Finally, we discuss several extensions of SCULPT including alternative semantics, types, complex content, and explore region selection expressions as a basis for a transformation language.
Infinite Object Coating in the Amoebot Model
Venue: arXiv cs.ET 2014
Year: 2014

The term programmable matter refers to matter which has the ability to change its physical properties (shape, density, moduli, conductivity, optical properties, etc.) in a programmable fashion, based upon user input or autonomous sensing. This has many applications like smart materials, autonomous monitoring and repair, and minimal invasive surgery. While programmable matter might have been considered pure science fiction more than two decades ago, in recent years a large amount of research has been conducted in this field. Often programmable matter is envisioned as a very large number of small locally interacting computational particles. We propose the Amoebot model, a new model which builds upon this vision of programmable matter. Inspired by the behavior of amoeba, the Amoebot model offers a versatile framework to model self-organizing particles and facilitates rigorous algorithmic research in the area of programmable matter. We present an algorithm for the problem of coating an infinite object under this model, and prove the correctness of the algorithm and that it is work-optimal.
Univariate Niho Bent Functions from o-Polynomials
Venue: arXiv cs.DM 2014
Year: 2014

In this paper, we discover that any univariate Niho bent function is a sum of functions having the form of Leander-Kholosha bent functions with extra coefficients of the power terms. This allows immediately, knowing the terms of an o-polynomial, to obtain the powers of the additive terms in the polynomial representing corresponding bent function. However, the coefficients are calculated ambiguously. The explicit form is given for the bent functions obtained from quadratic and cubic o-polynomials. We also calculate the algebraic degree of any bent function in the Leander-Kholosha class.
Large-scale Spatial Distribution Identification of Base Stations in Cellular Networks
Venue: arXiv cs.NI 2014
Year: 2014

The performance of cellular system significantly depends on its network topology, where the spatial deployment of base stations (BSs) plays a key role in the downlink scenario. Moreover, cellular networks are undergoing a heterogeneous evolution, which introduces unplanned deployment of smaller BSs, thus complicating the performance evaluation even further. In this paper, based on large amount of real BS locations data, we present a comprehensive analysis on the spatial modeling of cellular network structure. Unlike the related works, we divide the BSs into different subsets according to geographical factor (e.g. urban or rural) and functional type (e.g. macrocells or microcells), and perform detailed spatial analysis to each subset. After examining the accuracy of Poisson point process (PPP) in BS locations modeling, we take into account the Gibbs point processes as well as Neyman-Scott point processes and compare their accuracy in view of large-scale modeling test. Finally, we declare the inaccuracy of the PPP model, and reveal the general clustering nature of BSs deployment, which distinctly violates the traditional assumption. This paper carries out a first large-scale identification regarding available literatures, and provides more realistic and more general results to contribute to the performance analysis for the forthcoming heterogeneous cellular networks.
Measuring the impact of input data on energy consumption of software
Venue: arXiv cs.SE 2014
Year: 2014

The amount of energy consumed during the execution of software, and the ability to predict future consumption, is an important factor in the design of embedded electronic systems. In this technical report I examine factors in the execution of software that can affect energy consumption. Taking a simple embedded software benchmark I measure to what extent input data can affect energy consumption, and propose a method for reflecting this in software energy models.
Low-Complexity Soft-Output Signal Detection Based on Gauss-Seidel Method for Uplink Multi-User Large-Scale MIMO Systems
Venue: arXiv cs.IT 2014
Year: 2014

For uplink large-scale MIMO systems, minimum mean square error (MMSE) algorithm is near-optimal but involves matrix inversion with high complexity. In this paper, we propose to exploit the Gauss-Seidel (GS) method to iteratively realize the MMSE algorithm without the complicated matrix inversion. To further accelerate the convergence rate and reduce the complexity, we propose a diagonal-approximate initial solution to the GS method, which is much closer to the final solution than the traditional zero-vector initial solution. We also propose a approximated method to compute log-likelihood ratios (LLRs) for soft channel decoding with a negligible performance loss. The analysis shows that the proposed GS-based algorithm can reduce the computational complexity from O(K^3) to O(K^2), where K is the number of users. Simulation results verify that the proposed algorithm outperforms the recently proposed Neumann series approximation algorithm, and achieves the near-optimal performance of the classical MMSE algorithm with a small number of iterations.
Energy Consumption Of Visual Sensor Networks: Impact Of Spatio-Temporal Coverage
Venue: arXiv cs.NI 2014
Year: 2014

Wireless visual sensor networks (VSNs) are expected to play a major role in future IEEE 802.15.4 personal area networks (PAN) under recently-established collision-free medium access control (MAC) protocols, such as the IEEE 802.15.4e-2012 MAC. In such environments, the VSN energy consumption is affected by the number of camera sensors deployed (spatial coverage), as well as the number of captured video frames out of which each node processes and transmits data (temporal coverage). In this paper, we explore this aspect for uniformly-formed VSNs, i.e., networks comprising identical wireless visual sensor nodes connected to a collection node via a balanced cluster-tree topology, with each node producing independent identically-distributed bitstream sizes after processing the video frames captured within each network activation interval. We derive analytic results for the energy-optimal spatio-temporal coverage parameters of such VSNs under a-priori known bounds for the number of frames to process per sensor and the number of nodes to deploy within each tier of the VSN. Our results are parametric to the probability density function characterizing the bitstream size produced by each node and the energy consumption rates of the system of interest. Experimental results reveal that our analytic results are always within 7% of the energy consumption measurements for a wide range of settings. In addition, results obtained via a multimedia subsystem show that the optimal spatio-temporal settings derived by the proposed framework allow for substantial reduction of energy consumption in comparison to ad-hoc settings. As such, our analytic modeling is useful for early-stage studies of possible VSN deployments under collision-free MAC protocols prior to costly and time-consuming experiments in the field.
Precision-Energy-Throughput Scaling Of Generic Matrix Multiplication and Convolution Kernels Via Linear Projections
Venue: arXiv cs.MM 2014
Year: 2014

Generic matrix multiplication (GEMM) and one-dimensional convolution/cross-correlation (CONV) kernels often constitute the bulk of the compute- and memory-intensive processing within image/audio recognition and matching systems. We propose a novel method to scale the energy and processing throughput of GEMM and CONV kernels for such error-tolerant multimedia applications by adjusting the precision of computation. Our technique employs linear projections to the input matrix or signal data during the top-level GEMM and CONV blocking and reordering. The GEMM and CONV kernel processing then uses the projected inputs and the results are accumulated to form the final outputs. Throughput and energy scaling takes place by changing the number of projections computed by each kernel, which in turn produces approximate results, i.e. changes the precision of the performed computation. Results derived from a voltage- and frequency-scaled ARM Cortex A15 processor running face recognition and music matching algorithms demonstrate that the proposed approach allows for 280%~440% increase of processing throughput and 75%~80% decrease of energy consumption against optimized GEMM and CONV kernels without any impact in the obtained recognition or matching accuracy. Even higher gains can be obtained if one is willing to tolerate some reduction in the accuracy of the recognition and matching applications.
Analysis of Applicability of ISO 9564 PIN based Authentication to Closed-Loop Mobile Payment Systems
Venue: arXiv cs.CR 2014
Year: 2014

Payment transactions initiated through a mobile device are growing and security concerns must be ad-dressed. People coming from payment card industry often talk passionately about porting ISO 9564 PIN standard based authentication in open-loop card payment to closed-loop mobile financial transactions and certification of closed-loop payment product or solution against this standard. In reality, so far this standard has not been adopted in closed-loop mobile payment authentication and applicability of this ISO standard must be studied carefully before adoption. The authors do a critical analysis of the applicability of this ISO specification and makes categorical statement about relevance of compliance to closed-loop mobile payment. Security requirements for authentication in closed-loop mobile payment systems are not standardized through ISO 9564 standard, Common Criteria, etc. Since closed-loop mobile payment is a relatively new field, the authors make a case for Common Criteria Recognition Agreement (CCRA) or other standards organization to push for publication of a mobile device-agnostic Protection Profile or standard for it, incorporating the suggested authentication approaches.
HetNetwork Coding: Scaling Throughput in Heterogeneous Networks using Multiple Radio Interfaces
Venue: arXiv cs.NI 2014
Year: 2014

The explosive demand for data has called for solution approaches that range from spectrally agile cognitive radios with novel spectrum sharing, to use of higher frequency spectrum as well as smaller and denser cell deployments with diverse access technologies, referred to as heterogeneous networks (HetNets). Simultaneously, advances in electronics and storage, has led to the advent of wireless devices equipped with multiple radio interfaces (e.g. WiFi, WiMAX, LTE, etc.) and the ability to store and efficiently process large amounts of data. Motivated by the convergence of HetNets and multi-platform radios, we propose HetNetwork Coding as a means to utilize the available radio interfaces in parallel along with network coding to increase wireless data throughput. Specifically we explore the use of random linear network coding at the network layer where packets can travel through multiple interfaces and be received via multihoming. Using both simulations and experimentation with real hardware on WiFi and WiMAX platforms, we study the scaling of throughput enabled by such HetNetwork coding. We find from our simulations and experiments that the use of this method increases the throughput, with greater gains achieved for cases when the system is heavily loaded or the channel quality is poor. Our results also reveal that the throughput gains achieved scale linearly with the number of radio interfaces at the nodes.