OpenRaiser/Intern-Atlas huggingface dataset:
Feature and Variable Selection in Classification
Venue: arXiv cs.LG 2014
Year: 2014

The amount of information in the form of features and variables avail- able to machine learning algorithms is ever increasing. This can lead to classifiers that are prone to overfitting in high dimensions, high di- mensional models do not lend themselves to interpretable results, and the CPU and memory resources necessary to run on high-dimensional datasets severly limit the applications of the approaches. Variable and feature selection aim to remedy this by finding a subset of features that in some way captures the information provided best. In this paper we present the general methodology and highlight some specific approaches.
On the role of symmetry in solving maximum lifetime problem in two-dimensional sensor networks
Venue: arXiv cs.NI 2014
Year: 2014

We analyze a continuous and discrete symmetries of the maximum lifetime problem in two dimensional sensor networks. We show, how a symmetry of the network and invariance of the problem under a given transformation group $G$ can be utilized to simplify its solution. We prove, that for a $G$-invariant maximum lifetime problem there exists a $G$-invariant solution. Constrains which follow from the $G$-invariance allow to reduce the problem and its solution to a subset, an optimal fundamental region of the sensor network. We analyze in detail solutions of the maximum lifetime problem invariant under a group of isometry transformations of a two dimensional Euclidean plane.
New Codes and Inner Bounds for Exact Repair in Distributed Storage Systems
Venue: arXiv cs.IT 2014
Year: 2014

We study the exact-repair tradeoff between storage and repair bandwidth in distributed storage systems (DSS). We give new inner bounds for the tradeoff region and provide code constructions that achieve these bounds.
GraphX: Unifying Data-Parallel and Graph-Parallel Analytics
Venue: arXiv cs.DB 2014
Year: 2014

From social networks to language modeling, the growing scale and importance of graph data has driven the development of numerous new graph-parallel systems (e.g., Pregel, GraphLab). By restricting the computation that can be expressed and introducing new techniques to partition and distribute the graph, these systems can efficiently execute iterative graph algorithms orders of magnitude faster than more general data-parallel systems. However, the same restrictions that enable the performance gains also make it difficult to express many of the important stages in a typical graph-analytics pipeline: constructing the graph, modifying its structure, or expressing computation that spans multiple graphs. As a consequence, existing graph analytics pipelines compose graph-parallel and data-parallel systems using external storage systems, leading to extensive data movement and complicated programming model. To address these challenges we introduce GraphX, a distributed graph computation framework that unifies graph-parallel and data-parallel computation. GraphX provides a small, core set of graph-parallel operators expressive enough to implement the Pregel and PowerGraph abstractions, yet simple enough to be cast in relational algebra. GraphX uses a collection of query optimization techniques such as automatic join rewrites to efficiently implement these graph-parallel operators. We evaluate GraphX on real-world graphs and workloads and demonstrate that GraphX achieves comparable performance as specialized graph computation systems, while outperforming them in end-to-end graph pipelines. Moreover, GraphX achieves a balance between expressiveness, performance, and ease of use.
L-Shape based Layout Fracturing for E-Beam Lithography
Venue: arXiv cs.AR 2014
Year: 2014

Layout fracturing is a fundamental step in mask data preparation and e-beam lithography (EBL) writing. To increase EBL throughput, recently a new L-shape writing strategy is proposed, which calls for new L-shape fracturing, versus the conventional rectangular fracturing. Meanwhile, during layout fracturing, one must minimize very small/narrow features, also called slivers, due to manufacturability concern. This paper addresses this new research problem of how to perform L-shaped fracturing with sliver minimization. We propose two novel algorithms. The first one, rectangular merging (RM), starts from a set of rectangular fractures and merges them optimally to form L-shape fracturing. The second algorithm, direct L-shape fracturing (DLF), directly and effectively fractures the input layouts into L-shapes with sliver minimization. The experimental results show that our algorithms are very effective.
Strong Equivalence Relations for Iterated Models
Venue: arXiv cs.DC 2014
Year: 2014

The Iterated Immediate Snapshot model (IIS), due to its elegant geometrical representation, has become standard for applying topological reasoning to distributed computing. Its modular structure makes it easier to analyze than the more realistic (non-iterated) read-write Atomic-Snapshot memory model (AS). It is known that AS and IIS are equivalent with respect to \emph{wait-free task} computability: a distributed task is solvable in AS if and only if it solvable in IIS. We observe, however, that this equivalence is not sufficient in order to explore solvability of tasks in \emph{sub-models} of AS (i.e. proper subsets of its runs) or computability of \emph{long-lived} objects, and a stronger equivalence relation is needed. In this paper, we consider \emph{adversarial} sub-models of AS and IIS specified by the sets of processes that can be \emph{correct} in a model run. We show that AS and IIS are equivalent in a strong way: a (possibly long-lived) object is implementable in AS under a given adversary if and only if it is implementable in IIS under the same adversary. %This holds whether the object is one-shot or long-lived. Therefore, the computability of any object in shared memory under an adversarial AS scheduler can be equivalently investigated in IIS.
Sliding window and compressive sensing for low-field dynamic magnetic resonance imaging
Venue: arXiv cs.CE 2014
Year: 2014

We describe an acquisition/processing procedure for image reconstruction in dynamic Magnetic Resonance Imaging (MRI). The approach requires sliding window to record a set of trajectories in the k-space, standard regularization to reconstruct an estimate of the object and compressed sensing to recover image residuals. We validated this approach in the case of specific simulated experiments and, in the case of real measurements, we showed that the procedure is reliable even in the case of data acquired by means of a low-field scanner.
Optimizing the Cost for Resource Subscription Policy in IaaS Cloud
Venue: arXiv cs.DC 2014
Year: 2014

Cloud computing allow the users to efficiently and dynamically provision computing resource to meet their IT needs. Cloud Provider offers two subscription plan to the customer namely reservation and on-demand. The reservation plan is typically cheaper than on-demand plan. If the actual computing demand is known in advance reserving the resource would be straightforward. The challenge is how to make properly resource provisioning and how the customers efficiently purchase the provisioning options under reservation and on-demand. To address this issue, two-phase algorithm are proposed to minimize service provision cost in both reservation and on-demand plan. To reserve the correct and optimal amount of resources during reservation, proposed a mathematical formulae in the first phase. To predict resource demand, use kalman filter in the second phase. The evaluation result shows that the two-phase algorithm can significantly reduce the provision cost and the prediction is of reasonable accuracy.
Linial's Lower Bound Made Easy
Venue: arXiv cs.DC 2014
Year: 2014

Linial's seminal result shows that any deterministic distributed algorithm that finds a $3$-colouring of an $n$-cycle requires at least $\log^*(n)/2 - 1$ communication rounds. We give a new simpler proof of this theorem.
Real-Time Hand Shape Classification
Venue: arXiv cs.CV 2014
Year: 2014

The problem of hand shape classification is challenging since a hand is characterized by a large number of degrees of freedom. Numerous shape descriptors have been proposed and applied over the years to estimate and classify hand poses in reasonable time. In this paper we discuss our parallel framework for real-time hand shape classification applicable in real-time applications. We show how the number of gallery images influences the classification accuracy and execution time of the parallel algorithm. We present the speedup and efficiency analyses that prove the efficacy of the parallel implementation. Noteworthy, different methods can be used at each step of our parallel framework. Here, we combine the shape contexts with the appearance-based techniques to enhance the robustness of the algorithm and to increase the classification score. An extensive experimental study proves the superiority of the proposed approach over existing state-of-the-art methods.
An efficient algorithm for the entropy rate of a hidden Markov model with unambiguous symbols
Venue: arXiv cs.IT 2014
Year: 2014

We demonstrate an efficient formula to compute the entropy rate $H(μ)$ of a hidden Markov process with $q$ output symbols where at least one symbol is unambiguously received. Using an approximation to $H(μ)$ to the first $N$ terms we give a $O(Nq^3$) algorithm to compute the entropy rate of the hidden Markov model. We use the algorithm to estimate the entropy rate when the parameters of the hidden Markov model are unknown.In the case of $q =2$ the process is the output of the Z-channel and we use this fact to give bounds on the capacity of the Gilbert channel.
Design and Implementation of Hierarchical Visual cryptography with Expansion less Shares
Venue: arXiv cs.CR 2014
Year: 2014

Novel idea of hierarchical visual cryptography is stated in this paper. The key concept of hierarchical visual cryptography is based upon visual cryptography. Visual cryptography encrypts secret information into two pieces called as shares. These two shares are stacked together by logical XOR operation to reveal the original secret. Hierarchical visual cryptography encrypts the secret in various levels. The encryption in turn is expansionless. The original secret size is retained in the shares at all levels. In this paper secret is encrypted at two different levels. Four shares are generated out of hierarchical visual cryptography. Any three shares are collectively taken to form the key share. All shares generated are meaningless giving no information by visual inspection. Performance analysis is also obtained based upon various categories of secrets. The greying effect is completely removed while revealing the secret Removal of greying effect do not change the meaning of secret.
Tree-based Coarsening and Partitioning of Complex Networks
Venue: arXiv cs.DS 2014
Year: 2014

Many applications produce massive complex networks whose analysis would benefit from parallel processing. Parallel algorithms, in turn, often require a suitable network partition. For solving optimization tasks such as graph partitioning on large networks, multilevel methods are preferred in practice. Yet, complex networks pose challenges to established multilevel algorithms, in particular to their coarsening phase. One way to specify a (recursive) coarsening of a graph is to rate its edges and then contract the edges as prioritized by the rating. In this paper we (i) define weights for the edges of a network that express the edges' importance for connectivity, (ii) compute a minimum weight spanning tree $T^m$ with respect to these weights, and (iii) rate the network edges based on the conductance values of $T^m$'s fundamental cuts. To this end, we also (iv) develop the first optimal linear-time algorithm to compute the conductance values of \emph{all} fundamental cuts of a given spanning tree. We integrate the new edge rating into a leading multilevel graph partitioner and equip the latter with a new greedy postprocessing for optimizing the maximum communication volume (MCV). Experiments on bipartitioning frequently used benchmark networks show that the postprocessing already reduces MCV by 11.3%. Our new edge rating further reduces MCV by 10.3% compared to the previously best rating with the postprocessing in place for both ratings. In total, with a modest increase in running time, our new approach reduces the MCV of complex network partitions by 20.4%.
Computing Agents for Decision Support Systems
Venue: arXiv cs.MA 2014
Year: 2014

In decision support systems, it is essential to get a candidate solution fast, even if it means resorting to an approximation. This constraint introduces a scalability requirement with regard to the kind of heuristics which can be used in such systems. As execution time is bounded, these algorithms need to give better results and scale up with additional computing resources instead of additional time. In this paper, we show how multi-agent systems can fulfil these requirements. We recall as an example the concept of Evolutionary Multi-Agent Systems, which combine evolutionary and agent computing paradigms. We describe several possible implementations and present experimental results demonstrating how additional resources improve the efficiency of such systems.
An Anti-Folk Theorem for Large Repeated Games with Imperfect Monitoring
Venue: arXiv cs.GT 2014
Year: 2014

We study infinitely repeated games in settings of imperfect monitoring. We first prove a family of theorems that show that when the signals observed by the players satisfy a condition known as $(ε, γ)$-differential privacy, that the folk theorem has little bite: for values of $ε$ and $γ$ sufficiently small, for a fixed discount factor, any equilibrium of the repeated game involve players playing approximate equilibria of the stage game in every period. Next, we argue that in large games ($n$ player games in which unilateral deviations by single players have only a small impact on the utility of other players), many monitoring settings naturally lead to signals that satisfy $(ε,γ)$-differential privacy, for $ε$ and $γ$ tending to zero as the number of players $n$ grows large. We conclude that in such settings, the set of equilibria of the repeated game collapse to the set of equilibria of the stage game.
Efficient Truss Maintenance in Evolving Networks
Venue: arXiv cs.DB 2014
Year: 2014

Truss was proposed to study social network data represented by graphs. A k-truss of a graph is a cohesive subgraph, in which each edge is contained in at least k-2 triangles within the subgraph. While truss has been demonstrated as superior to model the close relationship in social networks and efficient algorithms for finding trusses have been extensively studied, very little attention has been paid to truss maintenance. However, most social networks are evolving networks. It may be infeasible to recompute trusses from scratch from time to time in order to find the up-to-date $k$-trusses in the evolving networks. In this paper, we discuss how to maintain trusses in a graph with dynamic updates. We first discuss a set of properties on maintaining trusses, then propose algorithms on maintaining trusses on edge deletions and insertions, finally, we discuss truss index maintenance. We test the proposed techniques on real datasets. The experiment results show the promise of our work.
Harnessing the Complexity of Education with Information Technology
Venue: arXiv cs.CY 2014
Year: 2014

Education at all levels is facing several challenges in most countries, such as low quality, high costs, lack of educators, and unsatisfied student demand. Traditional approaches are becoming unable to deliver the required education. Several causes for this inefficiency can be identified. I argue that beyond specific causes, the lack of effective education is related to complexity. However, information technology is helping us overcome this complexity.
Tasks for Temporal Graph Visualisation
Venue: arXiv cs.OH 2014
Year: 2014

In [1], we describe the design and development of a task taxonomy for temporal graph visualisation. This paper details the full instantiation of that task taxonomy. Our task taxonomy is based on the Andrienko framework [2], which uses a systematic approach to develop a formal task framework for visual tasks specifically associated with Exploratory Data Analysis. The Andrienko framework is intended to be applicable to all types of data, however, it does not consider relational (graph) data. We therefore extended both their data model and task framework for temporal graph data, and instantiated the extended version to produce a comprehensive list of tasks of interest during exploratory analysis of temporal graph data. As expected, our instantiation of the framework resulted in a very large task list; with more than 144 variations of attribute based tasks alone, it is too large to fit in a standard journal paper, hence we provide the detailed listing in this document.
TRIAD: a triple patterning lithography aware detailed router
Venue: arXiv cs.AR 2014
Year: 2014

TPL-friendly detailed routers require a systematic approach to detect TPL conflicts. However, the complexity of conflict graph (CG) impedes directly detecting TPL conflicts in CG. This work proposes a token graph-embedded conflict graph (TECG) to facilitate the TPL conflict detection while maintaining high coloring-flexibility. We then develop a TPL aware detailed router (TRIAD) by applying TECG to a gridless router with the TPL stitch generation. Compared to a greedy coloring approach, experimental results indicate that TRIAD generates no conflicts and few stitches with shorter wirelength at the cost of 2.41x of runtime.
MCMAS-SLK: A Model Checker for the Verification of Strategy Logic Specifications
Venue: arXiv cs.LO 2014
Year: 2014

We introduce MCMAS-SLK, a BDD-based model checker for the verification of systems against specifications expressed in a novel, epistemic variant of strategy logic. We give syntax and semantics of the specification language and introduce a labelling algorithm for epistemic and strategy logic modalities. We provide details of the checker which can also be used for synthesising agents' strategies so that a specification is satisfied by the system. We evaluate the efficiency of the implementation by discussing the results obtained for the dining cryptographers protocol and a variant of the cake-cutting problem.
A Programming Language Oriented Approach to Computability
Venue: arXiv cs.PL 2014
Year: 2014

The field of computability and complexity was, where computer science sprung from. Turing, Church, and Kleene all developed formalisms that demonstrated what they held "intuitively computable". The times change however and today's (aspiring) computer scientists are less proficient in building automata or composing functions and are much more native to the world of programming languages. This article will try to introduce typical concepts of computability theory and complexity in a form more fitted for a modern developer. It is mostly based on \cite{jones}, but takes input from other sources to provide examples, additional information, etc.
1-D and 2-D Parallel Algorithms for All-Pairs Similarity Problem
Venue: arXiv cs.IR 2014
Year: 2014

All-pairs similarity problem asks to find all vector pairs in a set of vectors the similarities of which surpass a given similarity threshold, and it is a computational kernel in data mining and information retrieval for several tasks. We investigate the parallelization of a recent fast sequential algorithm. We propose effective 1-D and 2-D data distribution strategies that preserve the essential optimizations in the fast algorithm. 1-D parallel algorithms distribute either dimensions or vectors, whereas the 2-D parallel algorithm distributes data both ways. Additional contributions to the 1-D vertical distribution include a local pruning strategy to reduce the number of candidates, a recursive pruning algorithm, and block processing to reduce imbalance. The parallel algorithms were programmed in OCaml which affords much convenience. Our experiments indicate that the performance depends on the dataset, therefore a variety of parallelizations is useful.
Regular Combinators for String Transformations
Venue: arXiv cs.FL 2014
Year: 2014

We focus on (partial) functions that map input strings to a monoid such as the set of integers with addition and the set of output strings with concatenation. The notion of regularity for such functions has been defined using two-way finite-state transducers, (one-way) cost register automata, and MSO-definable graph transformations. In this paper, we give an algebraic and machine-independent characterization of this class analogous to the definition of regular languages by regular expressions. When the monoid is commutative, we prove that every regular function can be constructed from constant functions using the combinators of choice, split sum, and iterated sum, that are analogs of union, concatenation, and Kleene-*, respectively, but enforce unique (or unambiguous) parsing. Our main result is for the general case of non-commutative monoids, which is of particular interest for capturing regular string-to-string transformations for document processing. We prove that the following additional combinators suffice for constructing all regular functions: (1) the left-additive versions of split sum and iterated sum, which allow transformations such as string reversal; (2) sum of functions, which allows transformations such as copying of strings; and (3) function composition, or alternatively, a new concept of chained sum, which allows output values from adjacent blocks to mix.
Community Detection via Random and Adaptive Sampling
Venue: arXiv cs.SI 2014
Year: 2014

In this paper, we consider networks consisting of a finite number of non-overlapping communities. To extract these communities, the interaction between pairs of nodes may be sampled from a large available data set, which allows a given node pair to be sampled several times. When a node pair is sampled, the observed outcome is a binary random variable, equal to 1 if nodes interact and to 0 otherwise. The outcome is more likely to be positive if nodes belong to the same communities. For a given budget of node pair samples or observations, we wish to jointly design a sampling strategy (the sequence of sampled node pairs) and a clustering algorithm that recover the hidden communities with the highest possible accuracy. We consider both non-adaptive and adaptive sampling strategies, and for both classes of strategies, we derive fundamental performance limits satisfied by any sampling and clustering algorithm. In particular, we provide necessary conditions for the existence of algorithms recovering the communities accurately as the network size grows large. We also devise simple algorithms that accurately reconstruct the communities when this is at all possible, hence proving that the proposed necessary conditions for accurate community detection are also sufficient. The classical problem of community detection in the stochastic block model can be seen as a particular instance of the problems consider here. But our framework covers more general scenarios where the sequence of sampled node pairs can be designed in an adaptive manner. The paper provides new results for the stochastic block model, and extends the analysis to the case of adaptive sampling.