OpenRaiser/Intern-Atlas huggingface dataset:
Graded quantization for multiple description coding of compressive measurements
Venue: arXiv cs.IT 2015
Year: 2015

Compressed sensing (CS) is an emerging paradigm for acquisition of compressed representations of a sparse signal. Its low complexity is appealing for resource-constrained scenarios like sensor networks. However, such scenarios are often coupled with unreliable communication channels and providing robust transmission of the acquired data to a receiver is an issue. Multiple description coding (MDC) effectively combats channel losses for systems without feedback, thus raising the interest in developing MDC methods explicitly designed for the CS framework, and exploiting its properties. We propose a method called Graded Quantization (CS-GQ) that leverages the democratic property of compressive measurements to effectively implement MDC, and we provide methods to optimize its performance. A novel decoding algorithm based on the alternating directions method of multipliers is derived to reconstruct signals from a limited number of received descriptions. Simulations are performed to assess the performance of CS-GQ against other methods in presence of packet losses. The proposed method is successful at providing robust coding of CS measurements and outperforms other schemes for the considered test metrics.
Error-Resilient Multicasting for Multi-View 3D Videos in Wireless Networks
Venue: arXiv cs.MM 2015
Year: 2015

With the emergence of naked-eye 3D mobile devices, mobile 3D video services are becoming increasingly important for video service providers, such as Youtube and Netflix, while multi-view 3D videos have the potential to inspire a variety of innovative applications. However, enabling multi-view 3D video services may overwhelm WiFi networks when every view of a video are multicasted. In this paper, therefore, we propose to incorporate depth-image-based rendering (DIBR), which allows each mobile client to synthesize the desired view from nearby left and right views, in order to effectively reduce the bandwidth consumption. Moreover, when each client suffers from packet losses, retransmissions incur additional bandwidth consumption and excess delay, which in turn undermines the quality of experience in video applications. To address the above issue, we first discover the merit of view protection via DIBR for multi-view video multicast using a mathematical analysis and then design a new protocol, named Multi-View Group Management Protocol (MVGMP), to support the dynamic join and leave of users and the change of desired views. The simulation results demonstrate that our protocol effectively reduces bandwidth consumption and increases the probability for each client to successfully playback the desired views in a multi-view 3D video.
Graphs Identified by Logics with Counting
Venue: arXiv cs.LO 2015
Year: 2015

We classify graphs and, more generally, finite relational structures that are identified by C2, that is, two-variable first-order logic with counting. Using this classification, we show that it can be decided in almost linear time whether a structure is identified by C2. Our classification implies that for every graph identified by this logic, all vertex-colored versions of it are also identified. A similar statement is true for finite relational structures. We provide constructions that solve the inversion problem for finite structures in linear time. This problem has previously been shown to be polynomial time solvable by Martin Otto. For graphs, we conclude that every C2-equivalence class contains a graph whose orbits are exactly the classes of the C2-partition of its vertex set and which has a single automorphism witnessing this fact. For general k, we show that such statements are not true by providing examples of graphs of size linear in k which are identified by C3 but for which the orbit partition is strictly finer than the Ck-partition. We also provide identified graphs which have vertex-colored versions that are not identified by Ck.
A Logarithmic Additive Integrality Gap for Bin Packing
Venue: arXiv cs.DS 2015
Year: 2015

For bin packing, the input consists of $n$ items with sizes $s_1,...,s_n \in [0,1]$ which have to be assigned to a minimum number of bins of size 1. Recently, the second author gave an LP-based polynomial time algorithm that employed techniques from discrepancy theory to find a solution using at most $OPT + O(\log OPT \cdot \log \log OPT)$ bins. In this paper, we present an approximation algorithm that has an additive gap of only $O(\log OPT)$ bins, which matches certain combinatorial lower bounds. Any further improvement would have to use more algebraic structure. Our improvement is based on a combination of discrepancy theory techniques and a novel 2-stage packing: first we pack items into containers; then we pack containers into bins of size 1. Apart from being more effective, we believe our algorithm is much cleaner than the one of Rothvoss.
Random Sampling in Computational Algebra: Helly Numbers and Violator Spaces
Venue: arXiv cs.DM 2015
Year: 2015

This paper transfers a randomized algorithm, originally used in geometric optimization, to computational problems in commutative algebra. We show that Clarkson's sampling algorithm can be applied to two problems in computational algebra: solving large-scale polynomial systems and finding small generating sets of graded ideals. The cornerstone of our work is showing that the theory of violator spaces of Gärtner et al.\ applies to polynomial ideal problems. To show this, one utilizes a Helly-type result for algebraic varieties. The resulting algorithms have expected runtime linear in the number of input polynomials, making the ideas interesting for handling systems with very large numbers of polynomials, but whose rank in the vector space of polynomials is small (e.g., when the number of variables and degree is constant).
A composite constraints approach to declarative agent-based modeling
Venue: arXiv cs.MA 2015
Year: 2015

Agent-based models (ABMs) are ubiquitous in research and industry. Currently, simulating ABMs involves at least some imperative (step-by-step) computer instructions. An alternative approach is declarative programming, in which a set of requirements is described at a high level of abstraction. Here we describe a fully declarative approach to the automated construction of simulations for ABMs. In this framework, logic for ABM simulations is encapsulated into predefined components. The user specifies a set of requirements describing the desired functionality. Additionally, each component has a set of consistency requirements. The framework iteratively seeks a simulation design that satisfies both user and system requirements. This approach allows the user to omit most details from the simulation specification, simplifying simulation design.
Index ARQ Protocol for Reliable Contents Distribution over Broadcast Channels
Venue: arXiv cs.IT 2015
Year: 2015

In the present paper, we propose a broadcast ARQ protocol based on the concept of index coding. In the proposed scenario, a server wishes to transmit a finite sequence of packets to multiple receivers via a broadcast channel with packet erasures until all of the receivers successfully receive all of the packets. In the retransmission phase, the server produces a coded packet as a retransmitted packet based on the side-information sent from the receivers via feedback channels. A notable feature of the proposed protocol is that the decoding process at the receiver side has low decoding complexity because only a small number of addition operations are needed in order to recover an intended packet. This feature may be preferable for reducing the power consumption of receivers. The throughput performance of the proposed protocol is close to that of the ideal FEC throughput performance when the erasure probability is less than $0.1$. This implies that the proposed protocol provides almost optimal throughput performance in such a regime.
Workload-Driven Vertical Partitioning for Effective Query Processing over Raw Data
Venue: arXiv cs.DB 2015
Year: 2015

Traditional databases are not equipped with the adequate functionality to handle the volume and variety of "Big Data". Strict schema definition and data loading are prerequisites even for the most primitive query session. Raw data processing has been proposed as a schema-on-demand alternative that provides instant access to the data. When loading is an option, it is driven exclusively by the current-running query, resulting in sub-optimal performance across a query workload. In this paper, we investigate the problem of workload-driven raw data processing with partial loading. We model loading as fully-replicated binary vertical partitioning. We provide a linear mixed integer programming optimization formulation that we prove to be NP-hard. We design a two-stage heuristic that comes within close range of the optimal solution in a fraction of the time. We extend the optimization formulation and the heuristic to pipelined raw data processing, scenario in which data access and extraction are executed concurrently. We provide three case-studies over real data formats that confirm the accuracy of the model when implemented in a state-of-the-art pipelined operator for raw data processing.
Operational Region of D2D Communications for Enhancing Cellular Network Performance
Venue: arXiv cs.IT 2015
Year: 2015

An important enabler towards the successful deployment of any new element/feature to the cellular network is the investigation and characterization of the operational conditions where its introduction will enhance performance. Even though there has been significant research activity on the potential of device-to-device (D2D) communications, there are currently no clear indications of whether D2D communications are actually able to provide benefits for a wide range of operational conditions, thus justifying their introduction to the system. This paper attempts to fill this gap by taking a stochastic geometry approach on characterizing the set (region) of operational conditions for which D2D communications enhance performance in terms of average user rate. For the practically interesting case of a heavy loaded network, the operational region is provided in closed form as a function of a variety of parameters such as maximum D2D link distances and user densities, reflecting a wide range of operational conditions (points). It is shown that under the appropriate deployment scheme, D2D communications can indeed be beneficial not only for the usually considered regime of "proximal communications" but to a wide range of operational conditions that include D2D link distances comparable to the distance to the cellular access point and considerably large user densities.
Extending Eventually Consistent Cloud Databases for Enforcing Numeric Invariants
Venue: arXiv cs.DC 2015
Year: 2015

Geo-replicated databases often operate under the principle of eventual consistency to offer high-availability with low latency on a simple key/value store abstraction. Recently, some have adopted commutative data types to provide seamless reconciliation for special purpose data types, such as counters. Despite this, the inability to enforce numeric invariants across all replicas still remains a key shortcoming of relying on the limited guarantees of eventual consistency storage. We present a new replicated data type, called bounded counter, which adds support for numeric invariants to eventually consistent geo-replicated databases. We describe how this can be implemented on top of existing cloud stores without modifying them, using Riak as an example. Our approach adapts ideas from escrow transactions to devise a solution that is decentralized, fault-tolerant and fast. Our evaluation shows much lower latency and better scalability than the traditional approach of using strong consistency to enforce numeric invariants, thus alleviating the tension between consistency and availability.
On data skewness, stragglers, and MapReduce progress indicators
Venue: arXiv cs.DC 2015
Year: 2015

We tackle the problem of predicting the performance of MapReduce applications, designing accurate progress indicators that keep programmers informed on the percentage of completed computation time during the execution of a job. Through extensive experiments, we show that state-of-the-art progress indicators (including the one provided by Hadoop) can be seriously harmed by data skewness, load unbalancing, and straggling tasks. This is mainly due to their implicit assumption that the running time depends linearly on the input size. We thus design a novel profile-guided progress indicator, called NearestFit, that operates without the linear hypothesis assumption and exploits a careful combination of nearest neighbor regression and statistical curve fitting techniques. Our theoretical progress model requires fine-grained profile data, that can be very difficult to manage in practice. To overcome this issue, we resort to computing accurate approximations for some of the quantities used in our model through space- and time-efficient data streaming algorithms. We implemented NearestFit on top of Hadoop 2.6.0. An extensive empirical assessment over the Amazon EC2 platform on a variety of real-world benchmarks shows that NearestFit is practical w.r.t. space and time overheads and that its accuracy is generally very good, even in scenarios where competitors incur non-negligible errors and wide prediction fluctuations. Overall, NearestFit significantly improves the current state-of-art on progress analysis for MapReduce.
Formalising Hypothesis Virtues in Knowledge Graphs: A General Theoretical Framework and its Validation in Literature-Based Discovery Experiments
Venue: arXiv cs.AI 2015
Year: 2015

We introduce an approach to discovery informatics that uses so called knowledge graphs as the essential representation structure. Knowledge graph is an umbrella term that subsumes various approaches to tractable representation of large volumes of loosely structured knowledge in a graph form. It has been used primarily in the Web and Linked Open Data contexts, but is applicable to any other area dealing with knowledge representation. In the perspective of our approach motivated by the challenges of discovery informatics, knowledge graphs correspond to hypotheses. We present a framework for formalising so called hypothesis virtues within knowledge graphs. The framework is based on a classic work in philosophy of science, and naturally progresses from mostly informative foundational notions to actionable specifications of measures corresponding to particular virtues. These measures can consequently be used to determine refined sub-sets of knowledge graphs that have large relative potential for making discoveries. We validate the proposed framework by experiments in literature-based discovery. The experiments have demonstrated the utility of our work and its superiority w.r.t. related approaches.
Top Tips to Make Your Research Irreproducible
Venue: arXiv cs.CE 2015
Year: 2015

It is an unfortunate convention of science that research should pretend to be reproducible; our top tips will help you mitigate this fussy conventionality, enabling you to enthusiastically showcase your irreproducible work.
A New Repair Operator for Multi-objective Evolutionary Algorithm in Constrained Optimization Problems
Venue: arXiv cs.NE 2015
Year: 2015

In this paper, we design a set of multi-objective constrained optimization problems (MCOPs) and propose a new repair operator to address them. The proposed repair operator is used to fix the solutions that violate the box constraints. More specifically, it employs a reversed correction strategy that can effectively avoid the population falling into local optimum. In addition, we integrate the proposed repair operator into two classical multi-objective evolutionary algorithms MOEA/D and NSGA-II. The proposed repair operator is compared with other two kinds of commonly used repair operators on benchmark problems CTPs and MCOPs. The experiment results demonstrate that our proposed approach is very effective in terms of convergence and diversity.
Faster linearizability checking via $P$-compositionality
Venue: arXiv cs.DC 2015
Year: 2015

Linearizability is a well-established consistency and correctness criterion for concurrent data types. An important feature of linearizability is Herlihy and Wing's locality principle, which says that a concurrent system is linearizable if and only if all of its constituent parts (so-called objects) are linearizable. This paper presents $P$-compositionality, which generalizes the idea behind the locality principle to operations on the same concurrent data type. We implement $P$-compositionality in a novel linearizability checker. Our experiments with over nine implementations of concurrent sets, including Intel's TBB library, show that our linearizability checker is one order of magnitude faster and/or more space efficient than the state-of-the-art algorithm.
Refuting Unique Game Conjecture
Venue: arXiv cs.CC 2015
Year: 2015

In this short note, the author shows that the gap problem of some $k$-CSPs with the support of its predicate the ground of a balanced pairwise independent distribution can be solved by a modified version of Hast's Algorithm BiLin that calls Charikar\&Wirth's SDP algorithm for two rounds in polynomial time, when $k$ is sufficiently large, the support of its predicate is combined by the grounds of three biased homogeneous distributions and the three biases satisfy certain conditions. To conclude, the author refutes Unique Game Conjecture, assuming $P\ne NP$.
Recent Development in Analog Computation - A Brief Overview
Venue: arXiv cs.ET 2015
Year: 2015

The recent development in analog computation is reviewed in this paper. Analog computation was used in many applications where power and energy efficiency is of paramount importance. It is shown that by using innovative architecture and circuit design, analog computation systems can achieve much higher energy efficiency than their digital counterparts, as they are able to exploit the computational power inherent to the devices and physics. However, these systems do suffer from some disadvantages, such as lower accuracy and speed, and designers have come up with novel approaches to overcome them. The paper provides an overview of analog computation systems, from basic components such as memory and arithmetic elements, to architecture and system design.
A general framework for compressed sensing and parallel MRI using annihilating filter based low-rank Hankel matrix
Venue: arXiv cs.IT 2015
Year: 2015

Parallel MRI (pMRI) and compressed sensing MRI (CS-MRI) have been considered as two distinct reconstruction problems. Inspired by recent k-space interpolation methods, an annihilating filter based low-rank Hankel matrix approach (ALOHA) is proposed as a general framework for sparsity-driven k-space interpolation method which unifies pMRI and CS-MRI. Specifically, our framework is based on the fundamental duality between the transform domain sparsity in the primary space and the low-rankness of weighted Hankel matrix in the reciprocal space, which converts pMRI and CS-MRI to a k-space interpolation problem using structured matrix completion. Using theoretical results from the latest compressed sensing literatures, we showed that the required sampling rates for ALOHA may achieve the optimal rate. Experimental results with in vivo data for single/multi-coil imaging as well as dynamic imaging confirmed that the proposed method outperforms the state-of-the-art pMRI and CS-MRI.
Composition in the Function-Behaviour-Structure Framework
Venue: arXiv cs.SE 2015
Year: 2015

We introduce composition in the function-behaviour-structure framework for design, as described by John Gero, in order to deal with complexity. We do this by connecting the frameworks for the design of several models, in which one is constrained by the others. The result is a framework for the design of an object that supports modularity. This framework can easily be extended for the design of an object with more than one layer of modularity.
A Bulk-Parallel Priority Queue in External Memory with STXXL
Venue: arXiv cs.DS 2015
Year: 2015

We propose the design and an implementation of a bulk-parallel external memory priority queue to take advantage of both shared-memory parallelism and high external memory transfer speeds to parallel disks. To achieve higher performance by decoupling item insertions and extractions, we offer two parallelization interfaces: one using "bulk" sequences, the other by defining "limit" items. In the design, we discuss how to parallelize insertions using multiple heaps, and how to calculate a dynamic prediction sequence to prefetch blocks and apply parallel multiway merge for extraction. Our experimental results show that in the selected benchmarks the priority queue reaches 75% of the full parallel I/O bandwidth of rotational disks and and 65% of SSDs, or the speed of sorting in external memory when bounded by computation.
Every property is testable on a natural class of scale-free multigraphs
Venue: arXiv cs.DS 2015
Year: 2015

In this paper, we introduce a natural class of multigraphs called hierarchical-scale-free (HSF) multigraphs, and consider constant-time testability on the class. We show that a very wide subclass, specifically, that in which the power-law exponent is greater than two, of HSF is hyperfinite. Based on this result, an algorithm for a deterministic partitioning oracle can be constructed. We conclude by showing that every property is constant-time testable on the above subclass of HSF. This algorithm utilizes findings by Newman and Sohler of STOC'11. However, their algorithm is based on the bounded-degree model, while it is known that actual scale-free networks usually include hubs, which have a very large degree. HSF is based on scale-free properties and includes such hubs. This is the first universal result of constant-time testability on the general graph model, and it has the potential to be applicable on a very wide range of scale-free networks.
Fast algorithms for morphological operations using run-length encoded binary images
Venue: arXiv cs.CV 2015
Year: 2015

This paper presents innovative algorithms to efficiently compute erosions and dilations of run-length encoded (RLE) binary images with arbitrary shaped structuring elements. An RLE image is given by a set of runs, where a run is a horizontal concatenation of foreground pixels. The proposed algorithms extract the skeleton of the structuring element and build distance tables of the input image, which are storing the distance to the next background pixel on the left and right hand sides. This information is then used to speed up the calculations of the erosion and dilation operator by enabling the use of techniques which allow to skip the analysis of certain pixels whenever a hit or miss occurs. Additionally the input image gets trimmed during the preprocessing steps on the base of two primitive criteria. Experimental results show the advantages over other algorithms. The source code of our algorithms is available in C++.