OpenRaiser/Intern-Atlas huggingface dataset:
Rethinking Abstractions for Big Data: Why, Where, How, and What
Venue: arXiv cs.GL 2013
Year: 2013

Big data refers to large and complex data sets that, under existing approaches, exceed the capacity and capability of current compute platforms, systems software, analytical tools and human understanding. Numerous lessons on the scalability of big data can already be found in asymptotic analysis of algorithms and from the high-performance computing (HPC) and applications communities. However, scale is only one aspect of current big data trends; fundamentally, current and emerging problems in big data are a result of unprecedented complexity--in the structure of the data and how to analyze it, in dealing with unreliability and redundancy, in addressing the human factors of comprehending complex data sets, in formulating meaningful analyses, and in managing the dense, power-hungry data centers that house big data. The computer science solution to complexity is finding the right abstractions, those that hide as much triviality as possible while revealing the essence of the problem that is being addressed. The "big data challenge" has disrupted computer science by stressing to the very limits the familiar abstractions which define the relevant subfields in data analysis, data management and the underlying parallel systems. As a result, not enough of these challenges are revealed by isolating abstractions in a traditional software stack or standard algorithmic and analytical techniques, and attempts to address complexity either oversimplify or require low-level management of details. The authors believe that the abstractions for big data need to be rethought, and this reorganization needs to evolve and be sustained through continued cross-disciplinary collaboration.
The Effect of Communication and Synchronization on Amdahl Law in Multicore Systems
Venue: arXiv cs.AR 2013
Year: 2013

This work analyses the effects of sequential-to-parallel synchronization and inter-core communication on multicore performance, speedup and scaling. A modification of Amdahl law is formulated, to reflect the finding that parallel speedup is lower than originally predicted, due to these effects. In applications with high inter-core communication requirements, the workload should be executed on a small number of cores, and applications of high sequential-to-parallel synchronization requirements may better be executed by the sequential core, even when f, the Amdahl fraction of parallelization, is very close to 1. To improve the scalability and performance speedup of a multicore, it is as important to address the synchronization and connectivity intensities of parallel algorithms as their parallelization factor.
Sparse Recovery of Streaming Signals Using L1-Homotopy
Venue: arXiv cs.IT 2013
Year: 2013

Most of the existing methods for sparse signal recovery assume a static system: the unknown signal is a finite-length vector for which a fixed set of linear measurements and a sparse representation basis are available and an L1-norm minimization program is solved for the reconstruction. However, the same representation and reconstruction framework is not readily applicable in a streaming system: the unknown signal changes over time, and it is measured and reconstructed sequentially over small time intervals. In this paper, we discuss two such streaming systems and a homotopy-based algorithm for quickly solving the associated L1-norm minimization programs: 1) Recovery of a smooth, time-varying signal for which, instead of using block transforms, we use lapped orthogonal transforms for sparse representation. 2) Recovery of a sparse, time-varying signal that follows a linear dynamic model. For both the systems, we iteratively process measurements over a sliding interval and estimate sparse coefficients by solving a weighted L1-norm minimization program. Instead of solving a new L1 program from scratch at every iteration, we use an available signal estimate as a starting point in a homotopy formulation. Starting with a warm-start vector, our homotopy algorithm updates the solution in a small number of computationally inexpensive steps as the system changes. The homotopy algorithm presented in this paper is highly versatile as it can update the solution for the L1 problem in a number of dynamical settings. We demonstrate with numerical experiments that our proposed streaming recovery framework outperforms the methods that represent and reconstruct a signal as independent, disjoint blocks, in terms of quality of reconstruction, and that our proposed homotopy-based updating scheme outperforms current state-of-the-art solvers in terms of the computation time and complexity.
The essence of component-based design and coordination
Venue: arXiv cs.SE 2013
Year: 2013

Is there a characteristic of coordination languages that makes them qualitatively different from general programming languages and deserves special academic attention? This report proposes a nuanced answer in three parts. The first part highlights that coordination languages are the means by which composite software applications can be specified using components that are only available separately, or later in time, via standard interfacing mechanisms. The second part highlights that most currently used languages provide mechanisms to use externally provided components, and thus exhibit some elements of coordination. However not all do, and the availability of an external interface thus forms an objective and qualitative criterion that distinguishes coordination. The third part argues that despite the qualitative difference, the segregation of academic attention away from general language design and implementation has non-obvious cost trade-offs.
Different Approaches to Community Evolution Prediction in Blogosphere
Venue: arXiv cs.SI 2013
Year: 2013

Predicting the future direction of community evolution is a problem with high theoretical and practical significance. It allows to determine which characteristics describing communities have importance from the point of view of their future behaviour. Knowledge about the probable future career of the community aids in the decision concerning investing in contact with members of a given community and carrying out actions to achieve a key position in it. It also allows to determine effective ways of forming opinions or to protect group participants against such activities. In the paper, a new approach to group identification and prediction of future events is presented together with the comparison to existing method. Performed experiments prove a high quality of prediction results. Comparison to previous studies shows that using many measures to describe the group profile, and in consequence as a classifier input, can improve predictions.
Cellular Automata in Cryptographic Random Generators
Venue: arXiv cs.CR 2013
Year: 2013

Cryptographic schemes using one-dimensional, three-neighbor cellular automata as a primitive have been put forth since at least 1985. Early results showed good statistical pseudorandomness, and the simplicity of their construction made them a natural candidate for use in cryptographic applications. Since those early days of cellular automata, research in the field of cryptography has developed a set of tools which allow designers to prove a particular scheme to be as hard as solving an instance of a well- studied problem, suggesting a level of security for the scheme. However, little or no literature is available on whether these cellular automata can be proved secure under even generous assumptions. In fact, much of the literature falls short of providing complete, testable schemes to allow such an analysis. In this thesis, we first examine the suitability of cellular automata as a primitive for building cryptographic primitives. In this effort, we focus on pseudorandom bit generation and noninvertibility, the behavioral heart of cryptography. In particular, we focus on cyclic linear and non-linear au- tomata in some of the common configurations to be found in the literature. We examine known attacks against these constructions and, in some cases, improve the results. Finding little evidence of provable security, we then examine whether the desirable properties of cellular automata (i.e. highly parallel, simple construction) can be maintained as the automata are enhanced to provide a foundation for such proofs. This investigation leads us to a new construction of a finite state cellular automaton (FSCA) which is NP-Hard to invert. Finally, we introduce the Chasm pseudorandom generator family built on this construction and provide some initial experimental results using the NIST test suite.
Faster deterministic Feedback Vertex Set
Venue: arXiv cs.DS 2013
Year: 2013

We present two new deterministic algorithms for the Feedback Vertex Set problem parameterized by the solution size. We begin with a simple algorithm, which runs in O*((2 + ϕ)^k) time, where ϕ< 1.619 is the golden ratio. It already surpasses the previously fastest O*((1+2sqrt(2))^k)-time deterministic algorithm due to Cao et al. [SWAT 2010]. In our developments we follow the approach of Cao et al., however, thanks to a new reduction rule, we obtain not only better dependency on the parameter in the running time, but also a solution with simple analysis and only a single branching rule. Then, we present a modification of the algorithm which, using a more involved set of branching rules, achieves O*(3.592^k) running time.
Message Passing Algorithms for Phase Noise Tracking Using Tikhonov Mixtures
Venue: arXiv cs.IT 2013
Year: 2013

In this work, a new low complexity iterative algorithm for decoding data transmitted over strong phase noise channels is presented. The algorithm is based on the Sum & Product Algorithm (SPA) with phase noise messages modeled as Tikhonov mixtures. Since mixture based Bayesian inference such as SPA, creates an exponential increase in mixture order for consecutive messages, mixture reduction is necessary. We propose a low complexity mixture reduction algorithm which finds a reduced order mixture whose dissimilarity metric is mathematically proven to be upper bounded by a given threshold. As part of the mixture reduction, a new method for optimal clustering provides the closest circular distribution, in Kullback Leibler sense, to any circular mixture. We further show a method for limiting the number of tracked components and further complexity reduction approaches. We show simulation results and complexity analysis for the proposed algorithm and show better performance than other state of the art low complexity algorithms. We show that the Tikhonov mixture approximation of SPA messages is equivalent to the tracking of multiple phase trajectories, or also can be looked as smart multiple phase locked loops (PLL). When the number of components is limited to one the result is similar to a smart PLL.
A note on scheduling with low rank processing times
Venue: arXiv cs.CC 2013
Year: 2013

We consider the classical minimum makespan scheduling problem, where the processing time of job $j$ on machine $i$ is $p_{ij}$, and the matrix $P=(p_{ij})_{m\times n}$ is of a low rank. It is proved in (Bhaskara et al., SODA 2013) that rank 7 scheduling is NP-hard to approximate to a factor of $3/2-ε$, and rank 4 scheduling is APX-hard (NP-hard to approximate within a factor of $1.03-ε$). We improve this result by showing that rank 4 scheduling is already NP-hard to approximate within a factor of $3/2-ε$, and meanwhile rank 3 scheduling is APX-hard.
Controlled Experimentation in Naturalistic Mobile Settings
Venue: arXiv cs.HC 2013
Year: 2013

Performing controlled user experiments on small devices in naturalistic mobile settings has always proved to be a difficult undertaking for many Human Factors researchers. Difficulties exist, not least, because mimicking natural small device usage suffers from a lack of unobtrusive data to guide experimental design, and then validate that the experiment is proceeding naturally.Here we use observational data to derive a set of protocols and a simple checklist of validations which can be built into the design of any controlled experiment focused on the user interface of a small device. These, have been used within a series of experimental designs to measure the utility and application of experimental software. The key-point is the validation checks -- based on the observed behaviour of 400 mobile users -- to ratify that a controlled experiment is being perceived as natural by the user. While the design of the experimental route which the user follows is a major factor in the experimental setup, without check validations based on unobtrusive observed data there can be no certainty that an experiment designed to be natural is actually progressing as the design implies.
Minimal Indices for Successor Search
Venue: arXiv cs.DS 2013
Year: 2013

We give a new successor data structure which improves upon the index size of the Pǎtraşcu-Thorup data structures, reducing the index size from $O(n w^{4/5})$ bits to $O(n \log w)$ bits, with optimal probe complexity. Alternatively, our new data structure can be viewed as matching the space complexity of the (probe-suboptimal) $z$-fast trie of Belazzougui et al. Thus, we get the best of both approaches with respect to both probe count and index size. The penalty we pay is an extra $O(\log w)$ inter-register operations. Our data structure can also be used to solve the weak prefix search problem, the index size of $O(n \log w)$ bits is known to be optimal for any such data structure. The technical contributions include highly efficient single word indices, with out-degree $w/\log w$ (compared to the $w^{1/5}$ out-degree of fusion tree based indices). To construct such high efficiency single word indices we device highly efficient bit selectors which, we believe, are of independent interest.
Non-Uniform Blind Deblurring with a Spatially-Adaptive Sparse Prior
Venue: arXiv cs.CV 2013
Year: 2013

Typical blur from camera shake often deviates from the standard uniform convolutional script, in part because of problematic rotations which create greater blurring away from some unknown center point. Consequently, successful blind deconvolution requires the estimation of a spatially-varying or non-uniform blur operator. Using ideas from Bayesian inference and convex analysis, this paper derives a non-uniform blind deblurring algorithm with several desirable, yet previously-unexplored attributes. The underlying objective function includes a spatially adaptive penalty which couples the latent sharp image, non-uniform blur operator, and noise level together. This coupling allows the penalty to automatically adjust its shape based on the estimated degree of local blur and image structure such that regions with large blur or few prominent edges are discounted. Remaining regions with modest blur and revealing edges therefore dominate the overall estimation process without explicitly incorporating structure-selection heuristics. The algorithm can be implemented using a majorization-minimization strategy that is virtually parameter free. Detailed theoretical analysis and empirical validation on real images serve to validate the proposed method.
Cluster coloring of the Self-Organizing Map: An information visualization perspective
Venue: arXiv cs.LG 2013
Year: 2013

This paper takes an information visualization perspective to visual representations in the general SOM paradigm. This involves viewing SOM-based visualizations through the eyes of Bertin's and Tufte's theories on data graphics. The regular grid shape of the Self-Organizing Map (SOM), while being a virtue for linking visualizations to it, restricts representation of cluster structures. From the viewpoint of information visualization, this paper provides a general, yet simple, solution to projection-based coloring of the SOM that reveals structures. First, the proposed color space is easy to construct and customize to the purpose of use, while aiming at being perceptually correct and informative through two separable dimensions. Second, the coloring method is not dependent on any specific method of projection, but is rather modular to fit any objective function suitable for the task at hand. The cluster coloring is illustrated on two datasets: the iris data, and welfare and poverty indicators.
On M2M communications standards for smart metering
Venue: arXiv cs.NI 2013
Year: 2013

The paper discusses M2M communications standards for smart metering. One of the our goals is to show the failures of ETSI standartization process for M2M communications. Our paper proposes some extesions to ETSI standards. At the first hand, it is M-Bus protocol and Open Metering System based on M-Bus. The paper shows how to estimate wireless M-bus throughput and how to avoid collisions. After analysis of Open API for M2M, submitted to ETSI, we propose a new approach in the client-side web development - Web Intents. The main goal for our suggestions is to simplify the development phase for new applications by support asynchronous calls and JSON versus XML for data exchange.
Bioclimating Modelling: A Machine Learning Perspective
Venue: arXiv cs.LG 2013
Year: 2013

Many machine learning (ML) approaches are widely used to generate bioclimatic models for prediction of geographic range of organism as a function of climate. Applications such as prediction of range shift in organism, range of invasive species influenced by climate change are important parameters in understanding the impact of climate change. However, success of machine learning-based approaches depends on a number of factors. While it can be safely said that no particular ML technique can be effective in all applications and success of a technique is predominantly dependent on the application or the type of the problem, it is useful to understand their behaviour to ensure informed choice of techniques. This paper presents a comprehensive review of machine learning-based bioclimatic model generation and analyses the factors influencing success of such models. Considering the wide use of statistical techniques, in our discussion we also include conventional statistical techniques used in bioclimatic modelling.
Ore Polynomials in Sage
Venue: arXiv cs.SC 2013
Year: 2013

We present a Sage implementation of Ore algebras. The main features for the most common instances include basic arithmetic and actions; gcrd and lclm; D-finite closure properties; natural transformations between related algebras; guessing; desingularization; solvers for polynomials, rational functions and (generalized) power series. This paper is a tutorial on how to use the package.
Distributed conjugate gradient strategies for parameter estimation over sensor networks
Venue: arXiv cs.IT 2013
Year: 2013

This paper presents distributed adaptive algorithms based on the conjugate gradient (CG) method for distributed networks. Both incremental and diffusion adaptive solutions are all considered. The distributed conventional (CG) and modified CG (MCG) algorithms have an improved performance in terms of mean square error as compared with least-mean square (LMS)-based algorithms and a performance that is close to recursive least-squares (RLS) algorithms . The resulting algorithms are distributed, cooperative and able to respond in real time to changes in the environment.
On the Fundamental Limits of Recovering Tree Sparse Vectors from Noisy Linear Measurements
Venue: arXiv cs.IT 2013
Year: 2013

Recent breakthrough results in compressive sensing (CS) have established that many high dimensional signals can be accurately recovered from a relatively small number of non-adaptive linear observations, provided that the signals possess a sparse representation in some basis. Subsequent efforts have shown that the performance of CS can be improved by exploiting additional structure in the locations of the nonzero signal coefficients during inference, or by utilizing some form of data-dependent adaptive measurement focusing during the sensing process. To our knowledge, our own previous work was the first to establish the potential benefits that can be achieved when fusing the notions of adaptive sensing and structured sparsity -- that work examined the task of support recovery from noisy linear measurements, and established that an adaptive sensing strategy specifically tailored to signals that are tree-sparse can significantly outperform adaptive and non-adaptive sensing strategies that are agnostic to the underlying structure. In this work we establish fundamental performance limits for the task of support recovery of tree-sparse signals from noisy measurements, in settings where measurements may be obtained either non-adaptively (using a randomized Gaussian measurement strategy motivated by initial CS investigations) or by any adaptive sensing strategy. Our main results here imply that the adaptive tree sensing procedure analyzed in our previous work is nearly optimal, in the sense that no other sensing and estimation strategy can perform fundamentally better for identifying the support of tree-sparse signals.
Energy-Aware Scheme used in Multi-level Heterogeneous Wireless Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

The wireless sensor networks (WSNs) is a power constrained system, since nodes run on limited power batteries which shorten its lifespan.The main challenge facing us in the design and conception of Wireless Sensor Networks (WSNs) is to find the best way to extend their life span. The clustering algorithm is a key technique used to increase the scalability and life span of the network in general. In this paper, we propose and evaluate a distributed energy-efficient clustering algorithm for WSNs. This heterogeneous-energy protocol is a new clustering algorithm to decrease probability of failure nodes and in which we introduce the node's remaining energy so as to determine the cluster heads. We study the impact of heterogeneity of nodes on WSNs that are hierarchically clustered. Finally, simulation results show that the proposed algorithm increases the life span of the whole network and performs better than LEACH and EEHC according to the metric:first node dies.
Event-Object Reasoning with Curated Knowledge Bases: Deriving Missing Information
Venue: arXiv cs.AI 2013
Year: 2013

The broader goal of our research is to formulate answers to why and how questions with respect to knowledge bases, such as AURA. One issue we face when reasoning with many available knowledge bases is that at times needed information is missing. Examples of this include partially missing information about next sub-event, first sub-event, last sub-event, result of an event, input to an event, destination of an event, and raw material involved in an event. In many cases one can recover part of the missing knowledge through reasoning. In this paper we give a formal definition about how such missing information can be recovered and then give an ASP implementation of it. We then discuss the implication of this with respect to answering why and how questions.