OpenRaiser/Intern-Atlas huggingface dataset:
Supporting Soft Real-Time Sporadic Task Systems on Heterogeneous Multiprocessors with No Utilization Loss
Venue: arXiv cs.OS 2014
Year: 2014

Heterogeneous multicore architectures are becoming increasingly popular due to their potential of achieving high performance and energy efficiency compared to the homogeneous multicore architectures. In such systems, the real-time scheduling problem becomes more challenging in that processors have different speeds. A job executing on a processor with speed $x$ for $t$ time units completes $(x \cdot t)$ units of execution. Prior research on heterogeneous multiprocessor real-time scheduling has focused on hard real-time systems, where, significant processing capacity may have to be sacrificed in the worst-case to ensure that all deadlines are met. As meeting hard deadlines is overkill for many soft real-time systems in practice, this paper shows that on soft real-time heterogeneous multiprocessors, bounded response times can be ensured for globally-scheduled sporadic task systems with no utilization loss. A GEDF-based scheduling algorithm, namely GEDF-H, is presented and response time bounds are established under both preemptive and non-preemptive GEDF-H scheduling. Extensive experiments show that the magnitude of the derived response time bound is reasonable, often smaller than three task periods. To the best of our knowledge, this paper is the first to show that soft real-time sporadic task systems can be supported on heterogeneous multiprocessors without utilization loss, and with reasonable predicted response time.
On computation with 'probabilities' modulo k
Venue: arXiv cs.CC 2014
Year: 2014

We propose a framework to study models of computation of indeterministic data, represented by abstract "distributions". In these distributions, probabilities are replaced by "amplitudes" drawn from a fixed semi-ring $S$, of which the non-negative reals, the complex numbers, finite fields $\mathbb F_{p^r}$, and cyclic rings $\mathbb Z_k$ are examples. Varying $S$ yields different models of computation, which we may investigate to better understand the (likely) difference in power between randomised and quantum computation. The "modal quantum states" of Schumacher and Westmoreland [arXiv:1010.2929] are examples of such distributions, for $S$ a finite field. For $S = \mathbb F_2$, Willcock and Sabry [arXiv:1102.3587] show that UNIQUE-SAT is solvable by polynomial-time uniform circuit families consisting of invertible gates. We characterize the decision problems solvable by polynomial uniform circuit families, using either invertible or "unitary" transformations over cyclic rings $S = \mathbb Z_k$, or (in the case that $k$ is a prime power) finite fields $S = \mathbb F_k$. In particular, for $k$ a prime power, these are precisely the problems in the class $\mathsf{Mod}_k\mathsf P$.
Deanonymisation of clients in Bitcoin P2P network
Venue: arXiv cs.CR 2014
Year: 2014

Bitcoin is a digital currency which relies on a distributed set of miners to mint coins and on a peer-to-peer network to broadcast transactions. The identities of Bitcoin users are hidden behind pseudonyms (public keys) which are recommended to be changed frequently in order to increase transaction unlinkability. We present an efficient method to deanonymize Bitcoin users, which allows to link user pseudonyms to the IP addresses where the transactions are generated. Our techniques work for the most common and the most challenging scenario when users are behind NATs or firewalls of their ISPs. They allow to link transactions of a user behind a NAT and to distinguish connections and transactions of different users behind the same NAT. We also show that a natural countermeasure of using Tor or other anonymity services can be cut-off by abusing anti-DoS countermeasures of the bitcoin network. Our attacks require only a few machines and have been experimentally verified. We propose several countermeasures to mitigate these new attacks.
Key Capacity with Limited One-Way Communication for Product Sources
Venue: arXiv cs.IT 2014
Year: 2014

We show that for product sources, rate splitting is optimal for secret key agreement using limited one-way communication at two terminals. This yields an alternative proof of the tensorization property of a strong data processing inequality originally studied by Erkip and Cover and amended recently by Anantharam et al. We derive a `water-filling' solution of the communication-rate--key-rate tradeoff for two arbitrarily correlated vector Gaussian sources, for the case with an eavesdropper, and for stationary Gaussian processes.
Incorporating Sharp Features in the General Solid Sweep Framework
Venue: arXiv cs.GR 2014
Year: 2014

This paper extends a recently proposed robust computational framework for constructing the boundary representation (brep) of the volume swept by a given smooth solid moving along a one parameter family $h$ of rigid motions. Our extension allows the input solid to have sharp features, i.e., to be of class G0 wherein, the unit outward normal to the solid may be discontinuous. In the earlier framework, the solid to be swept was restricted to be G1, and thus this is a significant and useful extension of that work. This naturally requires a precise description of the geometry of the surface generated by the sweep of a sharp edge supported by two intersecting smooth faces. We uncover the geometry along with the related issues like parametrization, self-intersection and singularities via a novel mathematical analysis. Correct trimming of such a surface is achieved by a delicate analysis of the interplay between the cone of normals at a sharp point and its trajectory under $h$. The overall topology is explicated by a key lifting theorem which allows us to compute the adjacency relations amongst entities in the swept volume by relating them to corresponding adjacencies in the input solid. Moreover, global issues related to body-check such as orientation are efficiently resolved. Many examples from a pilot implementation illustrate the efficiency and effectiveness of our framework.
Universal Compression of Envelope Classes: Tight Characterization via Poisson Sampling
Venue: arXiv cs.IT 2014
Year: 2014

The Poisson-sampling technique eliminates dependencies among symbol appearances in a random sequence. It has been used to simplify the analysis and strengthen the performance guarantees of randomized algorithms. Applying this method to universal compression, we relate the redundancies of fixed-length and Poisson-sampled sequences, use the relation to derive a simple single-letter formula that approximates the redundancy of any envelope class to within an additive logarithmic term. As a first application, we consider i.i.d. distributions over a small alphabet as a step-envelope class, and provide a short proof that determines the redundancy of discrete distributions over a small al- phabet up to the first order terms. We then show the strength of our method by applying the formula to tighten the existing bounds on the redundancy of exponential and power-law classes, in particular answering a question posed by Boucheron, Garivier and Gassiat.
Loo.py: transformation-based code generation for GPUs and CPUs
Venue: arXiv cs.PL 2014
Year: 2014

Today's highly heterogeneous computing landscape places a burden on programmers wanting to achieve high performance on a reasonably broad cross-section of machines. To do so, computations need to be expressed in many different but mathematically equivalent ways, with, in the worst case, one variant per target machine. Loo.py, a programming system embedded in Python, meets this challenge by defining a data model for array-style computations and a library of transformations that operate on this model. Offering transformations such as loop tiling, vectorization, storage management, unrolling, instruction-level parallelism, change of data layout, and many more, it provides a convenient way to capture, parametrize, and re-unify the growth among code variants. Optional, deep integration with numpy and PyOpenCL provides a convenient computing environment where the transition from prototype to high-performance implementation can occur in a gradual, machine-assisted form.
Aspect Based Sentiment Analysis to Extract Meticulous Opinion Value
Venue: arXiv cs.IR 2014
Year: 2014

Opinion Mining and Sentiment Analysis is a process of identifying opinions in large unstructured/structured data and then analysing polarity of those opinions. Opinion mining and sentiment analysis have found vast application in analysing online ratings, analysing product based reviews, e-governance, and managing hostile content over the internet. This paper proposes an algorithm to implement aspect level sentiment analysis. The algorithm takes input from the remarks submitted by various teachers of a student. An aspect tree is formed which has various levels and weights are assigned to each branch to identify level of aspect. Aspect value is calculated by the algorithm by means of the proposed aspect tree. Dictionary based method is implemented to evaluate the polarity of the remark. The algorithm returns the aspect value clubbed with opinion value and sentiment value which helps in concluding the summarized value of remark.
On the Existence of Certain Optimal Self-Dual Codes with Lengths Between $74$ and $116$
Venue: arXiv cs.IT 2014
Year: 2014

The existence of optimal binary self-dual codes is a long-standing research problem. In this paper, we present some results concerning the decomposition of binary self-dual codes with a dihedral automorphism group $D_{2p}$, where $p$ is a prime. These results are applied to construct new self-dual codes with length $78$ or $116$. We obtain $16$ inequivalent self-dual $[78,39,14]$ codes, four of which have new weight enumerators. We also show that there are at least $141$ inequivalent self-dual $[116,58,18]$ codes, most of which are new up to equivalence. Meanwhile, we give some restrictions on the weight enumerators of singly even self-dual codes. We use these restrictions to exclude some possible weight enumerators of self-dual codes with lengths $74$, $76$, $82$, $98$ and $100$.
Cold-start Problems in Recommendation Systems via Contextual-bandit Algorithms
Venue: arXiv cs.IR 2014
Year: 2014

In this paper, we study a cold-start problem in recommendation systems where we have completely new users entered the systems. There is not any interaction or feedback of the new users with the systems previoustly, thus no ratings are available. Trivial approaches are to select ramdom items or the most popular ones to recommend to the new users. However, these methods perform poorly in many case. In this research, we provide a new look of this cold-start problem in recommendation systems. In fact, we cast this cold-start problem as a contextual-bandit problem. No additional information on new users and new items is needed. We consider all the past ratings of previous users as contextual information to be integrated into the recommendation framework. To solve this type of the cold-start problems, we propose a new efficient method which is based on the LinUCB algorithm for contextual-bandit problems. The experiments were conducted on three different publicly-available data sets, namely Movielens, Netflix and Yahoo!Music. The new proposed methods were also compared with other state-of-the-art techniques. Experiments showed that our new method significantly improves upon all these methods.
A Probabilistic Framework for Learning Kinematic Models of Articulated Objects
Venue: arXiv cs.RO 2014
Year: 2014

Robots operating in domestic environments generally need to interact with articulated objects, such as doors, cabinets, dishwashers or fridges. In this work, we present a novel, probabilistic framework for modeling articulated objects as kinematic graphs. Vertices in this graph correspond to object parts, while edges between them model their kinematic relationship. In particular, we present a set of parametric and non-parametric edge models and how they can robustly be estimated from noisy pose observations. We furthermore describe how to estimate the kinematic structure and how to use the learned kinematic models for pose prediction and for robotic manipulation tasks. We finally present how the learned models can be generalized to new and previously unseen objects. In various experiments using real robots with different camera systems as well as in simulation, we show that our approach is valid, accurate and efficient. Further, we demonstrate that our approach has a broad set of applications, in particular for the emerging fields of mobile manipulation and service robotics.
Deformation corrected compressed sensing (DC-CS): a novel framework for accelerated dynamic MRI
Venue: arXiv cs.CV 2014
Year: 2014

We propose a novel deformation corrected compressed sensing (DC-CS) framework to recover dynamic magnetic resonance images from undersampled measurements. We introduce a generalized formulation that is capable of handling a wide class of sparsity/compactness priors on the deformation corrected dynamic signal. In this work, we consider example compactness priors such as sparsity in temporal Fourier domain, sparsity in temporal finite difference domain, and nuclear norm penalty to exploit low rank structure. Using variable splitting, we decouple the complex optimization problem to simpler and well understood sub problems; the resulting algorithm alternates between simple steps of shrinkage based denoising, deformable registration, and a quadratic optimization step. Additionally, we employ efficient continuation strategies to minimize the risk of convergence to local minima. The proposed formulation contrasts with existing DC-CS schemes that are customized for free breathing cardiac cine applications, and other schemes that rely on fully sampled reference frames or navigator signals to estimate the deformation parameters. The efficient decoupling enabled by the proposed scheme allows its application to a wide range of applications including contrast enhanced dynamic MRI. Through experiments on numerical phantom and in vivo myocardial perfusion MRI datasets, we demonstrate the utility of the proposed DC-CS scheme in providing robust reconstructions with reduced motion artifacts over classical compressed sensing schemes that utilize the compact priors on the original deformation un-corrected signal.
(Quantified) Horn Constraint Solving for Program Verification and Synthesis
Venue: arXiv cs.LO 2014
Year: 2014

We show how automatic tools for the verification of linear and branching time properties of procedural, multi-threaded, and functional programs as well as program synthesis can be naturally and uniformly seen as solvers of constraints in form of (quantified) Horn clauses over background logical theories. Such a perspective can offer various advantages, e. g., a logical separation of concerns between constraint generation (also known as generation of proof obligations) and constraint solving (also known as proof discovery), reuse of solvers across different verifications tasks, and liberation of proof designers from low level algorithmic concerns and vice versa. To appear in Theory and Practice of Logic Programming (TPLP)
DEM Registration and Error Analysis using ASCII values
Venue: arXiv cs.CV 2014
Year: 2014

Digital Elevation Model (DEM), while providing a bare earth look, is heavily used in many applications including construction modeling, visualization, and GIS. Their registration techniques have not been explored much. Methods like Coarse-to-fine or pyramid making are common in DEM-to-image or DEM-to-map registration. Self-consistency measure is used to detect any change in terrain elevation and hence was used for DEM-to-DEM registration. But these methods apart from being time and complexity intensive, lack in error matrix evaluation. This paper gives a method of registration of DEMs using specified height values as control points by initially converting these DEMs to ASCII files. These control points may be found by two mannerisms - either by direct detection of appropriate height data in ASCII files or by edge matching along congruous quadrangle of the control point, followed by sub-graph matching. Error analysis for the same has also been done.
Asymptotic Error Performance Analysis of Spatial Modulation under Generalized Fading
Venue: arXiv cs.IT 2014
Year: 2014

This letter presents a comprehensive framework analyzing the asymptotic error performance of a multiple-input-multiple-output (MIMO) wireless system employing spatial modulation (SM) with maximum likelihood detection and perfect channel state information. Generic analytical expressions for the diversity and coding gains are deduced that reveal fundamental properties of MIMO SM systems. The presented analysis can be used to obtain closed-form upper bounds for the average bit error probability (ABEP) of MIMO SM systems under generalized fading which become asymptotically tight in the high signal-to-noise ratio (SNR) region.
Vocal signal digital processing. Instrument for analog to digital conversion study
Venue: arXiv cs.SD 2014
Year: 2014

The goal of this article is to present interactive didactic software for analog to digital conversion using PCM method. After a short introduction regarding vocal signal processing we present some method for analog to digital conversion. The didactic software is an applet that can be direct accessed by any interested person.
Circle detection using electro-magnetism optimization
Venue: arXiv cs.CV 2014
Year: 2014

This paper describes a circle detection method based on Electromagnetism-Like Optimization (EMO). Circle detection has received considerable attention over the last years thanks to its relevance for many computer vision tasks. EMO is a heuristic method for solving complex optimization problems inspired in electromagnetism principles. This algorithm searches a solution based in the attraction and repulsion among prototype candidates. In this paper the detection process is considered to be similar to an optimization problem, the algorithm uses the combination of three edge points (x, y, r) as parameters to determine circles candidates in the scene. An objective function determines if such circle candidates are actually present in the image. The EMO algorithm is used to find the circle candidate that is better related with the real circle present in the image according to the objective function. The final algorithm is a fast circle detector that locates circles with sub-pixel accuracy even considering complicated conditions and noisy images.
Combined Approach for Image Segmentation
Venue: arXiv cs.CV 2014
Year: 2014

Many image segmentation techniques have been developed over the past two decades for segmenting the images, which help for object recognition, occlusion boundary estimation within motion or stereo systems, image compression, image editing. In this, there is a combined approach for segmenting the image. By using histogram equalization to the input image, from which it gives contrast enhancement output image .After that by applying median filtering,which will remove noise from contrast output image . At last I applied fuzzy c-mean clustering algorithm to denoising output image, which give segmented output image. In this way it produce better segmented image with less computation time.
On the measure of conflicts: A MUS-Decomposition Based Framework
Venue: arXiv cs.AI 2014
Year: 2014

Measuring inconsistency is viewed as an important issue related to handling inconsistencies. Good measures are supposed to satisfy a set of rational properties. However, defining sound properties is sometimes problematic. In this paper, we emphasize one such property, named Decomposability, rarely discussed in the literature due to its modeling difficulties. To this end, we propose an independent decomposition which is more intuitive than existing proposals. To analyze inconsistency in a more fine-grained way, we introduce a graph representation of a knowledge base and various MUSdecompositions. One particular MUS-decomposition, named distributable MUS-decomposition leads to an interesting partition of inconsistencies in a knowledge base such that multiple experts can check inconsistencies in parallel, which is impossible under existing measures. Such particular MUSdecomposition results in an inconsistency measure that satisfies a number of desired properties. Moreover, we give an upper bound complexity of the measure that can be computed using 0/1 linear programming or Min Cost Satisfiability problems, and conduct preliminary experiments to show its feasibility.
Piecewise Toeplitz Matrices-based Sensing for Rank Minimization
Venue: arXiv cs.IT 2014
Year: 2014

This paper proposes a set of piecewise Toeplitz matrices as the linear mapping/sensing operator $\mathcal{A}: \mathbf{R}^{n_1 \times n_2} \rightarrow \mathbf{R}^M$ for recovering low rank matrices from few measurements. We prove that such operators efficiently encode the information so there exists a unique reconstruction matrix under mild assumptions. This work provides a significant extension of the compressed sensing and rank minimization theory, and it achieves a tradeoff between reducing the memory required for storing the sampling operator from $\mathcal{O}(n_1n_2M)$ to $\mathcal{O}(\max(n_1,n_2)M)$ but at the expense of increasing the number of measurements by $r$. Simulation results show that the proposed operator can recover low rank matrices efficiently with a reconstruction performance close to the cases of using random unstructured operators.
Topological and Statistical Behavior Classifiers for Tracking Applications
Venue: arXiv cs.SY 2014
Year: 2014

We introduce the first unified theory for target tracking using Multiple Hypothesis Tracking, Topological Data Analysis, and machine learning. Our string of innovations are 1) robust topological features are used to encode behavioral information, 2) statistical models are fitted to distributions over these topological features, and 3) the target type classification methods of Wigren and Bar Shalom et al. are employed to exploit the resulting likelihoods for topological features inside of the tracking procedure. To demonstrate the efficacy of our approach, we test our procedure on synthetic vehicular data generated by the Simulation of Urban Mobility package.
Ambiguous Proximity Distribution
Venue: arXiv cs.CV 2014
Year: 2014

Proximity Distribution Kernel is an effective method for bag-of-featues based image representation. In this paper, we investigate the soft assignment of visual words to image features for proximity distribution. Visual word contribution function is proposed to model ambiguous proximity distributions. Three ambiguous proximity distributions is developed by three ambiguous contribution functions. The experiments are conducted on both classification and retrieval of medical image data sets. The results show that the performance of the proposed methods, Proximity Distribution Kernel (PDK), is better or comparable to the state-of-the-art bag-of-features based image representation methods.