OpenRaiser/Intern-Atlas huggingface dataset:
A Novel Progressive Image Scanning and Reconstruction Scheme based on Compressed Sensing and Linear Prediction
Venue: arXiv cs.IT 2013
Year: 2013

Compressed sensing (CS) is an innovative technique allowing to represent signals through a small number of their linear projections. In this paper we address the application of CS to the scenario of progressive acquisition of 2D visual signals in a line-by-line fashion. This is an important setting which encompasses diverse systems such as flatbed scanners and remote sensing imagers. The use of CS in such setting raises the problem of reconstructing a very high number of samples, as are contained in an image, from their linear projections. Conventional reconstruction algorithms, whose complexity is cubic in the number of samples, are computationally intractable. In this paper we develop an iterative reconstruction algorithm that reconstructs an image by iteratively estimating a row, and correlating adjacent rows by means of linear prediction. We develop suitable predictors and test the proposed algorithm in the context of flatbed scanners and remote sensing imaging systems. We show that this approach can significantly improve the results of separate reconstruction of each row, providing very good reconstruction quality with reasonable complexity.
A Scratch-like visual programming system for Microsoft Windows Phone 8
Venue: arXiv cs.CY 2013
Year: 2013

Pocket Code is a free and open source mobile visual programming system for the Catrobat language. It allows users, starting from the age of eight, to develop games and animations with their smartphones. Children can create programs with their Android phone, iPhone, Windows Phone, or other smartphone with an HTML5 browser. No notebook or desktop computer is needed. Pocket Code is inspired by, but distinct from, the Scratch programming system developed by the Lifelong Kindergarten Group at the MIT Media Lab. This tool demo describes an in-practice experience with Pocket Code, the Windows Phone IDE for the Catrobat language.
Codeless Screen-Oriented Programming for Enterprise Mobile Applications
Venue: arXiv cs.SE 2013
Year: 2013

Designing the user interface (UI) of mobile applications in the enterprise is performed in many cases by the application users who represent the business needs. This is based on existing developed enterprise services that can be accessed by these applications. Design the UI of the mobile applications require programming environments that are as much as possible codeless and easy to use. In this paper, we present NitroGen which is a cloud-based platform-independent tool that provides with no installation, a consumable integrated set of capabilities to construct mobile solutions aiming at reducing development and maintenance costs. We further illustrate how to use NitroGen showing its visual touch-based mostly codeless way of programming. NitroGen can easily connect to back-end services thus enable fast and facile development in enterprises.
Newton representation of functions over natural integers having integral difference ratios
Venue: arXiv cs.DM 2013
Year: 2013

Different questions lead to the same class of functions from natural integers to integers: those which have integral difference ratios, i.e. verifying $f(a)-f(b)\equiv0 \pmod {(a-b)}$ for all $a>b$. We characterize this class of functions via their representations as Newton series. This class, which obviously contains all polynomials with integral coefficients, also contains unexpected functions, for instance all functions $x\mapsto\lfloor e^{1/a}\;a^x\;x!\rfloor$, with $a\in\Z\setminus\{0,1\}$, and a function equal to $\lfloor e\;x!\rfloor$ except on 0. Finally, to study the complement class, we look at functions $\N\to\RR$ which are not uniformly close to any function having integral difference ratios.
Bounds on inference
Venue: arXiv cs.IT 2013
Year: 2013

Lower bounds for the average probability of error of estimating a hidden variable X given an observation of a correlated random variable Y, and Fano's inequality in particular, play a central role in information theory. In this paper, we present a lower bound for the average estimation error based on the marginal distribution of X and the principal inertias of the joint distribution matrix of X and Y. Furthermore, we discuss an information measure based on the sum of the largest principal inertias, called k-correlation, which generalizes maximal correlation. We show that k-correlation satisfies the Data Processing Inequality and is convex in the conditional distribution of Y given X. Finally, we investigate how to answer a fundamental question in inference and privacy: given an observation Y, can we estimate a function f(X) of the hidden random variable X with an average error below a certain threshold? We provide a general method for answering this question using an approach based on rate-distortion theory.
Optical Disk with Blu-Ray Technology
Venue: arXiv cs.OH 2013
Year: 2013

Blu-ray is the name of a next-generation optical disc format jointly developed by the Blu-ray Disc Association a group of the world's leading consumer electronics, personal computer and media manufacturers. The format was developed to enable recording, rewriting and playback of high-definition video, as well as storing large amounts of data. This extra capacity combined with the use of advanced video and audio codec will offer consumers an unprecedented HD experience. While current optical disc technologies such as DVD and DVDRAM rely on a red laser to read and write data, the new format uses a blue-violet laser instead, hence the name Blu-ray. Blu ray also promises some added security, making ways for copyright protections. Blu-ray discs can have a unique ID written on them to have copyright protection inside the recorded streams. Blu .ray disc takes the DVD technology one step further, just by using a laser with a nice color.
Cache Discovery Policies of MANET
Venue: arXiv cs.NI 2013
Year: 2013

In situations where establishing a network infrastructure is impossible, Ad-hoc networks are considered particularly important. Most of the previous research in Ad-hoc networks concentrated on the development and enhancement of dynamic routing protocols, which could efficiently discover routes between two communicating nodes. Although routing strategies is an important topic in MANETs, other topics such as data access are also crucial since the final goal of using Ad-hoc networks is to provide data access to mobile nodes. One of the most attractive techniques used to improve the data access performance in MANET environment is cooperative caching; which means multiple caching nodes share and cooperatively manage the cached contents. It is lead the research to important questions, what data should be cached, where, when, and how? A cooperative caching addressed into two basic issues: cache discovery and cache management, in other words, how to find requested data efficiently and how to manage an individual cache to improve the overall capacity of a cooperated cache. In this paper we have made a review of the existing cache discovery algorithms to address four stages after application request and before server response, using an historical file to record the previous data requests, and proposed cluster architecture with data cluster head election to store efficient information for future use and reducing the cost of flooding. In addition, this paper suggests some alternative techniques for cache discovery. Finally, the paper concludes with a discussion on future research directions.
Constellation Optimization in the Presence of Strong Phase Noise
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we address the problem of optimizing signal constellations for strong phase noise. The problem is investigated by considering three optimization formulations, which provide an analytical framework for constellation design. In the first formulation, we seek to design constellations that minimize the symbol error probability (SEP) for an approximate ML detector in the presence of phase noise. In the second formulation, we optimize constellations in terms of mutual information (MI) for the effective discrete channel consisting of phase noise, additive white Gaussian noise, and the approximate ML detector. To this end, we derive the MI of this discrete channel. Finally, we optimize constellations in terms of the MI for the phase noise channel. We give two analytical characterizations of the MI of this channel, which are shown to be accurate for a wide range of signal-to-noise ratios and phase noise variances. For each formulation, we present a detailed analysis of the optimal constellations and their performance in the presence of strong phase noise. We show that the optimal constellations significantly outperform conventional constellations and those proposed in the literature in terms of SEP, error floors, and MI.
QuickLexSort: An efficient algorithm for lexicographically sorting nested restrictions of a database
Venue: arXiv cs.DS 2013
Year: 2013

Lexicographical sorting is a fundamental problem with applications to contingency tables, databases, Bayesian networks, and more. A standard method to lexicographically sort general data is to iteratively use a stable sort -- a sort which preserves existing orders. Here we present a new method of lexicographical sorting called QuickLexSort. Whereas a stable sort based lexicographical sorting algorithm operates from the least important to most important features, in contrast, QuickLexSort sorts from the most important to least important features, refining the sort as it goes. QuickLexSort first requires a one-time modest pre-processing step where each feature of the data set is sorted independently. When lexicographically sorting a database, QuickLexSort (including pre-processing) has comparable running time to using a stable sort based approach. For a data base with $m$ rows and $n$ columns, and a sorting algorithm running in time $O(mlog(m))$, a stable sort based lexicographical sort and QuickLexSort will both take time $O(nmlog(m))$. However in many applications one has the need to lexicographically sort nested data, e.g.\ all possible sub-matrices up to a certain cardinality of columns. In such cases we show QuickLexSort gives a performance improvement of a log factor of the database length (rows in matrix) over using a standard stable sort based approach. E.g.\ to sort all sub-matrices up to cardinality $k$, QuickLexSort has running time $O(mn^k)$ whereas a stable sort based lexicographical sort will take time $O(mlog(m)n^k)$. After the pre-processing step that is run only once for the entire matrix, QuickLexSort has a running time linear in the number of nested sub-matrices to sort. We conclude with an application to Bayesian network scoring to detect epistasis using SNP marker data.
GENIUS: Generating Usable User Interfaces
Venue: arXiv cs.HC 2013
Year: 2013

In this report we describe the implementation and approach developed during the GENIUS Project. The GENIUS project is about the generation of usable user interfaces. It tries to cope with issues related to automatic generation where, usually end-user complain about the poor quality (in term of usability) of generated UI. To solve this issue GENIUS relies on Model-Driven Engineering principles and several MDE tools. Notably, it consists in a set of metamodels specific to the interaction, a set of model transformation embedding usability criteria and an environment for model execution/ interpretation.
The reachability problem for vector addition systems with a stack is not elementary
Venue: arXiv cs.FL 2013
Year: 2013

By adapting the iterative yardstick construction of Stockmeyer, we show that the reachability problem for vector addition systems with a stack does not have elementary complexity. As a corollary, the same lower bound holds for the satisfiability problem for a two-variable first-order logic on trees in which unbounded data may label only leaf nodes. Whether the two problems are decidable remains an open question.
Delineating geographical regions with networks of human interactions in an extensive set of countries
Venue: arXiv cs.SI 2013
Year: 2013

Large-scale networks of human interaction, in particular country-wide telephone call networks, can be used to redraw geographical maps by applying algorithms of topological community detection. The geographic projections of the emerging areas in a few recent studies on single regions have been suggested to share two distinct properties: first, they are cohesive, and second, they tend to closely follow socio-economic boundaries and are similar to existing political regions in size and number. Here we use an extended set of countries and clustering indices to quantify overlaps, providing ample additional evidence for these observations using phone data from countries of various scales across Europe, Asia, and Africa: France, the UK, Italy, Belgium, Portugal, Saudi Arabia, and Ivory Coast. In our analysis we use the known approach of partitioning country-wide networks, and an additional iterative partitioning of each of the first level communities into sub-communities, revealing that cohesiveness and matching of official regions can also be observed on a second level if spatial resolution of the data is high enough. The method has possible policy implications on the definition of the borderlines and sizes of administrative regions.
Overflow Probability of Variable-length Codes with Codeword Cost
Venue: arXiv cs.IT 2013
Year: 2013

Lossless variable-length source coding with codeword cost is considered for general sources. The problem setting, where we impose on unequal costs on code symbols, is called the variable-length coding with codeword cost. In this problem, the infimum of average codeword cost have been determined for general sources. On the other hand, overflow probability, which is defined as the probability of codeword cost being above a threshold, have not been considered yet. In this paper, we determine the infimum of achievable threshold in the first-order sense and the second-order sense for general sources and compute it for some special sources such as i.i.d. sources and mixed sources. A relationship between the overflow probability of variable-length coding and the error probability of fixed-length coding is also revealed. Our analysis is based on the information-spectrum methods.
Accounting for Secondary Uncertainty: Efficient Computation of Portfolio Risk Measures on Multi and Many Core Architectures
Venue: arXiv cs.DC 2013
Year: 2013

Aggregate Risk Analysis is a computationally intensive and a data intensive problem, thereby making the application of high-performance computing techniques interesting. In this paper, the design and implementation of a parallel Aggregate Risk Analysis algorithm on multi-core CPU and many-core GPU platforms are explored. The efficient computation of key risk measures, including Probable Maximum Loss (PML) and the Tail Value-at-Risk (TVaR) in the presence of both primary and secondary uncertainty for a portfolio of property catastrophe insurance treaties is considered. Primary Uncertainty is the the uncertainty associated with whether a catastrophe event occurs or not in a simulated year, while Secondary Uncertainty is the uncertainty in the amount of loss when the event occurs. A number of statistical algorithms are investigated for computing secondary uncertainty. Numerous challenges such as loading large data onto hardware with limited memory and organising it are addressed. The results obtained from experimental studies are encouraging. Consider for example, an aggregate risk analysis involving 800,000 trials, with 1,000 catastrophic events per trial, a million locations, and a complex contract structure taking into account secondary uncertainty. The analysis can be performed in just 41 seconds on a GPU, that is 24x faster than the sequential counterpart on a fast multi-core CPU. The results indicate that GPUs can be used to efficiently accelerate aggregate risk analysis even in the presence of secondary uncertainty.
An Event Structure Model for Probabilistic Concurrent Kleene Algebra
Venue: arXiv cs.LO 2013
Year: 2013

We give a new true-concurrent model for probabilistic concurrent Kleene algebra. The model is based on probabilistic event structures, which combines ideas from Katoen's work on probabilistic concurrency and Varacca's probabilistic prime event structures. The event structures are compared with a true-concurrent version of Segala's probabilistic simulation. Finally, the algebraic properties of the model are summarised to the extent that they can be used to derive techniques such as probabilistic rely/guarantee inference rules.
The Generalized Traveling Salesman Problem solved with Ant Algorithms
Venue: arXiv cs.AI 2013
Year: 2013

A well known N P-hard problem called the Generalized Traveling Salesman Problem (GTSP) is considered. In GTSP the nodes of a complete undirected graph are partitioned into clusters. The objective is to find a minimum cost tour passing through exactly one node from each cluster. An exact exponential time algorithm and an effective meta-heuristic algorithm for the problem are presented. The meta-heuristic proposed is a modified Ant Colony System (ACS) algorithm called Reinforcing Ant Colony System (RACS) which introduces new correction rules in the ACS algorithm. Computational results are reported for many standard test problems. The proposed algorithm is competitive with the other already proposed heuristics for the GTSP in both solution quality and computational time.
Survey on Modelling Methods Applicable to Gene Regulatory Network
Venue: arXiv cs.CE 2013
Year: 2013

Gene Regulatory Network (GRN) plays an important role in knowing insight of cellular life cycle. It gives information about at which different environmental conditions genes of particular interest get over expressed or under expressed. Modelling of GRN is nothing but finding interactive relationships between genes. Interaction can be positive or negative. For inference of GRN, time series data provided by Microarray technology is used. Key factors to be considered while constructing GRN are scalability, robustness, reliability and maximum detection of true positive interactions between genes. This paper gives detailed technical review of existing methods applied for building of GRN along with scope for future work.
Web Usage Mining: Pattern Discovery and Forecasting
Venue: arXiv cs.DB 2013
Year: 2013

Web usage mining: automatic discovery of patterns in clickstreams and associated data collected or generated as a result of user interactions with one or more Web sites. This paper describes web usage mining for our college log files to analyze the behavioral patterns and profiles of users interacting with a Web site. The discovered patterns are represented as clusters that are frequently accessed by groups of visitors with common interests. In this paper, the visitors and hits were forecasted to predict the further access statistics.
Pioneers of Influence Propagation in Social Networks
Venue: arXiv cs.SI 2013
Year: 2013

With the growing importance of corporate viral marketing campaigns on online social networks, the interest in studies of influence propagation through networks is higher than ever. In a viral marketing campaign, a firm initially targets a small set of pioneers and hopes that they would influence a sizeable fraction of the population by diffusion of influence through the network. In general, any marketing campaign might fail to go viral in the first try. As such, it would be useful to have some guide to evaluate the effectiveness of the campaign and judge whether it is worthy of further resources, and in case the campaign has potential, how to hit upon a good pioneer who can make the campaign go viral. In this paper, we present a diffusion model developed by enriching the generalized random graph (a.k.a. configuration model) to provide insight into these questions. We offer the intuition behind the results on this model, rigorously proved in Blaszczyszyn & Gaurav(2013), and illustrate them here by taking examples of random networks having prototypical degree distributions - Poisson degree distribution, which is commonly used as a kind of benchmark, and Power Law degree distribution, which is normally used to approximate the real-world networks. On these networks, the members are assumed to have varying attitudes towards propagating the information. We analyze three cases, in particular - (1) Bernoulli transmissions, when a member influences each of its friend with probability p; (2) Node percolation, when a member influences all its friends with probability p and none with probability 1-p; (3) Coupon-collector transmissions, when a member randomly selects one of his friends K times with replacement. We assume that the configuration model is the closest approximation of a large online social network, when the information available about the network is very limited. The key insight offered by this study from a firm's perspective is regarding how to evaluate the effectiveness of a marketing campaign and do cost-benefit analysis by collecting relevant statistical data from the pioneers it selects. The campaign evaluation criterion is informed by the observation that if the parameters of the underlying network and the campaign effectiveness are such that the campaign can indeed reach a significant fraction of the population, then the set of good pioneers also forms a significant fraction of the population. Therefore, in such a case, the firms can even adopt the naive strategy of repeatedly picking and targeting some number of pioneers at random from the population. With this strategy, the probability of them picking a good pioneer will increase geometrically fast with the number of tries.
Scenarios of Destruction for Large Network and Increasing Reliability
Venue: arXiv cs.NI 2013
Year: 2013

Damage scenarios for large networks are considered. The cascade scenario is described by means of powers of adjacency matrix. More difficult probabilistic variants of the large network damage are modeling by Markov chains. For reliability augmentation of networks we add a set of random intermediate agents with big dimensionality. It provides high reliability of all system even with low reliability of single components. Probabilistic estimation of reliability for reinforced network is made.
Model-free control of nonlinear power converters
Venue: arXiv cs.SY 2013
Year: 2013

A new "model-free" control methodology is applied to a boost power converter. The properties of the boost converter allow to evaluate the performances of the model-free strategy in the case of switching nonlinear transfer functions, regarding load variations. Our approach, which utilizes "intelligent" PI controllers, does not require any converter model identification while ensuring the stability and the robustness of the controlled system. Simulation results show that, with a simple control structure, the proposed control method is almost insensitive to fluctuations and large load variations.